- 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 à.


lúc 09:31 28 tháng 11, 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


lúc 20:39 13 tháng 12, 2012
vo duy dong nói...

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


lúc 10:34 21 tháng 12, 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


lúc 00:41 16 tháng 3, 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


lúc 00:41 16 tháng 3, 2013
Nặc danh nói...

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


lúc 07:55 18 tháng 3, 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?


lúc 14:09 24 tháng 3, 2013
Unknown 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


lúc 11:12 29 tháng 3, 2013
Nặc danh nói...

cam on nha


lúc 18:39 3 tháng 4, 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.


lúc 16:27 11 tháng 5, 2013
Unknown 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á


lúc 08:10 12 tháng 5, 2013
Nặc danh nói...

code về bị lỗi exit code


lúc 10:33 22 tháng 6, 2013
Unknown 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.


lúc 09:23 2 tháng 7, 2013
Unknown 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


lúc 14:01 21 tháng 9, 2013
Unknown nói...

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


lúc 16:08 4 tháng 11, 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.


lúc 21:41 18 tháng 11, 2013
Unknown nói...

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


lúc 20:51 20 tháng 11, 2013
Nặc danh nói...

kuku


lúc 20:52 20 tháng 11, 2013
Unknown 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);


lúc 19:52 16 tháng 12, 2013
Unknown 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


lúc 17:51 13 tháng 3, 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


lúc 17:54 13 tháng 3, 2014
Unknown nói...

hay.... thanks nhiều ạ


lúc 16:57 29 tháng 3, 2014
Unknown nói...

hay.... thanks nhiều ạ


lúc 16:58 29 tháng 3, 2014
Unknown nói...

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


lúc 20:20 13 tháng 4, 2014
Unknown nói...

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


lúc 20:20 13 tháng 4, 2014
Nặc danh nói...

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


lúc 20:11 30 tháng 11, 2014
Nặc danh nói...

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


lúc 20:12 30 tháng 11, 2014
Nặc danh nói...

Oooppp


lúc 21:53 14 tháng 12, 2014
Nặc danh nói...

ai lam ho minh ve so do khoi cua thuat toan tim ucln cua n so nguyen duong


lúc 10:38 18 tháng 1, 2015
Nặc danh nói...

viet chuong trinh con tim bcnn cua 2 so nguyen duong a,b. ban nao giup mk voi


lúc 14:44 3 tháng 4, 2015
Unknown nói...

lam theo Thuật toán Euclide bo di cau lenh x:= y di code pascal di nhe


lúc 20:24 14 tháng 4, 2015
Unknown nói...

Viet chuong trinh con duoi dang ham tinh boi so chung nho nhat cua hai so nguyen duong a,b. Làm giúp mình với.


lúc 14:40 24 tháng 4, 2015
Nặc danh nói...

nó cứ sao ý


lúc 21:21 4 tháng 6, 2015
Unknown nói...

nếu muốn áp dụng hàm tìm ucln của 2 so cho 4 số thì làm thế nào nhỉ mn ?


lúc 23:04 16 tháng 11, 2015
Lê Hữu Trung nói...

Mọi người có thể làm bài về tìm ước chung lớn nhất của 1 dãy số không ạ! cám ơn mọi người nhiều! :)


lúc 15:13 22 tháng 3, 2016
Unknown nói...

Các cao thủ ơi giúp e bài này với ạ. Nhập vào 4 số a=1, b=3, c=5, d=9 dùng vòng lặp in ra dãy bằng nhau 4 4 4 4
Các cao thủ giúp e với, e mới vọc nên trình độ còn kém lắm, e xin chân thành cảm ơn


lúc 23:01 5 tháng 4, 2016
Unknown nói...

Nếu có 2 giá trị của i thì saosao.??


lúc 11:33 6 tháng 4, 2016
Unknown nói...

Không có ai giúp mình à?


lúc 21:32 6 tháng 4, 2016
Trần Hoà nói...

bạn giúp minh code tim UCLN cua 3 so voi


lúc 15:30 21 tháng 4, 2016
Unknown nói...

thứ năm này ai đi thi tin thì điểm danh nào


lúc 18:41 26 tháng 4, 2016
Nguyễn Thái Chung nói...
Nhận xét này đã bị tác giả xóa.
Nặc danh nói...

Giúp mh lập ctrinh cho bài toán tìm số Fibonaci thứ n biết: F(1)=F(2)=1 và F(n)=F(n-1)+F(n-2) với ạ.


lúc 02:02 30 tháng 5, 2016
Unknown nói...

ucln cua 1 day so lam the nay ne may ban:
uses crt;
var a:array[1..100]of integer;x,i,n:longint;
function ucln(a,b:longint):longint;
var i:integer;
begin
for i:=b downto 1 do
begin
if (a mod i=0) and (b mod i=0) then break;
end;
ucln:=i;
end;
begin
clrscr;
write('nhap n= ');
readln(n);
for i:=1 to n do
begin
write('a[',i,']= ');readln(a[i]);
end;
x:=ucln(a[1],a[2]);
for i:=3 to n do
x:=ucln(x,a[i]);
write(x);
readln;
end.



lúc 14:28 30 tháng 5, 2016
Unknown nói...

tìm 2 số thì để tìm nhìu số mới khó


lúc 09:47 4 tháng 8, 2016
Nặc danh nói...

NHanh


lúc 19:35 14 tháng 4, 2017
Unknown nói...

Bc, Uc theo cách t thì dễ hơn
BC:
Uses crt;
var i,d,bc:integer;
a:array[1..1000] of integer;
begin
Clrscr;
readln(n);
for i:=1 to n do readln(a[i]);
bc:=1;
repeat
bc:=bc+1;
d:=0;
for i:=1 to n do if bc mod a[i]=0 then d:=d+1;
until d=n;
writeln(bc);
readln
end.
BC:
Uses crt;
var i,d,bc:integer;
a:array[1..1000] of integer;
begin
Clrscr;
readln(n);
for i:=1 to n do readln(a[i]);
bc:=1;
repeat
bc:=bc+1;
d:=0;
for i:=1 to n do if bc mod a[i]=0 then d:=d+1;
until d=n;
writeln(bc);
readln
end.
BC:
Uses crt;
var i,d,bc:integer;
a:array[1..1000] of integer;
begin
Clrscr;
readln(n);
for i:=1 to n do readln(a[i]);
bc:=1;
repeat
bc:=bc+1;
d:=0;
for i:=1 to n do if bc mod a[i]=0 then d:=d+1;
until d=n;
writeln(bc);
readln
end.
UC:
Uses crt;
var i,d,uc:integer;
a:array[1..1000] of integer;
begin
Clrscr;
readln(n);
uc:=0;
for i:=1 to n do
begin
readln(a[i]);
uc:=uc+a[i];
end;
repeat
uc:=uc-1;
d:=0;
for i:=1 to n do if a[i] mod uc=0 then d:=d+1;
until d=n;
writeln(uc);
readln
end.

Zeb :)))


lúc 20:03 16 tháng 11, 2017
NPN nói...

var n,a,b:int64;
function UC(a,b:integer):int64;
begin
if a=b then UC:=a;
if a>b then UC:=UC(a-b,b)
else UC:=uc(a,b-a);
end;
begin
read(a,b);
write(UC(a,b));
readln;
end.


lúc 22:00 6 tháng 12, 2017
Nặc danh nói...

con cặc ngu nhhuw con chó đòi gank team


lúc 14:35 22 tháng 3, 2018
Unknown nói...

Cho mình hỏi nếu chỉ muốn tìm BCNN của 2 số thôi thì làm thế nào ạ ?


lúc 22:43 27 tháng 3, 2018
Unknown nói...

TCA HeroZz hay nhưng lại bị lặp


lúc 20:12 28 tháng 4, 2018
vai cho nói...

fghgfffffffffffffffff


lúc 11:02 14 tháng 8, 2018
Unknown nói...

var a,b,bc:longint;
begin
i:=0;
while bc<>0 do begin
i:=i+1;
if (i mod a=0) and ( i mod b=0) then bc:=i;
end;
write('bcnn =',bc);
readln
end.
cho hỏi đúng hay sai á


lúc 11:16 21 tháng 11, 2018
Unknown nói...

- Cái này của lớp mấy ạ


lúc 22:05 22 tháng 3, 2019
Nặc danh nói...

Thế UCLN của 25, 11 là 25-11 a`


lúc 22:33 30 tháng 12, 2019
Unknown nói...

Sai rồi bạn ơi. Đảm bảo kết quả của bạn là i=1 :)) . bài này cũng khá lâu rồi. Bạn chắc đã đi trước mình. Mình mới lớp 11 và đang trên con đường làm 1 lập trình viên. Bạn có thể giúp mình được ko?


lúc 18:28 28 tháng 3, 2020
Nặc danh nói...

bú cu


lúc 13:11 9 tháng 2, 2021
Nặc danh nói...

Có bạn nói là i=1 theo mik là sai (ý kiến riêng) vì đây là vòng lặp for...do nên giá trị của i sẽ tăng dần và biến UCLN sẽ nhận giá trị khác (nếu i thay đổi và a,b mod i=0)
Vd: a=3, b=6;
+ Vòng lặp1: i:=1, biến UCLN=1 do a,b mod i=0
+ vòng lặp2: i:=2, UCLN=1 do a mod i=0 nhưng b mod i <>0 (k° thỏa mãn đk)
+ vòng lặp3: i=3, UCLN=3
do a,b mod i=0
-kết thúc vòng lặp vì vòng lặp có giá trị cuối là a(a=3).


lúc 13:12 24 tháng 3, 2021
Unknown nói...

Mình cũng đang cần bài này
Kiểu dùng ctc ấy


lúc 23:23 6 tháng 5, 2021
Unknown nói...

Giúp em bài này với
Tìm ucln của 3 số nguyên m, n, p(1<=m, n, p<=10000)
(có dùng chương trình con ạ)


lúc 23:33 6 tháng 5, 2021
Unknown nói...

Giúp em bài này với
Tìm ucln của 3 số nguyên m, n, p(1<=m, n, p<=10000)
(có dùng chương trình con ạ)


lúc 23:33 6 tháng 5, 2021
Nặc danh nói...

Bạn cứu mik một mạng nếu ko thầy mik kill mik chết


lúc 14:46 26 tháng 5, 2021
Nặc danh nói...

hé he he he he hè . . .


lúc 16:07 26 tháng 6, 2021
Nặc danh nói...

khá ok
chưa đầy đủ một tí thôi


lúc 10:56 30 tháng 7, 2021
Nặc danh nói...

ko chạy đc ;-;


lúc 16:43 18 tháng 5, 2022
Nặc danh nói...

:)))


lúc 22:53 8 tháng 4, 2023
Nặc danh nói...

kljs


lúc 14:18 2 tháng 11, 2023
Nặc danh nói...

cai nay tam on nhung chx hoan thien.


lúc 14:41 11 tháng 12, 2023

Đă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.