Bài giảng Môn Tin học lớp 11 - Bài tập chọn lọc

 0     1     0     0     2                             -     -     -     -     -      -
      0  1  0     1     0     2                             -     -     -     -     -     -
      1     0     1     0     2     0                             -     +     -     -     -      -
 GIAI THUAT:Doi voi M va N nhap vao ta se tao ra thanh 1 ma tran M+1*N+1
                               Gan cho moi vi tri deu la 1.Ta xet tung vi tri mot
                               Neu mot vi tri ma xung quanh no cac vi tri deu co gia tri >0
                               thi vi tri do la vi tri cua nguoi can su.
                               Sau do bot gia tri cua nhung vi tri xung quanh vi tri can
                               su lop 1 don vi}
Program DE_so_404;
Uses crt;
Const maxm=20;maxn=30;
Type Arr=array[0..maxm,0..maxn]of byte;
        Arrchar=array[1..maxm,1..maxn]of char;
Var A:arr;M,N:byte;B:arrchar;
{***********************************************************************}
Procedure Nhap;
Var I,J:byte;
Begin
  Fillchar(A,sizeof(a),1);
  Writeln('Input:');
  For I:=1 to M do
      Begin
       For J:=1 to N do
             begin
                  A[i,j]:=Random(5);
                  write(A[i,j]:4);
             end;
        writeln;
      end;
End;
{***********************************************************************}
Function Ok(a,b,c,d:byte):Boolean;
Begin
  If (a>0) and (b>0) and (c>0) and (d>0) then Ok:=true
  else Ok:=false;
End;
{***********************************************************************}
Procedure Xuly;
Var I,J:byte;
Begin
  For I:=1 to M do
       For J:=1 to N do
             If OK(A[i-1,j],A[i,j-1],A[i,j+1],A[i+1,j]) then
                                      Begin
                                           B[i,j]:='+';
                                           A[i-1,j]:=A[i-1,j]-1;
                                           A[i,j-1]:=A[i,j-1]-1;
                                           A[i,j+1]:=A[i,j+1]-1;
                                           A[i+1,j]:=A[i+1,j]-1;
                                      End
                        Else B[i,j]:='-';
end;
{***********************************************************************}
Procedure Output;
Var I,j:byte;
Begin
Writeln('Output:');
For I:=1 to M do
      Begin
       For J:=1 to N do
                  write(B[i,j]:4);
        writeln;
      end;
Writeln('Chu thich:Can su(+)');
End;
{***********************************************************************}
Begin
 clrscr;
 Randomize;
 N:=6;M:=6;
 Nhap;
 Xuly;
 Output;
readln;
end.
Bài 16:{De_so_408:Cho hai cap so nguyen duong (A1,B1),(A2,B2).Hay kiem tra xem hinh
chu nhat S1 co canh (A1,B1) co the nam trong hinh chu nhat S2 canh (A2,B2)
duoc khong.
GIAI THUAT:+ Dieu kien can la: Dien tich S2>Dien tich S1
         + Dieu kien du la:Canh lon nhat cua S1 phai nho hon canh lon
                                     nhat cua S2.
                       Canh nho nhat cua S1 phai nho hon canh nho
                                     nhat cua S2.}
Program DE_so_408;
Uses crt;
Var A1,B1,A2,B2:word;
{*********************************************************************}
Procedure Input;
Begin
 Repeat
  A1:=random(25);
  B1:=random(25);
  A2:=random(25);
  B2:=random(25);
 Until (A1>0) and (B1>0) and (A2>0) and (B2>0);
 Gotoxy(30,1);Writeln('Hinh chu nhat thu 1:');
 Gotoxy(30,2);Writeln('   A1    B1');
 Gotoxy(30,3);Writeln(A1:5,B1:5);
 Gotoxy(30,4);Writeln('Hinh chu nhat thu 2:');
 Gotoxy(30,5);Writeln('   A2    B2');
 Gotoxy(30,6);Writeln(A2:5,B2:5);
End;
{*********************************************************************}
Procedure Ve(a,b:word;j:byte);
Var I:Word;
Begin
  For I:=J to A do Begin Gotoxy(I,J);write('*');
                               Gotoxy(I,B);write('*');
                   End;
  For I:=J to B do
                   Begin Gotoxy(J,I);write('*');
                               Gotoxy(A+J-1,I);write('*');
                               End;
End;
{*********************************************************************}
Function Dientich(a,b:word):word;
Begin
  Dientich:=A*B;
End;
{*********************************************************************}
Function Max(A,B:word):word;
Begin
  If A>B then Max:=A
      else Max:=B;
End;
{*********************************************************************}
Function Min(A,B:word):word;
Begin
  If A<B then Min:=A
      else Min:=B;
End;
{*********************************************************************}
Function Ok:boolean;
Begin
Ok:=false;
  If Dientich(A2,B2)>Dientich(A1,B1) then
                  If (Max(A1,B1)<Max(A2,B2)) and (Min(A1,B1)<Min(A2,B2))
                   then OK:=true
End;
{*********************************************************************}
Begin
  Clrscr;
  Randomize;
  Input;
  Ve(Max(A1,B1),Min(A1,B1),2);
  Ve(Max(A2,B2),Min(A2,B2),1);
  Gotoxy(1,24);
  If OK then
        Writeln('Hinh chu nhat thu 1 co the nam trong hinh chu nhat thu 2')
  else
        Writeln('Hinh chu nhat thu 1 khong the nam trong hinh chu nhat thu 2');
readln;
End.
Bài 17:{De_so_42:Cho ma tran vuong A[i,j] (i,j=1,2,..,n).Cac phan tu cua A duoc
danh so tu 1 den NxN.
  Goi S la so luong cac "tu giac" A[i,j],A[i,j+1],A[i+1,j],A[i+1,j+1]
  sao cho cac so o dinh cua no xep tang theo thu tu tang dan theo chieu kim
  dong ho (Tinh tu 1 dinh nao do)
      1/ Lap chuong trinh tinh so luong S.
      2/ Lap thuat toan xac dinh A sao cho so S la:
             a.Lon nhat
             b.Nho nhat
  GIAI THUAT:
      1/ Xet tung phan tu cua mang voi cac vi tri cua ben phai,ben duoi,ben
      duoi phai.Neu thoa thi tang S
      2/  a.S lon nhat khi ma tran A xep tang tu trai sang phai.phai sang trai
          b.S nho nhat khi ma tran A xep giam tu trai sang phai}
Program De_so_42;
Uses crt;
Const n=6;
Type arr=array[1..n,1..n]of byte;
Var A:arr;
      Th:set of byte;
{*****************************************************************}
Procedure Nhap;
Var i,j:byte;
Begin
  Th:=[];
For i:=1 to sqr(n) do Th:=Th+[i];
  for i:=1 to N do
      begin
       for j:=1 to N do
       begin
            repeat
              A[i,j]:=random(sqr(n)+1);
            until (A[i,j]>0) and (A[i,j] in Th);
            write(A[i,j]:4);
            Th:=Th-[A[i,j]];
       end;
  writeln;
       end;
end;
{*****************************************************************}
Function Ok(a,b,c,d:byte):boolean;
begin
  If (a<b) and (b<c) and (c<d) then Ok:=true
       else Ok:=false;
end;
{*****************************************************************}
Function S:byte;
Var i,j,T:byte;
begin
  T:=0;
  For i:=1 to N-1 do
       For j:=1 to N-1 do
            if Ok(A[i,j],A[i,j+1],A[I+1,j+1],A[i+1,j]) then
                    T:=T+1;
S:=T;
end;
{*****************************************************************}
Procedure Nhaptang;
Var i,j,K:byte;
Begin
K:=1;
  for i:=1 to N do
      begin
      if odd(i) then
       for j:=1 to N do
              begin
                   A[i,j]:=K;
                   inc(k);
              end
        else
       for j:=N downto 1 do
              begin
                   A[i,j]:=K;
                   inc(k);
              end;
      end;
 for i:=1 to n do
        begin
              for j:=1 to n do
                    write(A[i,j]:4);
                  writeln;
       end;
end;
{*****************************************************************}
Procedure Nhapgiam;
Var I,j,k:Byte;
Begin
K:=Sqr(N);
  For i:=1 to N do
  begin
       For j:=1 to N do
            begin
              A[i,j]:=K;
              write(A[i,j]:4);
              Dec(k);
            end;
       writeln;
      end;
end;
{*****************************************************************}
begin
 clrscr;
 randomize;
repeat
 clrscr;
 writeln('Ma tran A ban dau:');
 Nhap;
 writeln('S=',s);
 until s0;
writeln('S lon nhat khi ta xep ma tran A nhu sau:');
Nhaptang;
writeln('Smax=',s);
writeln('S nho nhat khi ta xep ma tran A nhu sau:');
Nhapgiam;
writeln('Smin=',s);
readln;
end.
Bài 18:{De_so_422:Day nhi phan goi la "Gon" neu khong co hai so 0 nao dung canh nhau
.Lap chuong trinh in ra tat ca cac day nhi phan "Gon" do dai n.
GIAI THUAT:vet can va quay lui
                              + Th1:Chuoi nhi phan xuat phat ban dau la '1'
                              + Th2:Chuoi nhi phan xuat phat ban dau la '0'}
Program DE_so_422;
Uses crt;
Var st:string;N:byte;Solan:word;
Procedure Print;
Var J:byte;
Begin
Inc(solan);
If (Solan mod 10)=0 then readln;
  For J:=1 to N do write(St[J]);
  writeln;
End;
Procedure Truyhoi(I:byte);
Var KTC:char;
Begin
  If I>N then Print
      else
        For KTC:='0' to '1' do
             If (ST[i-1]='1') or ((St[i-1]='0') and (KTC'0')) then
                   Begin
                         ST:=ST+KTC;
                         Truyhoi(I+1);
                         Delete(st,I,1);
                   End;
end;
begin
 clrscr;
 N:=10;
 Solan:=0;
St:='1';
 Truyhoi(2);
St:='0';
 Truyhoi(2);
Writeln('Co tat ca ',solan,' xau nhi phan "Gon" co do dai la ',n);
readln;
end.
Bài 19:{De_so_423:Lap chuong trinh in ra tat ca cac day nhi phan "Gon" ,do dai N
va chua dung M so 1
  GIAI THUAT:Vet can ,Kiem tra dieu kien de chon :
                    + Khong co hai so nao la 0 lien nhau
                    + Co dung m chu so 1}
Program De_so_423;
Uses crt;
Var St:string;
       N:Byte;{Chieu dai xau}
       M:Byte;{So chu so 1 co trong xau}
       SL:Word;{Dem so luong xau nhi phan thoa man de bai}
       M1:Byte;{Dem so luong ky tu 1 co trong xau }
{*****************************************************************}
Procedure Print;
Var I:byte;
Begin
If M1=M then {Neu so ky tu 1 trong chuoi bang M thi Xuat}
  Begin
  For i:=1 to N do write(St[i]);
  Inc(Sl);
  if (Sl mod 20)=0 then readln;
  writeln;
  End;
End;
{*****************************************************************}
Procedure Truyhoi(I:byte);
Var KT:Char;
Begin
 If (I>N) then Print
  else
       For Kt:='0' to '1' do
            If (ST[i-1]='1') or ((ST[i-1]='0') and (KT'0')) then
                   Begin
                        If KT='1' then M1:=M1+1;{Neu ky tu duoc chon la 1 thi so luong
                                                                         chu so 1 trong chuoi duoc tang len}
                        ST:=ST+KT;
                        Truyhoi(I+1);
                        If St[I]='1' then M1:=M1-1;{Neu ky tu moi them vao la 1 khi
                                                                                xoa bo thi so luong Ky tu 1 trong
                                                                                chuoi se giam di 1}
                        Delete(St,i,1);         {Xoa bo ky tu mo them vao}
                   End;
end;
{*****************************************************************}
Begin
  Clrscr;
      Write('Nhap N:');readln(N);
  Repeat
      Write('Nhap M:');readln(M);
  Until M<N;
      Sl:=0;{So luong ban dau}
  St:='1';{Phan tu xuat phat cua chuoi}
  M1:=1;{So luong ky tu 1 co trong chuoi la 1}
  Truyhoi(2);
  St:='0';{Phan tu xuat phat cua chuoi}
  M1:=0;{So luong ky tu 1 co trong chuoi la 0}
  Truyhoi(2);
 Writeln('So luong cac day nhi phan "Gon " thoa man de bai la:',Sl);
readln;
end.
Bài 20: {De_so_424:Day nhi phan duoc goi la "Gon" bac K bat ky neu khong co K so
0 nao dung canh nhau .Lap Chuong trinh in ra tat ca cac day nhi phan "Gon"
bac K do dai N.
  Lap chuong trinh in ra tat ca cac day nhi phan "gon" bac K,do dai N va
chua dung M so 1}
Program De_so_424;
Uses crt;
Var St:string;
       M,N:Byte;
       M1,K,K1:Byte;
       SL:word;
{*****************************************************************}
Procedure Print;
Var J:byte;
Begin
  If M1=M then
              Begin
                    Writeln(ST);
                    SL:=Sl+1;
                    If (SL mod 20)=0 then Begin
                                                                          write('Press Enter to continue');
                                                                          readln;
                                                                  End;
             End;
End;
{*****************************************************************}
Procedure Truyhoi(I:byte);
Var Kt:char;
Begin
  If I>N then Print
  else
       For KT:='0' to '1' do
            If (ST[I-1]'0') or (Kt='1') or (ST[i-1]='0') and (K1<K-1) then
                  Begin
                    If Kt='0' then K1:=K1+1
                    Else If KT='1' then
                          Begin
                               K1:=0;
                               M1:=M1+1;
                         End;
                    ST:=ST+KT;
                    Truyhoi(i+1);
                    If KT='1' then M1:=M1-1;
                    DElete(ST,I,1);
                  End;
End;
{*****************************************************************}
Begin
  Clrscr;
  Write('Nhap N:');readln(n);
 Repeat
  Write('Nhap M:');readln(M);
  Write('Nhap K:');readln(K);
 Until (K<N) and (M<N);
  ST:='1';
  M1:=1;
  K1:=0;
  Sl:=0;
  Truyhoi(2);
  ST:='0';
  M1:=0;
  K1:=1;
  Truyhoi(2);
Writeln('Co ',sl,' xau nhi phan "Gon" thoa yeu cau de bai');
readln;
End.
Bài 21: {Chung minh rang so cach bieu dien cua so N thanh tong cua M so nguyen duong
 bang so cach bieu dien cua so cach bieu dien cua so N-M thanh tong cac so
 hang <=M.
 Vi du:N=8;M=3;
      8=1+1+6=1+2+5=1+3+4=2+2+4=2+3+3
      8-3=1+1+1+1+1=1+1+1+2=1+1+3=1+2+2=2+3
 GIAI THUAT:* Phan tich N thang tong cua cac so.Neu N bang tong cua M so
                        Thi chon cach bieu dien do (*)
                        * Phan tich N-M thanh tong cua cac so.
                        Chon cac cach bieu dien do (**)
        CHU Y:Neu M>N div 2-1 thi So cach bieu dien cua (*) hon so cach bieu
                        dien (**) 1 cach
                    Neu M<=N div 2-1 thi so cach bieu dien cua (*) bang so cach bieu
                        dien (**)}
Program De_so_425;
Uses Crt;
Var N,M,Tong,Giatri,Max,Sl:word;
       Luu:array[1..100]of word;
       K:byte;Q:boolean;
{********************************************************************}
Procedure Print;
Var J:byte;
Begin
  Case Q of
       True:If K=M then  {Truong hop 1}
            Begin
              For J:=1 to K do write(Luu[j],'+');
              Gotoxy(wherex-1,wherey);write('=');
              Inc(Sl);
            End;
       False:If K>1 then {Truong hop 2}
                    Begin
                          For J:=1 to K do write(Luu[j],'+');
                          Gotoxy(wherex-1,wherey);write('=');
                          Inc(Sl);
                    End;
      End;
End;
{********************************************************************}
Procedure Tim(I:byte);
Label Find;
Var J:word;
Begin
       If Tong=Giatri then Print Else
For J:=1 to Max do
             If (J+Tong=i) then
                          Begin
                               Tong:=Tong+J;
                               Inc(K);
                               Luu[k]:=J;
                               Tim(j);
                               Dec(K);
                               Tong:=Tong-J;
                          End;
End;
{********************************************************************}
Begin
 Clrscr;
 Write('Nhap N:');readln(N);
 Write('Nhap M:');Readln(M);
  {Truong hop 1:}
             Tong:=0;{Tong ban dau}
             Q:=true;{Truong hop 1}
             Sl:=0;{So cach bieu dien}
             K:=0;Giatri:=N;Max:=N;
             Write(N,'=');
             Tim(1);
             Gotoxy(wherex-1,wherey);writeln(' ');
             Writeln(#7,'Co ',sl,' cach');Readln;
  {Truong hop 2:}
             Tong:=0;
             Q:=false;
             Sl:=0;
             K:=0;Max:=M;Giatri:=N-M;
             write(n,'-',m,'=');
             Tim(1);
             Gotoxy(wherex-1,wherey);writeln(' ');
             Writeln(#7,'Co ',sl,' cach');Readln;
Readln;
End.
Bài 22: {De_so_439:Cho truoc n so tu nhien A1,A2,..,An.Tim ra so cuc dai K sao cho
tap tren co the chia thanh K nhom co tong nhu nhau.
  GIAI THUAT:
            Buoc 1:Tim tong tat ca cac so A1,A2,..,An
                                TONG:=A1+A2+..+An
            Buoc 2:Xet K tu N tro xuong den 2
                        (Vi it nhat la 2 nhom va nhieu nhat la N nhom)
                         K:N-->2;
                         Neu TONG chia cho K (nhom) la 1 so nguyen thi:
                                    Mot nhom se co tong so la:
                                            TONG1NHOM=TONG div K;
            Buoc 3:Tim nhung so co tong = TONG1NHOM
                         Neu ta chia N so duoc K nhom thi khong xet tiep nua}
Program De_so_439;
Uses Crt;
Const Mn=100;
Type Arr=array[1..MN]of integer;
Var A:arr;N:byte;
{******************************************************************}
Procedure Input;
Var I:byte;
Begin
  Write('N:');Readln(N);
  For I:=1 to N do
            Begin
              A[i]:=Random(9)+1;
              Write(A[i]:4);
            End;
End;
{******************************************************************}
Procedure Xuly;
Var I,K,Sl,Slchon:Byte;Tong,Ketqua,Tong1nhom:integer;Q:Boolean;
       Chon,B:array[1..mn]of byte;
       {Chon:Kiem tra so duoc chon chua;B:Luu lai so duoc chon cho 1 nhom}
   Procedure Timtong(I:byte);
       Var J,K:byte;
        Begin
            If Ketqua=Tong1nhom then Begin
                                                        Sl:=Sl+Slchon;{Tang so luong so A duoc chon}
                                                        For K:=1 to Slchon do
                                                                  Chon[B[k]]:=2;{Danh dau nhung so da duoc
                                                                                            chon vao 1 nhom}
                                                      End
       Else
       For J:=1 to N do
            If (Chon[j]=0) and (A[j]+Ketqua<=Tong1nhom) then
              Begin
                   Chon[j]:=1;{Danh dau Aj da duoc chon}
                   Inc(slchon);{Tang so luong so cua Nhom}
                   B[slchon]:=j;{Luu tru Aj duoc chon}
                   Ketqua:=Ketqua+A[j];{Tang tong cac so cua nhom}
                   Timtong(j);{Tim so ke tiep}
                   Ketqua:=Ketqua-A[j];
                   Dec(Slchon);
                   if Chon[j]=1 then Chon[j]:=0;
             End;
End;
Begin
  Tong:=0;
  For I:=1 to N do Tong:=Tong+A[i];{Tinh tong cac so}
  K:=N+1;
  Q:=False;
  Repeat
       Dec(K);
       If (Tong mod K)=0 then {Neu Tong chia K duoc 1 so nguyen}
                                            Begin
                                                 Tong1nhom:=Tong div K;{Trung binh 1 nhom}
                                                 Sl:=0;Ketqua:=0;Slchon:=0;
                                                 fillchar(chon,sizeof(chon),0);
                                                 Timtong(1);
                                                 If Sl=N then Q:=True;
                                           End;
  Until Q or (K=2);
  Writeln;
  If Q then
      Begin
  Writeln('K=',k);
  Writeln('Tong moi nhom la:',tong1nhom);
      End
  Else Writeln('Khong chia duoc');
End;
{******************************************************************}
Begin
  Clrscr;
  Randomize;
 Repeat
  Clrscr;
  Input;
  Xuly;
  Readln;
 Until False;
End.
Bài 23: {Xet tap cac xau nhi phan do dai N ,tren do