Tìm bội chung nhỏ nhất của N số (ví dụ: mảng 1 chiều)

Như trong bài viết Tìm UCLN và BCNN đã trình bày cách tìm tuy nhiên chỉ áp dụng với trường hợp 2 số. Bài toán ra là tìm BCNN của mảng 1 chiều, vậy sẽ phải viết chương trình như thế nào?

Bội số chung nhỏ nhất (The Least Common Multiple hay Lowest Common Multiple) của một nhóm các số nguyên, gọi tắt là LCM, là số nhỏ nhất mà có thể chia hết cho tất cả các số đó. Có nhiều giải pháp để tìm LCM của hai số nguyên, một trong những giải pháp dễ dàng nhất là dùng thuật giải Euclid. Cho hai số nguyên a và b, chúng ta có công thức LCM(a, b) = (a x b) / GCD(a, b). Như vậy quá trình tính toán sẽ thông qua các bước sau:

1. Bước 1. Sử dụng thuật toán Euclid để tìm ước chung lớn nhất GCD (a, b)
2. Bước 2. Tính giá trị a x b.
3. Bước 3. Chia kết quả bước 2 cho kết quả bước 1 chúng ta được giá trị LCM cần tìm.

Để tìm LCM của n số chúng ta đầu tiên chọn ra 2 số rồi tính LCM của chúng, sau đó lấy thêm số khác để tính LCM của LCM mới tìm được và số mới chọn ra, cứ như thế cho tới khi nào hết n số. Ví dụ tìm LCM của 2, 3 và 5. Đầu tiên ta tính LCM(2, 3) = 6. Sau đó tìm LCM(6, 5) = 30.

uses crt;
var x, y, i, n, ucln, bcnn: longint;
  a: array[1..100] of integer;
function h_ucln(x,y:integer):integer;
begin
 while x<>y do
  if x>y then
   x:=x-y
  else
   y:=y-x;
 h_ucln:=x;
end;
begin
 clrscr;
 repeat
  write('Nhap N (N>=2): ');
  readln(n);
 until(n>=2);
 for i:=1 to n do
 begin
  write('Phan tu thu ',i,' = ');
  readln(a[i]);
 end;
 ucln:=h_ucln(a[1],a[2]);
 bcnn:=(a[1]*a[2]) div ucln;
 for i:=3 to n do
 begin
  ucln:=h_ucln(bcnn,a[i]);
  bcnn:=(bcnn*a[i]) div ucln;
 end;
 writeln('bcnn la: ',bcnn);
 readln;
end.

CodePascal.Blogspot.com sưu tầm