Nội dung chính
Xem Tìm UCLN của 2 số nguyên dương M và N Pascal 2024
Ý 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.
Nhãn:
Bài tập Pascal,
Câu lệnh lặp,
Pascal cơ bản,
Vòng lặp while
Program UCLN;
uses crt; var a,b : integer;
begin write (‘nhap so a la ‘);
readln (a);
write (‘nhap so b la ‘);
readln (b);
while a < > b do
if a >b then a := a – b else b := b – a ;
write ( ‘ UCLN la :’ , a );
readln
end.
~~~~~~~~~~~~~~~~~~ Chúc bn học tốt ~~~~~~~~~~~~~~~~~
a. Lựa chọn thuật toán
Lựa chọn một thuật toán tối ưu.
Ví dụ:
Nếu M = N
– Đúng ƯCLN = M (hoặc N) ? Kết thúc;
– Sai Xét: nếu M > N
– Đúng ? M = M – N;
– Sai N = N – M;
Quá trình này được lặp lại cho đến khi M = N.
Bạn đang xem nội dung tài liệu Bài toán đặt vấn đề Tìm ước số chung lớn nhất (ưcln) của hai số nguyên dương M và N, để tải tài liệu về máy bạn click vào nút TẢI VỀ ở trên
Bài toán đặt vấn đề Với các giá trị: M = 25; N = 5. M = 88; N = 121. M = 997; N = 29. M = 2006; N=1998.Tìm ước số chung lớn nhất (ưCLN) của hai số nguyên dương M và N.Hãy chỉ ra những ưu điểm của việc giải bài toán bằng máy tính so với cách giải toán thông thường? Bài 6. Giải bài toán trên máy tínhCác bước thực hiện Bước 1: Xác định bài toán Xác định hai thành phần INPUT, OUTPUT.INPUT: M , N là hai số nguyên dương.OUTPUT: ưCLN(M, N).Ví dụ: Bước 2: Lựa chọn hoặc thiết kế thuật toán Nếu M = N – Đúng ưCLN = M (hoặc N) Kết thúc; – Sai Xét: nếu M > N – Đúng M = M – N; – Sai N = N – M; Quá trình này được lặp lại cho đến khi M = N. a. Lựa chọn thuật toán Lựa chọn một thuật toán tối ưu.Ví dụ: b. Diễn tả thuật toán Theo hai cách: Cách 1: Liệt kê các bước. Cách 2: Vẽ sơ đồ khối.Cách 1: Liệt kê các bước B1: Nhập M, N;B2: Nếu M = N lấy ưCLN = M (hoặc N), chuyển đến B5;B3: Nếu M >N thì M M – N rồi quay lại B2; B4: N N – M rồi quay B2;B5: Đưa ra kết quả ưCLN; Kết thúc. ĐĐSSCách 2: Diễn tả thuật toán bằng sơ đồ khối 5101010551525321LượtNhập M ,NM =N ?M > N ?N N – MM M – NĐưa ra M ; Kết thúc M= 25, N = 1025 = 10 ?25 >10M 25 – 1015 = 10 ?15 >10M 15 – 105 = 10 ?5 > 10 ?N = 10 – 55 = 5 ?ƯSLN (25,10) = 5MNNhập M,NM=N?M>N?Đưa ra M, kết thỳcM←M-NN←N-MM=25,N=1025=10?25>10?15←25-10ĐĐSSMô phỏng thuật toán tìm ƯCLN5101010551525321LượtNhập M ,NM =N ?M > N ?N N – MM M – NĐưa ra M ; Kết thúc M= 25 ,N = 1025 = 10 ?25 >10M 25 – 1015 = 10 ?15 >10M 15 – 105 = 10 ?5 > 10 ?N = 10 – 55 = 5 ?ƯCLN (25,10) = 5MNBước 3: Viết chương trình Sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán. Là tổng hợp giữa việc: Lựa chọn cách tổ chức dữ liệu. Bước 4: Hiệu chỉnh TEST:M = 8; N = 8 ưCLN = 8M = 25; N = 10 ưCLN = 5M = 88; N = 121 ưCLN = 11M = 17; N = 13 ưCLN = 1Thử chương trình bằng cách thực hiện nó với một số bộ INPUT tiêu biểu (TEST) để kiểm tra kết quả, nếu có sai sót thì hiệu chỉnh lại.Bước 5: Viết tài liệuMô tả chi tiết về bài toán, thuật toán, chương trình và kết quả thử nghiệm, hướng dẫn cách sử dụng. Từ tài liệu này, người sử dụng đề xuất các khả năng hoàn thiện thêm.Bước 2: Lựa chọn hoặc thiết kế thuật toán. Bước 1: Xác định bài toán. Bước 3: Viết chương trình. Bước 4: Hiệu chỉnh.Bước 5: Viết tài liệu.Các bước giải bài toán trên máy tính
File đính kèm:
bai 6 tim uoc so chung.ppt
Lorem ipsum dolor sit amet, consectetur adipiscing elit.Morbi adipiscing gravdio, sit amet suscipit risus ultrices eu.Fusce viverra neque at purus laoreet consequa.Vivamus vulputate posuere nisl quis consequat.
Đổi đơn vị (Tin học – Lớp 6)
5 trả lời
1 thẻ nhớ có 8GB chứa được bao nhiêu bài hát (Tin học – Lớp 6)
1 trả lời
1 thẻ nhớ có 8GB chứa được bao nhiêu bài hát (Tin học – Lớp 6)
1 trả lời
Mã hóa chữ số 2 (Tin học – Lớp 6)
1 trả lời
8 PB =….. kb (Tin học – Lớp 6)
1 trả lời
Nêu cách mã hóa các chữ số (Tin học – Lớp 6)
1 trả lời
Thao tác tạo và đổi tên tệp, thư mục (Tin học – Lớp 7)
1 trả lời
Hãy chuyển các biểu thức trong Python dưới đây sang biểu thức toán học tương ứng
a). a/b*2
b). a*b*c/2
c). 1/a*b/c
d). b/(a*a+b**0.5
27/09/2022 | 0 Trả lời
viết chương trình nhập từ bàn phím 2 số nguyên dương x,y (x
1) tính tổng các số chia hết cho 5
2) đếm các số chẵn
3) đưa ra màn hình danh sách các số lẻ chia hết cho 3
28/09/2022 | 0 Trả lời
a, xác định input, output
b, thiết kế thuật toán
c, viết khai báo biến
02/10/2022 | 0 Trả lời
viết chương trình hai số nguyên dương A,B từ bàn phím chu vi diện tích hình chữ nhật có 2 cạnh là a , b
02/10/2022 | 0 Trả lời
Bạn đang tìm hiểu bài viết: Tìm UCLN của 2 số nguyên dương M và N Pascal 2024
HỆ THỐNG CỬA HÀNG TRÙM SỈ QUẢNG CHÂU
Điện thoại: 092.484.9483
Zalo: 092.484.9483
Facebook: https://facebook.com/giatlathuhuongcom/
Website: Trumsiquangchau.com
Địa chỉ: Ngõ 346 Nam Dư, Trần Phú, Hoàng Mai, Hà Nội.
