- Ebook Giải thuật và lập trình Lê Minh Hoàng
- Các thuật toán sắp xếp trong Pascal

Tìm ước chung lớn nhất và bội chung nhỏ nhất pascal



Ý tưởng: Lấy số lớn hơn trong 2 số trừ đi nhau. Lặp lại thao tác đến khi nào 2 số bằng nhau -> UCLN. Lấy tích của 2 số chia cho UCLN -> BCNN.

Thuật toán tìm Bội chung nhỏ nhất và Ước chung lớn của 2 số trong Pascal:


Cách 1: Dưới đây là thuật toán tìm UCLN bằng cách trừ đi nhau, được trình bày trong SGK tin học 10.

var x,y,UCLN,BCNN:integer;
begin
readln(x,y);
BCNN:=x*y;
While x<>y do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;
write(UCLN,' ',BCNN);
end.

Cách 2: Thuật toán Euclide: Ngoài cách tìm UCLN như trên. Các bạn có thể sử dụng cách chia lấy dư (mod), chương trình sẽ tối ưu do phải thực hiện ít phép tính hơn.

Ý tưởng: UCLN của 2 số x, y cũng là UCLN của 2 số y và x mod y, vậy ta sẽ đổi x là y, y là x mod y cho đến khi y bằng 0. Khi đó UCLN là x.

var x,y,UCLN,BCNN,t:integer;
begin
readln(x,y);
BCNN:=x*y;
t:= y mod x;
While t <> 0 do
      Begin
        t:= x MOD y;
        x:= y;
        y:= t;
      End;
ucln:=x;
BCNN:=BCNN div UCLN;
write(UCLN,' ',BCNN);
end.

Cách 3: Tìm UCLN bằng cách dùng đệ quy: Đệ quy được hiểu đơn giản là sự gọi nhiều lần chương trình con trong chương trình. Thực sự, đối với bài toán đơn giản, không ai sử dụng đệ quy vì sẽ làm phức tạp vấn đề và làm chương trình trở nên rắc rối, phải thực hiện nhiều phép tính hơn. Tuy nhiên, nếu bắt buộc phải dùng đệ quy, các bạn có thể tham khảo cách làm dưới đây:

function ucln(x,y:integer):integer;
begin
if x = y then
ucln:=x
else if x > y then
ucln:=ucln(x mod y,y)
else
ucln:=ucln(x, y mod x);
end;
var x,y:integer;
begin
readln(x,y);
write('Ước chung lớn nhất là: ', UCLN(x,y), ' Bội chung nhỏ nhất là: ', (x*y) div UCLN(x,y));
end.




Nặc danh nói...

Nếu a=0 và b=0 thì UCLN, BCNN là bao nhiêu? Chương trình này chưa đầy đủ bạn à.


09:31 Ngày 28 tháng 11 năm 2012
Nặc danh nói...

Rất hay! Mình sắp thi Tin rồi nên dạo này ôn gấp quá. Mong code pascal có thể cung cấp thêm nhiều chương trình nữa. Cám ơn nhiều


20:39 Ngày 13 tháng 12 năm 2012
vo duy dong nói...

PHẦN ĐỆQUY TÌM UCLN NẾU DÙNG MOD LÀ SAI RỒI;;;;


10:34 Ngày 21 tháng 12 năm 2012
Nặc danh nói...

Every weekend i used to pay a quick visit this web site, for the
reason that i wish for enjoyment, as this this web page conations actually nice funny material
too.

Here is my webpage :: bankruptcy laws in florida


00:41 Ngày 16 tháng 03 năm 2013
Nặc danh nói...

Every weekend i used to pay a quick visit this
web site, for the reason that i wish for enjoyment,
as this this web page conations actually nice
funny material too.

Look into my web site; bankruptcy laws in florida


00:41 Ngày 16 tháng 03 năm 2013
Nặc danh nói...

lan sau nho dang nhung bai day du va chinh xax voi yeu cau cua nguoi dung


07:55 Ngày 18 tháng 03 năm 2013
Nặc danh nói...

Mình học thấy có một cách tìm ƯCLN rất hay mà đơn giản.
VD: Tìm ƯCLN của a và b
begin
For i:=1 to a do
If (a mod i=0) and (b mod i=0) then UCLN:=i;
end;
Các bạn thấy sao?


14:09 Ngày 24 tháng 03 năm 2013
ngoc nguyen nói...

CÁCH NÀO CŨNG ĐƯỢC NHƯNG TUỲ THUỘC VÀO YÊU CẦU BÀI TOÁN BẠN ƠI


11:12 Ngày 29 tháng 03 năm 2013
Nặc danh nói...

cam on nha


18:39 Ngày 03 tháng 04 năm 2013
Nặc danh nói...

program UCLN_BCNN;
uses crt;
var a, b, aa, bb: integer;
begin
clrscr;
writeln('TIM UOC CHUNG LON NHAT VA BOI CHUNG NHO NHAT');
writeln('-------------------------*****-----------------------');
writeln('Nhap a:'); readln(a);
writeln('Nhap b:'); readln(b);
aa:=a; bb:=b;
while aa<> bb do
begin
if aa<>bb then aa:= aa - bb
else
bb:= bb - aa;
end;
writeln('Uoc chung lon nhat la:',aa);
writeln('Boi chung nho nhat la:',a*b div aa);
readln;
end.


16:27 Ngày 11 tháng 05 năm 2013
Phẩm Nguyễn Văn nói...

Nếu a<b thì a mod b nó không thành công bạn à! bài này còn thiếu nhiều chỗ quá


08:10 Ngày 12 tháng 05 năm 2013
Nặc danh nói...

code về bị lỗi exit code


10:33 Ngày 22 tháng 06 năm 2013
Tin hoc tre Liem Chinh nói...

các bạn xem bài của mih xem sai cho nao nha
var x,y:integer;
function KTUB(x,y:integer):boolean;
var UCLN,BCNN:integer;
begin
BCNN:=x*y;
While x<>y do If x>y then x:=x-y else y:=y-x;
UCLN:=x;
BCNN:=BCNN div UCLN;
end;
begin
write('nhap x=');readln(x);
write('nhap y=');readln(y);
if KTUB(x,y) then write(x,',',y);
readln
end.


09:23 Ngày 02 tháng 07 năm 2013
Bích Nguyễn nói...

giải giúp mình bài này với :
Tìm UCLN và BCNN của 3 sô a, b, c


14:01 Ngày 21 tháng 09 năm 2013
Lê Hoàng nói...

mẹ dk quái đâu lặp vô hạn cmnr


16:08 Ngày 04 tháng 11 năm 2013
Nặc danh nói...

Nếu 1 trong 2 số a và b = 0 thì n=0 nên chương trình lập tức thoát khỏi vòng lặp: với n= b mod a; ta kiểm tra : while n <>0 do vì a và b của bạn đều = 0 nên ct sẽ dừng.


21:41 Ngày 18 tháng 11 năm 2013
Hán Long nói...

ngu zua thui toan dau dat
p co cau if i<>0 then ...
else exit;


20:51 Ngày 20 tháng 11 năm 2013
Bé Con nói...

ƯCLN
m:=a;
n:=b;
while a<>b do
if a>b then a:=a-b else b:=b-a;
write('ucln',a);
write('bc:',m*n div a);


19:52 Ngày 16 tháng 12 năm 2013
Hán Long nói...
Nhận xét này đã bị tác giả xóa.
Nặc danh nói...

tại sao BCNN=x*y, em lớp 7


17:51 Ngày 13 tháng 03 năm 2014
Nặc danh nói...

Cảm ơn trang web rất nhiều, nó đã giúp tôi giỏi giang hơn


17:54 Ngày 13 tháng 03 năm 2014
Tư Hà nói...

hay.... thanks nhiều ạ


16:57 Ngày 29 tháng 03 năm 2014
Tư Hà nói...

hay.... thanks nhiều ạ


16:58 Ngày 29 tháng 03 năm 2014
nguyen van nói...

Vậy còn tìm UCLN của 1 dãy số thì làm thế nào vậy


20:20 Ngày 13 tháng 04 năm 2014
nguyen van nói...

Vậy còn tìm UCLN của 1 dãy số thì làm thế nào vậy


20:20 Ngày 13 tháng 04 năm 2014
Nặc danh nói...

tìm a,b biết:
BCNN (a,b) + ƯCLN (a,b) = 15


20:11 Ngày 30 tháng 11 năm 2014
Nặc danh nói...

Tìm a,b biết:
BCNN (a,b) + ƯCLN (a,b) = 15


20:12 Ngày 30 tháng 11 năm 2014
Nặc danh nói...

Oooppp


21:53 Ngày 14 tháng 12 năm 2014

Đăng nhận xét

Thành viên Blog

Tổng số lượt xem trang

Translate

Return to top of page Copyright © 2012 | Theme by Hack Tutors. Cung cấp bởi Blogger.
Các code pascal trong blog được sưu tầm, lựa chọn sao cho tối ưu nhất. Cảm ơn các tác giả đã viết thuật toán.