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

Nội dung text: 100 Đề Toán Tin (Tin học và Nhà trường)

1. 100 Problems & Solutions Page 146 for h:=0 to can do begin t:=h; t:=sqr(t)-p; if (t>=h)and(t<=n) then inc(dem); end; end; procedure ghif; var f :text; begin assign(f,fo); rewrite(f); writeln(f,dem); close(f); end; BEGIN docf; if p mod 2=0 then lam; ghif; END. (Lời giải của Đỗ Đức Đông) Bài 85/2001 - Biến đổi 0 - 1 (Dành cho học sinh THPT) Thuật toán: Bài này sử dụng thuật toán duyệt nhưng có một vài chú ý sau: - Với 1 ô ta chỉ tác động nhiều nhất một lần. - Thứ tự tác động là không quan trọng. - Với một ô có nhiều nhất 5 ô ảnh hưởng được tới nó, vì vậy nếu với một ô ta biết 4 ô ảnh hưởng của nó có được tác động hay không thì ô còn lại ta sẽ biết là có nên tác động hay không tác động. Từ các chú ý trên ta sẽ duyệt một dòng 1 (hoặc một cột 1) được tác động như thế nào khi đó các ô ở dòng 1 (hoặc cột 1) sẽ chỉ còn 1 ô ảnh hưởng tới nó. Ta sẽ biết được rằng các ô dòng 2 (hoặc cột 2) cũng sẽ được tác động như thế nào, cứ như vậy cho các dòng tiếp theo. Bài sẽ phải duyệt 2N nếu duyệt theo dòng 1 (2M nếu duyệt theo cột 1) vì vậy để giảm độ phức tạp của bài bạn nên chọn duyệt theo chiều nào tuỳ thuộc vào M,N. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+} {$M 16384,0,655360} uses crt; const max =100; fi ='biendoi.inp'; fo ='biendoi.out'; tx : array[0 4]of integer=(0,0,-1,0,1); ty: array[0 4]of integer=(0,-1,0,1,0); type mg = array[1 max,1 max]of byte; var a,b,td,lkq,c:mg; m,n,dem,best:integer; procedure docf; var f :text; i,j :byte; begin assign(f,fi); Tin học & Nhà trường 100 Đề Toán - Tin học
2. 100 Problems & Solutions Page 148 procedure ghif; var f :text; i,j :integer; begin assign(f,fo); rewrite(f); if best<>maxint then begin writeln(f,best); for i:=1 to m do for j:=1 to n do if lkq[i,j]=1 then writeln(f,i,#32,j); end else writeln(f,'No solution'); close(f); end; begin clrscr; best:=maxint; docf; try(1); ghif; end. (Lời giải của Đinh Quang Huy) Bài 86/2001 - Dãy số tự nhiên logic (Dành cho học sinh Tiểu học) Số đầu và số cuối cần tìm của dãy số logic đã cho là: 10 và 24. Giải thích: dãy số đó là dãy các số tự nhiên liên tiếp không nguyên tố. Bài 87/2001 - Ghi các số trên bảng (Dành cho học sinh THCS) Procedure bai87; uses crt; var d, N:integer; begin clrscr; write('Nhap so nguyen duong N: '); readln(N); repeat if N mod 2 = 0 then N:= div 2 else N:=N-1; d:=d+1; until N=0; write('So lan ghi so len bảng: ', d); readln; End. (Lời giải của bạn Cao Le Thang Long) Bài 88/2001 - Về các số đặc biệt có 10 chữ số (Dành cho học sinh THCS và THPT) Thuật toán: mảng a[0 9] lưu kết quả, t[i] là số các chữ số i trong a. Theo bài ta có thể suy ra: a[0] + a[1] + + a[9] = số các chữ số 0 + số các chữ số 1 + + số các chữ số 9 = 10. Tin học & Nhà trường 100 Đề Toán - Tin học
3. 100 Problems & Solutions Page 150 Uses crt; Const fi ='number.inp'; fo ='number.out'; cs:array[1 8] of longint = (9, 180, 2700, 36000, 450000, 5400000, 63000000, 720000000); Var n : longint; f,g :text; Function num(n:longint):char; var k, so, mu : longint; s : string; Begin k:=1; mu:=1; while (k 0)-1; str(so,s);s:=s[k]+s; num:=s[n mod k+1]; End; BEGIN assign(f,fi); reset(f); assign(g,fo); rewrite(g); while not seekeof(f) do begin readln(f,n); writeln(g,num(n)); end; close(f); close(g); END. (Lời giải của bạn Lê Văn Đức - Nguyễn Huệ - Hà Đông - Hà Tây) Bài 90/2002 - Thay số trong bảng 9 ô (Dành cho học sinh Tiểu học) Do tổng các số trong các ô điền cùng chữ cái ban đầu là bằng nhau nên ta suy ra: 2M = 3I = 4S. Vì 4S chia hết cho 4, do đó 2M và 3I cũng chia hết cho 4. Suy ra: I chia hết cho 4; M = 2S; 3I = 4S. Đặt I = 4k (k = 1, 2, ), ta suy ra tương ứng: S = 3k, và M = 6k. Ví dụ, với k = 1 ta có đáp số sau: I = 4, S = 3, M = 6; Với k = 2, ta có: I = 8, S = 6, M = 12; Bài 91/2002 - Các số lặp (Dành cho học sinh THCS và THPT) Program bai91; {Thuat toan lua bo vao chuong} {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+} {$M 16384,0,655360} USES crt; CONST M1 = MaxInt div 4 + 1; Tin học & Nhà trường 100 Đề Toán - Tin học
4. 100 Problems & Solutions Page 152 integer và do giới hạn bộ nhớ là 64K nên ta dùng ba mảng động như sau: MG = array[- maxint maxint] of byte; L[1 3] of ^MG; Xử lý trong hệ cơ số 100. Chương trình. {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+} {$M 16384,0,655360} program bai91;{Đỗ Đức Đông} uses crt; const fi ='input.txt'; fo ='output.txt'; coso =100; type mg =array[-maxint maxint]of byte; var L :array[1 3]of ^mg; n,lap :longint; kq :integer; time :longint; clock :longint absolute $00:$0046c; procedure tao_test; var f :text; k :longint; begin n:=1000000; assign(f,fi); rewrite(f); writeln(f,n); for k:=1 to N do if random(2)=1 then write(f,random(maxint),#32) else write(f,-random(maxint),#32); close(f); end; procedure danhdau(x:integer); var i :integer; begin for i:=3 downto 1 do if L[i]^[x]<coso then begin inc(L[i]^[x]); break; end else L[i]^[x]:=0; end; procedure lam; var f :text; k :longint; x :integer; Tin học & Nhà trường 100 Đề Toán - Tin học
5. 100 Problems & Solutions Page 154 g:text; k,n,t,i,j,l:longint; function f(x:longint):byte; begin x:=x mod k; if x<0 then f:=x+k else f:=x; end; begin clrscr; assign(g,inp);reset(g); readln(g,n,k); t:=0; read(g,j); a[0]:=[f(j)]; for i:=2 to n do begin t:=1-t; a[t]:=[]; read(g,j); for l:=0 to k-1 do if l in a[1-t] then begin a[t]:=a[t]+[f(l+j)]; a[t]:=a[t]+[f(l-j)]; end; end; close(g); assign(g,out);rewrite(g); if 0 in a[t] then write(g,1) else write(g,0); close(g); write('Complete - Open file ',out,' to view the result'); readln; End. (Lời giải của bạn Vũ Lê An - 12T2 - Lê Khiết - Quảng Ngãi) Mở rộng bài toán: 1. Tìm dãy con liên tiếp có tổng bé nhất. 2. Tìm dãy con liên tiếp các phần tử thuộc dãy bằng nhau dài nhất. 3. Cho ma trận MxN hãy tìm hình chữ nhật có tổng lớn nhất (nhỏ nhất) với M,N<=100 4. Cho ma trận MxN hãy tìm hình chữ nhật có diện tích lớn nhất có các phần tử bằng nhau. Cách giải bài toán 2 giải giống với bài toán 1, bài toán 3 và 4 giải giống nhau dựa trên cơ sở bài 1,2. Cách giải bài toán 3: Xét hình các hình chữ nhật có toạ độ cột trái là i toạ độ cột phải là j (mất O(N2)). Coi mỗi dòng như một phần tử, để tìm hình chữ nhật có diện tích lớn nhất ta phải mất O(N) nữa. Như vậy độ phức tạp là O(N3). Bài 93/2002 - Trò chơi bắn bi (Dành cho học sinh Tiểu học) Có 3 đường đi đạt số điểm lớn nhất là: 32. Tin học & Nhà trường 100 Đề Toán - Tin học
6. 100 Problems & Solutions Page 156 Procedure input; begin assign(f,inp); reset(f); assign(g,out); rewrite(g); Readln(f,n); End; Procedure solve; var i,j:longint; begin dau:=1; cuoi:=1; d:=1; max:=-maxlongint; T:=0; for i:=1 to n do begin readln(f,j); T:=T + j ; If T > max then begin max:=T; dau:=d; cuoi:=i; end; If T<0 then begin T:=0; d:=i+1; end; end; End; Procedure output; Begin writeln(g,dau); writeln(g,cuoi); writeln(g,max); Close(f); Close(g); End; BEGIN input; solve; output; END. (Lời giải của bạn Võ Xuân Sơn - Lớp 11A2 THPT Phan Bội Châu - Nghệ An) Bài 96/2002 - Số chung lớn nhất (Dành cho học sinh THPT) {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+} {$M 16384,0,655360} uses crt; const maxn = 251; fi = 'string.inp'; fo = 'string.out'; var pa : array[0 maxn,0 maxn] of byte; s1,s2,skq : string; max : byte; procedure docf; var f : text; begin assign(f,fi); reset(f); readln(f,s1); read(f,s2); Tin học & Nhà trường 100 Đề Toán - Tin học
7. 100 Problems & Solutions Page 158 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. Giải: Từ (5) - Tích của các số tự nhiên đầu tiên cho kết quả là một số có 3 chữ số chỉ có thể là 120 hoặc 720 (1x2x3x4x5 = 120; 1x2x3x4x5x6 = 720). Do đó, (5) có thể là 120 hoặc 720. Suy ra: f = 0; e = 2; d = 1 hoặc d = 7. Tương tự, ta tìm được (6) có thể là 105 hoặc 385 (3x5x7 = 105; 5x7x11 = 385). Suy ra: i = 5; h = 0 hoặc h = 8; g = 1 hoặc g = 3. Từ (4) suy ra c chỉ có thể là số chẵn. Do f = 0, i = 5, từ (3) ta tìm được c = 6. Từ (2) - tích của nhiều thừa số 2 cho kết quả là một số có 3 chữ số chỉ có thể là một trong các số: 128, 256, 512. Mà theo trên e = 2 nên ta tìm được (2) là 128. Vậy b = 1, h = 8, g = 3. Từ (4) - Bội số nguyên của 8, do đó ta có thể tìm được (4) có thể là một trong các số: 216, 416, 616, 816. Tức là, a có thể bằng 2, 4, 6, hoặc 8. Kết hợp với (1), giả sử d = 1, như vậy ta không thể tìm được số nào thoả mãn (1). Với d = 7, ta tìm được a = 4 thoả mãn (1). Vậy a = 4, b = 1, c = 6, d = 7, e = 2, f = 0, g = 3, h = 8, i = 5. Và ta có kết quả như sau: 4 1 6 7 2 0 3 8 5 Bài 100/2002 - Mời khách dự tiệc (Dành cho học sinh THPT) program Guest; const Inp = 'Guest.inp'; Out = 'Guest.out'; var n: Integer; lSum: LongInt; t, v, p, Pred, Ind: array[0 1005] of Integer; Value: array[0 1005] of LongInt; Ok: array[0 1005] of Boolean; procedure ReadInput; var hFile: Text; i: Integer; begin Assign(hFile, Inp); Reset(hFile); Readln(hFile, n); Tin học & Nhà trường 100 Đề Toán - Tin học
8. 100 Problems & Solutions Page 160 end; if lSum1 > lSum2 then begin View := lSum1; Pred[n] := n - 1; end else begin View := lSum2; Pred[n] := n - 2; end; end; procedure Calculator(n: Integer); var i, j: Integer; begin if Pred[n] = n - 2 then begin Ok[n] := True; Inc(lSum); for i := Ind[n - 1] + 1 to Ind[n] do for j := Ind[p[i] - 1] + 1 to Ind[p[i]] do Calculator(p[j]) end else for i := Ind[n - 1] + 1 to Ind[n] do Calculator(p[i]) end; procedure WriteOutput; var hFile: Text; i: Integer; sView: LongInt; begin Assign(hFile, Out); Rewrite(hFile); sView := View(p[1]); Calculator(p[1]); Writeln(hFile, lSum, ' ', sView); for i := 1 to n do if Ok[i] then Writeln(hFile, i); Close(hFile); end; begin ReadInput; Prepare; WriteOutput; end. === The End === Tin học & Nhà trường 100 Đề Toán - Tin học