Cần gấp , sáng 3/5 thi rồi

[Jackychanh]

Tìm bội số chung nhỏ nhất (BSCNN) và ươc số chung lớn nhất (USCLN) của hai số nguyên dương m,n nhập từ bàn phím.

Program bt;
 Var a,b,ucln: integer; bcnn : real;
begin
 Write ('Nhap so nguyen m bat ky :');readln(m);
 Write ('Nhap so nguyen n bat ky :');readln(n);
 Repeat
  If a>b then
   a:=a-b
  Else
   b:=b-a;
 Until a=b;
 ucln :=a;
 bcnn := (a*b)/ucln;
 Writeln ('uoc so chung lon nhat cua 2 so nguyen m va n la :',ucln);
 Writeln ('Boi so chung lo nhat cua 2 so nguyen m va n la :',bcnn);
 readln;
end.

Bài của mình thế này nhưng ko biết tại sao kết quả lại ko đúng :
Vi du : m=20 ; n= 10
uoc so chung lon nhat cua 2 so nguyen m va n la : 10
Boi so chung nho nhat cua 2 so nguyen m va n la : 10
Đáng lẽ kết quả phải là :

uoc so chung lon nhat cua 2 so nguyen m va n la : 10
Boi so chung nho nhat cua 2 so nguyen m va n la : 20

Mong các bạn thể tìm chỗ sai và giải thích dùm trong thời gian ngắn nhất có thể, vì ngày mai là mình thi học kỳ môn Tin rồi ^^!! Hu Hu ~^_^~ !! Xin cám ơn.

[zoejoe]

Tìm bội số chung nhỏ nhất (BSCNN) và ươc số chung lớn nhất (USCLN) của hai số nguyên dương m,n nhập từ bàn phím.

Program bt;
 Var a,b,ucln: integer; bcnn : real;
begin
 Write ('Nhap so nguyen m bat ky :');readln(m);
 Write ('Nhap so nguyen n bat ky :');readln(n);
 Repeat
  If a>b then
   a:=a-b
  Else
   b:=b-a;
 Until a=b;
 ucln :=a;
 bcnn := (a*b)/ucln;
 Writeln ('uoc so chung lon nhat cua 2 so nguyen m va n la :',ucln);
 Writeln ('Boi so chung lo nhat cua 2 so nguyen m va n la :',bcnn);
 readln;
end.

Bài của mình thế này nhưng ko biết tại sao kết quả lại ko đúng :
Vi du : m=20 ; n= 10
uoc so chung lon nhat cua 2 so nguyen m va n la : 10
Boi so chung nho nhat cua 2 so nguyen m va n la : 10
Đáng lẽ kết quả phải là :

uoc so chung lon nhat cua 2 so nguyen m va n la : 10
Boi so chung nho nhat cua 2 so nguyen m va n la : 20

Mong các bạn thể tìm chỗ sai và giải thích dùm trong thời gian ngắn nhất có thể, vì ngày mai là mình thi học kỳ môn Tin rồi ^^!! Hu Hu ~^_^~ !! Xin cám ơn.

Đơn giản thế mà cũng sai à Bạn nên nhớ là việc sử lí tìm UCLN của bạn đã làm thay đổi giá trị của các biến a, b cho tới khi cả 2 bằng nhau (theo dữ liệu thì =10) => BCNN cùa bạn là 10*10/10 =)) Bạn nên dùng 2 biến tmp để chứa tạm a, b rồi xử lí nhé !

[Jackychanh]

Đơn giản thế mà cũng sai à Bạn nên nhớ là việc sử lí tìm UCLN của bạn đã làm thay đổi giá trị của các biến a, b cho tới khi cả 2 bằng nhau (theo dữ liệu thì =10) => BCNN cùa bạn là 10*10/10 =)) Bạn nên dùng 2 biến tmp để chứa tạm a, b rồi xử lí nhé !

Vâng , xin cám ơn nhiều nhé đúng là khờ thật

[lee_huynh306]

Như vậy mà compile đc cũng hay à ^^ m,n chưa khai báo nữa, bạn này hậu đậu wo'

[hung06061995]

Anh làm ơn giải thích cho em thuật giải của bài này với
Chứ không chắc đêm nay ngủ không được

[zoejoe]

Anh làm ơn giải thích cho em thuật giải của bài này với
Chứ không chắc đêm nay ngủ không được

Trùi, thuật toán sơ cấp thôi mà Tìm UCLN bằng cách trừ dần cho tới khi 2 số bằng nhau thì đó là ước chung lớn nhất. Bội chung nhỏ nhất có công thức mà, chỉ làm theo thôi !!

[Tri Duc]

Anh làm ơn giải thích cho em thuật giải của bài này với
Chứ không chắc đêm nay ngủ không được

ước chung lớn nhất là trừ dần cho tới khi bằng 0 thôi! còn bội chung nhỏ nhất = tích 2 số/ucln Okie!

[=========> Bổ sung bài viết <=========]

Đơn giản thế mà cũng sai à Bạn nên nhớ là việc sử lí tìm UCLN của bạn đã làm thay đổi giá trị của các biến a, b cho tới khi cả 2 bằng nhau (theo dữ liệu thì =10) => BCNN cùa bạn là 10*10/10 =)) Bạn nên dùng 2 biến tmp để chứa tạm a, b rồi xử lí nhé !

cái này hình như hổng phải :-? vì nếu cho a=10, b=10 thì chương trình sẽ xét trường hợp a=b chứ a<b hay a>b đâu mà a,b thay đổi! cần xem xét lại!

[hung06061995]

bó tay, em không hiểu ở chỗ là tại sao cách này lại cho ra UCLN

[tailoiloitai]

Các bạn ơi ai biết trò chơi dò mìn giúp tôi với cần gấp

[ConanKudo]

Mình sẽ giải thích cho bạn
Thuật toán tìm Ước chung lớn nhất của 2 số nguyên dương a,b mà các bạn trừ dần ở trên gọi là thuật toán Euclid.
Tư tưởng của thuật toán này khá đơn giản:
Nếu gọi d là ước chung lớn nhất của a và b
Thì (a-b) và (b-a) cũng chia hết cho a và b ! Do ở đây điều kiện là ước chung lớn nhất nên ta chỉ xét max(a-b,b-a) tức là nếu a>b với cả a<b ý.
Bạn làm như các bạn đã làm trên kia
đến khi nào a = b,thì ta thấy số lớn nhất mà cả a và b cùng chia hết chính là a.Và đó cũng là kết quả
Độ phức tạp của cái thuật toán này trong TH xấu nhất có thể lên đến O(A).
Nếu bạn sử dụng Binary Euclid thì chỉ cỡ O(LogA).Nếu bạn có nhã hứng mình sẽ post cho bạn tham khảo