Bài toán "đèn nhấp nháy"



tải về 30.96 Kb.
Chuyển đổi dữ liệu23.07.2016
Kích30.96 Kb.
Bài toán "đèn nhấp nháy"

Ta bắt đầu bằng bài toán trong chương trình "Đường lên đỉnh olimpia".

Bài toán 1. Một dãy gồm 10 bóng đèn được đánh số từ 1 đến 10 ở trạng thái tắt. Người ta thay đổi trạng thái các bóng đèn thẻo qui tắc sau đây.

Lần 1: thay đổi trạng thái tất cả các bóng đèn. Lần 2: thay đổi trạng thái các đèn có số hiệu chia hết cho 2. Lần 3: thay đổi trạng thái các bóng đèn có số hiệu chia hết cho 3. Cứ như vậy cho đến lần thứ 10 thì thay đổi trạng thái các bóng đèn có số hiệu chia hết cho 10.

Hỏi những bóng đèn có số hiệu nào còn sáng?

Giải. Khi thực hiện việc thay đổi trạng thái, một số bóng đèn tắt, một số khác sáng. Do đó trên dãy đèn đã cho trở thành dãy đèn nhấp nháy.

Trước hết ta nhận xét rằng, sau 10 lần thay đổi trạng thái như bài ra, những bóng đèn có số lẻ lần thay đổi sẽ là bóng đèn còn sáng. Ký hiệu S[k] là tập hợp các sối, 1<=i<=1, sao cho i là bội của k. Khi đó số lần k sẽ thay đổi trạng thái các bóng đèn có số hiệu i thuộc S[k], hay k là ước của i. Do đó số lần thay đổi tạng thái của bóng đèn i bừng các ước số T(i) của i.

Ta có thể giải bằng toán học như sau. Ta đã biết rằng, nếu:

+i=P1a1...pkak, trong đó p1,...,pk là các số nguyên tố khác nhau; thì T(i)=(a1+1)...(ak+1). Do đó nếu i là số chính phương thì T(i) lẻ, còn các trường hợp khác T(i) chẵn. Suy ra các bóng đèn có số hiệu 1, 4, 9 còn sáng. Các bóng đèn khác bị tắt.

+Ta có thuật toán như sau.

-Với mỗi i, 1<= i<= 10 đặt T(i)=0

-Xét tất cả k, 1<= k<= i, nếu k là ước của i thì T(i)=T(i)+1

-Nếu T(i) lẻ thì đèn T(i) sáng, nếu T(i) chẵn thì đèn T(i) tắt.

1.Rõ ràng là với số lượng bóng đèn n lớn hơn 10 rất nhiều thì giải bằng toán học không thể xác định được ngay số hiệu bóng đèn còn sáng. Khi đó nhờ cách giải quyết trực tiếp trên máy tính ta sẽ nhanh chóng xác định được số hiệu bóng đèn còn sáng.

Hơn nữa, nếu số lần thay đổi trạng thái là m bất kì thì cách giải 2 càng thuận tiện hơn.

Các bạn tự lập chương trình giải bài toán 1 với n,m và trạng thái ban đầu của dãy bóng đèn là tuỳ ý. Bạn có thể tham khoả thêm thuật giải bài toán 2.

Ta chuyển sang giải bài toán " đèn nhấp nháy" là bài toán ra trong kì thi Tion học quốc tế lần thứ 10 (năm 1998 tại Bồ Đào Nha)

Bài toán 2. Đèn cho ngày hội (PARTY)

Có N đèn màu đánh số tùe 1 đến N và 4 nút thay đổi trạng thái của chúng. ấn nút 1 thay đổi trạng thái các đèn; ấn nút 2 thay đổi trạng thái các đèn có số hiệu lẻ; ấn nút 3 thau đổi trạng thái đèn có số hiệu chẵn; ấn nút 4 thay đổi các đèn có số hiệu dạng 3k+1 (k>=0);

Có một máy đếm C để đếm tổng số các lần ấn nút trên. Ban đầu, tất cả ác đèn đều sáng và C chỉ 0.

Yêu cầu: Cho giá trị C và trạng thái cuối cùng của một số đèn. Hãy lập chương trình xác định tất cả các trạng thái ( có thể có) cuối cùng của N đèn tương ứng với các thông tin đã cho.

Dữ liệu vào: Tệp PARTY.IN chứa 4 dòng. Dong 1 cho số N. Dòng 2 cho giá trị của C. Dòng 3 và 4 cho danh sách các đèn có trạng thái cuối cùng tương ứng lad sáng hay tắt. Số hiệu các đèn trong mỗi danh sách cách nhau một dấu cách và kết thúc bởi số -1. Ví dụ tệp PARTY.IN có dạng

10

1

-1



7

-1

ở đây số đèn là 10, chỉ ấn 1 nút và ở trạng thái cuối cùng đèn 7 tắt.



Dữ liệu ra: Tệp PARTY.OUT chứa tất cả các trạngk thái cuối cùng có thể có (khác nhau) của các đèn. Mỗi trạng thái ghi trên 1 dòng gồm N kí tự 0 và 1, trong đó 0 ứng với đèn tắt, còn 1 là đèn sáng. Thứ tự các dòng tuỳ ý.

Với dữ liệu vào như trên tệp PARTY.Out có dạng.

0000000000

0110110110

0101010101

Hạn chế: 0<= N<= 100, 1<= C<= 10000. Số lượng các đèn sáng và đèn tắt ở trạng thái cuối cùng <= 2. Dữ liệu vào đảm bảo có ít nhất 1 trạng thái của N đèn thoã mãn.

Giải. Ta chia N đèn thành 4 nhóm không giao nhau:

+Nhóm 1 gồm các đèn số hiệu lẻ và khác dạng 3k+1

+Nhóm 2 gồm các đèn số hiệu chẵn và khác dạng 3k+1

+Nhóm 3 gồm các đèn số hiệu lẻ có dạng 3k+1

+Nhóm 4 gồm các đèn có số hiệu chẵn có dạng 3k+1

+Khi ấn nút 1 các đèn thuộc tất cả các nhóm thay đổi trạng thái.

+Khi ấn nút 2 các đèn thuộc nhóm 1và 3 thay đổi trạng thái.

+Khi ấn nút 3 các đèn thuộc nhóm 3 và 4 thay đổi trạng thái.

+Khi ấn nút 4 các đèn thuộc nhóm 3 và 4 thay đổi trạng thái.

+Khi ấn một nút bất kì các đèn trong 1 nhóm hoặc cùng thay đổi trạng thái hoặc không. Do đô ta chỉ cần xét 4 đèn đại diện cho 4 nhóm. Hơn nữa, một đèn bất kỳ không thay đổi trạng thái nếu số lần thay đổi trạng thái của nó chẵn. Ngược lại, đèn sẽ thay đổi trạng thái. Suy ra đối với mỗi nút chỉ cần xét 2 khả năng: số lần ấn nút chẵn kí hiệu 0 và số lần ấn nút lẻ kí hiệu 1. Như vậy, ta chỉ càn xet 24 =16 khả năng có thể xảy ra.

Ký hiệu ON là tập các đèn sáng và OFF là tập các đèn tắt trong trạng thái cuối cùng đã cho, còn s là tập đèn sáng trong trạng thái cuối cùng nào đó. Khi đó trạng thái này thừa nhận được nếu thoã mãn (ON<=S) và (OFF<=[1..4]-S)

Ta có chương trình Pascal đầy đủ như sau:



Program Party;

Uses Crt;

Type t= Set Of 1..4

Var c,i1,i2,i3,i4,j,k,m,n:integer;

On,off,s:T;

X:Array [ 1..50 ] Of Integer;

Contr:Array [ 1..16 ] Of t;

Flag:Boolean;

Inp,outp:Text;

 

Procedure ReadData; { thu tuc nhap du lieu }

Begin

Assign(inp,'a:pasparty.inp');

Reset(inp);

Readln(inp,a);

Readln(inp,c);

On:=[];Read(inp,j);



While j<>-1 Do

Begin

If j mod 3 <>1 Then

If od(j) Then

On:=On+[1]



Else

On:=On+[2]



Else

If Od(j) Then

On:=On+[3]



Else On:=On+4;

Read(inp,j);

End;

If j=-1 Then Readln(inp);

Off:=[];


readln(inp,j);

While j<>-1 Do

Begin

If j mod 3 <>1 Then

If od(j) Then

off:=off+[1]



Else

off:=off+[2]



Else

If Od(j) Then

off:=off+[3]



Else

off:=off+4;



Read(inp,j);

End;

Close(inp);



End;

 

Procedure Solve {Thu tuc tim cac trang thai N den thoa man}



Begin

Asign(out,'a:pasparty.out');rewrite(out);



For i4:=0 To 1 Do

For i3:=0 to 1 Do

For i2:=0 To 1 Do

For i3:=0 To 1 Do

Begin

K:=i1+i2+i3+i4;



If (c>=k) Then

Begin

S:=[1..4];



For m:=1 To 4 Do

Case m Of

1:If Od(i1+i2) Then s:=s-[1];

2:If od(i1+i3) Then S:=S-[2];

3:If od(i1+i2+i4) Then S:=S-[3];

4:If od(i1+i3+i4) Then s:=s-[4];

End;

If (on<=s) and(off<=[1..4]-s) Then

Begin

For j:=1 To n Do

If j mod 3<>1 Then

If od(j) then

If 1 in s then

write(out,1)

Else

write(out,0)

else

if 2 in s then

write(out,1)

else

write(out,0)

Else

if (od(j) then

If 3 In s Then

write(out,1)

Else

Write(out,0)

Else

if 4 in s then

write(out,1)

Else

write(out,0;

Writeln(out);



End;

End;

End;

Close(out);



End;

 

Begin

ClrScr;

Writeln('Chuong trinh bat dau');



ReadData;

Solve;


Writeln('Chuong trinh ket thuc');

Readln.


End.
: upload -> soft
soft -> Test 10 Phonetics: Chọn từ mà phần gạch chân có cách phát âm khác với những từ còn lại
soft -> PHÒng giáo dục và ĐÀo tạO Độc lập Tự do Hạnh phúc
soft -> TRƯỜng trung hoc phổ thông chuyên lê quý ĐÔN
soft -> NHẰm giúp các học sinh hiểu rõ HƠn một số khái niệm cơ BẢn và CÁc cụm từ viết tắt trong đỊa lý
soft -> Ôn tập chủ ĐỀ ĐẠi số TỔ HỢp nhận xét
soft -> Một thuật toán nổi tiếng Euclide Thuật toán Euclide
soft -> TRƯỜng thpt tôn thất tùNG
soft -> Ubnd quận hải châu cộng hoà XÃ HỘi chủ nghĩa việt nam
soft -> MÔn lịch sử 10 Bài 29: CÁch mạng tư SẢn hà lan và CÁch mạng tư SẢn anh cách mạnh tư sản Anh
soft -> Ubnh quận hải châu phòng giáo dục và ĐÀo tạO




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2019
được sử dụng cho việc quản lý

    Quê hương