Năm học 2002-2003 Bài 1
tải về 440.12 Kb.
|
- Điều hướng trang này:
- Năm học 2004-2005 BÀI 1: KHOẢNG CÁCH GIỮA HAI SỐ Tên chương trình: DISTANCE.PAS
- Bài toán
- BÀI 2: TẠO BẢNG Tên chương trình: TABLE.PAS
- BÀI 3: TÌM NGHIỆM Tên chương trình: EQUA.PAS
- Năm học 2005-2006 Bài 1
- Yêu cầu
Lời giải Vấn đề quan trọng nhất trong bài toán này là xây dựng thủ tục tính khoảng cách giữa hai hình vuông một cách hiệu quả. Để viết thủ tục này, ta sẽ phân chia công việc cần thực hiện thành nhiều công việc con. Nhưng trước tiên cần nhận xét rằng, luôn tồn tại một đoạn thẳng ngắn nhất nối giữa hai hình vuông mà có ít nhất một đầu mút là một trong các đỉnh của hai hình vuông. Thật vậy, với một đoạn thẳng mà hai đầu mút đều không phải là đỉnh của hình vuông, ta có thể dời hai đầu mút sao cho đoạn thẳng mới không dài hơn đoạn thẳng cũ và ít nhất một đầu mút sẽ trở thành đỉnh của hình vuông. Vậy thủ tục tính khoảng cách giữa hai hình vuông sẽ được xây dựng từ trên xuống như sau:
Khi đã có thủ tục tính khoảng cách giữa hai hình vuông, ta chỉ cần duyệt qua tất cả các cặp hình vuông và chọn ra cặp có khoảng cách xa nhất. Do giới hạn của bài toán là số hình vuông N ≤ 2000 nên cách làm này là khả thi, thời gian chạy là O(N2). Sau này các bạn sẽ được tiếp cận các lời giải hiệu quả hơn. Chương trình: const MAXN=2020; finp='square.inp'; fout='square.out'; var x1, y1, x2, y2: array[1..MAXN] of longint; n, luui, luuj: longint; function min(a,b: longint): longint; begin if a
function kc(x,a,b: longint): longint; begin if (a<=x) and (x<=b) then kc:=0 else if (x else kc:=x-b; end; function kcdoan(x,y,y0,x1,x2: longint): longint; begin kcdoan:=sqr(y0-y)+sqr(kc(x,x1,x2)); end; function kchinhvuong(x,y,x1,y1,x2,y2:longint):longint; var kq: longint; begin
kq:=kcdoan(x,y,y1,x1,x2); kq:=min(kq,kcdoan(x,y,y2,x1,x2)); kq:=min(kq,kcdoan(y,x,x1,y1,y2)); kq:=min(kq,kcdoan(y,x,x2,y1,y2)); kchinhvuong:=kq; end;
function kc2hinh(i,j: longint): longint; var kq: longint; begin kq:=kchinhvuong(x1[i],y1[i],x1[j],y1[j],x2[j],y2[j]); kq:=min(kq,kchinhvuong(x1[i],y2[i],x1[j],y1[j],x2[j],y2[j])); kq:=min(kq,kchinhvuong(x2[i],y1[i],x1[j],y1[j],x2[j],y2[j])); kq:=min(kq,kchinhvuong(x2[i],y2[i],x1[j],y1[j],x2[j],y2[j])); if (i kc2hinh:=kq;
end;
var i: longint; begin
readln(n); end;
procedure xuly; var i, j, d, xanhat: longint; begin xanhat:=-1; for i:=1 to n-1 do for j:=i+1 to n do begin d:=kc2hinh(i,j); writeln(d); if d>xanhat then begin xanhat:=d; luui:=i; luuj:=j;
end; end;
end; begin
assign(input, finp); reset(input); assign(output, fout); rewrite(output); nhap; xuly;
writeln(luui,' ',luuj); close(input); close(output); end.
Năm học 2004-2005 BÀI 1: KHOẢNG CÁCH GIỮA HAI SỐ Tên chương trình: DISTANCE.PAS Với hai chữ số x và t, khoảng cách của chúng được định nghĩa là số nguyên không âm nhỏ nhất d(x,y) mà khi cộng thêm d(x,y) vào một chữ số nào đó trong hai chữ số x,y thì kết quả nhận được là một số nguyên có chữ số hàng đơn vị trùng với chữ số còn lại. Ví dụ: d(2,5)=3 vì 2+3=5, d(5,1)=4 vì 1+4=5, còn d(1,9)=2 vì 9+2 = 11. Với hai số nguyên dương X và Y có cùng số lượng chữ số, khoảng cách d(X,Y) giữa hai số X và Y là tổng khoảng cách giữa các cặp chữ số cùng hàng tương ứng. Ví dụ d(213,419)=d(2,4) + d(1,1) + d(3,9) = 2 + 0 + 4 = 6. Bài toán: Cho hai số X và Y có cùng lượng chữ số N (0 < N < 100), hãy tìm khoảng cách d(X,Y). Dữ liệu vào từ file văn bản DISTANCE.INP trong đó dòng đầu chứa số X; dòng thứ hai chứa số Y thỏa mãn dàng buộc của bài toán. Kết quả ghi ra file văn bản DISTANCE.OUT trong đóchứa một số nguyên duy nhất là kết quả d(X,Y) tìm được. Ví du:
Lời giải: Ta xây dựng hàm d(a,b) tính khoảng cách hai chữ số a và b theo định nghĩa của bài toán, sau đó dùng hàm này để tính tổng khoảng cách giữa các cặp chữ số của hai số. Hàm d(a,b) được thể hiện qua đoạn lệnh sau: function d(a,b:byte):byte; var i: byte; begin for i:=0 to 9 do {duyệt qua các chữ số từ 0 đến 9} if ((a+i) mod 10=b) or {nếu cộng thêm i vào a mà thu được b} ((b+i) mod 10=a) then {hoặc ngược lại...) begin d:=i; {trả về chữ số i} exit; end;
end; Chương trình: const
finp='distance.inp'; fout='distance.out'; function d(a,b:byte):byte; var i: byte; begin for i:=0 to 9 do if ((a+i) mod 10=b) or ((b+i) mod 10=a) then begin
d:=i; exit;
end; end;
var x, y: string; i,s: longint; begin
assign(input, finp); reset(input); assign(output, fout); rewrite(output); readln(x,y); s:=0;
for i:=1 to length(x) do s:=s+d(ord(x[i])-ord('0'),ord(y[i])-ord('0')); writeln(s); close(input); close(output); end.
BÀI 2: TẠO BẢNG Tên chương trình: TABLE.PAS Cho một bảng A gồm N x N số nguyên (N Phần tử của B nằm ở dòng I, cột j có giá trị bằng tổng của các số nằm trong ô (i,j) và các ô kề nó trong bảng A: Bij = Aij+A(i+1)j+A(i-1)j+Ai(j+1)+Ai(j-1) Chú ý: Các phần tử nằm ngoài bảng được xem như có giá trị bằng 0. Bài toán: Cho bảng A. Hãy tạo ra bảng B tương ứng. Dữ liệu vào cho trong file văn bản TABLE.INP trong đó :
Kết quả ghi ra file văn bản TABLE.OUT cho biết bảng B tạo được có định dạng cùng một qui cách với file input, nghĩa là: Dòng đầu chứ số N. Dòng thứ i trong N dòng tiếp theo chứa N số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng B. Các số trên cùng một dòng cách nhau bởi khỏang trắng. Ví dụ:
Lời giải: Ta in ra các phần tử của mảng B theo công thức như đề bài nêu: for i:=1 to n do begin for j:=1 to n do write(a[i,j]+a[i,j-1]+a[i-1,j]+a[i,j+1]+a[i+1,j],' '); writeln;
end; Khi cài đặt chú ý để khai báo dư ra các phần tử biên trên mảng A và đặt chúng bằng giá trị 0: var a: array[0..MAXN+1, 0..MAXN+1] of longint;{0,n+1 là chỉ số của các hàng, cột biên} ... fillchar(a,sizeof(a),0); {tất cả các phần tử, bao gồm phần tử biên sẽ bằng 0} Chương trình: const
finp='table.inp'; fout='table.out'; MAXN=105; var
a: array[0..MAXN+1, 0..MAXN+1] of longint; n,i,j: longint; begin assign(input, finp); reset(input); assign(output, fout); rewrite(output); fillchar(a,sizeof(a),0); readln(n); for i:=1 to n do for j:=1 to n do read(a[i,j]); writeln(n); for i:=1 to n do begin for j:=1 to n do write(a[i,j]+a[i,j-1]+a[i-1,j]+a[i,j+1]+a[i+1,j],' '); writeln; end;
close(input); close(output); end.
Xét một phương trình có dạng sau: x + y+ z =K trong đó K là một số nguyên dương. Phương trình này có thể có vô số nghiệm. Tuy nhiên, ở đây người ta chỉ quan tâm đến các nghiệm (x,y,z) mà trong đó các số x,y,z đều là các số nguyên tố. Nhắc lại: số tự nhiên p được gọi là số nguyên tố nếu p>1 và p chỉ chia hết cho 1 và chính nó. Bài toán: Với số K cho trước (K < 5000), hãy tìm tất cả các bộ số nguyên tố x,y,z (x Dữ liệu vào cho trong file văn bản EQUA.INP trong đó chứa duy nhất số K Kết quả ghi ra file văn bản EQUA.OUT chứa N + 1 dòng (N là số nghiệm tìm được), trong đó:
Ví dụ:
Lời giải Ta kiểm tra các số nguyên tố từ 1 đến 5000 (giá trị lớn nhất của K) rồi lưu vào một mảng: for i:=2 to MAXK do if (nguyento(i)) then begin {nếu i là số nguyên tố} inc(n); p[n]:=i; {lưu i vào mảng p} nt[i]:=true; {đặt lại cờ đánh dấu cho biết i là số nguyên tố} end;
Sau đó dùng hai vòng lặp qua mảng này để duyệt qua x và y. Mảng đánh dấu nt dùng để kiểm tra nhanh xem z=K-x-y có phải là số nguyên tố không: for i:=1 to n do {i là chỉ số của số nguyên tố x trong mảng p} for j:=i to n do {j là chỉ số của số nguyên tố y trong mảng p} begin
z:=k-p[i]-p[j]; {z=k-x-y} if (nt[z]) and (p[j] writeln(p[i], ' ',p[j],' ', z); {in ra x, y, z}
end;
const finp='equa.inp'; fout='equa.out';
MAXK=5010; function nguyento(n: longint): boolean;
var i: longint; begin
nguyento:=false; nguyento:=true; end; var n, k, i, j, z: longint; nt: array[2..MAXK] of boolean; p: array[1..MAXK] of longint; begin assign(input, finp); reset(input); assign(output, fout); rewrite(output); fillchar(nt,sizeof(nt),0); for i:=2 to MAXK do if (nguyento(i)) then begin inc(n); p[n]:=i;
nt[i]:=true; end;
readln(k); for i:=1 to n do for j:=i to n do begin
z:=k-p[i]-p[j]; if (nt[z]) and (p[j] writeln(p[i], ' ',p[j],' ', z);
end;
close(input); close(output);
end.
Cho hai mảng số nguyên dương A và B lần lượt có N và M số (0 < N, M <50 000). Các phần tử trong cả hai mảng A và B đều được sắp theo thứ tự tăng dần. Dòng đầu của file A.INP chứa số N. Mỗi dòng trong N dòng tiếp theo chứa 1 số nguyên dương ứng với các phần tử của mảng A. Dòng đầu của file B.INP chứa số M. Mỗi dòng trong M dòng tiếp theo chứa 1 số nguyên dương ứng với các phần tử của mảng B.
Ví dụ:
1
2 2
4 2
2 5
Lời giải Trong bài toán này ta hoàn toàn không cần lưu trữ mảng A và B vào bộ nhớ. Thuật toán của ta sẽ đọc lần lượt các số từ hai mảng A, B, xử lý và in ra trực tiếp mảng C. Ta quản lý hai biến chạy i và j tương ứng trên mảng A và B. Ban đầu i và j được gán giá trị 1, nghĩa là vị trí đầu tiên của mảng. Tại một thời điểm, biến chạy i, j cho biết ta đã đọc đến phần tử Ai và Bj. Quy tắc tăng giá trị biến chạy là như sau:
{biến a, b chỉ phần tử đang xét Ai, Bj trên hai mảng} if (a<=b) then {điều kiện Ai ≤ Bj} begin writeln(fc,a); {in ra Ai như là phần tử tiếp theo của mảng C} inc(i); {tăng biến i} if (i<=n) then {nếu vẫn chưa đọc hết mảng A} readln(fa,a) {đọc số mới} else
a:=maxlongint; {nếu đã đọc hết mảng A, gán a giá trị bằng ∞ để sau này khi so sánh, chỉ các phần tử của mảng B mới được xét} end else begin ... {tương tự cho trường hợp Ai > Bj} end;
Thuật toán kết thúc khi ta đã đọc hết các số, nghĩa là khi hai biến chạy đều vượt ra khỏi phạm vi của mảng: i > N và j > M. Ta có thể dùng vòng lặp while sau đây để kiểm tra điều kiện này: while (i<=n) or (j<=m) do begin ... end;
Thời gian chạy của thuật toán là tuyến tính theo số phần tử của hai mảng: O(M+N). Chương trình: var fa,fb,fc: text; n, m, i, j, a, b: longint; begin
assign(fa,'a.inp'); reset(fa); assign(fb,'b.inp'); reset(fb); assign(fc,'c.out'); rewrite(fc); readln(fa,n); readln(fb,m); i:=1; readln(fa,a); j:=1; readln(fb,b); while (i<=n) or (j<=m) do begin if (a<=b) then begin writeln(fc,a); inc(i); if (i<=n) then readln(fa,a) else
a:=maxlongint; end else begin writeln(fc,b); inc(j);
if (j<=m) then readln(fb,b) else b:=maxlongint; end; end;
close(fa); close(fb); close(fc); end.
Bài 2:Hình chữ nhật Cho N hình chữ nhật (2 Dòng đầu chứa số N. Dòng thứ I trong N dòng tiếp theo mô tả hình chữ nhật thứ I, chứa 4 số nguyên x1, y1, x2, y2 ứng với các hòanh độ và tung độ của các hình chữ nhật (-10000< x1, < x2 <10000; -10000< y1, < y2 <10000).
Ví dụ:
1 1 5 5
10 10 1000 1000 Chúng ta cần viết thủ tục tính diện tích phần giao giữa hai hình chữ nhật. Chú ý phần giao của hai hình chữ nhật cũng là một hình chữ nhật và có chiều dài/rộng bằng phần giao của hai chiều dài/rộng tương ứng. Do đó ta chỉ cần viết thủ tục tìm phần giao giữa hai đoạn thẳng trên trục số và sử dụng. Thủ tục sau tìm giao giữa hai đoạn thẳng (a1,b1) và (a2,b2) trên trục số:
function giaodoan(a1,b1,a2,b2:longint):longint; begin
if (b1<=a2) or (a1>=b2) then else
giaodoan:=min(b1,b2)-max(a1,a2); {hai đoạn giao nhau} end;
Thủ tục giaohcn sau áp dụng thủ tục giaodoan để tìm diện tích phần giao của hai hình chữ nhật: function giaohcn(i,j: longint): longint; begin {phần giao là một hình chữ nhật có chiều dài/rộng là phần giao của hai chiều dài/rộng ban đầu} giaohcn:=giaodoan(x1[i],x2[i],x1[j],x2[j])*giaodoan(y1[i],y2[i],y1[j],y2[j]); end;
Sau khi có thủ tục tính diện tích phần giao giữa hai hình chữ nhật, ta xét qua tất cả các cặp hình chữ nhật và chọn ra cặp có phần giao lớn nhất: for i:=1 to n-1 do for j:=i+1 to n do begin
s:=giaohcn(i,j); if s>kq then {tìm được hai hình có diện tích phần giao lớn hơn} begin kq:=s; {cập nhật kết quả} luui:=i; {lưu lại chỉ số của hai hình} luuj:=j;
end; end;
Chương trình: const MAXN=505; finp='hcn.inp'; fout='hcn.out'; var x1,y1,x2,y2: array[1..MAXN] of longint; function min(a,b:longint):longint;begin if a function max(a,b:longint):longint;begin if a>b then max:=a else max:=b; end; function giaodoan(a1,b1,a2,b2:longint):longint; begin
if (b1<=a2) or (a1>=b2) then giaodoan:=0 else giaodoan:=min(b1,b2)-max(a1,a2); end;
function giaohcn(i,j: longint): longint; begin
giaohcn:=giaodoan(x1[i],x2[i],x1[j],x2[j])*giaodoan(y1[i],y2[i],y1[j],y2[j]); end;
var n, kq, s, i, j, luui, luuj: longint; begin
assign(input,finp); reset(input); assign(output,fout); rewrite(output); kq:=0; readln(n); for i:=1 to n do readln(x1[i],y1[i],x2[i],y2[i]); for i:=1 to n-1 do for j:=i+1 to n do begin s:=giaohcn(i,j); if s>kq then begin
kq:=s; luui:=i;
luuj:=j; end;
end; writeln(kq); writeln(luui,' ',luuj); close(input); close(output); end.
Bài 3: So sánh Cho 2 số nguyên dương A,B (0 Yêu cầu: hãy so sánh giá trị của 2 số. Dữ liệu cho trong file văn bản có tện SO.INP gồm 2 dòng: Dòng đầu chứa số A. Dòng thứ 2 chứa số B.
Ví dụ:
Lời giải: Thủ tục so sánh hai số A, B có thể được xây dựng như sau:
while (length(a)
for i:=1 to length(a) do if (a[i] sosanh:=-1; {kết luận A < B}
exit; {thoát khỏi thủ tục} end else if (a[i]>b[i]) then
begin
exit; {thoát khỏi thủ tục} end;
sosanh:=0; {kết luận A = B} const finp='so.inp'; fout='so.out'; function sosanh(a,b:string):longint; var i: longint; begin
while (length(a) for i:=1 to length(a) do if (a[i] sosanh:=-1;
exit;
begin
exit;
sosanh:=0; end;
var
begin
assign(input,finp); reset(input); assign(output,fout); rewrite(output); readln(a); readln(b); writeln(sosanh(a,b)); close(input); close(output); end.
Каталог: UserFiles -> HEAD393 -> news -> attachment UserFiles -> PHƯƠng pháp viết nghiên cứu khoa họC Ứng dụng sư phạM UserFiles -> 29 Thủ tục công nhận tuyến du lịch cộng đồng UserFiles -> BÀi phát biểu củA ĐẠi diện sinh viên nhà trưỜng sv nguyễn Thị Trang Lớp K56ktb UserFiles -> BỘ XÂy dựNG UserFiles -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập – Tự do – Hạnh phúc UserFiles -> BỘ XÂy dựng số: 10/2013/tt-bxd cộng hoà XÃ HỘi chủ nghĩa việt nam UserFiles -> CỘng hòa xã HỘi chủ nghĩa việt nam kho bạc nhà NƯỚC Độc lập Tự do Hạnh phúc UserFiles -> MÔn toán bài 1: Tính a) (28,7 + 34,5) X 2,4 b) 28,7 + 34,5 X 2,4 Bài 2: Bài toán UserFiles -> CỦa bộ trưỞng bộ VĂn hóa thông tin về việc thành lập tạp chí di sản văn hóa thuộc cục bảo tồn bảo tàng bộ trưỞng bộ VĂn hóa thông tin attachment -> PHÂn công trực nội trú Từ 01/09/2014 đến hết 30/09/2014 tải về 440.12 Kb. Chia sẻ với bạn bè của bạn:
| ||||||||||||||||||||||||||||||||||||||||||||||
100), các dòng được đánh số từ trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 30000. Bảng B được tạo ra từ bảng A theo qui tắc sau: