TỔNG QUAN BÀI THI
Hãy lập trình giải các bài toán sau:
Bài 4:
Số nguyên tố. (6 điểm)
Cho một bảng số C có kích thước nxn (n ≤ 100).
Mỗi ô của bảng số chứa một số nguyên dương m bất kỳ.
Yêu cầu: Tìm tất cả
các số nguyên tố trong bảng số đã cho. Nếu không tồn tại số nguyên tố nào thì
thông báo ‘khong tim thay’.
Dữ liệu
vào: Từ file văn bản NGUYENTO.INP
gồm:
- Dòng đầu là số nguyên dương n.
- n dòng tiếp theo, mỗi dòng n số nguyên dương (bảng
số C).
(các số trên một dòng cách nhau ít nhất một khoảng
trắng)
Dữ liệu
ra: Đưa vào file văn bản
NGUYENTO.OUT gồm:
- Dòng đầu là số lượng các số nguyên tố tìm được hoặc
‘khong tim thay’.
- Dòng tiếp theo ghi các số nguyên tố tìm được.
Ví dụ:
Bài 5: Ma phương. (7 điểm)
Một ma phương (còn gọi là ma trận kỳ ảo bậc n hay hình
vuông ma thuật) là một cách sắp xếp n² số, thường là các số nguyên
phân biệt, trong một bảng vuông sao cho tổng n số trên mỗi hàng, cột, và đường
chéo đều bằng nhau. Ma phương chuẩn là ma phương chỉ chứa các số nguyên từ 1
đến n².
Yêu cầu:
Hãy lập một ma phương chuẩn với n là số lẻ.
Dữ liệu vào:
Từ file văn bản MAPHUONG.INP chứa số nguyên dương n (n lẻ).
Dữ liệu
ra: Đưa vào file văn bản MAPHUONG.OUT
chứa ma phương chuẩn.
Ví dụ:
Bài 6: Du lịch. (7 điểm)
Có n thành phố, các thành phố được đánh số hiệu từ 1
đến n. Một nhóm du khách muốn đi du lịch từ thành phố a đến thành phố b và sau
đó trở về a, nhóm người đó muốn rằng trên đường từ b về a sẽ không đi qua những
thành phố mà họ đã đi trên đường từ a đến b.
Yêu cầu: Hãy tìm một hành trình theo điều kiện trên với chi
phí là nhỏ nhất.
Dữ liệu
vào: Từ file văn bản DULICH.INP gồm:
- Dòng đầu ghi 3 số nguyên dương n, a, b (n ≤ 100; a,
b ≤ n).
- Các dòng tiếp theo, mỗi dòng ghi 3 số nguyên dương
i, j, k có nghĩa là đi từ thành phố i đến thành phố j với chi phí là k.
(các số trên một dòng cách nhau ít nhất một khoảng
trắng)
Dữ liệu
ra: Đưa vào file văn bản DULICH.OUT gồm 2 dòng
- Dòng đầu ghi tổng chi phí phải đi hoặc ‘khong tim
duoc duong di’.
- Dòng tiếp theo ghi số hiệu các thành phố đi qua theo
hành trình tìm được.
Ví dụ:
---Hết---
Ghi chú:
·
Thí sinh không được sử dụng tài liệu.
·
Giám thị không giải thích gì thêm.
|
ĐÁP ÁN:
BÀI 1:
program so_nguyen_to;
const fi='nguyent3.inp';
fo='nguyent3.out';
var n,m,i,j:byte;
a:array[1..50,1..50]of byte;
procedure nhap;
var f:text;
begin
assign(f,fi);reset(f);
readln(f,n);
for i:=1 to n do
begin
for j:=1 to n do read(f,a[i,j]);
readln(f);
end;
close(f);
end;
function ok(i:byte):boolean;
var b:boolean; j:byte;
begin
b:=true;
for j:= 2 to i-1 do
if i mod j=0 then begin b:=false; break; end ;
ok:=b;
end;
procedure xuly;
var dem:byte; f:text;
begin
dem:=0;
assign(f,fo); rewrite(f);
for i:=1 to n do
for j:=1 to n do
if ok(a[i,j]) then
dem:=dem+1;
if dem>0 then
writeln(f,dem);
for i:=1 to n do
for j:=1 to n do
if ok(a[i,j]) then
write(f,a[i,j],' ');
if dem=0 then writeln(f,'khong tim thay');
close(f);
end;
begin
nhap;
xuly;
end.
BÀI 2:
const fi='maphuon3.inp';
fo='maphuon3.out';
Var A:Array[1..200,1..200] Of Word;
n,i,j,k:Word;
f,g:text;
procedure nhap;
Begin
assign(f,fi); reset(f);
readln(f,n);
i:=n DIV 2 + 1;
j:=n DIV 2 + 2;
For k:=1 To n*n Do
Begin
A[i,j]:=k;
If k MOD n=0 Then j:=j+2
Else Begin
j:=j+1; i:=i-1;
End;
If j>n Then j:=j MOD n;
If i=0 Then i:=n;
End;
assign(g,fo); rewrite(g);
For i:=1 To n Do
Begin
For j:=1 To n Do write(g,a[i,j]:4);
Writeln(g);
End;
close(f); close(g);
End;
begin
nhap;
end.
BÀI 3:
program dulich;
const fi='dulich3.inp';
fo='dulich3.out';
max=100;
vc=1e6;
Var n,a,b,sl:byte;
c:array[1..max,1..max]of real;
d:array[1..max]of byte;
x,lx:array[0..max]of byte;
tien:array[0..max]of real;
mint:real;
g:text;
procedure nhap;
var i,j:integer;
k:real;
f:text;
begin
assign(f,fi); reset(f);
readln(f,n,a,b);
for i:=1 to n do
for j:=1 to n do
if i=j then c[i,j]:=0 else c[i,j]:=vc;
while not seekeof(f) do
begin
readln(f,i,j,k);
c[i,j]:=k;
c[j,i]:=k;
end;
close(f);
end;
procedure khoitao;
var i:integer;
begin
mint:=vc;
for i:=1 to n do d[i]:=0;
x[0]:=a;
d[a]:=1;
tien[0]:=0;
end;
function dijkstra(s:byte):real;
var l:array[1..max]of real;
min:real;
p,i:byte;
begin
d[a]:=0; d[s]:=0;
for i:=1 to n do l[i]:=vc;
l[s]:=0;
repeat
min:=vc; p:=0;
for i:=1 to n do
if (d[i]=0)and(l[i]<min) then
begin
min:=l[i];
p:=i;
end;
if( p=0)or (p=a) then break;
d[p]:=2;
for i:=1 to n do
if (d[i]=0) and (l[i]>l[p]+c[p,i]) then
l[i]:=l[p]+c[p,i];
until false;
for i:=1 to n do
if d[i]=2 then d[i]:=0;
d[a]:=1; d[s]:=1;
dijkstra:=l[a];
end;
procedure try(i:integer);
var j:integer;
l:real;
begin
for j:=1 to n do
if (d[j]=0) and(c[x[i-1],j]<>vc) then
begin
x[i]:=j; d[j]:=1;
tien[i]:=tien[i-1]+c[x[i-1],j];
l:=tien[i]+dijkstra(j);
if l<mint then
begin
if j=b then
begin
mint:=l;
sl:=i;
lx:=x;
end
else try(i+1);
end;
d[j]:=0;
end;
end;
procedure dijkstra2;
var l:array[1..max] of real;
tr:array[1..max] of byte;
min:real;
p,i:byte;
begin
d[a]:=0;
for i:=1 to n do
begin
l[i]:=vc;
tr[i]:=0;
end;
l[a]:=0;
repeat
min:=vc;
p:=0;
for i:=1 to n do
if (d[i] =0) and(l[i]<min) then
begin
min:=l[i];
p:=i;
end;
if p=b then break;
d[p]:=1;
for i:=1 to n do
if (d[i]=0)and(l[i]>l[p]+c[p,i])then
begin
l[i]:=l[p]+c[p,i];tr[i]:=p;
end;
until false;
p:=tr[b];
while p<>0 do
begin
write(g,p,' ');
p:=tr[p];
end;
end;
procedure xuat;
var i:integer;
begin
assign(g,fo); rewrite(g);
if mint=vc then writeln(g,'Khong tim duoc')
else
begin
writeln(g,mint:1:0);
for i:=0 to sl do write(g,lx[i],' ');
for i:=1 to n do d[i]:=0;
for i:=1 to sl-1 do d[lx[i]]:=1;
dijkstra2;
end;
close(g);
end;
begin
nhap;
khoitao;
try(1);
xuat;
end.
Xin cảm ơn vì những bài viết cũng khá hay và bổ ích cho học sinh và giáo viên tin học.
Trả lờiXóaAnh Hồng Dân ơi? anh cho em xin đề cương ôn thi olimpic mà anh ôn cho học sinh lớp 10 và 11 đi. lúc đi tập huấn là anh sẽ nhiệt tình trợ giúp đó. anh gởi qua gmail dùm: buiphuocloi83@gmail.com ; xin cảm ơn anh nhiều.
Cám ơn Thầy rất nhiều! Chúc Thầy nhiều sức khỏe để cống hiến cho GD nhất kaf với bộ môn tin học này!
Trả lờiXóaCảm ơn thầy rất nhiều, thầy up thêm các đề thi những năm gần đây nhé thầy, cho thầy cô ôn học sinh giỏi tham khảo ạ. Chúc thầy nhiều sức khõe!
Trả lờiXóa