Tìm ƯCLN của 2 số nguyên dương M và N Pascal

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

Quảng cáo

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



Phương pháp 1: Dưới đây là thuật toán tìm ƯCLN bằng phép trừ nhau được trình bày trong SGK Tin học 10.


var x, y, ƯCLN, BCNN: số nguyên;

bắt đầu

readln (x, y);
Báo cáo trạng thái: = x * y;

While x <> y do If x> y then x: = xy else y: = yx; ƯCLN: = x;

BCNN: = BCNN div ƯCLN;

write (UCLN, ”, BCNN);

chấm dứt.

Cách 2: Thuật toán Euclide: Ngoài cách tìm ƯCLN như trên. Bạn có thể sử dụng phép chia và phần dư (mod), chương trình sẽ được tối ưu hóa vì nó phải thực hiện các phép tính ít hơn.

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

var x, y, ƯCLN, BCNN, t: integer;

bắt đầu

readln (x, y); Báo cáo trạng thái: = x * y; t: = y mod x; Trong khi t <> 0 do Begin t: = x MOD y; x: = y; y: = t;

Chấm dứt;

ucln: = x;
BCNN: = BCNN div ƯCLN;

write (UCLN, ”, BCNN);

chấm dứt.


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

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 );

chấm dứt;

var x, y: integer;

bắt đầu

readln (x, y);

write (‘Ước chung lớn nhất là:’, ƯCLN (x, y), ‘Bội chung nhỏ nhất là:’, (x * y) div ƯCLN (x, y));

chấm dứt.

Tìm ƯCLN của 2 số nguyên dương M và N Pascal

Labels: Bài tập Pascal, Câu lệnh lặp, Pascal cơ bản, While. Vòng lặp

Tìm ƯCLN của 2 số nguyên dương M và N Pascal



Chương trình UCLN;

sử dụng crt; var a, b: integer;

begin write (‘nhap so a la’);

readln (a);

write (‘nhap so b la’);

readln (b);

trong khi một < > b làm

if a> b then a: = a – b else b: = b – a;

write (‘UCLN la:’, a);

readln

chấm dứt.

~~~~~~~~~~~~~~~~~~~ Chúc các bạn học hành may mắn ~~~~~~~~~~~~~~~~~~

một. Lựa chọn thuật toán

Chọn một thuật toán tối ưu.

Ví dụ:

Nếu M = M

– Đúng GCC = M (hoặc N)? Chấm dứt;

– Phán đoán sai: nếu M> FEMALE

– Đú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 Bài toán Tìm ước chung lớn nhất (uccln) 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 DOWNLOAD ở trên

Bài toán đặt ra 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 chung lớn nhất (uCLN) của hai số nguyên dương M và N. Hãy chỉ ra ưu điểm của việc giải toán bằng máy tính so với cách làm thông thường? Bài 6. Giải bài toán trên máy tính Các bước thực hiện Bước 1: Nêu 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: uCLN (M, N) .Ví dụ: Bước 2: Lựa chọn hoặc thiết kế thuật toán If M = N – True  uCLN = M (or N)  End; – Sai  Xét: if M> N – True  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 Chọn một thuật toán tối ưu. Ví dụ: b. Mô 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 cCLN = 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 xoay B2; B5: Cho kết quả CLN; Chấm dứt. Phương án 2: Mô tả thuật toán bằng sơ đồ khối 5101010551525321 Đầu vào M, NM = N? M> N? N N – MM M – ND Đầu ra M; Hết M = 25, N = 1025 = 10? 25> 10M 25 – 1015 = 10? 15> 10M 15 – 105 = 10? 5> 10? N = 10 – 55 = 5? LSLN (25,10) = 5MN Nhập M, NM = N? M> N? Cho M, endMM-NN ← N-MM = 25, N = 1025 = 10? 25> 10? 15 ← 25-10ĐSS Thuật toán mô phỏng tìm ƯCLN510101010551525321, NM = N? M> N? N N – MM M – ND Trả về 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? CCLN (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. Nó là sự kết hợp của:  Lựa chọn cách tổ chức dữ liệu. Bước 4: Điều chỉnh TEST: M = 8; N = 8  uCLN = 8M = 25; N = 10  cLN = 5M = 88; N = 121  uCLN = 11M = 17; N = 13  CLN = 1Thử chương trình bằng cách thực hiện với một số bộ INPUT (TEST) điển hình để kiểm tra kết quả, nếu có sai sót thì sửa lại.Bước 5: Viết tài liệuNêu nội dung bài học. thuật toán, thuật toán, chương trình và kết quả kiểm tra, hướng dẫn sử dụng. Từ tài liệu này, người dùng đề xuất các khả năng bổ sung.Bước 2: Lựa chọn hoặc thiết kế thuật toán. Bước 1: Xác định vấn đề. Bước 3: Viết chương trình. Bước 4: Sửa lỗi.Bước 5: Soạn văn bản Các bước giải bài toán trên máy tính

File đính kèm:

  • Tìm ƯCLN của 2 số nguyên dương M và N Pascal

    Bài 6 so sánh trái tim.ppt

Lorem ipsum dolor sit amet, consectetur adipiscing elit.Morbi adipiscing gravdio, sit amet suscipit risus ultrices eu.Fusce viverra neque at purus laoreetequa.Vivamus vulputate posuere nisl quisequat.

Tạo một tài khoản

Tìm ƯCLN của 2 số nguyên dương M và N Pascal

Thay đổi đơn vị (Tin học – Lớp 6)

Tìm ƯCLN của 2 số nguyên dương M và N Pascal

5 câu trả lời

1 thẻ nhớ 8GB chứa được bao nhiêu bài hát? (Tin học – Lớp 6)

1 câu trả lời

1 thẻ nhớ 8GB chứa được bao nhiêu bài hát? (Tin học – Lớp 6)

1 câu trả lời

Mã hóa chữ số 2 (Tin học – Lớp 6)

1 câu trả lời

8 PB = ….. kb (Tin học – Lớp 6)

1 câu trả lời

Làm thế nào để mã hóa các chữ số? (Tin học – Lớp 6)

1 câu trả lời

Tạo và đổi tên tệp và thư mục (Tin học – Lớp 7)

1 câu trả lời

  • Chuyển đổi các biểu thức Python sau thành biểu thức toán học tương ứng

    một). a / b * 2

    b). a * b * c / 2

    c). 1 / a * b / c

    d). b / (a ​​* a + b ** 0,5

    27 tháng 9 năm 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ủa tất cả các số chia hết cho 5

    2) đếm số chẵn

    3) hiển thị danh sách các số lẻ chia hết cho 3

    28 tháng 9 năm 2022 | 0 Trả lời

  • a, xác định đầu vào, đầu ra

    b, thiết kế thuật toán

    c, viết khai báo biến

    Ngày 2 tháng 10 năm 2022 | 0 Trả lời

  • viết chương trình cho hai số nguyên dương A và B từ bàn phím, diện tích hình chữ nhật có 2 cạnh là a, b

    Ngày 2 tháng 10 năm 2022 | 0 Trả lời

Bạn đang xem chuyên mục Hỏi đáp
Thuộc website web giải đáp

Quảng cáo
Hỏi đáp

Leave a Reply

Email của bạn sẽ không được hiển thị công khai.

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>