//
you're reading...
01 - Chủ đề thuật toán, Dùng cho cấp THCS, Dùng cho cấp THPT

Thuật toán

Bài giảng thuật tóan


[Nội dung bài giảng] [Handbook of Algorithms and Data Structures]


Thí dụ về một  số thuật giải thường gặp


  1. Trao đổi giá trị của 2 biến A và B thông qua biến trung gian C
  2. Tìm phần tử nhỏ nhất trong dãy số A 1 ,A 2 ,…,A
  3. Duyệt dãy A 1 , A 2 , … , A n xem có phần tử X hay không
  4. Sắp xếp dãy A 1 ,A 2 ,…,A n , theo thứ tự tăng dần
  5. Thuật toán Lùa bò vào chuồng” 
  6. Thuật toán tìm Ước chung lớn nhất của 2 số nguyên A và B
  7. Thuật toán tìm số nguyên tố 
  8. Thuật toán tìm căn bậc 2 của số không âm A
  9. Tìm nghiệm gần đúng của một đa thức F(x) bằng thuật toán chia đôi 
  10. Thuật toán Greedy Algorithm với bài toán tô màu
  11. Tìm kiếm nhị phân trên mảng đã được sắp thứ tự
  12. Sắp xếp gọn từng Băng với thao tác đổi chỗ trực tiếp 2 phần tử

1 /  Trao đổi giá trị của 2 biến A và B thông qua biến trung gian C :


B0   Bắt đầu
B1   Nhập giá trị cho A và B
B2   C lấy giá trị của A ( Gọi là gán giá trị A cho C , viết C := A )
B3   A lấy giá trị của B ( Gọi là gán giá trị B cho A , viết A := B )
B4   B lấy giá trị của C  ( Gọi là gán giá trị C cho B , viết B := C )
B5   Thông báo kết quả
B6   Kết thúc


2 /  Tìm phần tử nhỏ nhất trong dãy số A 1 ,A 2 ,…,A n  :


B0   Bắt đầu
B1   Nhập các giá trị  N , A 1 ,A 2 ,…,A n
B2   Gán i := 2
B3   Nếu  A i < A 1 thì  A 1 :=  A i
B4   Tăng  i lên 1 đơn vị
B5   Nếu i<=N thì quay về  B3  ( Lệnh lặp )
B6   Nếu i > N thì A nhỏ nhất
B7   Thông báo kết quả
B8   Kết thúc


3 /  Duyệt dãy A 1 , A 2 , … , A xem có phần tử X hay không :


B0   Bắt đầu
B1   Nhập các giá trị N, A 1 ,A 2 ,…,A n
B2   Gán trị i :=1
B3   Nếu i >N thì chuyển sang B6
B4   Nếu  A <>   X thì  tăng i lên 1 đơn vị       , Chuyển về B3
B5   Thông báo kết quả : có X trong dãy A 1 ,A 2 ,…,A n  , rồi chuyển sang B7
B6   Thông báo kết quả : Không có X trong dãy A 1 ,A 2 ,…,A n ,
B7   Kết thúc chương trình .


4 /  Sắp xếp dãy A 1 ,A 2 ,…,A n , theo thứ tự tăng dần  :


B0   Bắt đầu
B1   Nhập N, A 1 ,A 2 ,…,A n
B2   Gán i :=1
B3   Gán k :=i+1
B4   Nếu A i <= A k  thì   B6
B5   Thực hiện thuật toán đổi giá trị A i và  A k
B6   Tăng k lên 1 đơn vị
B7   Nếu  k <= N thì chuyển  về B4
B8   Tăng i lên 1 đơn vị
B9   Nếu i < N thì chuyển về B3
B10 Thông báo dãy đã sắp tăng  là A 1 ,A 2 ,…,A n .
B11 Kết thúc .


 5 /  Thuật toán Lùa bò vào chuồng :
Tìm số nguyên dương bé nhất không có trong dãy A 1 ,A 2 ,…,A n .gồm các số nguyên dương  không lớn hơn 32.000


B0  Bắt đầu
B1  Nhập các giá trị  N , A 1 ,A 2 ,…,A n .
B2  Trên trục số đánh dấu các điểm A 1 ,A 2 ,…,A n  nếu chúng nhỏ hơn N.
B3  x := 1
B4   Duyệt trên trục số , nếu thấy X là điểm nguyên chưa được đánh dấu thì chuyển       sang bước B6
B5   Tăng x lên 1 đơn vị
B6   Thông báo số nguyên dương bé nhất chưa có trong dãy là X
B7   Kết thúc


 6 /  Thuật toán tìm Ước chung lớn nhất của 2 số nguyên A và B :


B0    Bắt đầu
B1    Nhập 2 số nguyên A và B
B2    Gán A = ½A ½, B = ½ B ½
B3    Nếu A =0 và B=0 thì B9
B4    Nếu A=0 và B <>0 thì B10
B5    Nếu B=0 và A <>0 thì B11
B6    Gán dư của phép chia A cho B vào biến D ( D = A mod B )
B7    Nếu D = 0 thì  chuyển sang B10
B8    Gán A := B ; B := D ; D := A mod B chuyển về B7
B9    Thông báo UCLN  không tồn tại  , chuyển về Bkt
B10  Thông báo kết quả : Ước số chung lớn nhất là số B , chuyển về Bkt
B11  Thông báo kết quả : Ước số chung lớn nhất là số  A
Bkt   Kết thúc


7 /  Thuật toán tìm số nguyên tố :


B0  Bắt đầu
B1  Nhập số N
B2  N = 1 thì chuyển sang bước B 9
B2  Nếu N=2 hoặc N=3 thì chuyển sang B8
B3  Gán i :=-1
B4  Nếu (N mod 2 =0) hoặc  (N Mod 3 =0) thì  chuyển sang B 9
B5  Tăng i lên 6 đơn vị
B6  Nếu (N mod i <> 0) và (N mod (i+2) <>0)  và ( i*i <= N ) chuyển sang B 5
B7  Nếu i*i <= N  thì  chuyển sang B 9
B8  Thông báo  : N là số nguyên tố , chuyển tới B10
B9  Thông báo  : N là  hợp số
B10 Kết thúc chương trình


8 /  Thuật toán tìm căn bậc 2 của số không âm A :


B0   Bắt đầu
B1   Nhập số không âm A  và sai số cho phép e
B2   X 0  = 1 ( X là giá trị gần đúng đầu tiên của căn bậc 2 của A )
B3   X    = X 0
B4   X o  = ( X +  A/X ) / 2
B5   Kiểm tra : | X 0 – X | < e thì chuyển sang B6 còn không thì chuyển về bước B3
B6   Thông báo căn bậc hai của A là X 0
B7   Kết thúc


 9 /  Tìm nghiệm gần đúng của một đa thức F(x) bằng thuật toán chia đôi  :


B0   Bắt đầu
B1   Nhập các hệ số của đa thức và độ sai số cho phép  e
B2   Nhập 2 giá trị A và B sao cho F(A) <0 và F(B) >0
B3   X = ( A+B )/2
B4   Nếu  | B – A | < e  thì chuyển tới B10
B5   Tính F(X)
B6   Nếu F(X) >0 thì B := X , chuyển về B3
B7   Nếu F(X) <0 thì A :=X , chuyển về B3
B8   Nếu F(X) = 0 thì  Chuyển tới B10
B10 Thông báo nghiệm là X
B11 Kết thúc


10 /  Thuật toán Greedy Algorithm với bài toán tô màu 


 Bài toán :  Cho tập n điểm gọi là tập G , các điểm này được đánh số từ 1 đến N và được nối với nhau bởi một số đoạn thẳng . Hãy tô màu cho các điểm theo nguyên tắc : 2 điểm có đoạn thẳng nối chúng phải tô bằng 2 màu khác nhau . Nêu cách tô màu cho các điểm sao cho càng dùng ít màu càng tốt .

Gợi ý xây dựng  thuật toán : Cần tổ chức 2 tập : Tập điểm đã tô màu D và tập điểm chưa tô màu C  .Mỗi lần có 1 đỉnh được tô màu thì kết nạp thêm đỉnh đó vào D , tập C loại trừ đỉnh đó . Dùng màu 1 tô cho đỉnh 1 . Số lượng lớn nhất các màu đã dùng là MD=1. Chọn đỉnh i chưa tô màu , cho tập màu T là rỗng , tìm tất cả các đỉnh k nối với i , nếu đỉnh k đã được tô màu thì ghi lại màu của đỉnh k vào tập màu T , so T với tập màu đã dùng TMD gồm các màu từ 1 tới MD , nếu có màu  của TMD không thuộc T thì chọn nó làm màu của đỉnh i , ngược lại phải chọn màu MD+1 làm màu cho đỉnh i ; tăng MD lên 1 đơn vị ; thoát khỏi việc chọn màu cho đỉnh i . Quá trình tiếp tục cho đến khi tất cả các đỉnh đều được tô màu

Rõ ràng thuật toán trên đã tìm mọi khả năng tốt nhất để gán màu cho 1 đỉnh . Song lời giải theo thuật toán này chưa tối ưu ( Chưa là lời giải tốt nhất ) vì việc chọn màu tốt nhất cho 1 đỉnh i chưa chắc bảo đảm có lợi cho việc chọn màu của các đỉnh tiếp sau i

Sau này chúng ta sẽ đề cập tới một thuật toán khác có tính tối ưu để giải bài toán tô màu này .


 11 /   Tìm kiếm nhị phân trên mảng đã được sắp thứ tự


B0    Bắt đầu
B1    Nhập số X và dãy A gồm N phần tử
B2    Gán   đầu := 1   ;  cuối := N
B3    Kiểm tra  đầu <= cuối  nếu sai thì chuyển về B 8
B4    giữa := ( đầu + cuối ) div 2
B5    Nếu X > A[giữa] thì đầu  := giữa +1. Chuyển về B3
B6    Nếu X < A[giữa] thì cuối := giữa -1. Chuyển về B3
B7    Nếu X= A[giữa] thì cuối := -1. Chuyển về B8
B8    Nếu cuối = -1 thì thông báo có X trong mảng ,còn ngược lại thì thông báo không có X trong mảng
B9    Kết thúc .


12 /  Sắp xếp gọn từng Băng với thao tác đổi chỗ  trực tiếp 2 phần tử :


Bài toán : Cho dãy số gồm N số , chỉ gồm số 1,2,3 (1<=N<=1000). Một thao tác đổi chỗ giữa 2 phần tử của dãy là trao đổi trực tiếp giá trị 2 phần tử này cho nhau .Bằng số ít nhất các thao tác đổi chỗ , hãy sắp dãy thành dãy không giảm .

Gợi ý :

Đếm số số 1 của dãy  là s1 , số số 2  là s2 ; đặt T2=s1+1,T3 = s1+ s2 + 1 , gọi dãy từ vị trí 1 đến vị trí T2-1 là băng 1, từ T2 đến T3-1 là băng 2 , còn lại từ T3 đến N là băng 3

Muốn có phương án sắp tốt nhất  , ta chia các thao tác thành 3 loại có thứ tự ưu tiên :

Loại 1 : Thao tác tốt  : đổi số 1 ở băng 2 cho số 2 ở băng 1 , hoặc đổi số 1 ở băng 3 cho số 3 ở băng 1

Loại 2 : Thao tác bắt buộc : xảy ra trong hoàn cảnh không còn cách giải quyết khác nữa : Thí dụ như ở băng 2 không còn số 1 , chỉ còn số 1 ở băng 3 , trong trường hợp này đành phải đổi số 2 ở băng 1 cho số 1 ở băng 3 ; hoặc như ở băng 3 không còn số 1 , chỉ còn số 1 ở băng 2 , trong trường hợp này đành phải đổi số 3 ở băng 1 cho số 1 ở băng 2

Loại 3 : Thao tác cuối cùng : Là những thao tác  còn lại , phải hoàn thành nốt,mang tính  hiển nhiên về cách thức thực hiện , thứ tự thực hiện không ảnh hưởng sự tối ưu  . Thí dụ : Khi đã xếp xong Băng 1 , do độ dài các băng đã tính toán sẵn nên có bao nhiêu số 3 trong băng 2 thì cũng còn bấy nhiêu số 2 trong băng 3 .Mặt khác thứ tự trong 1 băng không quan trọng nên có thể thực hiện các thao tác đổi chỗ hoàn toàn tuỳ ý cho các cặp (số 3 trong băng 2 – số 2 trong băng 3 )

B0        Bắt đầu
B1        Nhập N và dãy A(N) ;
B2        i := 1
B3       Nếu i > S1 thì về B11
B4       Nếu (A[i] = 1 )  thì i:=i+1 và về B3
B5        Tĩm vị trí số 1 trong băng 2 gọi là vị trí x (không có thì x=0)
Tĩm vị trí số 1 trong băng 3 gọi là vị trí y (không có thì y=0)
B6       Nếu x=0 và y = 0 thì B11
B7        Nếu A[i] =2  thì B9
B8       Nếu A[i] =3 thì B10
B9       Nếu x>0 thì (đổi A[i] và A[x]  ; tăng i := i+1 ; về B3 ) còn không ( x=0 , y>0) thì           (đổi A[i] với A[y]; tăng i := i+1 ; về B3 )
B10      Nếu y>0 thì (đổi A[i] và A[y] ; tăng i := i+1 ; về B3 ) còn không ( y=0 , x>0) thì            (đổi A[i] với A[x]; tăng i := i+1 ; về B3 )
B11      (Đã xong băng 1), i = T2
B12      Nếu i>T2-1 thì tới B15
B12      Nếu A[i]=2 thì i:=i +1 và về B12
B13      Tìm vị trí số 2 trong băng 3 , gọi vị trí này là z
B14      Đổi A[i] và A[z] ; tăng i := i+1 , về B12
B15      Hiện dãy đã xếp tăng
B16       Kết thúc


 

Một số chương trình minh hoạ thuật toán


{ Bài 1 Thuật toán tráo cốc }

Uses   Crt;
Var   A,B,C : Integer;
Begin
Clrscr;
Write('Nhap so A : ');
Readln(A);
Write('Nhap so B : ');
Readln(B);
C := A;
A := B;
B := C;
Writeln('A = ',A:5,#13#10'B = ',B:5);
Readln;
End.

{ Bài 2 Tìm phần tử nhỏ nhất trong dãy }


Uses   Crt;
Const Max = 10;
Var   j : Integer;
A : Array[1 .. Max] of Integer;
Begin
Clrscr;
For j:=1 to Max do
Begin
Write('A[',j:2,'] = ');
Readln(A[j]);
End;
j := 2;
Repeat
If A[j] < A[1] then A[1] := A[j];
Inc(j);
Until j>Max;
Writeln('So nho nhat la ',A[1]);
Readln;
End.

{ Bài 3 Duyệt dãy theo thứ tự , tìm phần tử X }


Uses   Crt;
Const Max = 10;
Var   i,X : Integer;
A   : Array[1..Max] of Integer;
Procedure Baoco;
Begin
Writeln(X,' co trong day ');
Readln;
Halt;
End;

Procedure Khongco;
Begin
Writeln(X,' khong co trong day ');
Readln;
End;

Begin
Clrscr;
Write('Nhap X = '); Readln(X);
Writeln('Nhap day A ');
For i:=1 to Max do
Begin
Write('A[',i:2,'] = ');
Readln(A[i]);
End;
i := 1;
While i<= Max do
Begin
If A[i] = X then Baoco { Trong Baoco co lenh Halt }
Else Inc(i);
End;
If i>max then Khongco;
End.

{ Bài 4 Sắp xếp dãy bằng phương pháp Nổi bọt – Phương pháp sắp xếp kém nhất }


Uses   Crt;
Const Max     = 10;
Var   N       : Integer;
A       : Array[1..Max] of Integer;

Procedure Nhap;
Var i : Integer;
Begin
Write('Nhap N = ');
Readln(N);
For i:=1 to N do
Begin
Write('A[',i:2,'] = ');
Readln(A[i]);
End;
End;

Procedure Hien;
Var i : Integer;
Begin
For i:=1 to N do
Write(A[i]:5);
Writeln;
End;

Procedure Traococ( Var x,y : Integer);
Var c : Integer;
Begin
c   := x;
x   := y;
y   := c;
End;

Procedure KieuFor;
Var i,j : Integer;
Begin
For i:=1 to N-1 do
For j:=i+1 to N do
If A[i] > A[j] then Traococ(A[i],A[j]);
Hien;
End;

BEGIN
Clrscr;
Nhap;
KieuFor;
Readln;
END.

{ Bài 5 Phương pháp Lùa bò vào chuồng ! }


Uses   Crt;
Const Max   = 32000;
M     = 10;
Var   x,N   : Integer;
A     : Array[1..M] of Integer;
B     : Array[1..Max] of Boolean;

Procedure Nhap;
Var i : Integer;
Ok : Boolean;
Begin
Write('Nhap N = ');
Repeat
{$I-} Readln(N); {$I+}
Until (IoResult=0) and (N<=10) and (N>0);
Writeln('Nhap mang ',N,' so nguyen duong : ');
For i:=1 to N do
Begin
Write('A[',i:2,'] = ');
Repeat
Readln(A[i]);
Ok := (IoResult=0) and (A[i]<=32000) and (A[i]>0);
Until Ok;
End;
End;

Procedure Thuchien;
Var i,j : Integer;
Begin
FillChar(B,Sizeof(B),False);
For i:=1 to Max do
For j:= 1 to N do
If i=A[j] then B[i]:= true;
For x:=1 to Max do
If B[x]=False then
Begin
Write('So nguyen duong nho nhat khong thuoc mang: ');
Writeln(x);
Readln;
Halt;
End;
End;

BEGIN
Clrscr;
Nhap;
Thuchien;
Readln;
END.

{ Bài 6 Thuật toán tìm USCLN của 2 số }


Uses   Crt;
Var   A,B,La,Lb : Integer;

Procedure Nhap(i : Char;Var x : Integer);
Var Ok : Boolean;
Begin
Write('Nhap so nguyen ',i,' = ');
Repeat
{$I-} Readln(x); {$I+}
Ok := (IoResult=0);
Until Ok;
End;

Procedure Hien(x : Integer);
Begin
Write('UCLN(',LA:5,',',LB:5,') = ',x);
Readln;
Halt;
End;

Procedure Hien2;
Begin
Writeln(' Moi so nguyen deu = UCLN(0, 0) ');
Readln;
Halt;
End;

Procedure Tim;
Var D : Integer;
Begin
A := Abs(A);
B := Abs(B);
If (A=0) and (B<>0) then Hien(B);
If (B=0) and (A<>0) then Hien(A);
If (A=0) and (B=0) then Hien2;
D := A mod B;
While D<>0 do { Chu y neu dung Repeat can tranh chia cho 0 }
Begin
A := B;
B := D;
D := A mod B;
End;
Hien(B);
End;

BEGIN
Clrscr;
Nhap('A',A);
Nhap('B',B);
La := A;
Lb := B;
Tim;
Readln;
END.

{ Bài 7 Tìm số nguyên tố – Thuật toán tốt }


Uses   Crt,dos;
Const Max = 400000; { 192/100 giay --> 50000 & 2269/100 giay --> 400000 }
Var   N , i   : LongInt;
h,m,s,p : Word;
T       : LongInt;
Begin
Clrscr;
Gettime(h,m,s,p);
t   := 6000*m + 100*s +p;
Write(2:8);
Write(3:8);
For N := 5 to Max do
If (N mod 2 <> 0) and (N mod 3 <> 0) then
Begin
i := -1;
Repeat
Inc(i,6);
Until (N mod i =0) or (N mod (i+2)=0) or (sqr(i)>N);
If sqr(i)>N then Write(N:8);
End;
Gettime(h,m,s,p);
t   := 6000*m + 100*s +p - t;
Writeln;
Writeln('Mat thoi gian la : ', T);
Readln;
End.

{ Bài 8 Tìm căn bậc hai của 1 số }


Uses   Crt;
Var   A,E,X0 : Real;
Procedure Baoloi;
Begin
Writeln('Loi du lieu nhap : ');
Readln;
Halt;
End;

Procedure Nhap;
Var Ok : Boolean;
Begin
Write('Nhap so trong can bac 2 : ');
Repeat
{$I-} Readln(A); {$I+}
Ok := (IoResult=0) and (A>=0);
If not Ok then BaoLoi;
Until Ok;
Write('Nhap do chinh xac : ');
Repeat
{$I-} Readln(E); {$I+}
Ok := (IoResult=0) and (E>=0.000001) ;
If not Ok then BaoLoi;
Until Ok;
End;

Procedure Lam;
Var X : Real;
Begin
X0 := 1;
Repeat
X := X0;
X0 := (X + A/X)/2;
Until Abs(X0-X) < E;
End;

Procedure Hien;
Begin
Writeln('can bac 2 cua ',A:8:2,' la ',X0:8:2,' voi do chinh xac ',E:8:6);
End;

BEGIN
Clrscr;
Nhap;
Lam;
Hien;
Readln;
END.

{ Bài 9   Tìm nghiệm đa thức bằng thuật toán chia đôi cung }


Uses   Crt;
Const Max   = 10;
e     = 0.0001;
Type   Mang   = Array[1..Max] of Real;
Var   A     : Mang;
x1,x2 : Real;
N     : Byte;

Procedure Nhap1;
Var i : Byte;
Begin
Clrscr;
Write('N = ');
Repeat
{$I-} Readln(N); {$I+}
Until (IoResult=0) and (N>0) and (N<Max);
For i:=N downto 0 do
Repeat
Write('A[',i:2,']=');
{$I-} Readln(A[i]); {$I+}
Until (IoResult=0);
End;

Function F(x:Real):Real;
Var i : Byte;
p : Real;
Begin
p := A[n]*x+A[n-1];
For i:=2 to n do
p := p*x+A[n-i];
F := p;
End;

Procedure Nhap2;
Var dem : Byte;
Ok : Boolean;
Begin
Writeln;
dem := 0;
Repeat
Write('Nhap x1 : F(x1)<0   x1 = ');
{$I-} Readln(x1); {$I+}
Ok := (IoResult=0) and (F(x1)<0);
If not Ok then
Begin
Inc(dem);
Writeln('Nhap sai yeu cau lan thu ',dem);
End;
Until Ok or (dem =3);
Writeln;
dem := 0;
Repeat
Write('Nhap x2 : F(x2)>0   x2 = ');
{$I-} Readln(x2); {$I+}
Ok := (IoResult=0) and (F(x2)>0);
If not Ok then
Begin
Inc(dem);
Writeln('Nhap sai yeu cau lan thu ',dem);
End;
Until Ok or (dem =3);
End;

Procedure Timnghiem;
Var x,p : Real;
Begin
x := (x1+x2)/2;
p := F(x);
While Abs(p) > e do
Begin
If p>0 then x2 := x;
If p<0 then x1 := x;
If p = 0 then
Begin
Write('Nghiem dung la x= ',x:10:4);
Readln;
Halt;
End;
x := (x1+x2)/2;
p := F(x);
End;
Writeln('nghiem gan dung la ',x:10:4);
End;

BEGIN
Nhap1;
Nhap2;
Timnghiem;
Readln
END.

{ Bài 10 Tô màu bằng phương pháp Greedy }


Uses   Crt;
Const Max   = 14;
Var   A             : Array[1..Max,1..Max] of 0..1;
Mau           : Array[1..Max] of Byte;
N             : Integer;
dato,chuato   : Set of Byte;

Procedure Nhap;
Var i,j : Integer;
F : Text;
Begin
FillChar(A,Sizeof(A),0);
Assign(F,'Tomau.txt');
Reset(F);
Readln(F,N);
While not Eof(F) do
Begin

Read(F,i);Readln(F,j);
A[i,j] := 1;
A[j,i] := 1;
End;
End;

Procedure Hien;
Var i,j : Integer;
Begin
Writeln;
For i:=1 to N do
Begin
For j:=1 to N do Write(A[i,j]:4);
Writeln;
End;
End;

Procedure Thongbao;
var i : Integer;
Begin
Write('Da   to mau   : ');
For i:=1 to N do
If i in dato then Write(i:4);
Writeln;
Write('Chua to mau   : ');
For i:=1 to N do
If i in chuato then Write(i:4);
Writeln;
Writeln;
Write('Danh sach dinh : ');
For i:=1 to N do
Write(i:4);Writeln;
Write('Mau da to la   : ');
For i:=1 to N do
Write(Mau[i]:4);
End;

Function Kt(x,m : Integer): Boolean;
Var i : Integer;
Begin
Kt := False;
For i:=1 to N do
If (A[x,i]=1) and (m=Mau[i]) then Exit;
Kt := True;
End;

Procedure Greedy;
Var i : Integer;
Lienquan : Array[1.. Max] of Byte;
Mp,Maxm,j : Integer;
Begin
Dato := [];
Chuato :=[];
For i:=1 to N do chuato := chuato +[i];
Mau[1]:=1;
dato:= dato+[1];
chuato := chuato-[1];
Maxm   := 1;
For i:=1 to N do
Begin
If i in chuato then
Begin
FillChar(Lienquan,Sizeof(Lienquan),0);
For j:=1 to N do
If (A[i,j]=1) and (Mau[j]>0) then
Lienquan[Mau[j]] := 1;
For j:=1 to N do
If Lienquan[j]=0 then
Begin
mp := j;
j := N;
End;
If mp<=N then
Begin
Mau[i] := mp;
dato   := dato + [i];
Chuato := chuato -[i];
End
Else
Begin
Inc(Maxm);
Mau[i]:=Maxm ;
dato   := dato + [i];
Chuato := chuato -[i];
End;
End;
End;
End;

BEGIN
Clrscr;
Nhap;
Hien;
Greedy;
Thongbao;
Readln;
END.

{Bài 11 : Tìm phần tử X trong dãy sắp thứ tự bằng phương pháp chia đôi }


Uses   Crt;
Const Max = 1000;
Var   A   : Array[1.. Max] of Integer;
N,X : Integer;
Procedure Nhap;
Var i : Integer;
Begin
Write('So phan tu cua mang : N = ');
Readln(N);
Randomize;
For i:=1 to N do A[i] := Random(100);
End;
Procedure Hien;
Var i : Integer;
Begin
For i:=1 to N do
Begin
If i mod 480 =0 then Readln;
Write(A[i]:4);
End;
End;

Procedure PPchiadoi;
Procedure Sap;
Var i,j,c : Integer;
Begin
For i:=1 to N-1 do
For j:=i+1 to N do
If A[j]<A[i] then
Begin
c   := A[i];
A[i] := A[j];
A[j] := c;
End;
End;

Procedure NhapN;
Begin
Writeln;
Write('Nhap so X can tim trong mang , X = ');
Readln(X);
End;

Procedure Thuchien;
Var g,d,c : Integer;
Begin
d := 1;
c := N;
While d<=c do
Begin
g := (d+c) div 2;
If X > A[g] then d := g+1;
If X < A[g] then c := g-1;
If X = A[g] then c := -1
End;
If c = -1 then Writeln('Co ',x:4,' trong mang ') Else
Writeln('Khong co ' ,x:4,' trong mang ');
End;
Begin
Sap;
Writeln;
Hien;
NhapN;
Thuchien;
End;

BEGIN
Clrscr;
Nhap;
Hien;
PPchiadoi;
Readln;
END.

Chữa bài tập về nhà
Một số thuật toán nêu ở trang 26


1 ) Thuật toán giải phương trình bậc 2 :


B0 Bắt đầu
B1 Nhập A,B,C với A<>0
B2 Tính D = B*B – 4*A*C
B3 Nếu D < 0 : Hiện phương trình vô nghiệm . Chuyển về bước Bkt B4 Nếu D = 0 : Tính x = -(b/(2*a)) Hiện phương trình có nghiệm kép x ; về Bkt B5 Nếu D > 0 : Tính x1 = (-b – sqrt( D ) ) / 2 , x2 = (-b + sqrt( D ) ) / 2 ,
Hiện phương trình có 2 nghiệm phân biệt x1 , x2 . về Bkt
Bkt Kết thúc


2 ) Thuật toán giải hệ phương trình bậc nhất 2 ẩn :


B0 Bắt đầu
B1 Nhập A1,B1,C1,A2,B2,C2
B3 Nếu A1=A2=B1=B2=C1=C2=0 Hiện mọi cặp (x,y) là nghiệm ; về Bkt
B4 Nếu A1=A2=B1=B2=0 và (C1<>0 hoặc C2<>0) phương trình vô nghiệm; về Bkt
B5 Tính D = A1*B2 – A2*B1 , Dx = C1*B2 – C2*B1 , Dy = A1*C2 – A2*C1
B6 Nếu D <> 0 : Phương trình có 1 nghiệm duy nhất là cặp số
x = Dx/D , y = Dy/D ; về Bkt
B7 Nếu D = 0 và Dx=Dy=0 : phương trình có vô số nghiệm là (x,y) thoả mãn 1 phưong trình của hệ ; về Bkt
B8 Nếu D=0 và ( Dx<>0 hoặc Dy<>0 ) phương trình vô nghiệm
Bkt Kết thúc


4 ) Thuật toán Ơclit tìm USCLN của hai số:


B0 Bắt đầu
B1 Nhập 2 số nguyên a, b
B2 a:= abs(a) và b := abs(b)
B3 Nếu b B4 Nếu a =0 về B7
B5 b := b – a
B6 Nếu b B7 Thông báo USCLN là b
B8 Kết thúc


6 ) Thuật toán xác định số N có là số nguyên tố không , dựa vào định nghĩa :


B0 Bắt đầu
B1 Nhập số N
B2 i := 2
B3 Nếu i > N div 2 chuyển tới B6 { Hoặc cải tiến hơn là : i > Trunc(SQRT(N)) }
B4 Nếu N mod i = 0 chuyển tới B7
B5 i := i +1 , chuyển về B3
B6 Hiện kết quả N là số nguyên tố ; về Bkt
B7 Hiện : N không là số nguyên tố
Bkt Kết thúc


7 ) Tìm các số nguyên tố từ 1 đến N bằng Sàng Erastosthène


B0 Bắt đầu
B1 Nhập N ,tạo mảng A gồm N phần tử kiểu Boolean , đánh dấu mọi phần tử chưa xoá
B2 Đánh dấu xoá phần tử 1
B3 c := Sqrt(N)
B4 nếu k >c thì chuyển tới B9
B5 Nếu A[k] đã bị đánh dấu xoá thì k := k+1 , chuyển về B4
B6 i := k*k
B7 Nếu i > N thì chuyển tới B 4
B8 Đánh dấu xoá phần tử i , i := i+k ; chuyển về B 7
B9 Hiện chỉ số của mọi phần tử của mảng A chưa bị đánh dấu xoá
Bkt Kết thúc


 

Lập trình minh hoạ phần bài tập về nhà


{4.Bài tìm USCLN bằng thuật toán Ơclit – Bài 4 / trang 26 }


Uses   Crt;
Var    a,b : Integer;
Procedure Traococ(Var x,y : Integer);
       Var  c : Integer;
       Begin
            c := x;
            x := y;
            y := c;
       End;
Begin
       Clrscr;
       Write('Nhap 2 so nguyen ');
       Repeat
             {$I-} Readln(a,b) {$I+}
       Until ( IoResult=0);
       a := abs(a);
       b := abs(b);
       If b0 do
          Begin
               b := b-a;
               If b

{6.Xác định N có là số nguyên tố không ? bằng định nghĩa – Bài 6/ trang 26 }


Uses   	Crt,dos;
Const  	Max     = 300000;  { Chay mat 1 phut }
Var    	N,i,k   	: LongInt;
       	Ok      	: Byte;
       	h,m,s,p	: Word;
       	T  	: LongInt;
Begin
     Clrscr;
     Gettime(h,m,s,p);
     t   	:=  6000*m + 100*s +p;
     For N := 2 to Max do
     Begin
          	k    	:= Trunc(sqrt(N));
          	i	:=2;
          	Ok   	:= 0;
          While (i<=k) and ( Ok=0) do
              If N mod i <> 0 then inc(i) Else Ok := 1;
          If i>k then Write(N:8);
     End;
     Gettime(h,m,s,p);
     t   := ( 6000*m + 100*s +p) -t ;
     Writeln;
     Writeln('Thoi gian chay la : ',t);
     Readln;
End.

{Bài 7: Tìm các số nguyên tố < N , bằng sàng Erastosthène }

Uses   Crt,Dos;
Const  	Max      = 5000; { Mat khoang 116 /100 giay. Khong tang len > 50000 }
Var    	N,i,j,c,k    : LongInt;
       	A        	: Array[1..max] of Boolean;
       	h,m,s,p,dem  : Word;
       	T        	: LongInt;
Begin
     Clrscr;
     N := Max;
     Gettime(h,m,s,p);
     T   :=  6000*m + 100*s +p;
     For i:=1 to Max do A[i] := False;
     c := Trunc(sqrt(Max));
     A[1] := True;
     For k:=2 to c do
         If Not A[k] then
              Begin
                   i := sqr(k);
                   While i<= Max do
                         Begin
                                A[i] := True;
                                Inc(i,k);
                         End;
             End;
    dem := 0;
    For i:=1 to Max do
            If not A[i] then
                   Begin
                        Write(i:8);
                        dem := dem+1;
                        If dem mod (10*25) = 0 then readln;
                   End;
    	Gettime(h,m,s,p);
     	T   := 6000*m + 100*s +p - T ;
	Writeln('Mat thoi gian la : ',T);
    	Readln;
End. 

Kết thúc

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Tám 2015
M T W T F S S
« Jan   Sep »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: