Xemtailieu Tải về Bài tập dạy học sinh giỏi môn tin học THPT
BÀI TẬP DẠY HỌC SINH GIỎI MÔN TIN HỌC THPT -------------------Bảng mục lục CHUYÊN ĐỀ: XÂU KÍ TỰ ............................................................................................................. 4 XKT.BÀI 1. Xóa kí tự ..................................................................................................................... 4 XKT.BÀI 2. Giải nén xâu ................................................................................................................ 4 XKT.BÀI 3. Xếp hàng ..................................................................................................................... 4 XKT.BÀI 4. Tìm chuỗi đối xứng dài nhất ........................................................................................ 5 XKT.BÀI 5. Tìm số kí tự cần chèn để được xâu đối xứng ................................................................ 6 XKT.BÀI 6. Tìm chữ số thứ N. ........................................................................................................ 6 XKT.BÀI 7. Tìm k chữ số từ chữ số thứ N ....................................................................................... 7 XKT.BÀI 8. Xóa số để thu được số lớn nhất .................................................................................... 7 XKT.BÀI 9. Xóa kí tự để thu được số lớn nhất ................................................................................ 7 XKT.BÀI 10. Xóa K số để thu được số nhỏ nhất.............................................................................. 7 XKT.BÀI 11. Dãy ngoặc đúng ......................................................................................................... 8 XKT.BÀI 12. Bài toán biểu thức dấu ngoặc ..................................................................................... 8 XKT.BÀI 13. Mật mã ...................................................................................................................... 9 XKT.BÀI 14. Chuẩn hóa họ tên (dạng bài toán chuẩn hóa văn bản) ................................................. 9 XKT.BÀI 15. Cộng hai số nguyên lớn ............................................................................................. 9 XKT.BÀI 16. So sánh hai số nguyên................................................................................................ 9 XKT.BÀI 17. Chuẩn hóa ngày tháng ............................................................................................. 10 XKT.BÀI 18. Chuỗi chẵn - Lẻ ....................................................................................................... 10 XKT.BÀI 19. Điền khuyết xâu kí tự............................................................................................... 10 XKT.BÀI 20. Giải mã .................................................................................................................... 11 XKT.BÀI 21. Rút gọn xâu ............................................................................................................. 11 XKT.BÀI 22. Xâu nghịch đảo ........................................................................................................ 11 XKT.BÀI 23. Tính số lần lặp lại của xâu s1 trong xâu s2 ............................................................... 11 XKT.BÀI 24. Xâu con chung dài nhất ........................................................................................... 12 XKT.BÀI 25. Đoạn chung ............................................................................................................. 13 XKT.BÀI 26. Nén và giải nén xâu (theo độ dài loạt) ...................................................................... 13 XKT.BÀI 27. Sắp xếp xâu theo số lượng kí tự trong xâu................................................................ 14 XKT.BÀI 28. Kiểm tra chuỗi ......................................................................................................... 14 XKT.BÀI 29. ................................................................................................................................. 15 XKT.BÀI 30. Đoạn con dài nhất .................................................................................................... 15 XKT.BÀI 31. Mã hoá và giải mã văn bản ...................................................................................... 16 XKT.BÀI 32. Tính tỉ lệ chữ nguyên âm ......................................................................................... 16 XKT.BÀI 33. Chữ cái xuất hiện ..................................................................................................... 16 XKT.BÀI 34. Biến đổi xâu ............................................................................................................ 16 XKT.BÀI 35. Chuẩn hóa văn bản (1) ............................................................................................. 17 XKT.BÀI 36. Chuẩn hóa văn bản (2) ............................................................................................. 17 XKT.BÀI 37. Sắp xếp xâu. ............................................................................................................ 17 XKT.BÀI 38. Mã hóa Caesar (1) ................................................................................................... 18 XKT.BÀI 39. Mã hóa Caesar (2) ................................................................................................... 18 XKT.BÀI 40. Mã hoá hồ sơ ........................................................................................................... 19 XKT.BÀI 41. Tìm từ đầu tiên dài nhất trong xâu ........................................................................... 20 XKT.BÀI 42: Chiếc nón diệu kì ..................................................................................................... 20 XKT.BÀI 43. Xâu nhị phân ........................................................................................................... 20 XKT.BÀI 44. Tìm số nhỏ nhất lớn hơn X có cùng chữ số với X..................................................... 21 CHUYÊN ĐỀ: HOÁN VỊ, CHỈNH HỢP, TỔ HỢP ...................................................................... 23 HVCH. BÀI 1. Hoán vị (123…n) .................................................................................................. 23 HVCH. BÀI 2. Liệt kê các hoán vị của một xâu ............................................................................. 23 HVCH. BÀI 3. Liệt kê xâu ............................................................................................................ 23 HVCH. BÀI 4. Tạo sơn tổng hợp ................................................................................................... 23 HVCH. BÀI 5. Trộn đề .................................................................................................................. 23 CHUYÊN ĐỀ: MẢNG MỘT CHIỀU, HAI CHIỀU ..................................................................... 24 M1C2C. BÀI 1. Tần số.................................................................................................................. 24 M1C2C. BÀI 2: Số may mắn......................................................................................................... 24 M1C2C. BÀI 3. Mã số nhân viên .................................................................................................. 25 M1C2C. BÀI 4. Mua hàng ............................................................................................................ 25 M1C2C. BÀI 5. Tập số đặc biệt..................................................................................................... 25 M1C2C. BÀI 6. Mua vé ................................................................................................................ 26 M1C2C. BÀI 7. Tổng các chữ số................................................................................................... 26 M1C2C. BÀI 8. Chia đồ vật .......................................................................................................... 26 M1C2C. BÀI 9. Tìm dãy con có tổng lớn nhất (không chọn 3 phần tử liên tiếp) ............................ 27 M1C2C. BÀI 10. Chọn phần thưởng ............................................................................................. 27 M1C2C. BÀI 11. Chia dãy số thành k nhóm có tổng bằng nhau..................................................... 27 M1C2C. BÀI 12. Dãy con liên tiếp có tổng lớn nhất...................................................................... 28 M1C2C. BÀI 13. Dãy con cấp số cộng .......................................................................................... 28 M1C2C. BÀI 14. Dãy con liên tiếp có tổng chia hết cho k ............................................................. 28 M1C2C. BÀI 15. Dãy con liên tiếp có tổng bằng M ...................................................................... 28 M1C2C. BÀI 16. Dãy con nguyên tố dài nhất ............................................................................... 29 M1C2C. BÀI 17. Dãy con có tổng bằng S (dãy không liên tiếp) .................................................... 29 M1C2C. BÀI 18. Tính tổng ........................................................................................................... 30 M1C2C. BÀI 19. Sắp xếp mảng 1 chiều ........................................................................................ 30 M1C2C. BÀI 20. Sắp xếp.............................................................................................................. 30 M1C2C. BÀI 21. Số tự nhiên nhỏ nhất .......................................................................................... 31 M1C2C. BÀI 22. Dãy phân số ....................................................................................................... 31 M1C2C. BÀI 23. Độ lệch .............................................................................................................. 32 M1C2C. BÀI 24. Số siêu nguyên tố .............................................................................................. 32 M1C2C. BÀI 25. Bình chọn qua điện thoại ................................................................................... 32 M1C2C. BÀI 26. Quan hệ huyết thống .......................................................................................... 33 M1C2C. BÀI 27. Tìm số ............................................................................................................... 33 M1C2C. BÀI 28. Số âm lớn nhất................................................................................................... 33 M1C2C. BÀI 29. Trò chơi may mắn .............................................................................................. 34 M1C2C. BÀI 30. Sắp xếp.............................................................................................................. 34 M1C2C. BÀI 31. Xếp việc ............................................................................................................ 34 M1C2C. BÀI 32. Dãy số ............................................................................................................... 35 M1C2C. BÀI 33. Số thân thiện...................................................................................................... 35 M1C2C. BÀI 34. Sa mạc ............................................................................................................... 35 M1C2C. BÀI 35. Vườn trường ...................................................................................................... 36 M1C2C. BÀI 36. Kho an toàn ....................................................................................................... 37 M1C2C. BÀI 37. Bố trí xe ............................................................................................................ 37 M1C2C. BÀI 38. Kết bạn .............................................................................................................. 38 M1C2C. BÀI 39. Đếm số ô vuông đơn vị ...................................................................................... 38 M1C2C. BÀI 40. Chuyển vị ma trận ............................................................................................. 39 M1C2C. BÀI 41. Sắp xếp trên ma trận .......................................................................................... 39 M1C2C. BÀI 42. Bài toán cái túi................................................................................................... 40 M1C2C. BÀI 43. Trò chơi (dạng bài toán cái túi - chọn 1 hoặc nhiều vật) ..................................... 40 M1C2C. BÀI 44. Tổng các hàng của ma trận ................................................................................ 40 M1C2C. BÀI 45. Ma trận số ......................................................................................................... 41 M1C2C. BÀI 46. Sắp xếp ma trận ................................................................................................. 41 M1C2C. BÀI 47. Sắp xếp mảng hai chiều tăng theo hàng, cột ....................................................... 41 M1C2C. BÀI 48. Rút tiền từ máy ATM ......................................................................................... 42 M1C2C. BÀI 49. Đóng gói sản phẩm ............................................................................................ 42 M1C2C. BÀI 50. Hệ thống cảnh báo thảm họa .............................................................................. 42 M1C2C. BÀI 51. Các điểm cực tiểu. ............................................................................................. 45 M1C2C. BÀI 52. Chữ số thứ N ..................................................................................................... 45 M1C2C. BÀI 53. Lá bài ................................................................................................................ 45 M1C2C. BÀI 54. Trộn hai tệp ....................................................................................................... 46 M1C2C. BÀI 55. Trộn hai tệp thành tệp tăng dần .......................................................................... 46 M1C2C. BÀI 56. Tìm số lần lặp lại nhiều nhất của một số trong dãy số ......................................... 47 M1C2C. BÀI 57. Xếp khách .......................................................................................................... 47 M1C2C. BÀI 58. Mã số sách ......................................................................................................... 47 M1C2C. BÀI 59. Tam giác số ........................................................................................................ 48 M1C2C. BÀI 60. Thuê máy tính .................................................................................................... 48 M1C2C. BÀI 61. Hàng đợi ............................................................................................................ 48 M1C2C. BÀI 62. Bản tin bóng đá .................................................................................................. 49 M1C2C. BÀI 63. Nhà chung cư...................................................................................................... 50 M1C2C. BÀI 64. Hành tinh XYZ .................................................................................................. 50 M1C2C. BÀI 65. Băng số .............................................................................................................. 51 M1C2C. BÀI 66. Tìm chữ số thứ M .............................................................................................. 51 M1C2C. BÀI 67. Diện tích miền phủ ............................................................................................. 52 M1C2C. BÀI 68: Tính diện tích..................................................................................................... 52 M1C2C. BÀI 69. Tạo bảng ............................................................................................................ 53 M1C2C. BÀI 70. Tìm số âm lớn nhất ............................................................................................ 54 M1C2C. BÀI 71. Trạm canh .......................................................................................................... 54 M1C2C. BÀI 72. Hình chữ nhật .................................................................................................... 55 M1C2C. BÀI 73. Dãy con chung dài nhất ...................................................................................... 55 M1C2C. BÀI 74. Số lượng nhóm đề tài ......................................................................................... 56 M1C2C. BÀI 75. Siêu nguyên tố ................................................................................................... 56 M1C2C. BÀI 76. Cấp số cộng ....................................................................................................... 56 M1C2C. BÀI 77. Đếm nhóm bạn trong hội trại.............................................................................. 56 M1C2C. BÀI 78. Tổng các chữ số ................................................................................................. 57 M1C2C. BÀI 79. Phân tích một số thành tổng các số ..................................................................... 57 M1C2C. BÀI 80. Phân phối hàng cứu trợ ...................................................................................... 61 M1C2C. BÀI 81. Tìm điểm thuộc tất cả N hình chữ nhật ............................................................... 61 M1C2C. BÀI 82. Con thạch sùng .................................................................................................. 61 Trang 3 CHUYÊN ĐỀ: XÂU KÍ TỰ Các thủ tục và hàm chuẩn xử lý xâu kí tự (bổ sung, các hàm – thủ tục khác hs xem SGK) * Thủ tục STR(value, st) Thủ tục này thực hiện việc chuyển đổi giá trị kiểu số(value) sang dạng xâu kí tự và gán cho biến st. Ví dụ: n là một só nguyên có giá trị: n:=150; STR(n:5,st) sẽ cho kết quả xâu st là: st=‘ 150’; * Thủ tục VAL(st, value,code) đổi một xâu kí tự st sang dạng số và gán cho biến value, nếu biến đối thành công thì code sẽ nhận giá trị bằng 0, ngược lại thì cho giá trị khác không Ví dụ: VAL(‘123’,value,code) lúc này code sẽ nhận giá trị bằng 0 và value=123 BÀI TẬP XKT.BÀI 1. Xóa kí tự (câu 1, đề thi HSG tỉnh Quảng Bình năm 2013-2014, lớp 11) Cho một xâu kí tự St có độ dài tối đa 255 kí tự, các kí tự được lấy từ tập: ‘a’ … ‘z’; ‘A’ … ‘Z’; ‘0’ … ‘9’. Yêu cầu: Hãy xóa hết các kí tự chữ số trong xâu St. Dữ liệu vào: Ghi trong file văn bản DELECHAR.INP có cấu trúc như sau: - Dòng 1: Ghi xâu St. Dữ liệu ra: Ghi ra file văn bản DELECHAR.OUT theo cấu trúc như sau: - Dòng 1: Ghi xâu St sau khi đã xóa đi các kí tự chữ số. Ví dụ: DELECHAR.INP DELECHAR.OUT abc123DEA97ijk abcDEAijk XKT.BÀI 2. Giải nén xâu (câu 2, đề thi HSG tỉnh Quảng Bình năm 2013-2014, lớp 11) Để tiết kiệm chi phí trong việc gửi và nhận dữ liệu thông qua các kênh truyền, các file văn bản trước khi được gửi đi đều được nén lại để giảm dung lượng bộ nhớ. Sau khi nhận được các file văn bản gửi đến, muốn đọc được nội dung thì các file vừa nhận phải được giải nén. Việc nén một xâu văn bản chỉ chứa các kí tự chữ cái in hoa được thực hiện như sau: Một đoạn liên tiếp các kí tự chữ cái giống nhau được thay bằng một đoạn kí tự mới gồm các kí tự chữ số thể hiện số lượng của chữ cái và tiếp theo sau là kí tự chữ cái đó (AAAAAAA được thay bằng 7A), nếu chỉ có một kí tự chữ cái thì giữ nguyên kí tự đó. Ví dụ: AAAAAABBBCDDD sẽ được nén lại là 6A3BC3D. Việc giải nén là chuyển một xâu đã được nén trở về xâu gốc ban đầu trước khi nó được nén. Ví dụ: 6A3BC3D được chuyển thành AAAAAABBBCDDD. Cho một file văn bản gồm nhiều dòng, mỗi dòng chứa một xâu văn bản đã được nén, file chỉ chứa tối đa 100 dòng (Mỗi xâu văn bản gốc trước khi nén có tối đa 255 kí tự). Yêu cầu: Hãy thực hiện giải nén các xâu văn bản trên mỗi dòng trong file đã cho chuyển thành các xâu gốc ban đầu. Dữ liệu vào: Ghi trong file văn bản UNZIP.INP có cấu trúc như sau: - Dòng 1: Ghi số nguyên dương N là số lượng xâu trong file văn bản. - Dòng thứ i trong N dòng tiếp theo: Mỗi dòng ghi một xâu đã được nén. Dữ liệu ra: Ghi ra file văn bản UNZIP.OUT theo cấu trúc như sau: Dữ liệu được ghi trên N dòng, dòng thứ i ghi xâu đã được giải nén tương ứng với xâu đã được nén trong file dữ liệu vào. Ví dụ: UNZIP.INP UNZIP.OUT 2 AAAAAABBBCDDD 6A3BC3D AAAAABC 5ABC Mở rộng bài toán: viết chương trình nén xâu XKT.BÀI 3. Xếp hàng (câu 1, đề thi HSG tỉnh Đồng Tháp năm 2013-2014, lớp 12) Trong giờ học thể dục, thầy giáo xếp N học sinh thành một hàng và vị trí của học sinh được đánh số từ 1 đến n từ trái sang phải. Ban đầu học sinh đứng tùy ý trong hàng. Tuy nhiên, để tôn trọng các bạn nữ, thầy muốn các bạn nam không được đứng liền trước bạn nữ nào (đứng liền trước ở đây được hiểu rằng vị trí của bạn nam là i và vị trí của bạn nữ là i+1). Để thực hiện quy định này, thầy bắt đầu đi từ đầu hàng đến cuối hàng, khi gặp bạn nam nào được đứng liền trước một bạn nữ, thầy sẽ yêu cầu bạn nam này đổi chỗ cho bạn nữ rồi đi tiếp đến bạn sau đó. Chú ý rằng trong một lượt sắp xếp, thầy chỉ đi theo một chiều và mỗi bạn nam chỉ được đổi chỗ một lần. Tất nhiên là chỉ với một lượt sắp xếp như vậy thì vẫn có thể có nhiều vị trí mà bạn nam đứng trước nữ xuất hiện thêm nên ta cần phải đi làm thao tác sắp xếp này nhiều lần. The linked image cannot be display ed. T he file may hav e been mov ed, renamed, or deleted. V erify that the link points to the correct file and location. Yêu cầu: cho hai số nguên dương n, t với và một dãy kí tự G và B, trong đó G là kí hiệu bạn nữ và B là kí hiệu bạn nam thể hiện vị trí các học sinh của lớp ban đầu. Hỏi sau lần thay đổi thứ t thì vị trí các học sinh như thế nào và bao nhiêu lần thao tác thì thầy giáo sẽ hoàn tất việc sắp xếp này. Dữ liệu vào: trong file xephang.inp gồm có: dòng thứ nhất chứa hai số nguyên dương n và t cách nhau bởi một khoảng trắng, dòng thứ hai gồm một dãy n kí tự ‘G’ và ‘B’ biểu thị vị trí đứng của các học sinh trong hàng (từ trái qua phải tương ứng với chỉ số vị trí tăng dần). Kết quả ra: in ra file xephang.out hai dòng: dòng thứ nhất gồm dãy n kí tự ‘G’ và ‘B’ biểu thị vị trí đứng của các học sinh sau khi thầy giáo xếp lại lần thứ t, dòng thứ hai là một số nguyên cho biết số lần thầy giáo cần sắp xếp. Chú ý rằng số t có thể lớn hơn số lần thầy giáo cần sắp xếp. DẠNG BÀI TOÁN LIÊN QUAN ĐẾN XÂU ĐỐI XỨNG XKT.BÀI 4. Tìm chuỗi đối xứng dài nhất (Câu 1, đề thi HSG tỉnh Ninh Thuận năm học 2013-2014, lớp 12) Một chuỗi kí tự được gọi là đối xứng nếu đọc từ trái qua phải cũng giống như đọc nó từ phải qua trái. Ví dụ: ‘EUROORUE’; ‘ DATATAD’ là chuỗi đối xứng. ‘STRING’; ‘TRANTIENDAT’là chuỗi không đối xứng. Cho chuỗi kí tự S có chiều dài N (10 ≤ N ≤ 1000). Hãy tìm chiều dài chuỗi con đối xứng dài nhất trong S. Chuỗi con đối xứng trong S là chuỗi gồm một số kí tự liên tiếp nhau trong S có độ dài nhỏ hơn hoặc bằng N. Dữ liệu: Cho trong file văn bản doixung.inp. - Dòng đầu ghi giá trị N(10 ≤ N ≤1000). - Dòng sau gồm N kí tự liên tiếp là các chữ cái in hoa (A→ Z). Kết quả: Ghi vào file văn bản doixung.out độ dài của chuỗi con đối xứng dài nhất (trường hợp không có thì ghi 0). Ví dụ: DOIXUNG.INP 20 ABCDEFABABBABAFFFFFF DOIXUNG.OUT 10 Ý tưởng Cách 1: Duyệt xâu từ kí tự đầu đến kí tự thứ length(S) -1. Với mỗi lần duyệt ta sẽ xét xâu con lần lượt từ vị trí đó có đối xứng không, nếu đối xứng thì so sánh độ dài với xâu kết quả, nếu lớn hơn thì thay đổi xâu kết quả. Cách 2: Dùng phương pháp quy hoạch động Dùng mảng F[i,j] có ý nghĩa F[i,j]= true/false nếu đoạn gồm các kí tự từ i đến j của S có/không là palindrome . Ta có công thức: F[i,i]= true F[i,j]= F[i+1, j-1] (nếu s[i]=s[j]) F[i,j]= false (nếu s[i]s[j]) Đoạn chương trình như sau: Fillchar(F, sizeof(F), false); For i:=1 to n do F[i,i]:= true; For k:=1 to n-1 do For i:=1 to n-k do Begin J:= i+k; F[i,j]:= F[i+1, j-1] and (s[i]=s[j]); End; Kết quả là max(j-i+1)dmax) then begin dmax:=d; csd:=i; csc:=j; end; end; for i:=csd to csc do write(S[i]); XKT.BÀI 5. Tìm số kí tự cần chèn để được xâu đối xứng (Thanh Hóa, 2008-2009) Xâu đối xứng là xâu đọc giống nhau nếu ta bắt đầu đọc từ trái qua phải hoặc từ phải qua trái. Ví dụ, xâu RADAR là xâu đối xứng, xâu TOMATO không phải là xâu đối xứng. Yêu cầu: Cho một xâu S gồm không quá 200 kí tự. Cho biết S có phải là xâu đối xứng hay không? Nếu không, cho biết số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Dữ liệu vào: từ file văn bản doixung.inp, gồm duy nhất 1 dòng ghi xâu S. Kết quả: Ghi ra file văn bản doixung.out, duy nhất số k là số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng. Nếu xâu S đã cho là đối xứng thì ghi k = 0. Ví dụ: DOIXUNG.INP DOIXUNG.OUT DOIXUNG.INP DOIXUNG.OUT RADAR 0 TOMATO 3 Hướng dẫn: Cách 1 Trong xâu đối xứng thì vị trí i sẽ đối xứng với vị trí length(s)-i+1 Do đó ta xét từng cặp kí tự ở vị trí đối xứng nhau: + Nếu kí tự ở vị trí i và kí tự ở vị trí đối xứng là length(s)-i+1 khác nhau và kí tự ở vị trí i và vị trí length(s)-i cũng khác nhau thì ta chèn kí tự ở vị trí thứ i và xâu S ở vị trí length(s)-i+2 và tính lại độ dài xâu, khi đó ta sẽ có kí tự thứ i và kí tự thứ length(s)-i+1 sẽ giống nhau. + Nếu kí tự ở vị trí i và kí tự ở vị trí đối xứng là length(s)-i+1 khác nhau và kí tự ở vị trí i và vị trí length(s)-i giống nhau thì ta chèn kí tự ở vị trí thứ length(s) – i +1 vào xâu S ở vị trí i và tính lại độ dài xâu, khi đó ta sẽ có kí tự thứ i và kí tự thứ length(s)-i+1 sẽ giống nhau, kí tự ở vị trí i+1 và lengh(s)-i cũng giống nhau. Ví dụ: S=‘TOMATO’ Ở vị trí i=1: kí tự ở vị trí i và vị trí đối xứng là length(s) –i +1 khác nhau; kí tự ở vị trí i và kí tự ở vị trí length(s)-i giống nhau. Khi đó cần chèn kí tự ‘O’ vào vị trí 1 để được xâu mới, khi đó ta có cặp kí tự đối xứng. Ta có hình ảnh xâu S sau khi chèn: i 1 S O 2 T 3 O 4 M 5 A 6 T 7 O Cách 2: Gọi S2 là xâu đảo của xâu ST ban đầu, T là xâu con chung của hai xâu S2 và ST. Khi đó các kí tự của ST không thuộc T chính là các kí tự cần chèn vào xâu ST để ST trở thành xâu đối xứng. Bài toán trở thành bài toán tìm dãy con chung dài nhất của hai xâu bằng phương pháp quy hoạch động. XKT.BÀI 6. Tìm chữ số thứ N. Khi viết các số tự nhiên tăng dần từ 1, 2, 3,… liên tiếp nhau, ta nhận được một dãy các chữ số thập phân vô hạn, đoạn đầu tiên của dãy sẽ là: 1234567891011121314151617181920... Yêu cầu: Hãy tìm chữ số thứ N của dãy số vô hạn trên. Dữ liệu: Cho trong file NUMBER.INP gồm một nguyên dương N (N < 106). Kết quả: Ghi kết quả ra file NUMBER.OUT. Ví dụ: Giải thích kết quả NUMBER.OUT NUMBER.OUT 21 5 Chữ số thứ 21 trong dãy là chữ số 5 XKT.BÀI 7. Tìm k chữ số từ chữ số thứ N Từ chuỗi nhị phân S=‘10’, người ta tạo ra chuỗi nhị phân mới bằng cách ghép chuỗi S ban đầu với chính nó sau khi đã đảo tất cả các bit của S ( nghĩa là 1 thành 0 và 0 thành 1) và cứ lặp lại các thao tác trên cho đến khi chuỗi S có không ít hơn N chữ số Ví dụ: Độ dài 2: chuỗi s=‘10’ Độ dài 4: chuỗi s:=‘1001’ ( ghép ‘10’ với ‘01’); Độ dài 8: chuỗi s:=‘10010110’ ( ghép ‘1001’ với ‘0110’); Độ dài 16: chuỗi s:=‘1001011001101001’ ( ghép ‘10010110’ với ‘01101001’); Yêu cầu: Cho 2 số N, K (0