Category: Thuật toán

Sàng số nguyên tố (Sàng Eratosthenes)
Sàng số nguyên tố (Sàng Eratosthenes)

Bài toán liệt kê các số nguyên tố nhỏ hơn số n cho trước là một bài toán quan trọng trong Toán học và Tin học.

Phương pháp đơn giản nhất là chúng ta duyệt qua các số tự nhiên nhỏ hơn n, và lần lượt kiểm tra tính nguyên tố của từng số này. Tuy nhiên, việc kiểm tra tính nguyên tố của một số tự nhiên n có độ phức tạp là $O(\sqrt{n})$, do đó duyệt qua n số này sẽ có độ phức tạp $O(\sqrt{1}+\sqrt{2}+\sqrt{3}+…+\sqrt{n})$.

Cách làm dưới đây sẽ giúp giảm độ phức tạp của chương trình đi rất nhiều.

Sàng Eratosthenes là gì?

Sàng Eratosthenes là một thuật giải toán cổ xưa để tìm các số nguyên tố nhỏ hơn 100. Thuật toán này do nhà toán học cổ Hy Lạp là Eratosthenes (Ơ-ra-tô-xten) “phát minh” ra.

Ban đầu, nhà toán học Eratosthenes sau khi tìm ra thuật toán, đã lấy lá cọ và ghi tất cả các số từ 2 cho đến 100. Ông đã chọc thủng các hợp số và giữ nguyên các số nguyên tố. Bảng số nguyên tố còn lại trông rất giống một cái sàng. Do đó, nó có tên là sàng Eratosthenes.

Bạn có thể xem trong hình dưới đây, các số tô màu giống nhau là bội của nhau số cùng màu nhưng được tô đậm hơn.

Thuật toán sàng số nguyên tố

Để tìm các số nguyên tố nhỏ hơn hoặc bằng số tự nhiên N bằng sàng Eratosthenes, ta làm như sau:
- Bước 1: Tạo 1 danh sách (List trong Python, Dart hoặc array trong C)các số tự nhiên liên tiếp từ 2 đến n: [2, 3, 4,..., n].
- Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
- Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
- Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p và nhỏ hơn hoặc bằng căn bậc 2 của n . Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.
Khi giải thuật kết thúc, tất các số chưa bị đánh dấu trong danh sách là các số nguyên tố cần tìm.

Thay vì phải đánh dấu, chúng ta có thể xóa phần tử không là số nguyên tố của danh sách thì cuối cùng sẽ còn lại là các số nguyên tố.

Mời bạn tham khảo mã nguồn chương trình bằng Python:
```
def SieveOfEratosthenes(n):
   
   # Create a boolean array "prime[0..n]" and initialize
   # all entries it as true. A value in prime[i] will
   # finally be false if i is Not a prime, else true.
   prime = [True for i in range(n + 1)]
   p = 2
   while (p * p <= n):
      
      # If prime[p] is not changed, then it is a prime
      if (prime[p] == True):
         
         # Update all multiples of p
         for i in range(p ** 2, n + 1, p):
            prime[i] = False
      p += 1
   prime[0]= False
   prime[1]= False
   # Print all prime numbers
   for p in range(n + 1):
      if prime[p]:
         print(p)
if __name__=='__main__':
   n = 30
   print("Following are the prime numbers smaller than or equal to", n)
   SieveOfEratosthenes(n)
```
21/10/2021
Thuật toán kiểm tra Số Nguyên Tố
Thuật toán kiểm tra Số Nguyên Tố

Thuật toán kiểm tra Số Nguyên Tố của một số nguyên dương, cùng với thuật toán tìm UCLN của hai số tự nhiên là những bài toán quan trọng trong Lập trình.

Kiểm tra tính nguyên tố là bài toán kiểm tra xem một số tự nhiên n có phải là số nguyên tố hay không. Bài toán này đặc biệt trở nên quan trọng khi các hệ mật mã khoá công khai ra đời.

1. Số nguyên tố là gì?

Số nguyên tố (prime) là số tự nhiên lớn hơn 1, chỉ có hai ước số là 1 và chính nó. Theo định nghĩa này thì các số 2, 3, 5, 7, 11,… là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất.

Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 đến 6 không tồn tại số nào mà 7 chia hết cả.

2. Các Thuật toán kiểm tra Số Nguyên Tố Đơn Giản

Phương pháp đơn giản nhất để kiểm tra một số n có là số nguyên tố không là kiểm tra xem nó có chia hết cho các số m nằm trong khoảng 2 đến n-1 hay không.

Nếu n chia hết cho một trong các số m nào đó thì n không là số nguyên tố (còn được gọi là hợp số composite). Ngược lại, nếu n không chia hết cho bất kì số m nào thì kết lianaj n là số nguyên tố.

Thực ra việc kiểm tra với m từ 2 đến n-1 là không cần thiết, mà chỉ cần kiểm tra đến $\sqrt{n}$ là đủ. Vì nếu n là hợp số thì nó chắc chắn có ước số không vượt quá sqrt(n).

Lặp từng phần tử với bước nhảy 1 đến n-1

Giả sử cần kiểm tra số n có phải là số nguyên tố hay không thì các bước thực hiện như sau:
- Bước 1: Nhập vào n
- Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố
- Bước 3: Lặp từ 2 tới (n-1), nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.
Độ phức tạp của thuật toán trên là $O(n)$.

Lặp từng phần tử với bước nhảy 2

Theo định nghĩa thì số 2 là số nguyên tố chẵn duy nhất, vì vậy ta sẽ loại 2 ra khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra các số lẻ mà thôi, cách này sẽ tối ưu hơn cách 1 rất nhiều.
- Bước 1: Nhập vào n;
- Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố;
- Bước 3: Kiểm tra nếu n = 2 thì kết luận n là số nguyên tố;
- Bước 4: Kiểm tra nếu n > 2 và chẵn thì kết luận n không phải là số nguyên tố;
- Bước 5. Lặp từ 3 tới (n-1), bước nhảy là 2 nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố.
Lặp từng phần tử đến $\sqrt{n}$

Để tối ưu hơn, thay vì lặp tới n-1, chúng ta chỉ cần lặp các số từ 2 đến sqrt(n), nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.

Độ phức tạp của thuật toán trên là $O(\sqrt{n})$.

Xem mã nguồn viết bằng ngôn ngữ Dart tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-17.html

3. Tối ưu thuật toán kiểm tra số nguyên tố

Chúng ta có thể tối ưu thuật toán trên bằng cách chỉ ra n không chia hết cho những số nguyên tố nhỏ hơn nó. Tuy nhiên, chúng ta lại chưa biết được các số nguyên tố nhỏ hơn nó là những số nào (Bạn có thể sử dụng phương pháp sàng số nguyên tố – Sàng Eratosthenes để tìm ra các số nguyên tố nhỏ hơn số n cho trước). Nên ta sử dụng kết quả sau đây:

Tất cả những số nguyên tố lớn hơn 3 đều có dạng 6k ± 1 (vì 6k, 6k ± 2, là những số chẵn; 6k + 3 thì chia hết cho 3).

Do đó, chúng ta chỉ cần kiểm tra các số có dạng 6k ± 1 từ 2 đến √n, nếu n chia hết cho một trong những số đó thì n không phải là số nguyên tố. Ngược lại thì n là số nguyên tố.
```
def is_prime(n: int) -> bool:
    """Primality test using 6k+-1 optimization."""
    if n <= 3:
        return n > 1
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i ** 2 <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True
```
4. Các Thuật toán kiểm tra Số Nguyên Tố Nâng Cao

Các cách kiểm tra số nguyên tố kể trên có độ chính xác tuyệt đối nhưng khối lượng tính toán rất lớn. Theo Wiki thì chúng ta còn có những cách khác để kiểm tra tính nguyên tố của một số với một độ chính xác cho trước.

Kiểm tra theo xác suất

Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên.

Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a <= p. Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= n được lấy ngẫu nhiên, khi đó a có khả năng là một số nguyên tố.

Ta đưa ra một thuật toán, kết luận rằng n là số nguyên tố. Nó là một thuật toán ngẫu nhiên hay thuật toán xác suất. Trong các thuật toán loại này, dùng một kiểm tra ngẫu nhiên sẽ không bao giờ kết luận một số nguyên tố là hợp số nhưng lại có thể kết luận một hợp số là số nguyên tố. Do đó, phương pháp này không chính xác một cách tuyệt đối.

Xác suất sai của phép kiểm tra có thể giảm xuống nhờ việc chọn một dãy độc lập các số a; nếu với mỗi số a xác suất để thuật toán kết luận một hợp số là số nguyên tố là nhỏ hơn một nửa thì sau k lần thử độc lập, xác suất sai là nhỏ hơn 2^k, độ tin cậy của thuật toán sẽ tăng lên theo k.

Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:
- Chọn một số ngẫu nhiên a.
- Kiểm tra một hệ thức nào đó giữa số a và số n đã cho. Nếu hệ thức sai thì chắc chắn n là một hợp số (số a là “bằng chứng” chứng tỏ n là hợp số) và dừng thuật toán.
- Nếu hệ thức đúng, chúng ta lặp lại hai bước trên cho đến khi đạt được một số lần định trước hoặc gặp trường hợp dừng thuật toán.
Sau nhiều lần thử, nếu hệ thức đúng với nhiều giá trị của a, ta có thể nói rằng n “có khả năng cao” là số nguyên tố chứ không thể chắc chắn n là số nguyên tố. Tất nhiên là chúng ta sẽ tìm cách tăng “khả năng” này lên bằng cách thực hiện nhiều tính toán hơn.

Các hệ thức thường sử dụng

Nếu p là một số nguyên tố thì
- 2^{p - 1} ≡ 1 (mod p) (đây là nội dung của định lí Fermat nhỏ)
- f_{p + 1} ≡ 0 (mod p) (với f_{p + 1} là số Fibonacci thứ p + 1 và p có dạng 5k ± 2)
- (p - 1)! ≡ -1 (mod p) khi và chỉ khi p nguyên tố. Đây là nội dung của định lí Wilson, nhưng việc tính toán biểu thức (n - 1)! % n sẽ có độ phức tạp lớn hơn log n.
Các phép kiểm tra tính nguyên tố ngẫu nhiên là:
- Phép kiểm tra tính nguyên tố của Fermat (kiểm tra Fermat). Đây là phép thử heuristic; tuy nhiên ít người sử dung phép thử này.
- Kiểm tra Miller-Rabin và Kiểm tra Solovay-Strassen. Với mỗi hợp số n, ít nhất 3/4 (với kiểm tra Miller-Rabin) hoặc 1/2 (Với kiểm tra Solovay-Strassen) các số a là bằng chứng chứng tỏ n là hợp số).
Các phép kiểm tra tất định

Vào năm 2002, Manindra Agrawal, Nitin Saxena và Neeraj Kayal đề xuất một giải thuật tất định kiểm tra tính nguyên tố, là kiểm tra AKS, có khả năng chạy trong O((log n)12). Trên thực tế thuật toán này chạy chậm hơn các phương pháp xác suất.

Các phương pháp này, mời bạn đọc tham khảo thêm tại https://en.wikipedia.org/wiki/Primality_test
21/10/2021
Thuật toán tìm UCLN của hai số nguyên dương
Thuật toán tìm UCLN của hai số nguyên dương

UCLN (ước chung lớn nhất) của 2 số là gì?

Ước chung lớn nhất (UCLN, tiếng Anh là GCD – Greatest Common Divisor) của 2 số nguyên dương a và b là số nguyên lớn nhất d thỏa mãn tính chất cả a và b đều chia hết cho d.

Ví dụ, UCLN của 10 và 35 là 5 vì 5 là số nguyên lớn nhất mà cả 10 và 35 đều chia hết cho 5.

Thuật toán tìm UCLN của hai số nguyên dương

Có nhiều thuật toán tìm UCLN của hai số nguyên, bạn có thể tham khảo thêm ở Wikipedia. Dưới đây, chúng tôi giới thiệu thuật toán tìm UCLN của hai số nguyên giải thuật Euclid. Cơ sở của giải thuật Euclid tìm UCLN của hai số nguyên a và b dựa trên tính chất sau.

Giả sử a >= b thì khi chia a cho b ta được thương q và số dư r, tức là

a = b*q + r

Khi đó:
- Nếu r = 0 thì UCLN(a,b) = b
- Nếu r >0 thì UCLN(a,b) = UCLN(b,r)
Tìm UCLN của hai số nguyên bằng phép chia

Áp dụng giải thuật Euclid để tính ƯCLN của a = 1071 và b = 462. Đầu tiên, ta chia 1071 cho 462 thì được thương là 2 và số dư là 147:

1071 = 2 × 462 + 147.

Do đó, UCLN(1071,462) = UCLN(462, 147). Tiếp tục chia 462 cho 147 thì được thương bằng 3 và số dư là 21:

462 = 3 × 147 + 21.

Do đó, UCLN(462,147) = UCLN(147, 21). Tiếp tục chia 147 cho 21 thì được thương là 7 và số dư là 0:

147 = 7 × 21 + 0.

Do đó, UCLN(1071,462)=21.

Giả mã của thuật toán này như sau:
```
function gcd(a, b)
    while b ≠ 0
        t:= b
        b:= a mod b
        a:= t
    return a
```
Một cách ngắn gọn, để tìm UCLN của hai số x và y có thể xem trong hình sau:

Đối với chương trình viết bằng Dart, bạn có thể tham khảo code tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-15.html

Nếu sử dụng hàm, hoặc đệ quy, mời bạn tham khảo trong bài…

Tìm UCLN của hai số nguyên bằng phép trừ

Tìm UCLN của hai số nguyên bằng cách phép trừ. Ở đây, chúng ta sử dụng không sử dụng phép chia mà sử dụng tính chất sau nếu a và b cùng chia hết cho d thì hiệu a-b cũng chia hết cho d.

Ví dụ, xét hai số nguyên 15 và 9 thì UCLN(15,9) = UCLN(15-9,9).

Giả mã của thuật toán này như sau:
```
function gcd(a, b)
    while a ≠ b 
        if a > b
            a:= a − b
        else
            b:= b − a
    return a
```
Bạn có thể tham khảo mã nguồn tại đây https://divin.dev/dart/2021/10/14/bai-tap-dart-15.html

Xem thêm: Thuật toán quay lui và minh họa
18/10/2021
50 bài tập lập trình Dart cơ bản

50 bài tập lập trình Dart cơ bản

50 bài tập lập trình Dart cơ bản dưới đây được chúng tôi gợi ý giải bằng ngôn ngữ Dart. Tuy nhiên, bạn hoàn toàn có thể sử dụng Python, C, C#, C++, Java hoặc các ngôn ngữ lập trình khác để giải quyết. Do đó chúng tôi tổng hợp chung lại thành một bài viết. Phần lời giải, nếu có, của từng ngôn ngữ sẽ có bài viết riêng.

Xem thêm: Giáo trình tự học Flutter/Dart

Playlist dạy lập trình Dart:

1. Bài tập lập trình Dart, C, Java cơ bản sử dụng if for while

Các bài tập này sử dụng các câu lệnh điều kiện if, câu lệnh rẽ nhánh for, while (câu lệnh điều khiển luồng chương trình).

Bài 1. Viết chương trình hỏi người dùng họ tên và tuổi (là một số nguyên). Tính và in ra màn hình còn bao nhiêu năm nữa thì người đó mừng thọ 100 tuổi 🙂

Xem thêm: Cách đọc input từ người dùng tại https://www.youtube.com/watch?v=UH9Hs1wiIqM

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-1.html

Bài 2. Viết chương trình hỏi người dùng nhập vào một số nguyên. In ra màn hình số nguyên đó là số chẵn hay lẻ.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-2.html

Bài 3. In ra màn hình tất cả các số nguyên dương lẻ nhỏ hơn 100.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-3.html

Bài 4. Viết chương trình in ra tất cả các số lẻ nhỏ hơn 100 trừ các số 5, 7, 93.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-4.html

Bài 5. Viết chương trình tìm số lớn nhất trong ba số thực a, b, c.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-5.html

Bài 6. Viết chương trình kiểm tra xem hai số thực a b cho trước có cùng dấu hay không.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-6.html

Bài 7. Viết chương trình in ra cách đọc của một số nguyên n cho trước có ba chữ số. Ví dụ với n=123 thì kết quả in ra màn hình là Một trăm hai mươi ba.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-7.html

Bài 8. Viết chương trình sinh ra một số tự nhiên n ngẫu nhiên từ 1 đến 100. Đề nghị người dùng đoán một số và nhập vào. In ra màn hình thông báo xem số người dùng đoán đúng, lớn hơn hay nhỏ hơn số n. Nếu chưa đúng thì cho phép người dùng đoán lại hai lần nữa.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-8.html

Bài 9. Viết chương trình tìm tất cả các số chia hết cho 7 nhưng không phải bội số của 5, nằm trong đoạn 10 và 200. Các số thu được sẽ được in thành chuỗi trên một dòng, cách nhau bằng dấu phẩy.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-9.html

Bài 10. Viết chương trình nhập ngày, tháng, năm. Hãy cho biết tháng đó có bao nhiêu ngày.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-10.html

Bài 11. Viết chương trình nhập ngày, tháng, năm. Hãy cho biết ngày đó là thứ mấy.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-11.html

Bài 12. Viết chương trình in bảng cửu chương ra màn hình.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-12.html

Bài 13. Hãy sử dụng vòng lặp for để in tất cả các ký tự A tới Z ra màn hình.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-13.html

Bài 14. Viết một chương trình tính giai thừa của một số nguyên dương n. Với n được nhập từ bàn phím. Ví dụ, n = 8 thì kết quả đầu ra phải là

1*2*3*4*5*6*7*8 = 40320

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-14.html

Bài 15. Viết chương trình tìm ước số chung lớn nhất (UCLN) của hai số nguyên dương a và b nhập từ bàn phím.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-15.html

Bài 16. Viết chương trình tìm bội số chung nhỏ nhất (BCNN) của hai số nguyên dương a và b nhập từ bàn phím.

Bài 17. Viết chương trình kiểm tra một số nguyên dương n có phải là số nguyên tố hay không.

Lời giải: https://divin.dev/dart/2021/10/14/bai-tap-dart-17.html

Bài 18. Viết chương trình liệt kê n số nguyên tố đầu tiên. Số nguyên dương n được nhập từ bàn phím.

Hướng dẫn. Bạn có thể tham khảo về sàng số nguyên tố

Bài 19. Tìm số nguyên dương n nhỏ nhất sao cho 1 + 2 + … + n > 10000.

Lời giải: Bài tập Dart số 19

Bài 20. Viết chương trình liệt kê n số hạng đầu tiên của dãy Fibonacci không sử dụng hàm.

Hướng dẫn. Nếu sử dụng hàm và lời gọi đệ qui thì bài toán khá đơn giản, xin mời xem lời giải ở bài 54. Ở đây, chúng ta sẽ sử dụng ba biến để luôn phiên thay đổi các số hạng của dãy Fibonacci và một biến đếm.

Lời giải: Bài tập Dart số 20-Dãy Fibonacci

Bài 21. Viết chương trình tính tổng các giá trị lẻ nguyên dương nhỏ hơn số nguyên dương n cho trước.

Bài 22. Viết chương trình tìm số nguyên dương m lớn nhất sao cho 1 + 2 + 3 + … + m < N.

Bài 23. Viết chương trình liệt kê tất cả số nguyên tố có 5 chữ số.

Bài 24. Viết chương trình phân tích số nguyên n thành các thừa số nguyên tố. Ví dụ: 100 = 2*2*5*5.

Bài 25. Viết chương trình tính tổng của các chữ số của môt số nguyên n trong Dart. Số nguyên dương n được nhập từ bàn phím. Với n = 1234, tổng các chữ số: 1 + 2 + 3 + 4 = 10.

Bài 26. Viết chương trình kiểm tra một số nguyên dương n có là số thuận nghịch hay không.

Bài 27. Viết chương trình liệt kê tất cả các số nguyên tố nhỏ hơn n. Số nguyên dương n được nhập từ bàn phím.

Bài 28. Liệt kê tất cả ước số của số nguyên dương n.

Bài 29. Tính tổng tất cả ước số của số nguyên dương n.

Bài 30. Tính tích tất cả ước số của số nguyên dương n.

Bài 31. Đếm số lượng ước số của số nguyên dương n.

Bài 32. Liệt kê tất cả ước số lẻ của số nguyên dương n.

Bài 33. Cho số nguyên dương n. Tính tổng các ước số nhỏ hơn chính nó.

Bài 34. Tìm ước số lẻ lớn nhất của số nguyên dương n. Ví dụ n = 100 ước lẻ lớn nhất của 100 là 25.

Bài 35. Cho số nguyên dương n. Kiểm tra số dương n có phải là số hoàn thiện (số hoàn hảo) hay không.

Bài 36. Cho số nguyên dương n. Kiểm tra số nguyên dương n có phải là số nguyên tố hay không.

Bài 37. Cho số nguyên dương n. Kiểm tra số nguyên dương n có phải là sốchính phương hay không.

Bài 38. Cho n là số nguyên dương. Hãy tìm giá trị nguyên dương k lớn nhất sao cho S(k) < n. Trong đó chuỗi S(k) được định nghĩa như sau:

S(k) = 1 + 2 + 3 + … + k

Bài 39. Hãy đếm số lượng chữ số của số nguyên dương n.

Bài 40. Hãy tính tổng các chữ số của số nguyên dương n.

Bài 41. Hãy tìm chữ số đảo ngược của số nguyên dương n.

Bài 42. Tìm chữ số nhỏ nhất của số nguyên dương n.

Bài 43. Hãy kiểm tra số nguyên dương n có toàn chữ số lẻ hay không.

Bài 44. Hãy kiểm tra các chữ số của số nguyên dương n có tăng dần từ trái sang phải hay không.

Bài 45. Hãy kiểm tra các chữ số của số nguyên dương n có giảm dần từ trái sang phải hay không.

Bài 46. Giải phương trình bậc nhất ax+b=0.

Bài 47. Giải phương trình bậc hai ax^2+bx+c=0.

Bài 48. Giải phương trình trùng phương ax^4+bx^2+c=0.

Bài 49. Viết chương trình nhập 3 cạnh của một tam giác là các số nguyên dương. Hãy cho biết đó là tam giác gì.

Bài 50. Lập chương trình giải hệ: $$\begin{cases} ax+by=c\\ dx+ey=f \end{cases}$$ Các hệ số a b c d e f nhập từ bàn phím. Yêu cầu xét tất cả các trường hợp có thể. (Gợi ý: Sử dụng định thức)

2. Bài tập lập trình Dart, C, Java cơ bản sử dụng hàm

Bài 51. Cần có tổng 200.000đ từ 3 loại tiền 1000đ, 2000đ, và 5000đ. Lập chương tình để tìm tất cả các phương án có thể.Tìm giá trị lớn nhất trong mảng một chiều các số thực.

Bài 52. Viết chương trình tính tổng các số tự nhiên từ 1 tới n.

Bài 53. Viết chương trình tính giai thừa của số tự nhiên n.

Bài 54. Viết hàm tính số hạng thứ n của dãy Fibonacci.

Bài 55. Viết hàm kiểm tra xem số nguyên dương n có là số nguyên tố hay không.

Bài 56. Viết hàm tìm UCLN của hai số nguyên a và b sử dụng đệ quy.

13/10/2021

100 đề Toán Tin (Tin học & Nhà trường)

O2 Education xin gửi tới bạn đọc TUYỂN TẬP 100 ĐỀ TOÁN TIN (100 đề Toán Tin được trích từ tạp chí Tin học & Nhà trường). Bản PDF và Word, mời các bạn tải ở cuối bài viết

Phần 1: ĐỀ BÀI 100 đề Toán Tin (Tin học & Nhà trường)

Bài 1/1999 – Trò chơi cùng nhau qua cầu

(Dành cho học sinh Tiểu học)

Bốn người cần đi qua một chiếc cầu. Do cầu yếu nên mỗi lần đi không quá hai người, và vì trời tối nên phải cầm đèn mới đi được. Bốn người đi nhanh chậm khác nhau, qua cầu với thời gian tương ứng là 10 phút, 5 phút, 2 phút và 1 phút. Vì chỉ có một chiếc đèn nên mỗi lần qua cầu phải có người mang đèn trở về cho những người kế tiếp. Khi hai người đi cùng nhau thì qua cầu với thời gian của người đi chậm hơn. Ví dụ sau đây là một cách đi:

Người 10 phút đi với người 5 phút qua cầu, mất 10 phút.
Người 5 phút cầm đèn quay về, mất 5 phút.
Người 5 phút đi với người 2 phút qua cầu, mất 5 phút.
Người 2 phút cầm đèn quay về, mất 2 phút.
Người 2 phút đi với người 1 phút qua cầu, mất 2 phút.

Thời gian tổng cộng là 10+5+5+2+2 = 24 phút.

Em hãy tìm cách đi khác với tổng thời gian càng ít càng tốt, và nếu dưới 19 phút thì thật tuyệt vời!

Bài 2/1999 – Tổ chức tham quan

(Dành cho học sinh THCS)

Trong đợt tổ chức đi tham quan danh lam thắng cảnh của thành phố Hồ Chí Minh, Ban tổ chức hội thi Tin học trẻ tổ chức cho $N$ đoàn (đánh từ số $1$ đến $N$) mỗi đoàn đi thăm quan một địa điểm khác nhau. Đoàn thứ $i$ đi thăm địa điểm ở cách Khách sạn Hoàng Đế $d_i$ km ($i=1,2,…,N$). Hội thi có $M$ xe taxi đánh số từ $1$ đến $M$ ($M\geqslant N$) để phục vụ việc đưa các đoàn đi thăm quan. Xe thứ $j$ có mức tiêu thụ xăng là $v_j$ đơn vị thể tích/km.

Yêu cầu: Hãy chọn $N$ xe để phục vụ việc đưa các đoàn đi thăm quan, mỗi xe chỉ phục vụ một đoàn, sao cho tổng chi phí xăng cần sử dụng là ít nhất.

Dữ liệu: File văn bản P2.INP:

Dòng đầu tiên chứa hai số nguyên dương $N$, $M$ ($N \leqslant M\leqslant 200$)
Dòng thứ hai chứa các số nguyên dương $d_1, d_2, …, d_N$
Dòng thứ ba chứa các số nguyên dương $v_1, v_2, …, V_M$
Các số trên cùng một dòng được ghi khác nhau bởi dấu trắng

Kết quả: Ghi ra file văn bản P2.OUT:

Dòng đầu tiên chứa tổng lượng xăng dầu cần dùng cho việc đưa các đoàn đi thăm quan (không tính lượt về);
Dòng thứ i trong số $N$ dòng tiếp theo ghi chỉ số xe phục vụ đoàn $i$ ($i=1, 2, …, N$).

Ví dụ:

P2.INP

P2.OUT

3 4

7 5 9

17 13 15 10

256

Bài 3/1999 – Mạng tế bào

(Dành cho học sinh THPT)

Mạng tế bào có dạng một lưới ô vuông hình chữ nhật. Tại mỗi nhịp thời gian: mỗi ô của lưới chứa tín hiệu là 0 hoặc 1 và có thể truyền tín hiệu trong nó cho một số ô kề cạnh theo một qui luật cho trước. Ô ở góc trên bên trái có thể nhận tín hiệu từ bên ngoài đưa vào. Sau nhịp thời gian đó, tín hiệu ở một ô sẽ là 0 nếu tất cả các tín hiệu truyền đến nó là 0, còn trong trường hợp ngược lại tín hiệu trong nó sẽ là 1. Một ô không nhận được tín hiệu nào từ các ô kề cạnh với nó sẽ giữ nguyên tín hiệu đang có trong nó. Riêng đối với ô trên trái, sau khi truyền tín hiệu chứa trong nó đi, nếu có tín hiệu vào thì ô trên trái sẽ chỉ nhận tín hiệu này, còn nếu không có tín hiệu nào thì ô trên trái cũng hoạt động giống như các ô khác. ở trạng thái đầu tín hiệu trong tất cả các ô là 0.

Yêu cầu: Cho trước số nhịp thời gian $T$ và dãy tín hiệu vào $S$ là một dãy gồm T ký hiệu $S_1$,…, $S_T$, trong đó $S_i$ là 0 hoặc 1 thể hiện có tín hiệu vào, ngược lại $S_i$ là $X$ thể hiện không có tín hiệu vào tại nhịp thời gian thứ $i$ ($1 \leqslant i \leqslant T$), hãy xác định trạng thái của lưới sau nhịp thời gian thứ $T$.

Dữ liệu: vào từ file văn bản P3.INP:

Dòng đầu tiên chứa 3 số nguyên $M$, $N$, $T$ theo thứ tự là số dòng, số cột của lưới và số nhịp thời gian ($1<M, N \leqslant 200$; $T \leqslant 100$);
Dòng thứ hai chứa xâu tín hiệu vào $S$;
$M$ dòng tiếp theo mô tả qui luật truyền tin. Dòng thứ $i$ trong số $M$ dòng này chứa $N$ số $a_{i1}, a_{i2}, …, a_{iN}$, trong đó giá trị của $a_{ij}$ sẽ là 1, 2, 3, 4, 5, 6, 7, 8 tương ứng lần lượt nếu ô $(i, j)$ phải truyền tin cho ô kề cạnh bên trái, bên phải, bên trên, bên dưới, bên trên và bên dưới, bên trái và bên phải, bên trên và bên trái, bên dưới và bên phải (xem hình vẽ); còn nếu ô $(i, j)$ không phải truyền tín hiệu thì $a_{ij}=0$.

Kết quả: Ghi ra file văn bản P3.OUT gồm M dòng, mỗi dòng là một xâu gồm N ký tự 0 hoặc 1 mô tả trạng thái của lưới sau nhịp thời gian thứ T.

Ví dụ:

P3.INP

P3.OUT

2 2 5

101XX

2 4

2 1

Quá trình biến đổi trạng thái được diễn tả trong hình dưới đây:

0	0			1	0			0	1			1	0			1	1			1	1
0	0			0	0			0	0			0	1			1	0			0	1

Bài 4/1999 – Trò chơi bốc sỏi

(Dành cho học sinh Tiểu học)

Trên mặt đất có một đống sỏi có 101 viên. Hai em học sinh Hoàng và Huy chơi trò chơi như sau: Mỗi em đến lượt đi phải bốc ra từ đống sỏi trên tối thiểu là 1 viên và tối đa là 4 viên. Người thua là người phải bốc viên sỏi cuối cùng. Giả sử Hoàng là người được bốc trước, Huy bốc sau. Các em thử nghĩ xem ai là người thắng cuộc, Hoàng hay Huy? Và người thắng cuộc phải suy nghĩ gì và thực hiện các bước đi của mình ra sao?

Bài 5/1999 – 12 viên bi

(Dành cho học sinh THCS)

Có 12 hòn bi giống hệt nhau về kích thước, hình dáng và khối lượng. Tuy nhiên trong chúng lại có đúng một hòn bi kém chất lượng: hoặc nhẹ hơn hoặc nặng hơn bình thường. Dùng một cân bàn hai bên, bạn hãy dùng 3 lần cân để tìm ra được viên bi đó. Cần chỉ rõ rằng viên bi đó là nặng hơn hay nhẹ hơn.

Viết chương trình mô phỏng việc tổ chức cân các hòn bi trên. Dữ liệu về hòn bi kém chất lượng do người sử dụng chương trình nắm giữ. Yêu cầu trình bày chương trình đẹp và mỹ thuật.

Bài 6/1999 – Giao điểm các đường thẳng

(Dành cho học sinh THPT)

Trên mặt phẳng cho trước n đường thẳng. Hãy tính số giao điểm của các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.

Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.

Dữ liệu vào của bài toán cho trong tệp B6.INP có dạng sau:

Dòng đầu tiên ghi số n
n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài toán thể hiện trên màn hình.

Bài 7/1999 – Miền mặt phẳng chia bởi các đường thẳng

(Dành cho học sinh THPT)

Xét bài toán tương tự như bài 6/1999 nhưng yêu cầu tính số miền mặt phẳng được chia bởi n đường thẳng này:

Trên mặt phẳng cho trước n đường thẳng. Hãy tính số miền mặt phẳng được chia bởi các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.

Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.

Dữ liệu vào của bài toán cho trong tệp B7.INP có dạng sau:

Dòng đầu tiên ghi số n
n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.

Kết quả của bài toán thể hiện trên màn hình.

Bài 8/1999 – Cân táo

(Dành cho học sinh Tiểu học)

Mẹ đi chợ về mua cho Nga 27 quả táo giống hệt nhau về kích thước và khối lượng. Tuy nhiên người bán hàng nói rằng trong số các quả táo trên có đúng một quả có khối lượng nhẹ hơn. Em hãy dùng một chiếc cân bàn hai bên để tìm ra quả táo nhẹ đó. Yêu cầu số lần cân là nhỏ nhất.

Các em hãy giúp bạn Nga tìm ra quả táo nhẹ đó đi. Nếu các em tìm ra quả táo đó sau ít hơn 5 lần cân thì đã là tốt lắm rồi.

Bài 9/1999 – Bốc diêm

(Dành cho học sinh Tiểu học)

Trên bàn có 3 dãy que diêm, số lượng que diêm của các dãy này lần lượt là 3, 5 và 8. Hai bạn Nga và An chơi trò chơi sau: Mỗi bạn đến lượt mình được quyền (và phải) bốc một số que diêm bất kỳ từ một dãy trên. Người thắng là người bốc được que diêm cuối cùng.

Ai là người thắng cuộc trong trò chơi trên? Và bạn đó phải bốc diêm như thế nào? Các bạn hãy cùng suy nghĩ với Nga và An nhé.

Bài 10/1999 – Dãy số nguyên

(Dành cho học sinh THCS)

Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:

1234567891011121314... (1)

Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?

Em hãy làm bài này theo hai cách: Cách 1 dùng suy luận logic và cách 2 viết chương trình để tính toán và so sánh hai kết quả với nhau.

Tổng quát bài toán trên: Chương trình yêu cầu nhập số K từ bàn phím và in ra trên màn hình kết quả là số nằm ở vị trì thứ K trong dãy (1) trên. Yêu cầu chương trình chạy càng nhanh càng tốt.

Bài 11/1999 – Dãy số Fibonaci

(Dành cho học sinh THCS)

Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, …. Dãy này cho bởi công thức đệ qui sau:

F₁ = 1, F₂ =1, F_n = F_n-1 + F_n-2 với n > 2

1. Chứng minh khẳng định sau:

Mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của một số số trong dãy số Fibonaci.

N = a_kF_k + a_k-1F_k-1 +…+a₁F₁

Với biểu diễn như trên ta nói N có biểu diễn Fibonaci là a_ka_k-1a₂a₁

2. Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.

Input:

Tệp văn bản P11.INP bao gồm nhiều dòng. Mỗi dòng ghi một số tự nhiên.

Output:

Tệp P11.OUT ghi kết quả của chương trình: trên mỗi dòng ghi lại biểu diễn Fibonaci của các số tự nhiên tương ứng trong tệp P11.INP.

Bài 12/1999 – N-mino

(Dành cho học sinh THPT)

N-mino là hình thu được từ N hình vuông $1\times 1$ ghép lại (cạnh kề cạnh). Hai n-mino được gọi là đồng nhất nếu chúng có thể đặt chồng khít lên nhau.

Bạn hãy lập chương trình tính và vẽ ra tất cả các N-mino trên màn hình. Số n nhập từ bàn phím.

Ví dụ: Với N=3 chỉ có hai loại N-mino sau đây:

3-mino thẳng và 3-mino hình thước thợ

Chú ý: Gọi Mn là số các n-mino khác nhau thì ta có M1=1, M2=1, M3=2, M4=5, M5=12, M6=35,…

Yêu cầu bài giải đúng và trình bày đẹp.

Bài 13/1999 – Phân hoạch hình chữ nhật

(Dành cho học sinh THPT)

Một hình vuông có thể chia thành nhiều hình chữ nhật có các cạnh song song với cạnh hình vuông (xem Hình vẽ). Xây dựng cấu trúc dữ liệu và lập chương trình mô tả phép chia đó. Tính xem có bao nhiêu cách chia như vậy.

Input

Dữ liệu nhập vào từ tệp P13.INP bao gồm hai số tự nhiên là n, m – kích thước hình chữ nhật.

Output

Dữ liệu ra nằm trong tệp P13.OUT có dạng sau:

Dòng đầu tiên ghi số K là tổng số các phép phân hoạch.
Tiếp theo là K nhóm, mỗi nhóm cách nhau bằng một dòng trống.
Mỗi nhóm dữ liệu bao gồm các cặp tọa độ của các hình chữ nhật nằm trong phân hoạch.

Bài 14/2000 – Tìm số trang sách của một quyển sách

(Dành cho học sinh Tiểu học)

Để đánh số các trang sách của 1 quyển sách cần tất cả 1392 chữ số. Hỏi quyển sách có tất cả bao nhiêu trang?

Bài 15/2000 – Hội nghị đội viên

(Dành cho học sinh Tiểu học)

Trong một hội nghị liên chi đội có một số bạn nam và nữ. Biết rằng mỗi bạn trai đều quen với N các bạn gái và mỗi bạn gái đều quen với đúng N bạn trai. Hãy lập luận để chứng tỏ rằng trong hội nghị đó số các bạn trai và các bạn gái là như nhau.

Bài 16/2000 – Chia số

(Dành cho học sinh THCS)

Bạn hãy chia N2 số 1, 2, 3, …., N2-1, N2 thành N nhóm sao cho mỗi nhóm có số các số hạng như nhau và có tổng các số này cũng bằng nhau.

Bài 17/2000 – Số nguyên tố tương đương

(Dành cho học sinh THCS)

Hai số tự nhiên được gọi là Nguyên tố tương đương nếu chúng có chung các ước số nguyên tố. Error: Reference source not foundVí dụ các số 75 và 15 là nguyên tố tương đương vì cùng có các ước nguyên tố là 3 và 5. Cho trước hai số tự nhiên N, M. Hãy viết chương trình kiểm tra xem các số này có là nguyên tố tương đương với nhau hay không.

Bài 18/2000 – Sên bò

(Dành cho học sinh THCS và THPT)

Trên lưới ô vuông một con sên xuất phát từ đỉnh (0,0) cần phải đi đến điểm kết thúc tại (N,0) (N là số tự nhiên cho trước).

Qui tắc đi: Mỗi bước (x1, y1) –> (x2, y2) thoả mãn điều kiện (sên bò):

x2 = x1 + 1
y1 – 1 <= y2 <= y1 + 1

Tìm một cách đi sao cho trong quá trình đi nó có thể lên cao nhất trên trục tung (tức là tọa độ y đạt cực đại). Chỉ cần đưa ra một nghiệm.

Input

Số N được nhập từ bàn phím.

Output

Output ra file P5.OUT có dạng:

Dòng đầu tiên ghi 2 số: m, h. Trong đó m là số các bước đi của con sên để đến được vị trí đích, h ghi lại độ cao cực đại đạt được của con sên.
m dòng tiếp theo, mỗi dòng ghi ra lần lượt các tọa độ (x,y) là các bước đi của sên trên lưới.

Yêu cầu kỹ thuật

Các bạn có thể mô tả các bước đi của con sên trên màn hình đồ họa. Để đạt được mục đích đó số N cần được chọn không vượt quá 50. Mặc dù không yêu cầu nhưng những lời giải có mô phỏng đồ họa sẽ có điểm cao hơn nếu không mô phỏng đồ họa.

Bài 19/2000 – Đa giác

(Dành cho học sinh THPT)

Hãy tìm điều kiện cần và đủ để N số thực dương a1, a2, …, aN tạo thành các cạnh liên tiếp của một đa giác N cạnh trên mặt phẳng. Giả sử cho trước N số a1, a2, …, aN thỏa mãn điều kiện là các cạnh của đa giác, bạn hãy lập chương trình biểu diễn và vẽ đa giác trên.

Input

Input của bài toán là tệp P6.INP bao gồm 2 dòng, dòng đầu tiên ghi số N, dòng thứ hai ghi N số thực cách nhau bởi dấu cách.

Output

Đầu ra của bài toán thể hiện trên màn hình.

Chú ý: Phần lý thuyết của bài toán cần được chứng minh một cách chặt chẽ.

Bài 20/2000 – Bạn Lan ở căn hộ số mấy?

(Dành cho học sinh Tiểu học)

Nhà Lan ở trong một ngôi nhà 8 tầng, mỗi tầng có 8 căn hộ. Một hôm, các bạn trong lớp hỏi Lan:

“Nhà bạn ở căn hộ số mấy?”.

“Các bạn hãy thử hỏi một số câu, mình sẽ trả lời tất cả câu hỏi của các bạn, nhưng chỉ nói “đúng” hoặc “không” thôi. Qua các câu hỏi đó các bạn thử đoán xem mình ở căn hộ số bao nhiêu”- Lan trả lời.

Bạn Huy nói:

“Mình sẽ hỏi, có phải bạn ở căn hộ số 1, số 2,…, số 63 không. Như vậy với nhiều nhất 63 câu hỏi mình sẽ biết được bạn căn hộ nào.”

Bạn Nam nói:

“Còn mình chỉ cần đến 14 câu, 7 câu đủ để biết bạn ở tầng mấy và 7 câu có thể biết chính xác bạn ở căn hộ số mấy”.

Còn em, em phải hỏi nhiều nhất mấy lần để biết được bạn Lan ở căn hộ số bao nhiêu?

Bài 21/2000 – Những trang sách bị rơi

(Dành cho học sinh Tiểu học)

Một cuốn sách bị rơi mất một mảng. Trang bị rơi thứ nhất có số 387, còn trang cuối cũng gồm 3 chữ số 3, 8, 7 nhưng được viết theo một thứ tự khác.

Hỏi có bao nhiêu trang sách bị rơi ra?

Bài 22/2000 – Đếm đường đi

(Dành cho học sinh THCS)

Cho hình sau:

a) Bạn hãy đếm tất cả các đường đi từ A đến B. Mỗi đường đi chỉ được đi qua mỗi đỉnh nhiều nhất là 1 lần.

b) Bạn hãy tìm tất cả các đường đi từ A đến D, sao cho đường đi đó qua mỗi cạnh đúng một lần.

c) Bạn hãy tìm tất cả các đường đi qua tất cảc các cạnh của hình, mỗi cạnh đúng một lần, sao cho:

Điểm bắt đầu và điểm kết thúc trùng nhau.
Điểm bắt đầu và điểm kết thúc không trùng nhau

Bài 23/2000 – Quay Rubic

(Dành cho học sinh THPT)

Rubic là một khối lập phương gồm 3´3´3 = 27 khối lập phương con. Mỗi mặt rubic gồm 3´3 = 9 mặt của một lớp 9 khối lập phương con. ở trạng thái ban đầu, mỗi mặt rubic được tô một màu. Các mặt khác nhau được tô các màu khác nhau. Giả sử ta đang nhìn vào một mặt trước của rubic. Có thể kí hiệu màu các mặt như sau: F: màu mặt trước là mặt ta đang nhìn; U: màu mặt trên; R: màu mặt phải; B: màu mặt sau; L: màu mặt bên trái; D: màu mặt dưới.

Một lớp gồm 3´3 khối lập phương con có thể quay 90 độ nhiều lần, trục quay đi qua tâm và vuông góc với mặt đang xét. Kết quả sau khi quay là khối lập phương 3´3´3 với các màu mặt đã bị đổi khác.

Một xâu vòng quay liên tiếp rubic có thể mô tả bằng xâu các chữ cái của U, R, F, D, B, L, trong đó mỗi chữ cái là kí hiệu một vòng quay cơ sở: quay mặt tương ứng 90 độ theo chiều kim đồng hồ. Hãy viết chương trình giải 3 bài toán dưới đây:

Cho 2 xâu INPUT khác nhau, kiểm tra xem liệu nếu áp dụng với trạng thái đầu có cho cùng một kết quả hay không?
Cho một xâu vào, hãy xác định số lần cần áp dụng xâu vào đó cho trạng thái đầu rubic để lại nhận được trạng thái đầu đó.

1. Cho 2 xâu INPUT khác nhau, kiểm tra xem liệu nếu áp dụng với trạng thái đầu có cho cùng một kết quả hay không?

2. Cho một xâu vào, hãy xác định số lần cần áp dụng xâu vào đó cho trạng thái đầu rubic để lại nhận được trạng thái đầu đó.

Bài 24/2000 – Sắp xếp dãy số

(Dành cho học sinh Tiểu học)

Cho dãy số: 3, 1, 7, 9, 5. Cho phép 3 lần đổi chỗ, mỗi, lần được đổi chỗ hai số bất kỳ. Em hãy sắp xếp lại dãy số trên theo thứ tự tăng dần.

Bài 25/2000 – Xây dựng số

(Dành cho học sinh THCS)

Cho các số sau: 1, 2, 3, 5, 7. Chỉ dùng phép toán cộng hãy dùng dãy trên để tạo ra số: 43, 52.

Ví dụ để tạo số 130 bạn có thể làm như sau: 123 + 7 = 130.

Bài 26/2000 – Tô màu

(Dành cho học sinh THCS)

Cho lưới ô vuông 4×4, cần phải tô màu các ô của lưới. Được phép dùng 3 màu: Xanh, đỏ, vàng. Điều kiện tô màu là ba ô bất kỳ liền nhau theo chiều dọc và ngang phải khác màu nhau. Hỏi có bao nhiêu cách như vậy, hãy liệt kê tất cả các cách.

Bài 27/2000 – Bàn cờ

(Dành cho học sinh THPT)

Cho một bàn cờ vuông 8×8, trên đó cho trước một số quân cờ. Ví dụ hình vẽ sau là một bàn cờ như vậy:

Dữ liệu nhập được ghi trên tệp BANCO.TXT bao gồm 8 dòng, mỗi dòng là một sâu nhị phân có độ dài bằng 8. Vị trí các quân cờ ứng với số 1, các ô trống ứng với số 0. Ví dụ tệp BANCO.TXT ứng với bàn cờ trên:

Hãy viết chương trình tính số quân cờ liên tục lớn nhất nằm trên một đường thẳng trên bàn cờ. Đường thẳng ở đây có thể là đường thẳng đứng. đường nằm ngang hoặc đường chéo. Kết quả thể hiện trên màn hình.

Với ví dụ nêu trên, chương trình phải in trên màn hình kết quả là 4.

Bài 28/2000 – Đổi tiền

(Dành cho học sinh Tiểu học)

Giả sử bạn có nhiều tờ tiền loại 1, 2 và 5 ngàn đồng. Hỏi với các tờ tiền đó bạn có bao nhiêu cách đổi tờ 10 ngàn đồng? Hãy liệt kê các cách đổi.

Bài 29/2000 – Chọn bạn

(Dành cho học sinh THCS)

Trong một trại hè người ta tình cờ chọn ra một nhóm 6 học sinh. Chứng minh rằng sẽ tìm được 3 trong số 6 bạn đó sao cho 3 bạn này hoặc đã quen nhau (đôi một) từ trước hoặc chưa hề quen nhau. Em hãy chỉ ra cách tìm 3 bạn đó.

Bài 30/2000 – Phần tử yên ngựa

(Dành cho học sinh THCS)

Cho bảng A kích thước MxN. Phần tử Aij được gọi là phần tử yên ngựa nếu nó là phần tử nhỏ nhất trong hàng của nó đồng thời là phần tử lớn nhất trong cột của nó. Ví dụ trong bảng số sau đây:

15 3 9
55 4 6
76 1 2

thì phần tử A22 chính là phần tử yên ngựa.

Bạn hãy lập chương trình nhập từ bàn phím một bảng số kích thước MxN và kiểm tra xem nó có phần tử yên ngựa hay không?

Bài 31/2000 – Biểu diễn phân số

(Dành cho học sinh PTTH)

Một phân số luôn luôn có thể được viết dưới số thập phân hữu hạn hoặc vô hạn tuần hoàn. Ví dụ:

23/5 = 4.6

3/8 = 0.375

1/3 = 0.(3)

45/56 = 0.803(571428)

….

Trong các ví dụ trên thì các chữ số đặt trong dấu ngoặc chỉ phần tuần hoàn của số thập phân.

Nhiệm vụ của bạn là viết một chương trình nhập tử số (N) và nhập mẫu số (D), sau đó đưa ra kết quả là dạng thập phân của phân số N/D.

Ví dụ chạy chương trình:

Nhap N, D:1 7

1/7 = 0.(142857)_

Bài 32/2000 – Bài toán 8 hậu

(Dành cho học sinh Tiểu học)

Trên bàn cờ vua hãy sẵp xếp đúng 8 quân Hậu sao cho không còn con nào có thể ăn được con nào. Hãy tìm ra nhiều cách sắp nhất?

Bài 33/2000 – Mã hoá văn bản

(Dành cho học sinh THCS)

Bài toán sau mô tả một thuật toán mã hoá đơn giản (để tiện ta lấy ví dụ tiếng Anh, các bạn có thể mở rộng cho tiếng Việt):

Tập hợp các chữ cái tiếng Anh bao gồm 26 chữ cái được đánh sô thứ tự từ 0 đến 25 như sau:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	Z

Quy tắc mã hoá một ký tự như sau (lấy ví dụ ký tự X):

– Tìm số thứ tự tương ứng của ký tự ta được 23

– Tăng giá trị số này lên 5 ta được 28

– Tìm số dư trong phép chia số này cho 26 ta được 2

– Tra ngược bảng chữ cái ta thu được C.

a. Sử dụng quy tắc trên để mã hoá các dòng chữ sau:

PEACE

HEAL THE WORLD

I LOVE SPRING

b. Hãy tìm ra quy tắc giải mã các dòng chữ sau:

N FR F XYZIJSY

NSKTVRFYNHX

MFSTN SFYNTSFQ ZSNBJVXNYD

Bài 34/2000 – Mã hoá và giải mã

(Dành cho học sinh THCS)

Theo quy tắc mã hoá ở bài trên (33/2000), hãy viết chương trình cho phép:

– Nhập một xâu ký tự và in ra xâu ký tự đã được mã hóa

– Nhập một xâu ký tự đã được mã hoá và in ra sâu ký tự đã được giải mã.

Ví dụ khi chạy chương trình:

Nhap xau ky tu:

PEACE

Xau ky tu tren duoc ma hoa la:

UJFHJ

Nhap xau ky tu can giai ma:

Xau ky tu tren duoc giai ma la:

AM_

Bài 35/2000 – Các phân số được sắp xếp

(Dành cho học sinh THPT)

Xét tập F(N) tất cả các số hữu tỷ trong đoạn [0,1] với mẫu số không vượt quá N.

Ví dụ tập F(5):

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

Hãy viết chương trình cho phép nhập số nguyên N nằm trong khoẳng từ 1 đến 100 và xuất ra theo thứ tự tăng dần các phân số trong tập F(N) cùng số lượng các phân số đó.

Ví dụ khi chạy chương trình:

Nhap so N: 5

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

Tat ca co 11 phan so_

Bài 36/2000 – Anh chàng hà tiện

(Dành cho học sinh Tiểu học)

Một chàng hà tiện ra hiệu may quần áo. Người chủ hiệu biết tính khách nên nói với anh ta: “Tôi tính tiền công theo 2 cách: cách thứ nhất là lấy đúng 11700 đồng. Cách thứ hai là lấy theo tiền cúc: chiếc cúc thứ nhất tôi lấy 1 đồng, chiếc cúc thứ 2 tôi lấy 2 đồng gấp đôi chiếc thứ nhất, chiếc cúc thứ 3 tôi lấy 4 đống gấp đôi lần chiếc cúc thứ 2 và cứ tiếp tục như thế cho đến hết. áo của anh có 18 chiếc cúc. Nếu anh thấy cách thứ nhất là đắt thì anh có thể trả tôi theo cách thứ hai.”

Sau một hồi suy nghĩ chàng hà tiện quyết định chọn theo cách thứ hai. Hỏi anh ta phải trả bao nhiêu tiền và anh ta có bị “hố” hay không?

Bài 37/2000 – Số siêu nguyên tố

(Dành cho học sinh THCS)

Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.

Ví dụ 7331 là một số siêu nguyên tố có 4 chữ số vì 733, 73, 7 cũng là các số nguyên tố.

Nhiệm vụ của bạn là viết chương trình nhập dữ liệu vào là một số nguyên N (0< N <10) và đưa ra kết quả là một số siêu nguyên tố có N chữ số cùng số lượng của chúng.

Ví dụ khi chạy chương trình:

Nhap so N: 4

Cac so sieu nguyen to có 4 chu so la: 2333 2339 2393 2399 2939 3119 3137 3733 3739 3793 3797 5939 7193 7331 7333 7393

Tat ca co 16 so_

Bài 38/2000 – Tam giác số

(Dành cho học sinh THPT)

Hình sau mô tả một tam giác số có số hàng N=5:

				7
			3		8
		8		1		0
	2		7		4		4
4		5		2		6		5

Đi từ đỉnh (số 7) đến đáy tam giác bằng một đường gấp khúc, mỗi bước chỉ được đi từ số ở hàng trên xuống một trong hai số đứng kề bên phải hay bên trái ở hàng dưới, và cộng các số trên đường đi lại ta được một tổng.

Ví dụ: đường đi 7 8 1 4 6 có tổng là S=26, đường đi 7 3 1 7 5 có tổng là S=23

Trong hình trên, tổng Smax=30 theo đường đi 7 3 8 7 5 là tổng lớn nhất trong tất cả các tổng.

Nhiệm vụ của bạn và viết chương trình nhận dữ liệu vào là một tam giác số chứa trong text file INPUT.TXT và đưa ra kết quả là giá trị của tổng Smax trên màn hình.

File INPUT.TXT có dạng như sau:

Dòng thứ 1: có duy nhất 1 số N là số hàng của tam giác số (0<N<100).

N dòng tiếp theo, từ dòng thứ 2 đến dòng thứ N+1: dòng thứ i có (i-1) số cách nhau bởi dấu trống (space).

Ví dụ: với nội dung của file INPUT.TXT là

thì kết quả chạy chương trình sẽ là: Smax=30.

Bài 39/2000 – Ô chữ

(Dành cho học sinh THCS và THPT)

Trò chơi ô chữ thông dụng 30 năm trước của trẻ em gồm một khung ô chữ kích thước 5×5 chứa 24 hình vương nhỏ kích thước như nhau. Trên mặt mỗi hình vuông nhỏ có in một chữ cái trong bảng chữ cái. Vì chỉ có 24 hình vuông trong ô chữ nên trong ô chữ còn thừa ra một ô trống, có kích thước đúng bằng kích thước các hình vuông. Một hình vuông có thể đẩy trượt vào ô trống đó nếu nó nằm ngay sát bên trái, bên phải, bên trên hay bên dưới ô trống. Mục tiêu của trò chơi là trượt các hình vuông vào ô trống sao cho cuối cùng các chữ cái trong ô chữ được xếp theo đúng thứ tự của chúng trong bảng chữ cái. Hình sau đây minh hoạ một ô chữ với cấu hình ban đầu và cấu hình của nó sau 6 nước đi sau:

1.Trượt hình vuông phía trên ô trống.

2.Trượt hình vuông bên phải ô trống.

3.Trượt hình vuông bên phải ô trống.

4.Trượt hình vuông phía dưới ô trống.

5.Trượt hình vuông phía dưới ô trống.

6.Trượt hình vuông bên trái ô trống.

Bạn hãy viết một chương trình của bạn chứa cấu hình ban đầu của ô chữ cùng các nước đi để vẽ ra ô chữ kết quả.

Input

Đầu vào của chương trình của bạn chứa cấu hình ban đầu của một ô chữ và một dẫy các nước đi trong ô chữ đó.

Năm dòng đầu tiên mô tả cấu hình ban đầu của ô chữ, mỗi dòng tương ứng với một hàng của ô chữ và chứa đúng 5 ký tự tương ứng với 5 hình vuông của ô chữ trên hàng đó. Ô trống được diễn tả bằng một dấu cách.

Các dòng tiếp theo sau là dẫy các nước đi. Dãy các nước đi được ghi bằng dãy các chữ A,B,R và L để thể hiện hình vuông nào được trượt vào ô trống. A thể hiện hình vuông phía trên ô trống được trượt vào ô trống, tương ứng: B-phía dưới, R-bên phải, L-bên trái. Có thể có những nước đi không hợp cách, ngay cả khi nó được biểu thị bằng những chữ cái trên. Nếu xuất hiện một nước đi không hợp cách thì ô chữ coi như không có cấu hình kết quả. Dãy các nước đi có thể chiếm một số dòng, nhưng nó sẽ được xem là kết thúc ngay khi gặp một số 0.

Out put

Nếu ô chữ không có cấu hình kết quả thì thông báo ‘This puzzle has no final configuration.’; ngược lại thì hiển thị cấu hình ô chữ kết quả. Định dạng mỗi dòng kết quả bằng cách đặt một dấu cách vào giữa hai kí tự kế tiếp nhau. Ô trống cũng được sử lý như vậy. Ví dụ nếu ô trống nằm bên trong hàng thì nó được xuất hiện dưới dạng 3 dấu cách: một để ngăn cách nó với kí tự bên trái, một để thể hiện chính ô trống đó, còn một để ngăn cách nó với kí tự bên phải.

Chú ý: Input mẫu đầu tiên tương ứng với ô chữ được minh hoạ trong ví dụ trên.

Sample Input 1

TRGSJ
XDOKI
M VLN
WPABE
UQHCF
ARRBBL0

Sample Output 1

T R G S J

X O K L I

M D V B N

W P A E

U Q H C F

Sample Input 2

AB C DE

F G H I J

KLMNO

PQRS

TUVWX

AAA

LLLL0

Sample Output 2

A B C D

F G H I E

K L M N J

P Q R S O

T U V W X

Sample Input 3

ABCDE

FGHIJ

KLMNO

PQRS

TUVWX

AAAAABBRRRLL0

Sample Output 3

This puzzle has no final configuration.

Bài 40/2000 – Máy định vị Radio

Một con tàu được trang bị ăng-ten định hướng có thể xác định vị trí hiện thời của mình nhờ các lần đọc đèn hiệu địa phương. Mỗi đèn hiệu được đặt ở một vị trí đã biết và phát ra một tín hiệu đơn nhất. Mỗi khi bắt được tín hiệu, tàu liền quay ăng-ten của mình cho đến khi đạt được tín hiệu cực đại. Điều đó cho phép xác định được phương vị tương đối của đèn hiệu. Cho biết dữ liệu của lần đọc trước (thời gian, phương vị tương đối, vị trí của đèn), một lần đọc mới đủ để xác định vị trí hiện thời của tàu. Bạn phải viết một chương trình xác định vị trí hiện thời của tàu từ hai lần đọc đèn hiệu.

Vị trí của các đèn hiệu và các con tàu được cho trong hệ toạ độ vuông góc, trục Ox hướng về phía đông, còn Oy hướng về phía bắc. Hướng đi của con tàu được đo bằng độ, theo chiều kim đồng hồ tính từ hướng bắc. Như vậy, hướng bắc sẽ là 00, hướng đông là 900, hướng nam là 1800 và hướng tây là 2700. Phương vị tương đối của đèn hiệu cũng được đo bằng độ, tương đối với hướng đi của tàu và theo chiều kim đồng hồ. ăng ten không thể chỉ ra đèn hiệu nằm ở hướng nào trên phương vị. Như vậy, một phương vị 900 có nghĩa là đèn hiệu có thể nằm ở hướng 900 hoặc 2700.

Input

Dòng đầu tiên của input là một số nguyên chỉ số lượng các đèn hiệu (nhiều nhất là 30). Mỗi dòng tiếp theo cho một đèn hiệu. Mỗi dòng bắt đầu bằng tên đèn (là một chuỗi kí tự không vượt quá 20 kí tự), sau đó là vị trí của đèn cho bằng hoành độ và tung độ. Các trường này phân cách bởi một dấu cách.

Dòng tiếp theo ngay sau các dữ liệu về đèn hiệu là một số nguyên chỉ số lượng các kịch bản đường đi của tàu. Mỗi kịch bản chứa 3 dòng gồm một dòng cho biết hướng đi của tàu so với hướng Bắc và vận tốc vận tốc thực của tàu, và hai dòng chỉ hai lần đọc đèn hiệu. Thời gian được đo bằng phút, tính từ lúc nửa đêm trong vòng 24 giờ. Vận tốc đo bằng đơn vị độ dài (như các đơn vị của hệ trục toạ độ) trên đơn vị thời gian. Dòng thứ hai của kịch bản là lần đọc thứ nhất gồm thời gian (là một số nguyên), tên đèn và góc phương vị tương đối với hướng đi của tàu. Ba trường được ngăn cách nhau bởi một dấu cách. Dòng thứ ba của kịch bản là lần đọc thứ hai. Thời gian của lần đọc này luôn lớn hơn lần đọc thứ nhất.

Output

Với mỗi kịch bản, chương trình của bạn phải chỉ ra được số thứ tự của kịch bản (Scenario 1, Scenario 2,…), và một thông báo về vị trí của con tàu (được làm tròn đến hai chữ số thập phân) tại thời điểm của lần đọc thứ hai. Nếu vị trí của tàu không thể xác định thì thông báo: ”Position cannot be determined.”

Mẫu input và output chính xác tương ứng được cho như sau:

Sample Input

First 2.0 4.0

Second 6.0 2.0

Third 6.0 7.0

Fourth 10.0 5.0

0.0 1.0

1 First 270.0

2 Fourth 90.0

116.5651 2.2361

4 Third 126.8699

5 First 319.3987

Sample Output

Scenario 1: Position cannot be determined

Scenario 2: Position is (6.00, 5.00)

Bài 41/2000 – Cờ Othello

(Dành cho học sinh THCS và THPT)

Cờ Othello là trò chơi cho 2 người trên một bàn cờ kích thước 8×8 ô, dùng những quân tròn một mặt đen, một mặt trắng. Các đấu thủ sẽ được lần lượt đi một quân vào ô còn trống trên bàn cờ. Khi đi một quân, đấu thủ phải lật được ít nhất một quân của đấu thủ kia. Các quân sẽ lật được nếu chúng nằm liên tiếp trên cùng một đường thẳng (ngang, dọc hoặc chéo) mà ở hai đầu của đường đó là hai quân có mầu của đấu thủ đang đi. Khi xong một lượt đi, tất cả các quân đã bị lật đã được đổi sang màu của đấu thủ vừa đi. Trong một lượt đi có thể lật được nhiều hàng.

Ví dụ: Nếu thế cờ hiện thời ở bàn cờ bên trái và lượt đi là của đấu thủ trắng, thì anh ta có thể đi được một trong các nước sau: (3,5) (4,6) (5,3) (6,4). Nếu anh ta đi nước (3,5) thì sau nước đi thế cờ sẽ như ở bàn cờ bên phải.

Vẽ bàn cờ

Bạn hãy viết một chương trình để đọc một ván cờ từ một text file có qui cách:

8 dòng đầu tiên là bàn cờ thế, mỗi dòng chứa 8 kí tự, mỗi kí tự có thể là:

‘-‘ thể hiện một ô trống,

‘B’ thể hiện một ô có quân đen,

‘W’ thể hiện một ô có quân trắng.

Dòng thứ 9 chứa một trong hai kí tự ‘B’ hoặc ‘W’ để chỉ nước đi thuộc về đấu thủ nào.

Các dòng tiếp theo là các lệnh. Mỗi lệnh có thể là: liệt kê tất cả các nước đi có thể của đấu thủ hiện thời, thực hiện một nước đi, hay thôi chơi ván cờ đó. Mỗi lệnh ghi trên một dòng theo qui cách sau:

Liệt kê tất cả các nước đi có thể của đấu thủ hiện thời:

Lệnh là một chữ ‘L’ ở cột đầu tiên của dòng. Chương trình phải kiểm tra cả bàn cờ và in ra tất cả các nước đi hợp lệ của đấu thủ hiện thời theo dạng (x,y) trong đó x là hàng và y là cột của nước đi. Các nước đi này phải được in theo qui cách:

+ Mọi nước đi trên hàng i sẽ được in trước mỗi nước đi trên hàng j nếu j>i.

+ Nếu trên hàng i có nhiều hơn 1 nước đi thì các nước đi được in theo thứ tự của cột.

Mọi nước đi hợp lệ phải in trên một dòng. Nếu không có nước đi nào hợp lệ vì đấu thủ hiện thời không thể lật bất cứ một quân nào thì phải in ra thông báo ‘No legal move’.

Thực hiện một nước đi

Lệnh là một chữ ‘M’ ở cột đầu tiên của dòng, tiếp theo sau là 2 chữ số ở cột thứ hai và thứ ba của dòng. Các chữ số chỉ ra hàng và cột của ô trống trên bàn cờ nơi đấu thủ hiện thời sẽ đặt quân của mình, trừ phi anh ta không có nước đi hơp lệ nào. Nếu đấu thủ hiện thời không có nước đi hợp lệ nào thì anh ta được thay bởi đấu thủ kia và bây giờ nước đi là của đấu thủ mới. Chương trình phải kiểm tra khi đó nước đi là hợp lệ. Bạn sẽ phải ghi nhận sự thay đổi trên bàn cờ, kể cả việc thêm các quân mới lẫn việc thay đổi màu sắc quân cờ bị lật. Cuối mỗi nước đi hãy in ra số lượng tất cả các quân cờ mỗi màu trên bàn cờ theo qui cách ‘Black – xx White – yy, trong đó xx là số lượng các quân đen còn yy là số lượng các quân trắng. Sau một nước đi, đấu thủ hiện thời được thay bởi đấu thủ kia.

Thôi chơi ván cờ đó

Lệnh là một chữ ‘Q’ ở cột đầu tiên của dòng, dòng lệnh này kết thúc Input cho ván cờ đang xét. Chương trình phải in thế cờ cuối cùng của ván cờ theo qui cách được dùng ở input.

Bạn phải kiểm tra tính chính xác của các lệnh. Không được để dòng trắng ở bất cứ nơi nào trong output.

Bài 42/2000 – Một chút về tư duy số học

(Dành cho học sinh Tiểu học)

Tìm số tự nhiên nhỏ nhất khi chia cho 2, 3, 4, 5, 6, 7, 8, 9, 10 cho phần dư tương ứng là 1, 2, 3, 4, 5, 6, 7, 8, 9.

Bài 43/2000 – Kim giờ và phút gặp nhau bao nhiêu lần trong ngày

(Dành cho học sinh Tiểu học)

Đồng hồ quả lắc có 2 kim: giờ và phút. Tính xem trong vòng 1 ngày đêm (từ 0h – 24h) có bao nhiêu lần 2 kim gặp nhau và đó là những lúc nào.

Bài 44/2000 – Tạo ma trận số

(Dành cho học sinh THCS)

Cho trước số nguyên dương N bất kỳ. Hãy viết thuật toán và chương trình để tạo lập bảng NxN phần tử nguyên dương theo quy luật được cho trong ví dụ sau:

1 2 3 4 5 6

2 4 6 8 10 12

3 6 9 12 2 4

4 8 12 2 4 6

5 10 2 4 6 8

6 12 4 6 8 10

Thực hiện chương trình đó trên máy với N=12, đưa ra màn hình ma trận kết quả (có dạng như trong ví dụ).

Bài 45/2000 – Các vòng tròn Olimpic

(Dành cho học sinh THPT)

Có 5 vòng tròn Olimpic chia mặt phẳng thành 15 phần (không kể phần vô hạn) (hình vẽ). Hãy đặt vào mỗi phần đó một số sao cho tổng số các số trong mỗi vòng tròn bằng 39.

Lập chương trình giải quyết bài toán trên và cho biết có bao nhiêu cách xếp như vậy.

Bài 46/2000 – Đảo chữ cái

(Dành cho học sinh THCS và THPT)

Bạn phải viết chương trình đưa ra tất cả các từ có thể có phát sinh từ một tập các chữ cái.

Ví dụ: Cho từ “abc”, chương trình của bạn phải đưa ra được các từ “abc”, “acb”, “bac”, “bca”, “cab” và “cba” (bằng cách khảo sát tất cả các trường hợp khác nhau của tổ hợp ba chữ cái đã cho).

Input

Dữ liệu vào được cho trong tệp input.txt chứa một số từ. Dòng đầu tiên là một số tự nhiên cho biết số từ được cho ở dưới. Mỗi dòng tiếp theo chứa một từ. Trong đó, một từ có thể chứa cả chữ cái thường hoặc hoa từ A đến Z. Các chữ thường và hoa được coi như là khác nhau. Một chữ cái nào đó có thể xuất hiện nhiều hơn một lần.

Output

Với mỗi từ đã cho trong file Input.txt, kết quả nhận được ra file Output.txt phải chứa tất cả các từ khác nhau được sinh từ các chữ cái của từ đó. Các từ được sinh ra từ một từ đã cho phải được đưa ra theo thứ tự tăng dần của bảng chữ cái.

Sample Input

abc

acba

Sample Output

abc

acb

bac

bca

cab

cba

aabc

aacb

abac

abca

acab

acba

baac

baca

bcaa

caab

caba

cbaa

Bài 47/2000 – Xoá số trên vòng tròn

(Dành cho học sinh THCS và PTTH)

Các số từ 1 đến 2000 được xếp theo thứ tự tăng dần trên một đường tròn theo chiều kim đồng hồ. Bắt đầu từ số 1, chuyển động theo chiều kim đồng hồ, cứ bước qua một số lại xoá đi một số. Công việc đó tiếp diễn cho đến khi trên vòng tròn còn lại đúng một số. Lập chương trình tính và in ra số đó.

Bài 48/2000 – Những chiếc gậy

(Dành cho học sinh THCS và THPT)

George có những chiếc gậy với chiều dài như nhau và chặt chúng thành những đoạn có chiều dài ngẫu nhiên cho đến khi tất cả các phần trở thành đều có chiều dài tối đa là 50 đơn vị. Bây giờ anh ta muốn ghép các đoạn lại như ban đầu nhưng lại quên mất nó như thế nào và chiều dài ban đầu của chúng là bao nhiêu. Hãy giúp George thiết kế chương trình để ước tính nhỏ nhất có thể của chiều dài những cái gậy này. Tất cả chiều dài được biểu diễn bằng đơn vị là những số nguyên lớn hơn 0.

Input

Dữ liệu vào trong file Input.txt chứa các khối mỗi khối 2 dòng. Dòng đầu tiên chứa số phần của chiếc gậy sau khi cắt. Dòng thứ 2 là chiều dài của các phần này cách nhau bởi một dấu cách. Dòng cuối cùng kết thúc file Input là số 0.

Output

Kết quả ra trong file Output.txt chứa chiều dài nhỏ nhất có thể của những cái gậy, mỗi chiếc trong mỗi khối trên một dòng.

Sample Input

5 2 1 5 2 1 5 2 1

1 2 3 4

Sample Output

Bài 49/2001 – Một chút nhanh trí

(Dành cho học sinh Tiểu học)

Số tự nhiên A có tính chất là khi chia A và lập phương của A cho một số lẻ bất kỳ thì nhận được số dư như nhau. Tìm tất cả các số tự nhiên như vậy.

Bài 50/2001 – Bài toán đổi màu bi

(Dành cho học sinh THCS và THPT)

Trên bàn có N1 hòn bi xanh, N2 hòn bi đỏ và N3 hòn bi vàng. Luật chơi như sau:

Nếu 2 hòn bi khác màu nhau chạm nhau thì chúng sẽ cùng biến thành màu thứ 3 (ví dụ: xanh, vàng –> đỏ, đỏ).

Tìm thuật toán và lập chương trình cho biết rằng có thể biến tất cả các hòn bi đó thành một màu đỏ có được không?

Bài 51/2001 – Thay thế từ

(Dành cho học sinh THCS và PTTH)

Hai file INPUT1.TXT và INPUT2.TXT được cho như sau: File INPUT1.TXT chứa một đoạn văn bản bất kì. File INPUT2.TXT chứa không quá 50 dòng, mỗi dòng gồm hai từ: từ đầu là từ đích và từ sau là từ nguồn. Hãy tìm trong file INPUT1.TXT tất cả các từ là từ đích và thay thế chúng bằng các từ nguồn tương ứng. Kết quả ghi vào file KQ.OUT (sẽ là một đoạn văn bản tương tự như trong file INPUT1.TXT nhưng đã được thay thế từ đích bởi từ nguồn).

Sample INPUT

File INPUT1.TXT chứa đoạn văn bản sau:

Nam moi sap den roi, ban co zui khong?

Chuc cac ban don mot cai Tet that vui ve va hanh phuc.

Chuc ban luon hoc gioi!

File INPUT2.TXT chứa các dòng sau:

ban em
zui vui

Sample OUTPUT

File KQ.OUT sẽ chứa đoạn văn bản sau:

Nam moi sap den roi, em co vui khong?
Chuc cac em don mot cai Tet that vui ve va hanh phuc.
Chuc em luon hoc gioi!

Bài 52/2001 – Xác định các tứ giác đồng hồ trong ma trận

(Dành cho học sinh THCS và THPT)

Cho ma trận vuông A[i,j] (i,j = 1, 2 … n). Các phần tử của A được đánh số từ 1 đến nn.

Gọi S là số lượng các “tứ giác” có bốn đỉnh là: A[i,j]; A[i,j+1]; A[i+1,j]; A[i+1,j+1] sao cho các số ở đỉnh của nó xếp theo thứ tự tăng dần theo chiều kim đồng hồ (tính từ một đỉnh nào đó).

1) Lập chương trình tính số lượng S.

2) Lập thuật toán xác định A sao cho số S là:

a. Lớn nhất.

b. Nhỏ nhất.

Bài 53/2001 – Lập lịch tháng kỳ ảo

(Dành cho học sinh THCS và THPT)

Lịch của các tháng được biểu diễn bằng một ma trận có số cột bằng 7 và số hàng nhỏ hơn hoặc bằng 6.

		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

Ví dụ: Trong hình vẽ, lịch này thỏa mãn tính chất sau: Mọi ma trận con 33 không có ô trống đều là ma trận “kỳ ảo” theo nghĩa: Tổng các số của mỗi đường chéo bằng tổng của trung bình cộng của tất cả các cột và hàng. Hãy xây dựng tất cả các lịch tháng có tính chất như trên. Lập chương trình mô tả tất cả các khả năng xảy ra.

Bài 54/2001 – Bạn hãy gạch số

(Dành cho học sinh Tiểu học và THCS)

Chúng ta viết liên tiếp 10 số nguyên tố đầu tiên theo thứ tự tăng để tạo thành một số có nhiều chữ số. Trong số này hãy gạch đi một nửa số chữ số để số còn lại là:

a. Nhỏ nhất

b. Lớn nhất

Trong từng trường hợp phải nêu cụ thể thuật giải (tại sao lại gạch như vậy)?

Bài 55/2001 – Bài toán che mắt mèo

(Dành cho học sinh THCS và THPT)

Trên bàn cờ ô vuông NxN tại mỗi ô có thể xếp hoặc một con mèo con, hoặc một quân cờ. Hai con mèo trên bàn cờ sẽ nhìn thấy nhau nếu trên đường thẳng nối chúng theo hàng ngang, hàng dọc hay đường chéo không có quân cờ nào cả.

Hãy tìm cách xếp mèo và quân cờ như trên sao cho số mèo lớn nhất mà không có hai con mèo nào nhìn thấy nhau?

Bài 56/2001 – Chia lưới

(Dành cho học sinh THPT)

Cho lưới MN (m, n <= 20) ô vuông, trong mỗi ô cho trước một số tự nhiên. Hãy tìm cách chia lưới trên làm hai phần (chia theo cạnh lưới) sao cho trị tuyệt đối hiệu số của tổng các số trong mỗi phần có giá trị nhỏ nhất (như hình dưới đây).

			7
1	3	5
12	2	5
9	2	10

Dữ liệu được cho trong file LUOI.INP, được cho như sau:

– Dòng đầu tiên gồm 2 số m, n là kích thước của ô lưới.

– m dòng tiếp theo, mỗi dòng gồm n số cách nhau bởi dấu cách, ô nào không có giá trị được cho bằng 0.

Dữ liệu ra trong file LUOI.OUT miêu tả lưới sau khi chia thành hai phần: là một ma trận kích thước mn gồm các số 0 và 1 (số 0 kí hiệu cho các ô tương ứng với phần thứ nhất, và số 1 kí hiệu cho các ô tương ứng với phần thứ hai).

Sample Input:

Dữ liệu cho sau đây tương ứng với hình trên:

5 6

0 0 0 0 7 0

0 1 3 5 0 0

0 12 2 5 0 0

0 9 2 10 0 0

0 0 0 0 0 0

Sample Output:

0 1 1 1 1 1

0 1 0 1 1 1

0 0 0 1 1 1

0 0 0 0 0 1

Bài 57/2001 – Chọn số

(Dành cho học sinh Tiểu học và THCS )

Cho 2000 số a1, a2,…, a2000 mỗi số là +1 hoặc -1. Hỏi có thể hay không từ 2000 số đó chọn ra các số nào đó để tổng các số được chọn ra bằng tổng các số còn lại? Giả sử cho 2001 số, liệu có thể có cách chọn không? Nêu cách giải tổng quát.

Bài 58/2001 – Tổng các số tự nhiên liên tiếp

(Dành cho học sinh THCS và THPT)

Cho trước số tự nhiên n. Lập thuật toán cho biết n có thể biểu diễn thành tổng của hai hoặc nhiều số tự nhiên liên tiếp hay không?

Trong trường hợp có, hãy thể hiện tất cả các cách có thể có.

Bài 59/2001 – Đếm số ô vuông

(Dành cho học sinh THCS và THPT)

Cho một bảng vuông gồm NxN điểm nằm trên các mắt lưới ô vuông. Các điểm kề nhau trên một hàng hay một cột có thể được nối với nhau bằng một đoạn thẳng hoặc không được nối. Các đoạn đó sẽ tạo ra các ô vuông trên bảng. Ví dụ với bảng sau đây thì n = 4 và có 3 ô vuông:

Trên mỗi hàng có thể có nhiều nhất n-1 đoạn thẳng nằm ngang và có tất cả n hàng như vậy. Tương tự như vậy có tất cả n-1 hàng các đoạn thẳng nằm dọc và trên mỗi hàng có thể có nhiều nhất n đoạn.

Để mô tả người ta dùng hai mảng nhị phân: một mảng ghi các đoạn nằm ngang kích thước n x (n-1), và một mảng ghi các đoạn nằm dọc kích thước (n-1) xn. Trong mảng, số 1 dùng để mô tả đoạn thẳng nối giữa 2 điểm, còn số 0 miêu tả giữa hai điểm không có đoạn thẳng nối. Trong ví dụ trên thì ma trận “ngang” là:

và ma trận “dọc” là:

Cho trước ma trận “ngang” và ma trận “dọc”, dữ liệu nhập từ các tệp văn bản có tên là NGANG.INP và DOC.INP. Hãy lập trình đếm số các ô vuông trên bảng.

Bài 60/2001 – Tìm số dư của phép chia

(Dành cho học sinh Tiểu học)

Một số nguyên khi chia cho 1976 và 1977 đều dư 76. Hỏi số đó khi chia cho 39 dư bao nhiêu?

Bài 61/2001 – Thuật toán điền số vào ma trận

(Dành cho học sinh THCS và THPT)

Hãy lập thuật toán điền các phần tử của ma trận NN các số 0, 1 và -1 sao cho:

a) Tổng các số của mọi hình vuông con 2×2 đều bằng 0.

b) Tổng các số của ma trận trên là lớn nhất.

Bài 62/2001 – Chèn Xâu

(Dành cho học sinh THCS và THPT)

Cho một xâu S = ’123456789’ hãy tìm cách chèn vào S các dấu ‘+’ hoặc ‘-‘ để thu được số M cho trước (nếu có thể). Số M nguyên được nhập từ bàn phím. Trong file Output Chenxau.Out ghi tất cả các phương án chèn (nếu có) và ghi “Khong co” nếu như không thể thu được M từ cách làm trên.

Ví dụ: Nhập M = 8, một trong các phương án đó là: ‘-1+2-3+4+5-6+7’;

M = -28, một trong các phương án đó là: ‘-1+2-34+5’;

(Đề ra của bạn: Lê Nhân Tâm – 12 Tin Trường THPT Lam Sơn)

Bài 63/2001 – Tìm số nhỏ nhất

(Dành cho học sinh Tiểu học)

Hãy viết ra số nhỏ nhất bao gồm tất cả các chữ số 0, 1, 2, 3, … 9 mà nó:

a. Chia hết cho 9
b. Chia hết cho 5
c. Chia hết cho 20

Có giải thích cho từng trường hợp?

Bài 64/2001 – Đổi ma trận số

(Dành cho học sinh THCS và THPT)

Cho mảng số thực vuông A kích thước 2nx2n. Hãy lập các mảng mới bằng cách đổi chỗ các khối vuông kích thước nxn của A theo các cách sau:

Bài 65/2001 – Lưới ô vuông vô hạn

(Dành cho học sinh THCS và THPT)

Cho lưới ô vuông vô hạn về hai phía (trên và phải). Các ô của lưới được đánh số theo quy tắc sau:

Ô trái dưới – vị trí (0,0) – được đánh số 0.
Các ô còn lại được đánh số theo nguyên tắc lan toả từ vị trí (0,0) và theo quy tắc: tại một vị trí số được điền vào là số nguyên không âm nhỏ nhất chưa được điền trên hàng và cột chứa ô hiện thời. Ví dụ, ta có hình dạng của một số ô của lưới như sau:


3	2	1	0
2	3	0	1
1	0	3	2
0	1	2	3

Cho trước cặp số tự nhiên M, N – kích thước ô lưới. Hãy viết chương trình mô tả lưới trên, kết quả được ghi vào file KQ.TXT.

Bài 66/2001 – Bảng số 9 x 9

(Dành cho học sinh Tiểu họcvà THCS)

Hãy xếp các số 1, 2, 3, …, 81 vào bảng 9 x 9 sao cho:

a) Trên mỗi hàng các số được xếp theo thứ tự tăng dần (từ trái qua phải).

b) Tổng các số ở cột 5 là lớn nhất.

Yêu cầu:

Đối với các bạn học sinh khối Tiểu học chỉ cần viết ra bảng số thoả mãn tính chất trên.
Các bạn học sinh khối THCS thì phải lập trình hiển thị kết quả ra màn hình.

Bài 67/2001 – Về các phép biến đổi “Nhân 2 trừ 1”

(Dành cho học sinh THCS và THPT)

Cho ma trận A kích thước M x N, Aij – là các số tự nhiên. Các phép biến đổi có thể là:

Nhân tất cả các số của một hàng với 2.
Trừ tất cả các số của một cột cho 1.

Tìm thuật toán sao cho sau một số phép biến đổi trên ma trận A trở thành toàn số 0.

Bài 68/2001 – Hình tròn và bảng vuông

(Dành cho học sinh THPT)

Một đường tròn đường kính 2n -1 đơn vị được vẽ giữa bàn cờ 2n2n. Với n = 3 được minh hoạ như dưới đây:

Viết chương trình xác định số ô vuông của bảng bị cắt bởi hình tròn và số ô vuông nằm hoàn toàn trong hình tròn.

Dữ liệu vào trong file Input.txt bao gồm: Mỗi dòng là một số nguyên dương không lớn hơn 150 – là các giá trị của n.

Dữ liệu ra trong file Output.txt: Với mỗi giá trị vào n, kết quả ra phải tính được số ô vuông bị cắt bởi hình tròn và số ô vuông nằm hoàn toàn trong hình tròn, mỗi số trên một dòng. Mỗi kết quả tương ứng với một giá trị n phải cách nhau một dòng.

Sample Input

Sample Output

Bài 69/2001 – Bội của 36

(Dành cho học sinh Tiểu học)

Tìm số tự nhiên nhỏ nhất chia hết cho 36 mà trong dạng viết thập phân của nó có chứa tất cả các chữ số từ 1 tới 9.

Bài 70/2001 – Mã hoá theo khoá

(Dành cho học sinh THCS và THPT)

Cho trước khoá là một hoán vị của n số (1, 2, …, n). Khi đó để mã hoá một xâu kí tự ta có thể chia xâu thànhtừng nhóm n kí tự (riêng nếu nhóm cuối cùng không đủ n kí tự thì ta coa thể thêm các dấu cách vào sau cho đủ) rồi hoán vị các kí tự trong từng nhóm. Sau đó, ghép lại theo thứ tự các nhóm ta được một xâu đã mã hoá.

Chẳng hạn: với khoá 3241 (n=4) thì ta có thể mã hoá xâu ‘english’ thành ‘gnlehs i’.

Hãy viết chương trình mã hoá một xâu kí tự cho trước.

Bài 71/2001 – Thực hiện phép nhân

(Dành cho học sinh THCS và THPT)

Bạn hãy lập chương trình nhập 2 số nguyên dương a và b. Sau đó thực hiện phép nhân (a x b) như cách nhân bằng tay thông thường. Ví dụ:

Bài 72/2001 – Biến đổi trên lưới số

(Dành cho học sinh THCS và THPT)

Trên một lưới N x N các ô được đánh số 1 hoặc -1. Lưới trên được biến đổi theo quy tắc sau: một ô nào đó được thay thế bằng tích của các số trong các ô kề nó (kề cạnh). Lập chương trình thực hiện sao cho sau một số bước toàn lưới còn lại chữ số 1.

Bài 73/2001 – Bài toán chuỗi số

(Dành cho học sinh Tiểu họcvà THCS)

Cho một chuỗi số có quy luật. Bạn có thể tìm được hai số cuối của dãy không, thay thế chúng trong dấu hỏi chấm (?). Bài toán không dễ dàng lắm đâu, vì chúng được tạo ra bởi một quy luật rất phức tạp. Bạn thử sức xem?

5 8 11 14 17 23 27 32 35 41 49 52 ? ?

Bài 74/2001 – Hai hàng số kỳ ảo

(Dành cho học sinh THCS và THPT)

Hãy xếp 2N số tự nhiên 1, 2, …, 2N thành 2 hàng số:

A1, A2 … An

B1, B2 … Bn

Thỏa mãn điều kiện: tổng các số theo n cột bằng nhau, tổng các số theo các hàng bằng nhau.

Bài 75/2001 – Trò chơi Tích – Tắc vuông

(Dành cho học sinh THCS và THPT)

Trên một lưới kẻ ô vuông có 2 người chơi như sau: người thứ nhất mỗi lần chơi sẽ đánh dấu x vào 1 ô trống. Người thứ hai được đánh dấu 0 vào 1 ô trống. Người thứ nhất muốn đạt được mục đích là đánh được 4 dấu x tạo thành 4 đỉnh của 1 hình vuông. Người thứ hai có nhiệm vụ ngăn cản mục đích đó của người thứ nhất.

Lập chương trình tìm thuật toán tối ưu cho người thứ nhất (người thứ nhất có thể luôn thắng).

Chú ý: Lưới ô vuông được coi là vô hạn về cả hai phía.

Bài76/2001 – Đoạn thẳng và hình chữ nhật

(Dành cho học sinh THPT)

Hãy viết một chương trình xác định xem một đoạn thẳng có cắt hình chữ nhật hay không?

Ví dụ:

Cho tọa độ điểm bắt đầu và điểm kết thúc của đường thẳng: (4,9) và (11,2);

Và tọa độ đỉnh trái trên và đỉnh phải dưới của hình chữ nhật: (1,5) và (7,1);

: Đoạn thẳng không cắt hình chữ nhật

Đoạn thẳng được gọi là cắt hình chữ nhật nếu đoạn thẳng và hình chữ nhật có ít nhất một điểm chung.

Chú ý: mặc dù tất cả dữ liệu vào đều là số nguyên, nhưng tọa độ của các giao điểm tính ra chưa chắc là số nguyên.

Input

Dữ liệu vào trong file Input.Inp kiểm tra N trường hợp (N <= 1000). Dòng đầu tiên của file dữ liệu vào là số N. Mỗi dòng tiếp theo chứa một trường hợp kiểm tra theo quy cách sau:

xstart ystart xend yend xleft ytop xright yboottm

trong đó: (xstart, ystart) là điểm bắt đầu và (xend, yend) là điểm kết thúc của đoạn thẳng. Và (xleft, ytop) là đỉnh trái trên, (xright, ybottom) là đỉnh phải dưới của hình chữ nhật. 8 số này được cách nhau bởi một dấu cách.

Output

Với mỗi một trường hợp kiểm tra trong file Input.txt, dữ liệu ra trong file Output.out phải đưa ra một dòng gồm hoặc là chữ cái “T” nếu đoạn thẳng cắt hình chữ nhật, hoặc là “F” nếu đoạn thẳng không cắt hình chữ nhật.

Ví dụ

Input.Inp

4 9 11 2 1 5 7 1

Output.out

Bài 77/2001 – Xoá số trên bảng

(Dành cho học sinh Tiểu học)

Trên bảng đen cô giáo ghi lên 23 số tự nhiên: 1, 2, 3, …, 23

Các bạn được phép xoá đi 2 số bất kỳ trên bảng và thay vào đó một số mới là hiệu của chúng.

Hỏi có thể thực hiện sau một số bước trên bảng còn lại toàn số 0 hay không? Nếu được hãy chỉ ra một cách làm cụ thể.
Bài toán còn đúng không nếu thay số 23 bằng 25.

Bài 78/2001 – Cà rốt và những chú thỏ

(Dành cho học sinh Tiểu học)

Các số ở mỗi ô trong hình thoi dưới đây biểu thị số lượng củ cà rốt. Chú thỏ đi từ góc dưới với 14 củ cà rốt và đi lên đỉnh trên với 13 củ cà rốt, chỉ được đi theo đường chéo, đi đến đâu ăn hết tổng số cà rốt trong ô đó. Hỏi rằng chú thỏ có thể ăn được nhiều nhất bao nhiêu củ cà rốt?

Bài 79/2001 – Về một ma trận số

(Dành cho học sinh THCS)

Mô tả thuật toán, lập chương trình xây dựng ma trận A[10,10] thoả mãn các tính chất:

A[i,j] là các số nguyên từ 0..9 (1 <= i, j <= 10),
Mỗi số từ 0..9 được gặp 10 lần trong ma trận A,
Mỗi hàng và mỗi cột của A chứa không quá 4 số khác nhau.

Bài 80/2001 – Xếp số 1 trên lưới

(Dành cho học sinh THCS)

Hãy xếp 16 số 1 lên ma trận 10×10 sao cho nếu xoá đi bất kỳ 5 hàng và 5 cột thì vẫn còn lại ít nhất là một số 1. Nêu thuật toán và lập trình hiển thị ra màn hình kết quả ma trận thoả mãn tính chất trên.

Bài 81/2001 – Dãy nghịch thế

(Dành cho học sinh THPT)

Cho dãy số (a1, a2, a3, …, an) là một hoán vị bất kỳ của tập hợp (1, 2, 3, …, n). Dãy số (b1, b2, b3, …, bn) gọi là nghịch thế của dãy a nếu bi là các phần tử đứng trước số i trong dãy a mà lớn hơn i.

Ví dụ:

Dãy a là: 3 2 5 7 1 4 6

Dãy b là: 4 1 0 2 0 1 0

a. Cho dãy a, hãy xây dựng chương trình tìm dãy b.

b. Cho dãy b, xây dựng chương trình tìm dãy a.

Dữ liệu vào trong file NGICH.INP với nội dung:

Dòng đầu tiên là số n (1 <= n <= 10 000).

Các dòng tiếp theo là n số của dãy a, mỗi số cách nhau một dấu cách,

Các dòng tiếp theo là n số của dãy b, mỗi số cách nhau bởi một dấu cách.

Dữ liệu ra trong file NGHICH.OUT với nội dung:

n số đầu tiên là kết quả của câu a,

Tiếp đó là một dòng trống và sau đó là n số kết quả của câu b (nếu tìm được dãy a).

Bài 82/2001 – Gặp gỡ

(Dành cho học sinh THPT)

Trên một lưới ô vuông kích thước MN (M dòng, N cột) người ta đặt k rôbôt. Rôbôt thứ i được đặt ở ô (xi,,yi). Mỗi ô của lưới có thể đặt một vật cản hay không. Tại mỗi bước, mỗi rôbôt chỉ có thể di chuyển theo các hướng lên, xuống, trái, phải – vào các ô kề cạnh không có vật cản. k rôbôt sẽ gặp nhau nếu chúng cùng đứng trong một ô. k rôbôt bắt đầu di chuyển đồng thời và mỗi lượt cả k rôbôt đều phải thực hiện việc di chuyển (nghĩa là không cho phép một rôbôt dừng lại một ô nào đó trong khi rôbôt khác thực hiện bước di chuyển). Bài toán đặt ra là tìm số bước di chuyển ít nhất mà k rôbôt phải thực hiện để có thể gặp nhau. Chú ý rằng, tùy trạng thái của lưới, k rôbôt có thể không khi nào gặp được nhau.

Dữ liệu vào cho trong file văn bản MEET.INP, bao gồm:

+ Dòng đầu tiên chứa 3 số M,N và k (M,N<=50;k<=10)

+ k dòng sau, dòng thứ i gồm 2 số xi,yi là vị trí của rôbốt thứ i.

+ M dòng tiếp theo, mỗi dòng ghi N số gồm 0 và 1 mô tả trạng thái dòng tương ứng của lưới, trong đó mỗi số mô tả một ô với quy ước: 0 – không có vật cản, 1 – có vật cản.

Các số trên cùng một dòng của file dữ liệu được ghi cách nhau ít nhất một dấu trắng.

Dữ liệu ra ghi lên file văn bản MEET.OUT: nếu k rôbôt không thể gặp nhau thì ghi một dòng gồm một ký tự #, trái lại ghi k dòng, mỗi dòng là một dãy các ký tự viết liền nhau mô tả các bước đi của rôbôt: U-lên trên, D-xuống dưới, L-sang trái, R-sang phải.

Ví dụ:

MEET.INP

4 6 2

1 1

4 6

0 1 1 0 0 0

0 0 0 0 0 1

0 0 1 0 0 1

0 1 0 1 0 0

MEET.OUT

DRRR

LUUL

Bài 83/2001 – Các đường tròn đồng tâm

(Dành cho học sinh Tiểu học)

Ba đường tròn đồng tâm, mỗi hình được chia thành 8 phần (như hình dưới).

Hãy đặt các số trong danh sách dưới đây vào các phần trong các hình tròn sao cho: mỗi đường tròn gồm 8 số trong tám phần có tổng bằng 80, mỗi phần của hình tròn ngoài gồm 3 số (mỗi phần của hình tròn ngoài chứa cả phần của hai hình tròn trong) có tổng bằng 30.

Các số bạn được sử dụng là:

14, 11, 10, 12, 7, 9, 9, 8, 9, 9, 11, 11, 10, 10, 10, 10, 14, 9, 7, 11, 10, 8, 12, 9.

Bài 84/2001 – Cùng một tích

(Dành cho học sinh THCS và THPT)

Cho n số x1, x2, …, xn chỉ nhận một trong các giá trị -1, 0, 1. Và cho một số nguyên P. Hãy tính số lượng tất cả các cách gán giá trị khác nhau của n số trên sao cho: $\sum x_i x_j = P$ (với i =1..n, j =1..n, i $\ne$ j). Hai cách gán được gọi là khác nhau nếu số lượng các số xi = 0 là khác nhau.

Input: gồm 2 số n, P.

Output: số các cách chọn khác nhau.

Giới hạn: 2 <= n <= 1010 ; |P| <= 1010.

(Đề ra của bạn Lý Quốc Vinh – Tp. Hồ Chí Minh)

Bài 85/2001 – Biến đổi 0 – 1

(Dành cho học sinh THPT)

Cho 2 lưới ô vuông A và B cùng kích thước M xN, mỗi ô có chỉ nhận các giá trị 0 hoặc 1 (A khác B). Các ô lưới được đánh số từ trên xuống dưới, từ trái qua phải bắt đầu từ 1. Cho phép thực hiện phép biến đổi sau đây với lưới A:

– Chọn ô (i, j) và đảo giá trị của ô đó và các ô chung cạnh với nó (0 thành 1, 1 thành 0).

Hãy xác định xem bằng cách áp dụng dãy biến đổi trên có thể đưa A về B được hay không? Nếu có hãy chỉ ra cách sử dụng một số ít nhất phép biến đổi.

Dữ liệu nhập vào từ file văn bản BIENDOI.INP:

Dòng đầu tiên ghi hai số M, N – kích thước ô lưới (M, N <= 100),
M dòng tiếp theo, mỗi dòng một xâu N kí tự 0, 1 ứng với dòng tương ứng của A,
Tiếp theo là một dòng trống,
M dòng cuối mỗi dòng 1 xâu N kí tự 0, 1 ứng với dòng tương ứng của B.

Dữ liệu ra trong file BIENDOI.OUT:

Dòng đầu số nguyên k là số lượng phép biến đổi ít nhất cần áp dụng (k = 0 nếu không biến đổi được)
Dòng thứ i trong số k dòng tiếp theo ghi hai số nguyên xác định ô cần chọn để thực hiện phép biến đổi.

Ví dụ:

BIENDOI. INP

BIENDOI.OUT

2
2 1
3 2

(Đề ra của bạn Nguyễn Văn Đức – Cần Thơ)

Bài 86/2001 – Dãy số tự nhiên logic

(Dành cho học sinh Tiểu học)

Đây là một chuỗi các số tự nhiên được sắp xếp theo một logic nào đó. Hãy tìm con số đầu tiên và cuối cùng của dãy số để thay thế cho dấu ?

? 12 14 15 16 18 20 21 22 ?

Bài 87/2001 – Ghi số trên bảng

(Dành cho học sinh THCS)

Trên bảng ghi số 0. Mỗi lần được tăng số đã viết lên bảng thêm 1 đơn vị hoặc tăng gấp đôi. Hỏi sau ít nhất là bao nhiêu bước sẽ thu được số nguyên dương N?

Bài 88/2001 – Về các số đặc biệt có 10 chữ số

(Dành cho học sinh THCS và THPT)

Lập chương trình tính (và chỉ ra) tất cả các số có 10 chữ số a0a1a2…a9 thoả mãn các tính chất sau:
a0 bằng số chữ số 0 của số trên;

a1 bằng số chữ số 1 của số trên;

a2 bằng số chữ số 2 của số trên;

…….

a9 bằng số chữ số 9 của số trên;

Bài 89/2001 – Chữ số thứ N

(Dành cho học sinh THCS và THPT)

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, ví dụ:

234567891011121314151617181920...

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 vào từ file ‘Number.inp’ gồm một số dòng, mỗi dòng ghi một số nguyên dương N (N<109).

Kết quả ra file ’Number.out’, với mỗi số N đọc được từ file Number.inp, ghi trên dòng tương ứng chữ số thứ N của dãy.

Ví dụ:

Number.inp

Number.out

Bài 90/2002 – Thay số trong bảng 9 ô

(Dành cho học sinh Tiểu học)

Cho một bảng vuông gồm 9 ô. Đầu tiên các ô được điền bởi các chữ cái I, S, M. Bạn hãy thay những số thích hợp vào các ô sao cho tổng các số trong các ô điền cùng chữ cái ban đầu là bằng nhau và là một số chia hết cho 4.

Chú ý: các ô cùng chữ cái phải thay bởi những số như nhau.

Bài 91/2002 – Các số lặp

(Dành cho học sinh THCS và THPT)

Cho dãy số nguyên gồm N phần tử. Lập chương trình in ra số được lặp nhiều nhất trong dãy.

Bài 92/2002 – Dãy chia hết

(Dành cho học sinh THPT)

Xét một dãy gồm N số nguyên tuỳ ý. Giữa các số nguyên đó ta có thể đặt các dấu + hoặc – để thu được các biểu thức số học khác nhau. Ta nói dãy số là chia hết cho K nếu một trong các biểu thức thu được chia hết cho K. Hãy viết chương trình xác định tính chia hết của một dãy số đã cho.

Dữ liệu vào: Lấy từ một file văn bản có tên là DIV.INP có cấu trúc như sau:

– Dòng đầu là hai số N và K (2 ≤ N ≤ 10 000, 2 ≤ K ≤ 100), cách nhau bởi dấu trống.

– Các dòng tiếp theo là dãy N số có trị tuyệt đối không quá 10 000 cách nhau bởi dấu trống hoặc dấu xuống dòng.

Dữ liệu ra: Ghi ra file văn bản DIV.OUT số 1 nếu dãy đã cho chia hết cho K và số 0 nếu ngược lại.

Ví dụ:

DIV.INP DIV.OUT DIV.INP DIV.OUT

4 6 0 4 7 1

1 2 3 5 1 2 3 5

(Đề ra của bạn Trần Đình Trung – Lớp 11A Tin – Khối PTCT – ĐH Vinh)

Bài 93/2002 – Trò chơi bắn bi

(Dành cho học sinh Tiểu học)

Cho bảng bắn bi sau:

Bạn có thể bắn bi vào từ một trong số các đỉnh ở ngoài cùng. Khi được bắn vào trong, hòn bi chỉ có thể tiếp tục đi vào trong ở đỉnh gần đó nhất hoặc lăn theo nhiều nhất là một cạnh để đi vào ở đỉnh kề đó. Biết rằng khi đến hình chữ nhật trong cùng, hòn bi không đợc lăn trên một cạnh nào mà phải đi thẳng vào tâm.

Hãy tìm đường đi sao cho tổng số điểm mà nó đi qua là lớn nhất và có bao nhiêu đường đi để có được số điểm đó.

Bài 94/2002 – Biểu diễn tổng các số Fibonaci

(Dành cho học sinh THCS)

Cho số tự nhiên N và dãy số Fibonaci: 1, 1, 2, 3, 5, 8, ….

Bạn hãy viết chơng trình kiểm tra xem N có thể biểu diễn thành tổng của của các số Fibonaci khác nhau hay không?

Bài 95/2002 – Dãy con có tổng lớn nhất

(Dành cho học sinh THPT)

Cho dãy gồm n số nguyên a1, a2, …, an. Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.

Dữ liệu: Vào từ file văn bản SUBSEQ.INP

Dòng đầu tiền chứa số nguyên dơng n (n < 106).
Dòng thứ i trong số n dòng tiếp theo chứa số ai (|ai|  1000).

Kết quả: Ghi ra file văn bản SUBSEQ.OUT

Dòng đầu tiên ghi vị trí của phần tử đầu tiên của dãy con tìm được.
Dòng thứ hai ghi vị trí của phần tử cuối cùng của dãy con tìm được
Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.

Ví dụ:

SUBSEQ.INP	SUBSEQ.OUT
8 12 -14 1 23 -6 22 -34 13	3 6 40

Bài 96/2002 – Số chung lớn nhất

(Dành cho học sinh THPT)

Cho 2 xâu:

X = x1x2..xM. (Với xi là các kí tự số từ ‘0’ đến ‘9’)

Y = y1y2..yN.( Với yi là các kí tự số từ ‘0’ đến ‘9’)

(M, N <= 250)

Ta gọi: Z = z1z2..zk là xâu chung của 2 xâu X, Y nếu xâu Z nhận đợc từ xâu X bằng cách xoá đi một số kí tự và cũng nhận được từ xâu Y bằng cách xoá đi một số kí tự.

Yêu cầu: Tìm một xâu chung của 2 xâu X, Y sao cho xâu nhận được tạo thành một số lớn nhất có thể được.

Dữ liệu vào file: String.inp

Gồm 2 dòng, dòng 1 là xâu X, dòng 2 là xâu Y.

Kết quả ra file: String.out

Gồm 1 dòng duy nhất là số lớn nhất có thể nhận được.

Ví dụ:

String.inp	String.out
19012304 034012	34

Bài 97/2002 – Thay số trong bảng

(Dành cho học sinh Tiểu học)

Bảng dưới gồm 9 ô, ban đầu được điền bởi các chữ cái. Bạn hãy thay các chữ cái bởi các chữ số từ 0 đến 8 vào ô sao cho tất cả các số theo hàng ngang, hàng dọc đều là số có 3 chữ số (chữ số hàng trăm phải khác 0) và thoả mãn:

1 2 3

a	b	c
d	e	f
g	h	i

Ngang

4 – Bội số nguyên của 8;

5 – Tích của các số tự nhiên liên tiếp đầu tiên;

6 – Tích các số nguyên tố kề nhau

Dọc

1 – Bội nguyên của 11;

2 – Tích của nhiều thừa số 2;

3 – Bội số nguyên của 11.

(Đề ra của bạn Đào Tuấn Anh – Lớp 10A Trường THPT Năng Khiếu Ngô Sĩ Liên – thị xã Bắc Giang)

Bài 98/2002 – Số phản nguyên tố

(Dành cho học sinh THCS và THPT)

Một số n gọi là số phản nguyên tố nếu số ước số của nó là nhiều nhất trong n số tự nhiên đầu tiên. Cho số K (K <= 2 tỷ). Hãy ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.

Dữ liệu vào trong file PNT.INP nội dung gồm:

– Dòng đầu tiên là số M (1 < M <= 100) – số các số cần tìm số phản nguyên tố lớn nhất của nó;

– M dòng tiếp theo lần lượt là các số K1, K2, K3, …, KM;

Dữ liệu ra trong file PNT.OUT gồm M dòng: dòng thứ i là số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng Ki.

Ví dụ:

PNT.INP

1000

PNT.OUT

840

(Tác giả: Master – gửi bài qua Website của Tin học & Nhà trường)

Bài 99/2002 – Bài toán chúc Tết

(Dành cho học sinh THPT)

Một người quyết định dành một ngày Tết để đến chúc Tết các bạn của mình. Để chắc chắn, hôm trước anh ta đã điện thoại đến từng người để hỏi khoảng thời gian mà người đó có thể tiếp mình. Giả sử có N người được hỏi (đánh số từ 1 đến N), người thứ i cho biết thời gian có thể tiếp trong ngày là từ Ai đến Bi (i = 1, 2, …, N). Giả thiết rằng, khoảng thời gian cần thiết cho mỗi cuộc gặp là H và khoảng thời gian chuẩn bị từ một cuộc gặp đến một cuộc gặp kế tiếp là T. Bạn hãy xây dựng giúp một lịch chúc Tết để anh ta có thể chúc Tết được nhiều người nhất.

File dữ liệu vào trong file CHUCTET.INP gồm dòng đầu ghi số N, dòng thứ i trong số N dòng tiếp theo ghi khoảng thời gian có thể tiếp khách của người i gồm 2 số thực Ai và Bi (cách nhau ít nhất một dấu trắng). Dòng tiếp theo ghi giá trị H (số thực) và dòng cuối cùng ghi giá trị T (số thực). Giả thiết rằng các giá trị thời gian đều được viết dưới dạng thập phân theo đơn vị giờ, tính đến 1 số lẻ (thí dụ 10.5 có nghĩa là mời giờ rỡi) và đều nằm trong khoảng từ 8 đến 21 (từ 8 giờ sáng đến 9 giờ tối). Số khách tối đa không quá 30.

Kết quả ghi ra file CHUCTET.OUT gồm dòng đầu ghi K là số người được thăm, K dòng tiếp theo ghi trình tự đi thăm, mỗi dòng gồm 2 số (ghi cách nhau ít nhất một dấu trắng): số đầu là số hiệu người được thăm, số tiếp theo là thời điểm gặp tương ứng.

Thí dụ:

CHUCTET.INP

10.5 12.6

15.5 16.6

14.0 14.1

17.5 21.0

15.0 16.1

10.5 10.6

19.0 21.0

10.5 13.6

12.5 12.6

11.5 13.6

12.5 15.6

16.0 18.1

13.5 14.6

12.5 17.6

13.0 13.1

18.5 21.0

9.0 13.1

10.5 11.6

10.5 12.6

18.0 21.0

0.5

0.1

CHUCTET.OUT

17 9.0

1 10.5

18 11.1

19 11.7

8 12.3

10 12.9

11 13.5

13 14.1

5 15.0

2 15.6

12 16.2

14 16.8

4 17.5

7 19.0

16 19.6

20 20.2

(Đề ra của bạn Đinh Quang Huy – ĐHKHTN – ĐHQG Hà Nội )

Bài 100/2002 – Mời khách dự tiệc

(Dành cho học sinh THPT)

Công ty trách nhiệm hữu hạn “Vui vẻ” có n cán bộ đánh số từ 1 đến n. Cán bộ i có đánh giá độ vui tính là vi (i = 1, 2, …, n). Ngoại trừ Giám đốc Công ty, mỗi cán bộ có 1 thủ trưởng trực tiếp của mình.

Bạn chỉ cần giúp Công ty mời một nhóm cán bộ đến dự dạ tiệc “Vui vẻ” sao cho trong số những người được mời không đồng thời có mặt nhân viên và thủ trưởng trực tiếp và đồng thời tổng đánh giá độ vui tính của những người dự tiệc là lớn nhất.

Giả thiết rằng mỗi một thủ trưởng có không quá 20 cán bộ trực tiếp dưới quyền.

Dữ liệu: Vào từ file văn bản GUEST.INP

Dòng đầu tiên ghi số cán bộ của Công ty: n (1 < n < 1001);
Dòng thứ i trong số n dòng tiếp theo ghi hai số nguyên dương ti, vi; trong đó ti là số hiệu của thủ trưởng trực tiếp và vi là độ vui tính của cán bộ i (i = 1, 2, …, n). Quy ước ti = 0 nếu i là số hiệu của Giám đốc Công ty.

Kết quả: Ghi ra file văn bản GUEST.OUT

Dòng đầu tiên ghi hai số m, v; trong đó m là tổng số cán bộ được mời còn v là tổng độ vui tính của các cán bộ được mời dự tiệc;
Dòng thứ i trong số m dòng tiếp theo ghi số hiệu của cán bộ được mời thứ i (i = 1, 2, …, m).

Ví dụ:

GUEST.INP

GUEST.OUT

0 3

1 6

2 4

2 7

GUEST.INP

GUEST.OUT

0 1

1 1

1 12

2 50

2 1

3 1

3 63

(Đề ra của bạn Lưu Văn Minh)

Phần 2: LỜI GIẢI 100 đề Toán Tin (Tin học & Nhà trường)

Lời giải cho các bài toán, mời bạn đọc xem trong file: [PDF]100DeToanTin_o2.edu.vn

24/09/2021

Python: Bài toán xếp hậu sử dụng đệ quy
Python: Bài toán xếp hậu sử dụng đệ quy

Bài toán xếp hậu là một bài toán kinh điển thường được giới thiệu trong các cuốn sách về thuật toán. Ở đây, chúng ta sẽ giải quyết bài toán bằng các sử dụng giải thuật đệ quy và thuật toán quay lui (vét cạn).

Xem thêm: Thuật toán giải sudoku bằng quay lui backtracking

Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột hoặc cùng đường chéo. Hãy tìm các xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào.

Ví dụ một cách xếp với n = 8

1. Giải bài toán xếp hậu sử dụng đệ quy

Để giải quyết bài toán xếp 8 quân hậu này, chúng ta sử dụng list (mảng) a có kích thước bằng 8 với quy ước a[i]=j để đánh dấu vị trí xếp quân hậu thuộc dòng i ở cột thứ j.

1.1. Tạo danh sách để lưu vị trí các quân hậu

Để khởi tạo mảng a, chúng ta dùng lệnh
```
n = 8
a = n*[0]
```
Lưu ý rằng các list danh sách trong Python được đánh chỉ số từ 0, do đó vị trí của quân hậu ở dòng thứ nhất được lưu ở a[0]

Ví dụ a=[0, 4, 7, 5, 2, 6, 1, 3]có ý nghĩa, quân hậu ở dòng thứ nhất sẽ ở cột thứ nhất, quân hậu ở dòng thứ hai sẽ ở cột thứ 5, quân hậu ở dòng thứ 3 sẽ ở cột thứ 8…

1.2. Viết hàm in vị trí các quân hậu dạng ma trận

Chúng ta sẽ viết một hàm print_board() để in ra màn hình vị trí các quân hậu dạng ma trận (bảng), ví dụ với mảng a ở trên, in ra màn hình được:
```
1 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 1 0 0 0 0 0 0 
0 0 0 1 0 0 0 0
```
Hàm in vị trí các quân hậu như sau:
```
def print_board(b):
   l = len(b)
   for i in range(l):
      for j in range(l):
         if j == a[i]:
            print(1, end = " ")
         else:
            print(0, end = " ")
      print()
```
1.3. Viết hàm kiểm tra vị trí (d,c) có còn đặt được quân hậu mới không?

Chúng ta quy ước d vàc là vị trí của dòng và cột đang xét để xem có khả năng đặt được quân hậu mới hay không.

Rõ ràng, ta chỉ cần kiểm tra xem trong các dòng từ 0 tới d-1 đã có quân hậu nào mà có thể ăn được quân hậu nếu đặt ở ô đang xét hay không, do đó chỉ cần duyệt từ các dòng có chỉ số thuộc range(d).

Chúng ta viết hàm possible(d,c) để kiểm tra vị trí d,c còn có khả năng đặt hậu hay không. Khi đó, kết quả trả về là False nếu một trong 3 khả năng sau xảy ra:
- Tại cột c đã có quân hậu ở dòng i nào đó, điều kiện là a[i] == c
- Tại 2 đường chéo đi qua điểm (d,c) đã có một quân hậu nào đó.
Lưu ý rằng các đường chéo sẽ song song hoặc trùng với các tia phân giác của góc phần tư trong hệ tọa độ Oxy. Các tia phân giác có phương trình là y = x hoặc y = - x. Do đó phương trình các đường chéo đi qua điểm có tọa độ (d,c) sẽ là c - d =y -x hoặc c + d = y + x. Từ đó suy ra điều kiện:
```
a[i] == c  or c - d == a[i] - i or c + d == a[i] + i
```
Mã nguồn của hàm kiểm tra vị trí có thể đặt hậu như sau:
```
def possible(x, y):
   for i in range(x):      
      if a[i] == y  or y - x == a[i] - i or y + x == a[i] + i:
         return False
   return True
```
1.4. Hàm đệ quy để sinh ra các vị trí đặt quân hậu
```
def gen(i, n):
   for j in range(n):
      if possible(i,j):
         a[i] = j
         if i == n - 1:
            print(a)
         gen(i+1, n)
```
Chương trình bắt đầu với lời gọi gen(0, n).

Mã nguồn hoàn chỉnh bằng Python của bài toán xếp hậu như sau:
```
n = 8
a = n*[0]

def print_board(b):
   l = len(b)
   for i in range(l):
      for j in range(l):
         if j == a[i]:
            print(1, end = " ")
         else:
            print(0, end = " ")
      print()

def possible(d, c):
   for i in range(d):
      # if a[i] == y or abs(i - x) == abs(a[i] - y):
      if a[i] == c  or c - d == a[i] - i or c + d == a[i] + i:
         return False
   return True

def gen(i, n):
   for j in range(n):
      if possible(i,j):
         a[i] = j
         if i == n - 1:
            print(a)
         gen(i+1, n)

gen(0, n)
```
Kết quả trả về là tất cả các phương án mỗi phương án là một danh sách chứa vị trí các quân hậu. Nếu muốn in một phương án nào đó, chúng ta sử dụng hàm print_board()

2. Bài toán xếp hậu quay lui

Chúng tôi giới thiệu thêm bài toán xếp hậu sử dụng thuật toán quay lui để bạn đọc tham khảo. Cách làm này có thời gian chạy khá chậm, và mỗi lần chỉ in ra một phương án xếp các quân hậu. Muốn tìm được phương án khác, chúng ta cần thay đổi giá trị của mảng board ban đầu.

Cách giải này tôi có tham khảo từ bài viết này.
```
board = [
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0]
      ]


def print_board(bo):
    for d in bo:        
        for c in d:
            print(c, end = " ")
        print()


def solve(bo):
   l = len(bo)
   for d in range(l):
      for c in range(l):
         if bo[d][c] == 0:
            if possible(bo, d, c):
               bo[d][c] = 1
               solve(bo)
            if sum(sum(a) for a in bo) == l:
               return bo
            else:
               bo[d][c] = 0
   return bo		


def possible(bo, d, c):
   l = len(bo)
   for i in range(l):
      if bo[i][c] == 1:
         return False
   for i in range(l):
      if bo[d][i] == 1:
         return False
   for i in range(l):
      for j in range(l):
         if bo[i][j] == 1:
            if c-d == j-i or c+d == i+j:
               return False
   return True

solve(board)
print_board(board)
```
19/01/2021
Thuật toán giải sudoku bằng quay lui backtracking
Thuật toán giải sudoku bằng quay lui backtracking

Trong bài này chúng ta sẽ sử dụng thuật toán quay lui để giải quyết bài toán giải Sudoku. Để hiểu thuật toán quay lui là gì mời bạn xem bài Thuật toán quay lui và minh họa.

Xem thêm: Python: Bài toán xếp hậu sử dụng đệ quy

Bài viết tham khảo từ techwithtim.net

1. Giới thiệu luật chơi và cách giải Sudoku

Sudoku là một trò chơi giải đố theo wiki định nghĩa như sau:

Sudoku (数独すうどく (số độc) sūdoku?) (suːˈdoʊkuː/, /-ˈdɒ-/, /sə-/, ban đầu có tên gọi là Number Place) là một trò chơi câu đố sắp xếp chữ số dựa trên logic theo tổ hợp. Mục tiêu của trò chơi là điền các chữ số vào một lưới 9×9 sao cho mỗi cột, mỗi hàng, và mỗi phần trong số chín lưới con 3×3 cấu tạo nên lưới chính (cũng gọi là “hộp”, “khối”, hoặc “vùng”) đều chứa tất cả các chữ số từ 1 tới 9. Câu đố đã được hoàn thành một phần, người chơi phải giải tiếp bằng việc điền số. Mỗi câu đố được thiết lập tốt có một cách làm duy nhất.

Cách giải trò chơi Sudoku, mời các bạn xem video hướng dẫn sau:

2. Thuật toán giải Sudoku

Sau đây ta sẽ tìm thuật toán giải Sudoku bằng kỹ thuật backtracking, ngôn ngữ lập trình sử dụng là Python. Các bước tiến hành như sau:
- Viết hàm in câu đố Sudoku ra màn hình.
- Tìm vị trí các ô trống trong Sudoku.
- Với mỗi vị trí ô trống vừa tìm được, lần lượt thử đặt số từ 1 đến 9 vào ô trống đó. Kiểm tra xem sau khi thử đặt số đó vào ô trống đó thì có hợp lệ (thỏa mãn các điều kiện về luật chơi của Sudoku hay không). Nếu hợp lệ thì tiếp tục tìm các ô trống tiếp theo và lại thử, nếu không thì thử với số_tiếp_theo
- Lặp lại quy trình trên cho đến khi không còn ô trống nào trên câu đố, hoặc không tìm được lời giải.
Input, một câu đố sudoku biểu diễn bởi danh sách list 2 chiều (một danh sách gồm 9 phần tử, mỗi phần tử là dòng – lại là một danh sách gồm 9 phần tử tương ứng với 9 ô trong một dòng) với các ô trống được quy ước điền bởi số 0, ví dụ Sudoku cau_do được biểu diễn như sau:
```
cau_do = [
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]
```
Chú ý rằng chỉ số index trong Python được đánh từ 0 trở đi, do đó các vị trí của từng ô trong bảng số sẽ là cau_d0[0][0] cho đến cau_do[8][8], ở đây cau_do[d][c] là ô số ở vị trí dòng d và cột c.

2.1. Viết hàm in câu đố Sudoku ra màn hình

Ở đây chúng ta sử dụng giao diện dòng lệnh, chưa sử dụng giao diện đồ họa GUI nên sẽ sử dụng hàm print() của Python để in một đối tượng ra màn hình CMD.

Ta sẽ viết hàm in_sudoku để in một câu đố Sudoku có tên là q ra màn hình, sử dụng biến d và c để biểu diễn dòng và cột.

Nếu dòng d là dòng thứ 3 hoặc 6 thì ta sẽ in ra màn hình một dòng gồm các kí tự - - - - - - - - - - - để ngăn cách, mục đích là biểu diễn cho các khối ô vuông 3x3 của Sudoku. Tương tự, nếu cột ở vị trí 3 hoặc 6 thì ta sẽ in ra kí tự | để ngăn cách. Nếu cột ở vị trí thứ 8 thì ta sẽ xuống dòng mới.
```
def in_sudoku(q):
    for d in range(len(q)):
        if d % 3 == 0 and d != 0:
            print("- - - - - - - - - - -")
        for c in range(len(q[0])):
            if c % 3 == 0 and c != 0:
                print("| ", end ="")
            if c == 8:
                print(str(q[d][c]))
            else:
                print(str(q[d][c]) + " ", end = "")
```
Thử in với cau_do ở phần đầu, chúng ta được kết quả như sau, ở đây tôi dùng SublimeText để code:

2.2. Viết hàm tìm các ô trống trong Sudoku

Mục tiêu của chúng ta là tìm các vị trí ô trống trong câu đố q
```
def tim_o_trong(q):
    for d in range(len(q)):
        for c in range(len(q[0])):
            if q[d][c] == 0:
                return d, c
    return None
```
2.3. Viết hàm kiểm tra tính hợp lệ của một câu đố
```
def kiem_tra(q, gia_tri, dong, cot):
    for i in range(len(q[0])):
        if q[i][cot] == gia_tri and i != dong:
            return False
    for i in range(len(q)):
        if q[dong][i] == gia_tri and i != cot:
            return False

    x = cot // 3
    y = dong // 3

    for i in range(y*3, y*3+3):
        for j in range(x*3, x*3+3):
            if q[i][j] == gia_tri and i != dong and j != cot:
                return False
    return True
```
2.4. Viết hàm chính để tìm lời giải cho một câu đố Sudoku
```
def giai(q):
    tim_thay = tim_o_trong(q)
    if not tim_thay:
        return True
    else:
        d, c = tim_thay
    for i in range(1,10):
        if kiem_tra(q, i, d, c):
            q[d][c] = i
            if giai(q):
                return True
            else:
                q[d][c] = 0
        
    return False
```
3. Chương trình Python giải Sudoku hoàn chỉnh
```
cau_do = [
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]

def in_sudoku(q):
    for d in range(len(q)):
        if d % 3 == 0 and d != 0:
            print("- - - - - - - - - - -")
        for c in range(len(q[0])):
            if c % 3 == 0 and c != 0:
                print("| ", end ="")
            if c == 8:
                print(str(q[d][c]))
            else:
                print(str(q[d][c]) + " ", end = "")


def giai(q):
    tim_thay = tim_o_trong(q)
    if not tim_thay:
        return True
    else:
        d, c = tim_thay
    for i in range(1,10):
        if kiem_tra(q, i, d, c):
            q[d][c] = i
            if giai(q):
                return True
            else:
                q[d][c] = 0
        
    return False
        
    

def tim_o_trong(q):
    for d in range(len(q)):
        for c in range(len(q[0])):
            if q[d][c] == 0:
                return d, c
    return None


def kiem_tra(q, gia_tri, dong, cot):
    for i in range(len(q[0])):
        if q[i][cot] == gia_tri and i != dong:
            return False
    for i in range(len(q)):
        if q[dong][i] == gia_tri and i != cot:
            return False

    x = cot // 3
    y = dong // 3

    for i in range(y*3, y*3+3):
        for j in range(x*3, x*3+3):
            if q[i][j] == gia_tri and i != dong and j != cot:
                return False
    return True

in_sudoku(cau_do)
giai(cau_do)
print('Loi giai cua Sudoku tren la:')
in_sudoku(cau_do)
```
Cho chạy chương trình, chúng ta được kết quả như hình sau:
18/01/2021
Thuật toán quay lui và minh họa
Thuật toán quay lui và minh họa

1. Thuật toán quay lui là gì?

Thuật toán quay lui (Backtracking) là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. H. Lehmer vào những năm 1950.

2. Thuật toán quay lui sử dụng khi nào?

Thuật toán quay lui thường được sử dụng để giải bài toán liệt kê các cấu hình (như bài toán sinh các xâu nhị phân). Mỗi cấu hình được xây dựng bằng cách xác định từng phần tử. Mỗi phần tử lại được chọn bằng cách thử tất cả các khả năng.

Các bước trong việc liệt kê cấu hình dạng X[1…n]:
- Xét tất cả các giá trị X[1] có thể nhận, thử X[1] nhận các giá trị đó. Với mỗi giá trị của X[1] ta sẽ:
- Xét tất cả giá trị X[2] có thể nhận, lại thử X[2] cho các giá trị đó. Với mỗi giá trị X[2] lại xét khả năng giá trị của X[3]…tiếp tục như vậy cho tới bước:
- …
- Xét tất cả giá trị X[n] có thể nhận, thử cho X[n] nhận lần lượt giá trị đó.
- Thông báo cấu hình tìm được.
Để cài đặt thuật toán quay lui, chúng ta sử dụng một chương trình con (hàm function, thủ tục procedure) và gọi đến hàm đó trong chương trình chính của mình. Mô hình của thuật toán quay lui sử dụng ngôn ngữ Python như sau:
```
def quay_lui(i):
   for j in [tập_các_phương_án_x[i] có thể nhận]:
      <thử đặt x[i] = j>
      if <x[i] là phần tử cuối cùng trong cấu hình>:
         <thông báo cấu hình>
      else:
         <ghi nhận việc cho x[i] nhận giá trị j nếu cần>
         <gọi đệ quy đến quay_lui(i+1)>
         <bỏ ghi nhận việc cho x[i] nhận giá trị j để thử giá trị khác nếu cần>
```
Thuật toán quay lui sẽ bắt đầu bằng lời gọi quay_lui(1)

3. Minh họa của thuật toán quay lui (Backtracking)

3.1. Sử dụng thuật toán quay lui để sinh các dãy nhị phân độ dài n

Dưới đây, chúng ta cùng xem mã chương trình sinh các dãy nhị phân có độ dài n bằng cách sử dụng thuật toán quay lui.
```
n = 3
x = n*[0]


def fine_print(x):
   tmp = ''
   for i in x:
      tmp += str(i)
   return tmp


def bin_gen(i):
   for j in range(0,3):
      x[i] = j
      if i == n-1:
         print(fine_print(x))
      else:
         bin_gen(i+1)

bin_gen(0)
```
Các giải khác bằng cách sử dụng vòng lặp, xin mời bạn đọc xem tại đây Thuật toán sinh các dãy nhị phân có độ dài n

3.2. Sử dụng backtracking để giải Sudoku

Mời các bạn xem chi tiết trong bài Thuật toán giải sudoku bằng quay lui backtracking

3.3. Sử dụng quay lui để giải bài toán xếp hậu

Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột hoặc cùng đường chéo. Hãy tìm các xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào. Mời bạn xem chi tiết trong bài Python: Bài toán xếp hậu sử dụng đệ quy

4. Đặc điểm của thuật toán quay lui
Bản chất của quay lui là một quá trình tìm kiếm theo chiều sâu(Depth-First Search).
- Ưu điểm: Việc quay lui là thử tất cả các tổ hợp để tìm được một lời giải. Thế mạnh của phương pháp này là nhiều cài đặt tránh được việc phải thử nhiều trường hợp chưa hoàn chỉnh, nhờ đó giảm thời gian chạy.
- Nhược điểm: Trong trường hợp xấu nhất độ phức tạp của quay lui vẫn là cấp số mũ. Vì nó mắc phải các nhược điểm sau:
- Rơi vào tình trạng “thrashing”: quá trình tìm kiếm cứ gặp phải bế tắc với cùng một nguyên nhân.
  
  Thực hiện các công việc dư thừa: Mỗi lần chúng ta quay lui, chúng ta cần phải đánh giá lại lời giải trong khi đôi lúc điều đó không cần thiết.
  
  Không sớm phát hiện được các khả năng bị bế tắc trong tương lai. Quay lui chuẩn, không có cơ chế nhìn về tương lai để nhận biết được nhánh tìm kiếm sẽ đi vào bế tắc.
18/01/2021
Thuật toán sinh các dãy nhị phân có độ dài n
Thuật toán sinh các dãy nhị phân có độ dài n

Trong bài viết này chúng ta sẽ tìm cách liệt kê toàn bộ các dãy nhị phân có độ dài n cho trước.
- Yêu cầu: Liệt kê tất cả các dãy nhị phân có độ dài n. (dãy nhị phân là dãy chỉ gồm hai số 0 và 1)
- Input: Nhập vào n – độ dài của chuỗi nhị phân cần in ra.
- Output : In ra màn hình tất cả các chuỗi nhị phân có độ dài n nhập từ đầu vào.
Ví dụ:
- Input: 3
- Output:
- ```
000   001   010   011   100   101   110   111
```
1. Liệt kê các dãy nhị phân độ dài n bằng phương pháp sinh tuần tự

Phương pháp sinh tuần tự sử dụng để liệt kê tất cả các phương án [cấu hình] của bài toán tổ hợp, sao cho các bài toán đó thỏa mãn:
- Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể biết đượccấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đó.
- Xây dựng được thuật toán từ một cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp nó.
Theo đó, thuật toán sinh tuần tự các cấu hình được mô tả như sau:
```
<Xây dựng cấu hình đầu tiên>
while True:
   <Đưa ra cấu hình đang có>
   <Từ cấu hình đang có sinh ra cấu hình kế tiếp nếu còn>
   if <hết cấu hình>:
      break
```
Lưu ý rằng, Python không có câu lệnh điều khiển luồn repeat... until như một số ngôn ngữ khác, nên ta phải sử dụng vòng lặp while (Xem chi tiết trong bài Bài 7. Câu lệnh vòng lặp while trong Python)

Vì kiểu xâu string là immutable nên chúng ta sẽ sử dụng kiểu danh sách list để thao tác trên đó, và định nghĩa hàm fine_print() để in toàn bộ các phần tử của danh sách dưới dạng xâu kí tự.

Một lưu ý là các chỉ số index trong Python luôn được đánh số từ 0, do đó phần tử thứ nhất của một danh sách list x sẽ có chỉ số là 0, tức là phần tử x[0]
```
n = 3
s = n*[0]

def fill_char(s,i):
   for j in range(i,n):
      s[j] = 0
def fine_print(x):
   tmp = ''
   for i in x:
      tmp += str(i)
   return tmp


while True:
   print(fine_print(s))
   i = n - 1
   while (i > -1) and s[i] == 1:
      i = i - 1
   s[i] = 1
   fill_char(s,i+1)
   if i == -1:
      break
```
Kết quả thu được như sau:
```
000
001
010
011
100
101
110
111
```
2. Sinh các dãy nhị phân độ dài n bằng thuật toán quay lui (Backtracking)

Vẫn sử dụng kiểu danh sách list và hàm fine_print() như ở phần trên, chúng ta có chương trình liệt kê tất cả các xâu nhị phân có độ dài n sử dụng thuật toán quay lui như sau:
```
n = 3
x = n*[0]


def fine_print(x):
   tmp = ''
   for i in x:
      tmp += str(i)
   return tmp

   
def bin_gen(i):
   for j in range(0,2):
      x[i] = j
      if i == n-1:
         print(fine_print(x))
      else:
         bin_gen(i+1)

bin_gen(0)
```
Thuật toán quay lui có ưu điểm là rất dễ cài đặt so với phương pháp sinh tuần tự, hơn nữa có thể dễ dàng mở rộng để giải quyết nhiều bài toán khác nhau. Chẳng hạn, ta dễ dàng giải quyết bài toán sinh các dãy tam phân bằng cách thay range(0,2) bởi range(0,3). Kết quả thu được như sau:
```
000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122
200
201
202
210
211
212
220
221
222
```
12/01/2021

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	Z

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	Z

Category: Thuật toán

Sàng số nguyên tố (Sàng Eratosthenes)

Sàng Eratosthenes là gì?

Thuật toán sàng số nguyên tố

Thuật toán kiểm tra Số Nguyên Tố

1. Số nguyên tố là gì?

2. Các Thuật toán kiểm tra Số Nguyên Tố Đơn Giản

Lặp từng phần tử với bước nhảy 1 đến n-1

Lặp từng phần tử với bước nhảy 2

Lặp từng phần tử đến $\sqrt{n}$

3. Tối ưu thuật toán kiểm tra số nguyên tố

4. Các Thuật toán kiểm tra Số Nguyên Tố Nâng Cao

Kiểm tra theo xác suất

Cấu trúc cơ bản của một phép kiểm tra ngẫu nhiên là:

Các hệ thức thường sử dụng

Các phép kiểm tra tất định

Thuật toán tìm UCLN của hai số nguyên dương

UCLN (ước chung lớn nhất) của 2 số là gì?

Thuật toán tìm UCLN của hai số nguyên dương

Tìm UCLN của hai số nguyên bằng phép chia

Tìm UCLN của hai số nguyên bằng phép trừ

50 bài tập lập trình Dart cơ bản

1. Bài tập lập trình Dart, C, Java cơ bản sử dụng if for while

2. Bài tập lập trình Dart, C, Java cơ bản sử dụng hàm

100 đề Toán Tin (Tin học & Nhà trường)

Phần 1: ĐỀ BÀI 100 đề Toán Tin (Tin học & Nhà trường)

Bài 1/1999 – Trò chơi cùng nhau qua cầu

Bài 2/1999 – Tổ chức tham quan

Bài 3/1999 – Mạng tế bào

Bài 4/1999 – Trò chơi bốc sỏi

Bài 5/1999 – 12 viên bi

Bài 6/1999 – Giao điểm các đường thẳng

Bài 7/1999 – Miền mặt phẳng chia bởi các đường thẳng

Bài 8/1999 – Cân táo

Bài 9/1999 – Bốc diêm

Bài 10/1999 – Dãy số nguyên

Bài 11/1999 – Dãy số Fibonaci

Bài 12/1999 – N-mino

Bài 13/1999 – Phân hoạch hình chữ nhật

Bài 14/2000 – Tìm số trang sách của một quyển sách

Bài 15/2000 – Hội nghị đội viên

Bài 16/2000 – Chia số

Bài 17/2000 – Số nguyên tố tương đương

Bài 18/2000 – Sên bò

Bài 19/2000 – Đa giác

Bài 20/2000 – Bạn Lan ở căn hộ số mấy?

Bài 21/2000 – Những trang sách bị rơi

Bài 22/2000 – Đếm đường đi

Bài 23/2000 – Quay Rubic

Bài 24/2000 – Sắp xếp dãy số

Bài 25/2000 – Xây dựng số

Bài 26/2000 – Tô màu

Bài 27/2000 – Bàn cờ

Bài 28/2000 – Đổi tiền

Bài 29/2000 – Chọn bạn

Bài 30/2000 – Phần tử yên ngựa

Bài 31/2000 – Biểu diễn phân số

Bài 32/2000 – Bài toán 8 hậu

Bài 33/2000 – Mã hoá văn bản

Bài 34/2000 – Mã hoá và giải mã

Bài 35/2000 – Các phân số được sắp xếp

Bài 36/2000 – Anh chàng hà tiện

Bài 37/2000 – Số siêu nguyên tố

Bài 38/2000 – Tam giác số

Bài 39/2000 – Ô chữ

Bài 40/2000 – Máy định vị Radio

Bài 41/2000 – Cờ Othello

Bài 42/2000 – Một chút về tư duy số học

Bài 43/2000 – Kim giờ và phút gặp nhau bao nhiêu lần trong ngày

Bài 44/2000 – Tạo ma trận số

Bài 45/2000 – Các vòng tròn Olimpic

Bài 46/2000 – Đảo chữ cái

Bài 47/2000 – Xoá số trên vòng tròn

Bài 48/2000 – Những chiếc gậy

Bài 49/2001 – Một chút nhanh trí

Bài 50/2001 – Bài toán đổi màu bi

Bài 51/2001 – Thay thế từ

Bài 52/2001 – Xác định các tứ giác đồng hồ trong ma trận

Bài 53/2001 – Lập lịch tháng kỳ ảo

Bài 54/2001 – Bạn hãy gạch số

Bài 56/2001 – Chia lưới

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
a	b	c	d	e	f	g	h	i	j	k	l	m	n	o	p	q	r	s	t	u	v	w	x	y	Z