Tài liệu Bài Tập Tin học chọn lọc ppt

Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

4
Begin
If (Can1=Can2) and (Can1>0) then Print
Else
For J:=1 to Soqua do
If Chon[j]=0 then
Case Can1<Can2 Of
True:Begin
Chon[j]:=1;
Inc(K1);Luu1[k1]:=Qua[j];
Can1:=Can1+Qua[j];
Tim(J);
Chon[j]:=0;
Dec(K1);
Can1:=Can1-Qua[j];
End;
False:Begin
Chon[j]:=1;
Inc(K2);Luu2[k2]:=Qua[j];
Can2:=Can2+Qua[j];
Tim(J);
Chon[j]:=0;
Dec(K2);
Can2:=Can2-Qua[j];
End;
End;
End;
{*********************************************************************}
Begin
Clrscr;Randomize;
Input;
Tim(0);
Readln;
End.
{(Chai mang ty le 1:k);Tim cach chia A[1 N] cho truoc thanh hai doan
co tong cac phan tu trong doan nay gap k lan tong cac phan tu trong doan
kia ,K nguyen duong
GIAI THUAT:Tim tong cua toan bo cac phan tu
Neu tong chia het cho K+1 phan thi
+ Tinh gia tri cua phan 1:TB=Tong div (K+1);
+ Tim nhung so trong day co tong la TB}
Program baitap3;
Uses Crt;
Const Mn=100;
Type Arr=Array[1 MN]of integer;
Arrbool=Array[1 MN]of Boolean;
Var A,Luu:arr;N,K,Dem,Gap:Byte;Sum,Tong,Trungbinh:Integer;Chon:Arrbool;
{********************************************************************}
Procedure Input;
Var I:Byte;
Begin
Write('Nhap N:');Readln(N);
Write('Nhap K:');Readln(Gap);
Tong:=0;
For I:=1 to N do
Begin
A[i]:=random(10);
Write(A[i]:4);
Tong:=Tong+A[i];
End;
End;
{********************************************************************}
Procedure Print;
Var J:Byte;
Begin
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

5
If Sum=Trungbinh then
Begin
For J:=1 to K do Write(Luu[j]:4);Write(' ');
For J:=1 to N do If Chon[j]=False then Write(j:4);Writeln;
For J:=1 to K do Write(A[Luu[j]]:4);Write(' ');
For J:=1 to N do If Chon[j]=False then Write(A[j]:4);
Writeln;
Inc(Dem);
End;
End;
{********************************************************************}
Procedure Tim(I:byte);
Var J:Byte;
Begin
If Sum>=Trungbinh then Print
Else
For J:=1 to N do
If (Chon[j]=False) and (J>i) then
Begin
Inc(K);
Luu[K]:=J;
Sum:=Sum+A[j];
Chon[j]:=True;
Tim(J);
Dec(K);
Chon[j]:=False;
Sum:=Sum-A[j];
End;
End;
{********************************************************************}
Procedure Tim1(I:byte);
Var J:Byte;
Begin
If Sum=Trungbinh then Print
Else
For J:=1 to N do
If (Chon[j]=False) and (J>i) then
Begin
Inc(K);
Luu[K]:=J;
Sum:=Sum+A[j];
Chon[j]:=True;
Tim(J);
Dec(K);
Chon[j]:=False;
Sum:=Sum-A[j];
End;
End;
{********************************************************************}
Begin
Clrscr;
Randomize;
Repeat
Input;
Writeln;
Writeln('Tong=',tong);
If (Tong mod (Gap+1))=0 then
Begin
Dem:=0;
Fillchar(Chon,Sizeof(chon),False);
K:=0;
Sum:=0;
Trungbinh:=Tong div (Gap+1);
Tim(1);
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

6
End;
Until Dem>0;
Readln;
End.

program ma_tran_chuyen_vi;
uses crt;
const dim=20;
type mang=array[1 dim,1 dim] of integer;
var a:mang;
n:integer;
procedure nhap(var a:mang;var n:integer);
var i,j:integer;
begin
write('Kich thuoc ma tran : ');readln(n);
for i:=1 to n do
for j:=1 to n do a[i,j]:=random(99);
end;
procedure xuat;
var i,j:integer;
begin
writeln;
for i:=1 to n do
begin
for j:=1 to n do write(a[i,j]:3);
writeln;
end;
end;
procedure chuyenvi(var a:mang;n:integer);
var i,j,k,tg,m:integer;
begin k:=1;m:=n;
for i:=1 to n div 2 do
begin
for j:=k to m-1 do
begin
tg:=a[i,j];
a[i,j]:=a[j,m];
a[j,m]:=a[m,n-j+1];
a[m,n-j+1]:=a[n-j+1,k];
a[n-j+1,k]:=tg;
end;
inc(k);
dec(m);
end;
end;
begin clrscr;
randomize;
nhap(a,n);
xuat;
chuyenvi(a,n);
xuat;
readln
end.
{De-so-153:Cho M loai tien voi gia tri tu nhien A1,A2, ,Am va 1 gia tri tien
N(tu nhien).Viet thuat toan va chuong trinh de tinh tat cac cach bieu dien N
thanh M loai tien ke tren
Giai thuat:Quay lui(Back tracking)}
Program De154;
Uses Crt;
Const MN=100;
Type Arr=Array[1 MN]of integer;
ArrBool=Array[1 MN]of Boolean;
Var A,Luu:arr;Tong,N:Integer;M,K:Byte;
{***********************************************************************}
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

7
Procedure Input;
Var I:Byte;
Begin
Write('Nhap So loai tien:');Readln(M);
Write('Nhap so tien can doi:');Readln(N);
For I:=1 to M do
Begin
A[i]:=Random(10)+1;
Write(A[i]:4);
End;
Writeln;
K:=0;
Tong:=0;
End;
{***********************************************************************}
Procedure Print;
Var J:Byte;
Begin
For J:=1 to K do
Write(Luu[J]:4);
Writeln;
End;
{***********************************************************************}
Procedure Tim(I:Byte);
Var J:Byte;
Begin
If Tong=N then Print
Else
For J:=1 to M do
If (Tong+A[j]<=N) and (J>I) then
Begin
Tong:=Tong+A[j];
Inc(K);
Luu[k]:=A[j];
Tim(J);
Dec(K);
Tong:=Tong-A[j];
End;
End;
{***********************************************************************}
Begin
Clrscr;
Randomize;
Repeat
Input;
Tim(1);
Until False;
Readln;
End.
{De_so_158:O mot dat nuoc co N thanh pho.Giua cac thanh pho co cac tuyen duong
(1 chieu).Biet rang:
1) Giua hai thanh pho bat ky co the di den nhau (co the qua nhieu tuyen
duong).
2) Tu 1 thanh pho so cac duong di ra bang so cac duong di vao.
Lap thuat toan tim mot con duong xuat phat tu 1 thanh pho nao do ,di qua tat
ca cac tuyen duong ,moi tuyen duong 1 lan ,cuoi cung tro ve thanh pho ban dau
GIAI THUAT:Quay lui}
Program De_so_158;
uses crt;
const n=5;
type so=0 1;
arr=array[1 n,1 n]of so;
arr1=array[1 n]of byte;
arr2=array[1 n]of boolean;
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

8
var A:arr;{Quan he cua Thanh pho I voi J}
TD:arr1;{Luu tru thanh pho da di qua}
Ok:arr2;{Kiem tra thnh pho da duoc di qua}
K:byte;
dem:byte;{So duong di}
{**********************************************************************}
Procedure Nhap;
var i,j:byte;
begin
for i:=1 to n do
for j:=i to n do
if i=j then a[i,j]:=0
else
begin
a[i,j]:=random(2);
a[j,i]:=a[i,j];
end;
for i:=1 to n do
begin
for j:=1 to n do write(a[i,j]:4);
writeln;
end;
end;
{**********************************************************************}
Procedure Print;
var j:byte;
begin
if A[TD[n],Td[1]]=1 then {Kiem tra thanh pho cuoi cung voi thanh pho
dau tien di qua co
duong di voi nhau khong}
begin
inc(dem);{Tang so duong di}
for j:=1 to n do write(Td[j]:4);
writeln(Td[1]:4);
end;
end;
{**********************************************************************}
Procedure Truyhoi(i:byte);
var j:byte;
begin
if k=n then print
else
for j:=1 to n do
if (a[i,j]=1) and Ok[j] then
{Dieu kien de di tu TP I de TP J la hai thanh pho phai thong nhau
Va thanh pho J chua di qua}
begin
Inc(k);
TD[k]:=j;{luu tru thanh pho duoc di qua}
Ok[j]:=false;{Thanh pho J da di qua}
truyhoi(j);{Xet thanh pho J voi thanh pho chua duoc
chon}
dec(k);
Ok[j]:=true;{Xoa bo viec ghi thanh Tp J da duoc di
qua}
end;
end;
{**********************************************************************}
Begin
clrscr;
randomize;
repeat
clrscr;
nhap;
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

9
dem:=0;
fillchar(Ok,sizeof(ok),true);
Ok[2]:=false;k:=1;
Td[1]:=2;{Xuat phat tu thanh pho thu 2}
writeln('Cac cach di:');
truyhoi(2);
if dem=0 then writeln('Khong co cach di nao')
else writeln('Co ',dem,' cach di');
until dem>0;
readln;
end.
{Co N nguoi va N cong viec.Goi Cij la cong suc lam viec j cua nguoi i.Lap
chuong trinh
de sap xep moi nguoi 1 cong viec sao cho cong suc bo ra la it nhat
THUAT TOAN: Vet can tat ca cac truong hop xay ra .Chon truong hop toi uu}
Program baitoan_congviec;
Uses crt;
Const mn=7;
Type arr=array[1 mn,1 mn] of word;
arr1=array[1 mn] of word;
arrbol=array[1 mn] of boolean;
Var C:arr;{Cong suc lam viec}
A:arr1;{Chua cong viec duoc chon khi xet tung truong hop}
B:arr1;{Luu lai ket qua cong viec duoc chon tam thoi}
j,n:byte;
Tong:word;{Chua tong cac cong viec cua tung buoc chon}
min:word;{Giu gia tri de tim ra TONG cac cong viec nho nhat}
Chon:arrbol;{keim tra xem Cong Viec do duoc chon hay chua}
{***************************************************************************}
Procedure nhap;
Var i,j:byte;
Begin
n:=mn;
for i:=1 to n do
Begin
for j:=1 to n do
Begin
c[i,j]:=random(10)+1;
write(c[i,j]:4);
End;
writeln;
End;
End;
{***************************************************************************}
Procedure Output;
Var J:byte;
Begin
If tong<min then
Begin
min:=tong;{So sanh de tim ra TONG nho nhat}
for j:=1 to n do b[j]:=a[j];{Giu lai suc lam
viec cau nguoi j}
End;
End;
{***************************************************************************}
Procedure truyhoi(i:byte);
var j,k:byte;
begin
if i=n+1 then Output
Else
for j:=1 to n do
if Chon[j]=False then {Neu cong viec chua duoc chon}
Begin
A[i]:=j;{Nguoi thu i se chon cong viec j}
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

10
Tong:=Tong+C[i,j];{Tinh TONG cac cong suc lam viec cua
nguoi i voi viec j}
Chon[j]:=true;{Danh dau cong viec J duoc chon}
Truyhoi(i+1);{Xet nguoi tiep theo}
Tong:=Tong-c[i,j];{Bot lai cong suc lam viec J cua
nguoi I}
Chon[j]:=False;{Tra lai cong viec J}
End;
end;
{***************************************************************************}
Begin
clrscr;
randomize;
Nhap;
writeln;
Fillchar(Chon,Sizeof(chon),False);
Min:=65000;{Xuat phat gia tri ban dau cua Min}
Tong:=0;
Truyhoi(1);
writeln('Cong viec duoc sap xep lai la:');
write('Nguoi thu :');for j:=1 to n do write(j:4);writeln;
write('Cong viec :');for j:=1 to n do write(b[j]:4);writeln;
write('Suc Lam :');for j:=1 to n do write(c[j,b[j]]:4);writeln;
writeln('Cong suc bo ra la:',min);
Readln;
end.
{De 211:Cho truoc so tu nhien N.Lap thuat toan cho biet N co the bieu dien
thanh tong cua hai hay nhieu so tu nhien lien tiep hay khong?
Trong truong hop co ,hay the hien tat ca cac cach co the co.
GIAI THUAT:Vet can tat cac cac truong hop xay voi dieu kien so duoc
chon sau phai lon hon so duoc chon truoc}
Program De_so_211;
uses crt;
var a:array[1 255]of byte;{Chua cac so duoc chon}
n:byte;{So muon phan tich}
k:byte;{So luong So duoc chon}
tong:byte;{Chua tong cac so duoc chon ,de so sanh voi N}
solan:word;{So luong cac cach bieu dien}
{******************************************************************}
Procedure print;
var j:byte;
begin
solan:=solan+1;{Tang so cach bieu dien}
write('Cach thu ',solan,':');
for j:=1 to k do begin write(a[j]);if j<k then write('+');end;
writeln('=',n);
if (solan mod 24)=0 then begin
readln;clrscr;
writeln('Press Enter to continue');readln;
end;
end;
{******************************************************************}
Procedure tim(i:byte);
var j:byte;
begin
if tong=n then print
else for j:=1 to n-1 do
if (j+tong<=n) and (i<j) then
{Dieu kien de so duoc chon:So do cong voi tong cu <=N,So chon sau
phai
lon hon so chon truoc}
begin
tong:=tong+j;{Cong so duoc chon vao tong}
inc(k);
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

11
a[k]:=j;{Ghi nhan so duoc chon}
Tim(j);{Tim so tiep theo}
dec(k);{Lui lai}
tong:=tong-j;{Bot di so j de quay lui}
end;
end;
{******************************************************************}
Begin
clrscr;
solan:=0;
write('N:');readln(n);
writeln('Voi N=',n,' ta co cac cach phan tich thanh tong cac so tu
nhien');
tong:=0;k:=0;
tim(0);
writeln('Co tat cac ',solan,' cach');
readln;
end.
{De 211:Cho truoc so tu nhien N.Lap thuat toan cho biet N co the bieu dien
thanh tong cua hai hay nhieu so tu nhien lien tiep hay khong?
Trong truong hop co ,hay the hien tat ca cac cach co the co.
GIAI THUAT:Vet can tat cac cac truong hop xay voi dieu kien so duoc
chon sau phai lon hon so duoc chon truoc}
Program De_so_211;
uses crt;
var a:array[1 255]of byte;{Chua cac so duoc chon}
n:byte;{So muon phan tich}
k:byte;{So luong So duoc chon}
tong:byte;{Chua tong cac so duoc chon ,de so sanh voi N}
solan:word;{So luong cac cach bieu dien}
{******************************************************************}
Procedure print;
var j:byte;
begin
solan:=solan+1;{Tang so cach bieu dien}
write('Cach thu ',solan,':');
for j:=1 to k do begin write(a[j]);if j<k then write('+');end;
writeln('=',n);
if (solan mod 24)=0 then begin
readln;clrscr;
writeln('Press Enter to continue');readln;
end;
end;
{******************************************************************}
Procedure tim(i:byte);
var j:byte;
begin
if tong=n then print
else for j:=1 to n-1 do
if (j+tong<=n) and (i<j) then
{Dieu kien de so duoc chon:So do cong voi tong cu <=N,So chon sau
phai
lon hon so chon truoc}
begin
tong:=tong+j;{Cong so duoc chon vao tong}
inc(k);
a[k]:=j;{Ghi nhan so duoc chon}
Tim(j);{Tim so tiep theo}
dec(k);{Lui lai}
tong:=tong-j;{Bot di so j de quay lui}
end;
end;
{******************************************************************}
Begin
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

12
clrscr;
solan:=0;
write('N:');readln(n);
writeln('Voi N=',n,' ta co cac cach phan tich thanh tong cac so tu
nhien');
tong:=0;k:=0;
tim(0);
writeln('Co tat cac ',solan,' cach');
readln;
end.
{Co N ban trai va N ban gai cung den 1 cuoc khieu vu .Biet rang moi ban trai
quen voi 2 ban gai va moi ban gai quen voi 2 ban trai.Lap cach chia 2N ban tran
thanh N doi nhay sao cho moi doi nhay gom 2 ban da quen nhau
GIAI THUAT:Quay lui.
Ban Nu nao da duoc moi khieu vu cung voi nguoi ban trai
ma minh quen thi ban do khong duoc chon nua.Neu chon
duoc dung N cap thi Print,neu khong thi quay lai chon
cach khac}
Program De_so_216;
uses crt;
const n=8;{So cap}
type arr=array[1 n,1 n]of byte;
var A:arr;{Quan he cua N ban nam va N ban nnu}
dem:byte;{Dem so lan chon}
dance:array[1 n]of boolean;{Xet xem ban Nu duoc chon chua}
nguoi:array[1 n]of integer;{Luu tru lai nhung ban nu duoc chon}
{************************************************************}
Procedure readfile;
var f:text;i,j:byte;
begin
assign(f,'a:\216.dat');
reset(f);
i:=0;
while not eof(f) do
begin
inc(i);j:=0;
while not eoln(f) do
begin
inc(j);
read(f,A[i,j]);
gotoxy(j*7,i+1);
write(A[i,j]);
end;
readln(f);
end;
end;

{************************************************************************}
Function Ok(a:arr):boolean;
{Kiem tra xem quan he ban dau co dung qui dinh khong:
2 nam quen voi 2 nu va nguoc lai}
var tong1,tong2,i,j:byte;
begin
Ok:=false;
for i:=1 to n do
begin
tong1:=0;tong2:=0;
for j:=1 to n do
begin
if a[i,j]=1 then tong1:=tong1+1;
if a[j,i]=1 then tong2:=tong2+1;
if (tong1>2) or (tong2>2) then exit;
end;
end;
Mét sè bμi to¸n Tin häc chän läc NguyÔn §×nh ChiÕn

13
Ok:=true;
end;
{************************************************************************}
Procedure Print;
var j:byte;
begin
inc(dem);
writeln('Cach chon thu ',dem,':');
write('Nam:');for j:=1 to n do write(j:2);writeln;
write('Nu :');for j:=1 to n do write(nguoi[j]:2);readln;
end;
{************************************************************************}
Procedure Timketiep(i:byte);
var j:byte;
begin
if i>n then print
else
for j:=1 to n do
if (dance[j]=false) and (A[i,j]=1) then
begin
nguoi[i]:=j;{Ghi lai Nguoi Nu j duoc nguoi nam i
moi nhay}
dance[j]:=true;{Danh dau nguoi Nu thu j da duoc
moi nhay}
timketiep(i+1);{Xet nguoi Nam ke tiep}
dance[j]:=false;{Xoa bo viec danh dau,Nguoi Nu
thu j khong
duoc chon}
end;
end;
{************************************************************************}
begin
clrscr;
readfile;
writeln;
dem:=0;
fillchar(dance,sizeof(dance),false);
timketiep(1);{bat dau tu nguoi Nam thu 1}
readln;
end.
{De 239:Cho hai so tu nhien a,b.Ta noi rang a nam trong b neu nhu khai trien
nhi phan cua a co the thu duoc tu khai trien nhi phan cau b bang cach xoa di
1 so chu so.
Lap thuat toan cho phep tu hai so cho truoc m,n tim so tu nhien d lon nhat
sao cho d nam trong ca m va n
GIAI THUAT:Viet 1 ham doi ra nhi phan(nguoc) cua 1 so
Viet ham OK kiem tra so a co nam trong so b khong
Cho d chay tu N xuong M .Kiem tra dong thoi d co nam trong
M va N khong}
Program De_so_239;
uses crt;
const so:array[0 1]of char=('0','1');
var m,n,d:word;
{**************************************************************}
Function Nhiphan(a:word):string;{Doi ra nhi phan cua 1 so}
var st:string;
begin
st:='';
repeat
st:=st+so[a mod 2];
a:=a div 2;
until a=0;
nhiphan:=st;
end;

Xem chi tiết: Tài liệu Bài Tập Tin học chọn lọc ppt