Tài liệu tin 20

Trò chơi úp bài



Cho M quân bài mang các số từ 1 đến M ( M<=12 ) , các quân bài đang lật ngửa .Cho một số nguyên dương N ( N<=200 ) . Trò chơi như sau : Hai người lần lượt thay nhau úp quân bài theo qui tắc :
+ Cộng giá trị quân bài vào tổng điểm , nếu tổng điểm bằng N thì người đó thắng
+ Khi úp một quân bài (ngửa ) thì đồng thời lật ngửa lại quân bài đang bị úp trước đó.

Hãy lập trình theo yêu cầu :
1) Nhậptừ bàn phím số N,M.
2) Bốc thăm ai đi trước
3) Thể hiện trò chơi trên màn hình trò chơi giữa người và máy sao cho khả năng thắng của máy có thuận lợi hơn

Thuật toán :

Giả sử N=10 , M=3 . Trước hết lập bảng phương án sau :


1
2
3
4
5
6
7
8
9
10

1
1
0
0
1
1
0
0
1
1
0

2
0
0
0
1
0
0
0
1
0
0

3
0
0
1
1
0
0
1
0
0
0


Nếu máy đi trước :
Chọn quân số 1 ( vì A[1,1] = 1 ) , dồn người chơi phải chọn quân 2 hoặc 3 , do đó cột điểm tiếp theo là 1+2 =3 hoặc 1+3=4 . Trong các cột điểm 3 và 4 , đến lượt máy đi lại có số 1 , nên máy lại được chọn quân ở hàng nào đó có số 1 . . . Quá trình cứ như thế , cho đến khi sẽ dẫn tới tình trạng : sau khi người đi quân số 2 hoặc 3 thì tổng điểm là 9 đến lượt máy đi , máy úp quân số 1 , được tổng điểm là 10 . Máy thắng .

Nếu máy đi sau :
Rất có thể máy bị dồn vào tình trạng : nhận cột điểm không có số 1 . Khi đó máy phải úp quân nào đó để cột điểm mới có ít số 1 nhất , nghĩa là tạo ra tình thế bất lợi nhất cho người ( Máy hy vọng người chơi này này không biết qui luật , úp phải quân bài ở hàng 0 của cột điểm mới này)

Vấn đề còn lại các em sẽ thắc mắc là : Làm thế nào có bảng phương án như vậy ?
Lý do đơn giản là chúng ta lần ngược từ trạng thái kết thúc chắc thắng về trạng thái đầu . Cụ thể
+ Gán A[1,N-1] = 1
+ Sau đó xây dựng dần các số 1 ở các cột điểm đ = N-2,N-3,.....,1 theo qui tắc :
Chọn số quân lần lượt là Sq = 1 .. M . Gọi số lượng số 1 ở cột đ+Sq là x ( với điều kiện x<=N ) . Nếu x=0 hoặc ( x=1 và A[Sq,x]=1 ) thì A[Sq,đ]=1 ; còn lại A[Sq,đ]=0
Chương trình

Uses Crt;
Type pt = 0..1;
Var Diem,sq,m,n,Luu : Byte;
S : String;
A : Array[1..12,0..200] of 0..1;
Ch : Char;
Ok :