Bài tập cơ sở dữ liệu - Bài toán chương trìnhĐường lên đỉnh olimpia

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 đánhsố từ 1 đến 10 ở trạng thái tắt. Ngườita thay đổi trạng thái cácbóng đèn thẻo qui tắc sau đây.
Nội dung trích xuất từ tài liệu:
Bài tập cơ sở dữ liệu - Bài toán chương trình"Đường lên đỉnh olimpia" Bài toán Vũ Văn ThảoTa 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 đánhsố từ 1 đến 10 ở trạng thái tắt. Ngườita thay đổi trạng thái cácbó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ần3: 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 đèncó số hiệu chia hếtcho 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ộtsố bóng đèn tắt, một số khác sáng. Dođó trên dãy đèn đã chotrở 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 đổitrạng thái như bài ra, những bóng đèncó 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,1Các bạn tự lập chương trình giải bài toán 1 vớin,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áylà bài toán ra trong kì thi Tion học quốctế lần thứ 10 (năm 1998 tạiBồ Đà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 đổitrạng thái của chúng. ấn nút 1 thayđổi trạng thái các đèn; ấnnút 2 thay đổi trạng thái các đèn có số hiệu lẻ; ấn nút 3 thauđổitrạ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úttrên. Ban đầu, tất cả ác đèn đềusáng và C chỉ 0.Yêu cầu: Cho giá trị C và trạng thái cuối cùng củamột số đèn. Hãy lập chương trìnhxá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ôngtin đã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 đèntrong 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ạng101-17-1ở đây số đèn là 10, chỉ ấn 1 nút và ở trạngthá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ạngkthái cuối cùng có thể có (khácnhau) của các đèn. Mỗi trạng tháighi trên 1 dòng gồm N kí tự 0 và 1, trong đó 0 ứngvớ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.000000000001101101100101010101Hạn chế: 0Contr:Array [ 1..16 ] Of t;Flag:Boolean;Inp,outp:Text;Procedure ReadData; { thu tuc nhap du lieu }BeginAssign(inp,a:pasparty.inp);Reset(inp);Readln(inp,a);Readln(inp,c);On:=[];Read(inp,j);While j-1 DoBeginIf j mod 3 1 ThenIf ođ(j) Then On:=On+[1] Else On:=On+[2]Else If Ođ(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 DoBeginIf j mod 3 1 ThenIf ođ(j) Then off:=off+[1] Else off:=off+[2]Else If Ođ(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}BeginAsign(out,a:pasparty.out);rewrite(out);For i4:=0 To 1 DoFor i3:=0 to 1 DoFor i2:=0 To 1 DoFor i3:=0 To 1 DoBeginK:=i1+i2+i3+i4;If (c>=k) ThenBeginS:=[1..4];For m:=1 To 4 DoCase m Of1:If Ođ(i1+i2) Then s:=s-[1];2:If ođ(i1+i3) Then S:=S-[2];3:If ođ(i1+i2+i4) Then S:=S-[3];4:If ođ(i1+i3+i4) Then s:=s-[4];End;If (onBeginFor j:=1 To n DoIf j mod 31 ThenIf ođ(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 (ođ(j) thenIf 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;BeginClrScr;Writeln(Chuong trinh bat daú);ReadData;Solve;Writeln(Chuong trinh ket thuc);Readln.End.