//
you're reading...
Bài tập huấn luyện, Dùng cho thi học sinh giỏi

Đề tham khảo 1 – 100

1. Điểm và tam giác

Cho tam giác có 3 đỉnh với tọa độ (x1, y1), (x2, y2), (x3, y3). Lập thuật toán cho biết điểm
(x, y) nằm trong hay ngoài tam giác.

2. Ba hình hộp

Cho 3 hình hộp với các cạnh (là số nguyên) a1>=b1>=c1, a2>=b2>=c2, a3>=b3>=c3.

Lập thuật toán cho biết 3 hình hộp trên có thể lập thành một hình lập phương được không.

3. Số hạnh phúc

Lập chương trình tính số vé hạnh phúc gồm 2n chữ số (các số vé ghi trong hệ cơ số 10), với
định nghĩa vé hạnh phúc là vé có tổng n số đầu bằng tổng n số cuối.

4. Tính 100!

Lập chương trình tính 100!

5. Tính 750

Lập chương trình tính 750.

6. Bài toán “Tháp Hà nội”

Cho 3 cọc và n đĩa (lồng vào cọc) đặt ở cọc số 1 và theo thứ tự to dưới nhỏ trên (xem hình vẽ). Hãy chuyển n đĩa đó sang cọc số 3 sao cho thứ tự vẫn được bảo toàn. Được sử dụng cọc số 2 làm trung gian và thỏa mãn yêu cầu khi chuyển thì chỉ cho phép đĩa bé đặt trên đĩa to. Mỗi lần được chuyển một đĩa. Hãy lập chương trình mô tả quá trình chuyển đổi đó.

7. Bài toán “8 Hậu”

Hãy lập chương trình xếp 8 con hậu lên bàn cờ quốc tế sao cho không có hai con hậu nào ở tình
trạng đe dọa lẫn nhau.

8. Bài toán “Mã đi”

Hãy lập chương trình di chuyển con mã trên bàn cờ n x n, xuất phát từ một vị trí nào đó sao cho nó di qua mỗi ô đúng một lần và quay về ô xuất phát.

9. Tìm “giao  điểm” của các hình chữ nhật

Trên mặt phẳng tọa độ cho n hình chữ nhật có các cạnh song song với các trục tọa độ. Hãy xây
dựng thuật toán để tìm số lớn nhất k thỏa mãn điều kiện: Tồn tại một điểm trên mặt phẳng nằm trong k hình chữ nhật trên.

10. Dãy số gần nhau

Cặp 2 số a,b gọi là gần nhau nếu |a-b|<10. Dãy số a1, a2, …, an gọi là gần nhau nếu tồn tại một hoán vị của dãy trên b1, b2, …, bnsao cho các cặp số (b1, b2), (b2, b3),…, (bn-1, bn) là gần nhau.

Hãy tìm thuật toán cho phép biết được rằng một dãy số cho trước có phải là gần nhau hay không.

11. Đường đi ngắn nhất

Cho một lưới ô vuông kích thước m x n (xem hình vẽ). Lập thuật toán tính số các đường đi ngắn
nhất từ A đến B và chỉ đi trên các cạnh của lưới.

12. Danh sách lớp

Lập chương trình nhập từ bàn phím danh sách học sinh (vào cả Họ, Đệm và Tên)của một lớp
(<100 hs) và sau đó in ra theo thứ tự từ điển tên của các học sinh đó,nghĩa là xếp theo thứ tự A, B, C của tên trước, họ và đệm sau.

13. Cộng – Trừ – Nhân – Chia

Lập chương trình nhập từ bàn phím hai số tự nhiên m, n nhỏ hơn 1000000 và in ra kết quả số m x n, m+n, m/n, m-n.

14. Dãy điểm gần nhau

Cho n điểm trên mặt phẳng. Hai điểm (ax, ay), (bx, by) được gọi là gần nhau nếu max(|ax-bx|,|ay-by|) <10. Một dãy điểm được gọi là gần nhau nếu tồn tại một hoán vị của n điểm trên sao cho 2 điểm (bxi, byi) và (bxi+1, byi+1) là gần nhau với i=1, 2, …, n-1.

Hãy tìm thuật toán cho phép biết được rằng 1 dãy điểm cho trước có phải là gần nhau hay không?

15. 4 hình chữ nhật

Cho 4 hình chữ nhật với các cạnh (a1, b1), …, (a4, b4). Tìm thuật toán cho biết 4 hình này
có thể ghép lại thành một hình vuông hay không?

16. Hội bàn tròn

Có 2N người ngồi dự họp tại 1 bàn tròn. Biết rằng mỗi người trong số đó có không quá N-1 kẻ
thù. Tìm thuật toán sắp xếp 2N người này ngồi họp sao cho không có hai người nào là kẻ thù của nhau lại ngồi cạnh nhau.

17. Bài toán “Luật chơi Đôminô”

Giả sử đã có 1 quân đôminô trên mặt bàn. Trò chơi đôminô thực hiện như sau: Xếp một cách tuần
tự về 2 phía các quân bài (theo luật đôminô) cho đến khi không xếp được nữa. Lập thuật toán xác định được cách chơi sao cho khi đã xếp xong, số quân trên tay có số điểm bé nhất.

18. Về một phân hoạch của hình chữ nhật

Cho hình chữ nhật ABCD. Trên các cạnh AB, CD cho các phân hoạch N điểm. Trên BC, AD cho các phân hoạch M điểm. Nối lần lượt các điểm trên phân hoạch đối diện, theo thứ tự lần lượt. Biết rằng đường nối các phân hoạch trên AB, CD sẽ song song với AD. Ta thu được một phân hoạch Q của hình chữ nhật ABCD thành các hình tứ giác. Chỉ ra thuật toán tìm ra được hình tứ giác có diện tích lớn nhất.

19. Dãy số xoáy Spiral

Lập chương trình nhập dãy các số tự nhiên 1,2,3, …,N2 vào một mảng A[NxN] theo chiều xoáy
(spiral) như hình vẽ.

20. Đếm hình chữ nhật

Trên giấy kẻ ca rô kích thước 100 x 100 vẽ một số hình chữ nhật. Mỗi hình chữ nhật được tạo từ một số các ô vuông. Các hình chữ nhật khác nhau thì rời nhau (không kề cạnh và đỉnh). Cho mảng kích thước 100 x 100 với điều kiện: Aij= 1 nếu ô (i,j) nằm trong một hình chữ nhật nào đó và Aij= 0 nếu ngược lại. Hãy lập chương trình để tính số các hình chữ nhật có trên tờ giấy.

21. Bài toán “Mêcung”

Mêcung được cho bởi mảng A kích thước N x N, Aij = 0 nếu vị trí (i,j) là “tự do”, Aij = 1 nếu vị trí (i,j) là “đóng kín”. Từ vị trí ban đầu là một điểm tự do có thể dịch chuyển sang điểm “tự do” ở bên cạnh. Nếu ra được điểm bên ngoài thì ta nói là có thể thoát khỏi Mêcung. Lập thuật toán cho phép biết được rằng từ một điểm “tự do” có thể thoát khỏi Mê cung hay không.

Xem lời giải

22. Dãy sỏi 3 màu

Giả sử có dãy N hòn sỏi (N>3). Mỗi hòn sỏi có 1 trong 3 màu: Trắng, Xanh, đỏ. Viết thuật toán đổi chỗ N hòn sỏi sao cho các hòn màu trắng được xếp đầu tiên, sau đó đến các hòn màu xanh, cuối cùng đến màu đỏ.

23. Xâu nhị phân không lặp

Xâu nhị phân là xâu chỉ chứa các ký tự 0 và 1. Xâu nhị phân S được gọi là không lặp bậc k nếu mỗi xâu con độ dài k của nó đều khác nhau từng đôi một (nghĩa là không có 2 xâu con độ dài k nào giống hệt nhau). Xâu nhị phân không lặp bậc k được gọi là cực đại nếu việc bổ sung vào bên phải hay trái của nó một ký tự 0 hoặc 1 sẽ phá vỡ tính không lặp bậc k của nó. Xây dựng thuật toán tìm một xâu nhị phân cực đại không lặp bậc k có độ dài ngắn nhất (với k cho trước).

Xem lời giải

24. Tính giá trị một biểu thức

Cho các số tự
nhiên M, N (N>2) và mảng 3 chiều A(M,M,N-1). Tìm giá trị nhỏ nhất của tổng
sau đây: R = A(i1, i2, 1) + A(i2, i3,
2) + … + A(iN-1, iN, N-1)

ở đây giới hạn
được xét trên tập các dãy số nguyên 1<= i1,i2,…iN
<= M (không cho phép độ phức tạp cỡ M x N).

Xem lời giải

25. Bài toán “Trộn mảng”

Cho 2 mảng số
a1,…aM và b1,…bN thỏa mãn a1<=a2<=<=aM và b1<=b2<=<=bN.
Lập chương trình trộn 2 mảng này và in ra mảng trộn: c1<= c2<= … cM+N
(không được sử dụng mảng độ dài lớn hơn M + N)

Xem lời giải

26. Về mảng 2 chiều

Cho mảng 2 chiều A kích thước M x M, các phần tử của nó bằng 0, 1, 5, 11. Tính số các phần tử Aij sao cho các phần tử Ai,j, Ai+1,j, Ai,j+1, Ai+1,j+1 là khác nhau.

Xem lời giải

27. Mô hình các điều kiện và hành động

Cho bảng T = (Tij) gồm m hàng và n cột (Tij = 0,1,2), m hàng sẽ xác định được m điều kiện logic C1, C2,…, Cm, n cột sẽ xác định được n “hành động” H1,H2,…Hn.

Các điều kiện Ci xác định như sau:

Nếu Tij = 1 thì Ci = True;

Nếu Tij = 0 thì Ci = False;

Nếu Tij = 2 thì Ci chưa được xác định (hay nhận giá trị nào cũng được). Mỗi hành động Hj ứng với cột j của T sẽ xác định một bộ các điều kiện (C1, C2,…, Cm).

Bảng T gọi là mâu thuẫn nếu tồn tại một bộ điều kiện (C1,…,Cm) ứng với nhiều hành động khác nhau. Bảng T gọi là đầy đủ nếu nó không mâu thuẫn và mọi bộ điều kiện (C1, …,Cm) sẽ ứng với một hành động xác định (trong số các hành động H1, H2, …, Hn).

 1) Lập thuật toán và chương trình kiểm tra xem bảng T cho trước có mâu thuẫn không?

 2) Lập thuật toán và chương trình kiểm tra xem T có đầy đủ không?

Xem lời giải

28. Thuật toán sinh phân số tối giản

In ra theo trật tự tăng dần tất cả các phân số tối giản 0<m/n <1 với mẫu số <= 10.

Xem lời giải

29. Về một hàm đệ qui

Cho hàm F(n), n-nguyên >= 0 xác định như sau:

            f(0)=0, f(1)=1, f(2n)=f(n), f(2n+1) = f(n) + f(n+1)

Với N cho trước, không dùng mảng độ dài N hãy lập thuật toán tính f(N).

Xem lời giải

30. Đường đi hợp lệ

Cho lưới N x M các đường. Một đường đi từ A đến B gọi là hợp lệ nếu nó không đi lại điểm đã đi
qua. Lập thuật toán và chương trình tính số các đường đi hợp lệ từ A đến B.

Xem lời giải

31. Bài toán đường đi hợp lệ tổng quát

Cho lưới ô vuông kích thước M x N. Một đường đi từ một điểm đến một điểm khác gọi là hợp lệ nếu nó không đi lại điểm đã đi qua. Lập thuật toán và chương trình tính số các đường đi hợp lệ từ điểm A0 đến điểm A1 nào đó trong lưới.

Xem lời giải

32. Bài toán Hậu min

Tìm số con Hậu ít nhất xếp trên bàn cờ (8 x 8) sao cho chúng khống chế được tất cả các ô trên bàn cờ.

Xem lời giải

33. Sắp xếp công việc trên 2 máy

Có n chi tiết máy phải gia công lần lượt ở 2 máy (1) và (2). Các thời gian gia công tương ứng là ti1, ti2, i = 1, 2,…., n. Tìm cách sắp xếp thứ tự công việc để từ khi bắt đầu đến khi kết thúc chiếm thời gian là ngắn nhất.

Xem lời giải

34. Tích hai ma trận nguyên

Cho ma trận vuông A(n x n) với các phần tử là các số nguyên. Tìm thuật toán cho phép biết rằng A có phải là tích của 2 ma trận nguyên bậc n hay không?

Xem lời giải

35. Mô tả các phép toán trên số nguyên

Lập thuật toán và chương trình mô tả các phép toán cộng, trừ, nhân, chia cho các số nguyên với độ lớn tùy ý.

Xem lời giải

36. Kiểm tra tứ giác lồi

Cho 4 điểm A,B,C,D trên mặt phẳng. Tìm thuật toán xác định xem tứ giác ABCD có phải là tứ giác lồi hay không? Tổng quát cho đa giác n đỉnh.

Xem lời giải

37. Dãy số độc lập nguyên tố

Dãy số tự nhiên a1, a2,… an gọi là độc lập nguyên tố nếu tồn tại một hoán vị của nó: b1,b2,…bn sao cho các cặp (b1,b2), (b2,b3),… (bn-1,bn) là nguyên tố cùng nhau.

Từ một tập các số tự nhiên cho trước, xây dựng thuật toán lập một hệ cực tiểu các số tự nhiên, bao hàm tập số trên và là độc lập nguyên tố.

Xem lời giải

38. Bao lồi

Cho n điểm A1 … An trên mặt phẳng. Lập thuật toán cho biết đa giác lồi nhỏ nhất chứa các điểm trên có bao nhiêu cạnh (ở đây nhỏ nhất được hiểu theo nghĩa là nó không chứa một đa giác lồi nào cùng tính chất trên).

Xem lời giải

39. Bài toán “đổi màu bi”

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.

Xem lời giải

40. Bài toán đổi màu bi Tổng quát

Điều kiện giống như trong đề số 39. Tìm thuật toán biến số bi trên thành M1 hòn bi xanh, M2 hòn bi đỏ, M3 hòn bi vàng (M1+M2 + M3 = N1 + N2 + N3).

Xem lời giải

41. Ma trận thuần nhất

Cho ma trận vuông Aij bậc n với tính chất sau:

1. Các số Aij = 0 hoặc Aij = 1.

2. Nếu Aij = 1 <=> Aji = 0 (i khác j).

Bộ 3 số tự nhiên (i,j,k) gọi là thuần nhất nếu Aij= Ajk= Aki

Với n cho trước:

1) Lập thuật toán và chương trình xác định ma trận A sao cho không tồn tại bộ thuần nhất
nào.

2) Lập thuật toán và chương trình xác định A với số cực đại các bộ thuần nhất và tính số cực đại đó.

Xem lời giải

42. Xác định các tứ giác đồng hồ trong ma trận

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 n x n. Gọi S là số
lượng các “tứ giác” Ai,j; Ai,j+1; Ai+1,j; Ai+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.

Xem lời giải

43. Bài toán “hậu” tổng quát

Trên bàn cờ n x n xếp số “hậu” lớn nhất Pk sao cho mỗi chúng đều khống chế đúng k “hậu” khác. (Với n=8 kết quả như sau: P0=8 (bài toán “hậu” cổ điển),

P1=10, P2=14,
P3=18, P4=21).

Xem lời giải

44. Ma trận kỳ ảo bậc lẻ

Tìm thuật toán xây dựng ma trận kỳ ảo bậc lẻ n. Ma trận kỳ ảo là ma trận bao gồm các số từ 1 đến nxn mà tổng các hàng, các cột và các đường chéo đều bằng nhau.

Xem lời giải

45. Ma trận kỳ ảo

Tìm thuật toán xây dựng ma trận kỳ ảo bậc n bất kỳ.

Xem lời giải

46. Lịch tháng kỳ ảo

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.

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 3 x 3 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.

Xem lời giải

47. Các vòng tròn Olimpic

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.

Xem lời giải

48. Về một ma trận số

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

1. Aij là các số nguyên từ 0 … 9

2. Mỗi số từ 0 … 9 được gặp 10 lần trong ma trận A .

3. Mỗi hàng và mỗi cột của A chứa không quá 4 số khác nhau.

Xem lời giải

49. Phân hoạch hình chữ nhật

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.

50. Bài toán về dây xích

Giả sử hình vuông A chia thành n hình chữ nhật con P1, P2, … Pn như đã mô tả trong bài 49. Tập con Q nằm trong [P1,P2 … Pn] gọi là một dây xích nếu hình chiếu của chúng lên một trong các cạnh của hình vuông là các đoạn thẳng không chồng lên nhau và phủ kín cạnh này của hình vuông.

1) Cho trước 2 hình chữ nhật con Pi, Pj nào đó. Lập thuật toán và chương trình để xác định một dây xích chứa Pi, Pj (dây xích này bao giờ cũng tồn tại !).

2) Hãy tìm tất cả các dây xích chứa 2 hình Pi, Pj cho trước.

3) Hãy chỉ ra một dây xích có độ dài cực đại.

4) Hãy chỉ ra một dây xích có độ dài cực tiểu.

Xem lời giải

51. Phân hoạch hình hộp chữ nhật

Cho một hình lập phương. Có thể chia hình đó thành nhiều hình hộp chữ nhật có các cạnh song song với các cạnh của hình lập phương. 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 phép chia như vậy.

Xem lời giải

52. Bài toán “đấu cờ”

Có 2n vận động viên đấu cờ. Mọi vận động viên cần đấu 1 lần với mỗi vận động viên còn lại. Tất cả chỉ có n bàn cờ. Hãy lập lịch đấu cờ cho các vận động viên sao cho lúc nào cũng có đủ n đôi chơi với nhau.

Xem lời giải

53. Bài toán “Bàn trà”

Có n người ngồi xung quanh một cái bàn tròn uống trà với nhau. Sau 1 phút lại có 1 cặp ngồi cạnh nhau đổi chỗ cho nhau. Lập thuật toán và viết chương trình cho phép sau một thời gian ngắn nhất tất cả các cặp cạnh nhau đều được “đổi chỗ” cho nhau (nghĩa là khi đó tất cả những người ngồi bên trái chuyển sang bên phải và ngược lại).

Xem lời giải

54. Bảng số kỳ lạ Tổng quát

Dãy số tự nhiên khác nhau đôi một a, b, c, d, e, … k được xây dựng từ biểu đồ thoả mãn tính chất: Mỗi số bằng tổng của 2 số có mũi tên đến số đã cho (xem hình vẽ). Ví dụ: b = a+e, c = b+f,…

Với số d cho trước, xây dựng thuật toán cho phép thiết lập được biểu đồ đó.Tính số d nhỏ nhất cho phép xây dựng biểu đồ trên.

Xem lời giải

55. Bảng số kỳ lạ tổng quát

Cho dãy số tự  nhiên khác nhau từng đôi một a1, a2, …an được xây dựng từ biểu đồ thoả mãn tính chất: Mỗi số bằng tổng của 2 số có mũi tên đến số đã cho (hình vẽ).

Tìm số ak nhỏ nhất với n cho trước.

56. Bài toán “Kangaroo”

Trên một lưới N x N ô, Kangaroo có thể bước như sau: (x,y) _ (x+1, y-1) hoặc (x, y) _ (x-5, y+7) (nhưng không được ra khỏi lưới).

Hãy xác định xem từ những điểm ban đầu nào, con Kangaroo có thể đi đến được tất cả các ô khác của lưới (không loại trừ trường hợp đi lại các ô đã đi qua).

Xem lời giải

57. Xây dựng một lớp dãy nhị phân

Xây dựng chương trình và thuật toán để thiết lập tất cả các dãy A1, A2,…An (n -cho trước) gồm các số 0,1 và thoả mãn điều kiện: A1.Ak+1 + A2.Ak+2+ … + An-k.An là số lẻ với mọi k = 0, 1,… , n-1 (đáp số có thể là phủ định sự tồn tại của các dãy trên).

Xem lời giải

58. Dãy số tựa giao hoán

Viết chương trình thực hiện các công việc sau:

1) Nhập hai số nguyên dương m, n và n số nguyên a1,…,an.

2) Tìm và in ra trong dãy n số trên m số liên tiếp là hoán vị của m số tự nhiên đầu tiên. Nếu không có m số liên tiếp như vậy, hãy thông báo trên màn hình.

3) Tìm và in ra dãy con liên tiếp dài nhất của dãy a1,…,an mà dãy đó là dãy các số nguyên liên tiếp.

Xem lời giải

59. Bài toán “Tú lơ khơ 4 màu”

Có một tập bài 4n quân gồm n tờ màu xanh, n tờ màu đỏ, n tờ màu vàng, n tờ màu tím được xếp thành một tập. Luật chơi là xáo bài trên tay, mỗi lần chơi được rời một phần bài liên tục lên đầu tập. Lập thuật toán và chương trình cho phép sau một số ít lần nhất xáo bài không có 2 quân bài nào cùng màu liền nhau.

Xem lời giải

60. Hệ các tam giác cực tiểu

Trên mặt phẳng cho n điểm B1 … Bn (tọa độ cho trước). Một tam giác với các đỉnh trong B1 …
Bn gọi là cực tiểu nếu nó không chứa một điểm nào khác của hệ này.

1) Lập thuật toán và chương trình tìm ra một tam giác cực tiểu.

2) Tìm hệ cực đại các tam giác cực tiểu rời nhau.

Xem lời giải

61. Phép biến đổi trên bộ ba số

Trên bảng cho 3 số tự nhiên N1, N2, N3. Mỗi bước đi được thực hiện như sau:

Xoá đi 1 trong 3 số trên và thay thế số đó bằng tổng của 2 số còn lại trừ đi 1. Tìm thuật toán cho phép biết rằng sau một số hữu hạn bước có thu được bộ 3 số (A, B, C) cho trước hay không nếu 3 số đầu tiên là 2,2,2.

62. Tiếp tục phép biến đổi bộ 3 số

Trên bảng cho 3 số tự nhiên N1, N2, N3. Mỗi bước đi được thực hiện như sau:

Xoá đi 1 trong 3 số trên và thay thế số đó bằng tổng của 2 số còn lại trừ đi 1. Tìm thuật toán cho phép biết rằng sau một số hữu hạn bước có thu được bộ 3 số (A, B, C) cho trước hay không nếu 3 số đầu tiên là bộ (m, n, l) cho trước.

Xem lời giải

63. Ma trận hoán vị

Lập chương trình xây dựng ma trận A bậc N´N thỏa mãn các điều kiện sau:

1. đối xứng: Aij = Aji.

2. Aii = 0, (i = 1, 2, … n)

3. Mỗi hàng và mỗi cột của ma trận A đều là các hoán vị của dãy số 0, 1, 2, … n-1.

Xem lời giải

64. Trò chơi Tích – Tắc vuông

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.

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

Xem lời giải

65. Trò chơi Tích – Tắc vuông tổng quát

Cách chơi tương tự bài 64. điểm khác là người thứ hai có thể đánh dấu đồng thời được nhỏ hơn hoặc bằng k ô trống (k>1). Tìm thuật toán tối ưu cho các người chơi.

Xem lời giải

66. Kim giờ và phút gặp nhau bao nhiêu lần trong ngày

Đồ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.

Xem lời giải

67. Kim giờ, phút, giây gặp nhau bao nhiêu lần trong ngày

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

Xem lời giải

68. Về một bài toán và đồng hồ điện tử

Giờ của đồng hồ điện tử thông báo giờ và phút. Ví dụ: 02:51, 11:02. Lập chương trình tính tổng số thời gian trên mặt đồng hồ xuất hiện chữ số k (k = 0, 1, … 9).

Xem lời giải

69. Chia nhóm công nhân

Có N công nhân phải sản xuất M sản phẩm. Mỗi sản phẩm phải lần lượt trải qua n công đoạn, mỗi công đoạn tốn lần lượt t1, t2, … ,tn thời gian. Cần sắp xếp N công nhân thành n tốp: N = A1 + A2+ … + An, mỗi tốp chuyên làm một công đoạn của sản phẩm. Mỗi công nhân chỉ làm được từng sản phẩm một.Hãy tìm cách chia N = A1 + … + An thành n tốp sao cho công việc sẽ được diễn ra trong thời gian nhỏ nhất.

Xem lời giải

70. Về một phép biến đổi trên lưới số

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.

Xem lời giải

71. Khoảng cách giữa các ô cùng lưới số tự nhiên

Các phần tử của ma trận A[NxN] là các số tự nhiên từ 1đN2. Khoảng cách giữa 2 ô Aij, Akl được
tính bằng max(|i-k|, |j-l|).

Tính số tự nhiên lớn nhất d thỏa mãn tính chất: Tồn tại một hoán vị các phần tử của A sao cho mỗi phần tử của A đều dịch đi một khoảng cách lớn hơn hoặc bằng d.

Xem lời giải

72. Về một thuật toán sinh dãy số nguyên

Trên các máy vi tính 16 bit, thông thường các số nguyên được hiểu nằm trong khoảng cách  

 -32768<= x <= 32767.

Hãy viết chương trình sinh ra một dãy số nguyên dài nhất thỏa mãn điều kiện: Trong dãy này không tồn tại một bộ 3 số nào là một cấp số cộng.

Xem lời giải

73. Trò chơi tô cạnh lưới ô vuông

Trên mặt phẳng có một lưới ô vuông n x n. Hai người chơi trò chơi sau: Mỗi người đến lượt mình được tô lại cạnh của 1 ô vuông. Người thắng cuộc là người đầu tiên vẽ được một đường kín (không được tô vào cạnh đã tô). Xây dựng thuật toán tối ưu cho các người chơi.

Xem lời giải

74. Về trò chơi đảo tô cạnh lưới ô vuông

Trên mặt phẳng có một lưới ô vuông n x n. Hai người chơi trò chơi sau: Mỗi người đến lượt mình được tô lại cạnh của 1 ô vuông. Người thua cuộc là người bắt buộc vẽ một đường kín (không được tô vào cạnh đã tô). Xây dựng thuật toán tối ưu cho các người chơi.

Xem lời giải

75. Phép biến đổi

Có n người ngồi xung quanh một bàn tròn. Mọi người được ghi lên trước mặt mình một số 0 hoặc 1. Mỗi bước, hai người nào đó ngồi gần nhau có thể đồng thời tăng các số của mình lên 1 đơn vị. Cần chỉ ra thuật toán cho phép sau một số hữu hạn phép chơi, tất cả mọi người đều có các số bằng nhau.

Xem lời giải

76. Trò chơi lập số chính phương

Hai người chơi trò chơi sau:

Người thứ nhất viết lên bảng một chữ số (từ 0-9). Người thứ hai được viết thêm về bên trái hoặc phải 1 chữ số nữa. Cứ như vậy …. Mỗi người đều cố gắng sao cho khi viết xong lượt mình số thu được sẽ là số chính phương.

Tìm thuật toán cho người đi nước đầu tiên sao cho người thứ hai không bao giờ đạt được mục đích.

Xem lời giải

77. Lịch thi đấu bóng đá

Có 2N-1 đội bóng đá cần đấu loại vòng tròn với nhau. Mỗi đội bóng phải chơi với 2N-2 đội còn lại. Cần xếp lịch thi đấu thành N vòng. Mỗi vòng có N-1 cặp đội đấu với nhau (như vậy mỗi vòng sẽ có 1 đội được nghỉ). Lập chương trình xếp lịch thi đấu sao cho mỗi đội sẽ được đấu N-1 lần ở sân nhà và N-1 lần ở sân khách.

Xem lời giải

78. 49 tù nhân

Có 49 tù nhân cần được giam trong 49 phòng, mỗi phòng là 1 hình vuông 1 x 1 được đặt trong 1 nhà tù hình vuông 7 x 7. Biết rằng mỗi tù nhân có không quá 8 kẻ thù trong số các tù nhân khác. Hãy xếp các tù nhân này sao cho không có 2 tù nhân nào là kẻ thù mà lại ở cạnh nhau (tức là chung tường).

Xem lời giải

79. Bài toán tô màu chấp nhận được

Trên một lưới vuông N x N đánh dấu tập M gồm hữu hạn điểm. Các điểm của M sẽ được đánh dấu bởi một trong hai màu xanh và đỏ. Cách đánh màu được coi là chấp nhận được nếu trên mỗi đường nằm ngang hoặc thẳng đứng của lưới số các điểm xanh và đỏ hơn kém nhau không quá 1.

Lập thuật toán xây dựng một cách tô mầu chấp nhận được cho tập M cho trước.

Viết chương trình liệt kê tất cả các cách tô màu chấp nhận được.

80. Về phép biến đổi 5 số

Có 5 người ngồi xung quanh một bàn tròn. Trước mặt mọi người cho 1 số nguyên (tổng các số nguyên này >0). Qui tắc chơi như sau: Nếu có 3 số nguyên liên tiếp X, Y, Z sao cho Y<0 thì có thể thay thế 3 số này thành X+Y, -Y, Z+Y. Lập chương trình kiểm tra xem quá trình này có kết thúc hay không và tính ra số bước đi ngắn nhất để kết thúc quá trình này.

Xem lời giải

81. Xếp người ngồi trên bàn tròn

Xung quanh một bàn tròn có 2N người ngồi: N nam, N nữ. Mỗi lần đổi có thể đổi chỗ được 2 người bất kỳ. Xác định thuật toán tìm ra số bước đổi ít nhất sao cho không có 2 người cùng giới ngồi cạnh nhau.

Xem lời giải

82. Hai hàng số kỳ ảo

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.

Xem lời giải

83. Thuật toán lan số trên mảng

Cho lưới ô vuông n x m. Các ô vuông ở biên đã điền số -1. Các ô bên trong được điền tiếp các số 1,-1 theo qui tắc sau: điền vào một ô trống số bằng tích của 2 số khác 0 gần nhất theo hàng hoặc cột của lưới.

1) Lập chương trình cho phép điền vào tất cả các ô còn lại cho đến khi công việc kết thúc. Sau đó in ra số các số một có trong lưới. Gọi số này là S.

2) Xây dựng thuật toán điền số sao cho S là nhỏ nhất.

3) Xây dựng thuật toán điền số sao cho S là lớn nhất.

Xem lời giải

84. Trò chơi “Phân rã số”

Trên bảng đen được viết một số tự nhiên n. Hai người chơi trò chơi sau: Người thứ nhất xóa số n và viết vào đó hai số m, k sao cho m+k=n. Người thứ hai lại làm tương tự đối với một trong hai số m, k. Cuộc chơi dừng lại khi trên bảng còn toàn số 1.

Tìm thuật toán tối ưu trong hai trường hợp:

1) Người thắng cuộc là người đi sau cùng.

2) Người thua cuộc là người đi sau cùng.

Xem lời giải

85. Thuật toán bẻ Sôcôla

Có một thanh Sôcôla kích thước m x n được vạch thành m x n ô vuông nhỏ, mỗi ô kích thước 1 x 1. Hai người chơi như sau: Người đầu tiên bẻ miếng Sôcôla làm 2 mảnh theo một đường vạch. Người thứ hai làm tương tự với một trong hai mảnh Sôcôla còn lại.
Tìm thuật toán tối ưu trong hai trường hợp:

1) Người thắng cuộc là người được bẻ lần cuối.

2) Người thua cuộc là người được bẻ lần cuối.

(Cuộc chơi dừng lại khi còn lại toàn các ô vuông 1 x 1).

Xem lời giải

86. Bài toán “đẩy” bi

Trên một lưới vuông N x N có một hòn bi tại ô vuông ở góc trái dưới. Tọa độ các ô lưới ký hiệu (i,j), vị trí góc trái dưới là (1,1). Mỗi bước đi của luật chơi như sau:  Nếu hòn bi ở vị trí (i,j) mà tại các ô (i+1, j) và (i, j+1) trống thì hòn bi này có thể cất đi và đặt vào hai ô (i+1, j), (i, j+1) hai hòn bi khác. Mục đích
chơi là làm sao “đẩy” các hòn bi càng xa gốc tọa độ càng tốt. Cụ thể là cần đẩy khỏi tam giác vuông đỉnh ở gốc tọa độ và có cạnh d. Tìm thuật toán xác định số d lớn nhất sao cho có thể đạt được mục đích.

Xem lời giải

87. Về các số 0 và 1 trong ma trận

Cần xếp vào các số 0, 1 vào ma trận A[M x N] với M x N chẵn, thỏa mãn các tính chất sau:

1) Tổng số các số 0 và 1 trong toàn ma trận là bằng nhau.

2) Trên mỗi hàng và mỗi cột, tỉ số giữa số lượng các số 0 và 1 hoặc nhỏ hơn 1/4 hoặc lớn
hơn 3/4.

Xem lời giải

88. Xây dựng số tự nhiên “ngoại đạo”

Cho trước các số tự nhiên A1, A2, … ,An. Lập chương trình in ra số tự nhiên nhỏ nhất M không biểu diễn dưới dạng tổng của một hay nhiều số hạng trong dãy trên (mỗi phần tử chỉ được có trong một số hạng của tổng mà thôi).

Xem lời giải

89. Các số lặp

Cho mảng A[1 ..N]. Lập chương trình in ra số được lặp lại nhiều nhất trong mảng (ghi tất cả các số như vậy).

90. So sánh các tứ diện

Cho hai tứ diện đều bằng nhau. Trên các mặt của các tứ diện này theo cùng một thứ tự ghi các số A1, A2, A3, A4 và B1, B2, B3, B4. Biết rằng B1, …, B4 là một hoán vị của A1, A2, A3, A4. Lập thuật toán và chương trình cho phép biết được rằng có thể đặt hai tứ diện đó chồng khít vào nhau sao cho các số trên các mặt trùng nhau của hai tứ diện đó là giống nhau.

Xem lời giải

91. Xây dựng các số tốt

Một số tự nhiên gồm 2m chữ số được gọi là “tốt” nếu tập hợp các chữ số có chỉ số chẵn và lẻ chứa số các số chẵn và lẻ như nhau. Ví dụ: số 2347169824 là số “tốt” vì tập các chữ số chỉ số chẵn và lẻ đều chứa 3 số chẵn và 2 số lẻ.

Cho trước một số có (2m+1) chữ số. Lập thuật toán để sau khi xóa đi một chữ số của nó, số này sẽ trở nên “tốt”. Lập đoạn chương trình nhập từ bàn phím một số (2m+1) chữ số và biến đổi chúng thành số “tốt”. In ra kết quả.

Xem lời giải

92. Bài toán “điện thoại”

Có n điểm cho trước (đó là n trạm điện thoại). Hai người chơi trò chơi sau: Mỗi người đến lượt mình được phép nối dây của hai trạm điện thoại chưa được nối dây. Người thắng cuộc là người mắc được đường dây cần thiết cuối cùng (nếu sau đó tất cả các trạm đều có thể nói chuyện được với nhau, dù có phải qua các trạm trung gian). Tìm thuật toán tối ưu cho các người chơi.

Xem lời giải

93. Ma trận tựa kỳ ảo

Lập thuật toán điền vào ma trận A[N x N] các số tự nhiên khác nhau thỏa mãn điều kiện sau: Với mọi k=2, 3, … n, mọi ma trận con bậc k của A đều thỏa mãn tính chất: Tổng các số trên hai đường chéo bằng nhau (ma trận con hiểu là k hàng và cột liền nhau).

Xem lời giải

94. Các ma trận con kỳ dị

Lập thuật toán điền vào ma trận A[N x N] các số tự nhiên khác nhau thỏa mãn điều kiện sau: Với mọi k=2, 3, … n, mọi ma trận con bậc k của A đều thỏa mãn tính chất: Tích các số trên hai đường chéo bằng nhau (ma trận con hiểu là k hàng và cột liền nhau).

Xem lời giải

95. Ma trận hoàn chỉnh

Ma trận số A[Mx N] gọi là “hoàn chỉnh” nếu nó không có hai hàng nào giống hệt nhau. Cho trước ma trận hoàn chỉnh A[M x N]. Lập thuật toán để sau khi xóa đi một cột nào đó, ma trận thu được vẫn là hoàn chỉnh (chương trình phải chỉ ra chỉ số cột cần phải xóa đi).

Xem lời giải

96. Hệ thống bóng điện kỳ ảo

Trên tường treo n bóng điện, giữa một số cặp bóng điện có nối dây trang trí. Các bóng điện được thắp sáng theo hai màu xanh và đỏ. Sau mỗi phút các bóng điện sẽ được thay đổi màu theo nguyên tắc sau:

Xét bóng điện A và tập DA các bóng điện của hệ thống có nối dây với A. Bóng điện A sẽ đổi màu nếu như quá một nửa các bóng của DA khác màu với A (không đổi màu nếu ngược lại). Người ta đã quan sát được sau một khoảng thời gian nào đó toàn cảnh bóng điện sẽ có hiện tượng sau: Một số bóng điện sẽ dừng lại không đổi mầu nữa, còn một số bóng điện khác sẽ đổi màu liên tục sau mỗi bước. Lập chương trình để tính số thời gian đó.

Xem lời giải

97. Về một ma trận kỳ lạ

Điền vào ma trận m x n (m hàng, n cột) các số tự nhiên từ 1, 2, … m x n sao cho tổng số các số trong các cột của ma trận là như nhau (làm được khi m chẵn hoặc n x m lẻ).

Xem lời giải

98. Tìm cách đi tối ưu cho con xe

Trên bàn cờ ô vuông n x m, góc trái dưới cùng có một con xe. Hai người lần lượt đi con xe đó. Qui tắc chỉ cho phép đi lên hoặc về bên phải (quãng đường tùy ý). Người thua cuộc là người phải đi nước cuối cùng. Lập thuật toán tối ưu.

99. Bài toán “Thủy chiến”

Trên một lưới ô vuông NxN, một người đánh dấu lên đó (một cách bí mật) một số “tàu chiến” dạng 1xk, các tàu chiến này phải rời nhau. Người thứ hai “thả bom” tại từng ô vuông và sau một lần đánh bom thu được câu trả lời: “trúng” hoặc “trượt”. Tìm thuật toán tối ưu cho người thứ hai để xác định được vị trí tàu.

Xem lời giải

100. Lại về bài toán thuỷ chiến khác

Trên một lưới ô vuông N x N, một người đánh dấu lên đó (một cách bí mật) một số “tàu chiến” dạng 1x N, các tàu chiến này phải rời nhau. Người thứ hai đánh một loạt “bom” tại từng ô vuông và sau một lần đánh bom thu được câu trả lời: “trúng” hoặc “trượt”. Tính xem người thứ hai phải đánh nhiều nhất là bao nhiêu bom để biết được vị trí tàu.

Xem lời giải

 

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Một 2014
H B T N S B C
« Th10   Th12 »
 12
3456789
10111213141516
17181920212223
24252627282930

NCT Computer

Flickr Photos

Thống kê

  • 181,058 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: