Lũy thừa 2, 3 và 5

Với mỗi giá trị N cho trước hãy sinh N số đầu tiên theo trật tự tăng dần là tích các lũy thừa của 2, 3 và 5.

LUYTHUA.INP	LUYTHUA.OUT
12	1 2 3 4 5 6 8 9 10 12 15 16

Dữ liệu vào: tệp văn bản LUYTHUA.INP

Chứa số tự nhiên N,            1 £ N £ 1000.

Dữ liệu ra: tệp văn bản LUYTHUA.OUT

N số tìm được, mỗi dòng một số.

Thuật toán

Gọi S là tập các số cần tìm. Ta có

   (i) 1 Î S

   (ii) Nếu x Î S thì 2x, 3x, 5x Î S.

Giả sử các phần tử trong S được sắp tăng và ta đã tìm được phần tử thứ i. Ta kí hiệu S(i) = { a₁, a₂,…,a_i }. Để tìm phần tử thứ i+1 ta nhận xét

a_i+1 = Min { 2x, 3y, 5z | x, y, z Î S(i), 2x > a_i, 3y > a_i, 5z > a_i }

Ta sử dụng 3 biến i2, i3, i5 để ghi nhận các chỉ số trong S sao cho a_i2 = x, a_i3 = y và a_i5 = z.  Các biến a[1], i2, i3 và i5 được khởi trị 1.

Khi đó hàm Next(i) sinh phần tử sát sau phần tử A[i] sẽ như sau:

function Next(i: integer): integer;

begin

   while (a[i2] * 2 <= a[i]) do i2 := i2 + 1;

   while (a[i3] * 3 <= a[i]) do i3 := i3 + 1;

   while (a[i5] * 5 <= a[i]) do i5 := i5 + 1;

   Next := Min(a[i2]*2, a[i3]*3, a[i5]*5);

end;

(*  Pascal  *)

(***************************************

         LUY THUA cua 2, 3, 5

  *************************************)

program LuyThua;

uses crt;

const bl = #32; mn = 1001; fn = 'LUYTHUA.INP'; gn = 'LUYTHUA.OUT';

type ml1 = array[0..mn] of longint;

var f,g: text;

n: integer;

a: ml1;

procedure Doc: tự viết;

function Min(a,b,c: longint): tự viết;

function Next(i: integer): tự viết;

procedure Sinh;

 var i: longint;

begin

  assign(g,gn); rewrite(g);

  a[1] := 1; writeln(g,1);

  i2 := 1; i3 := 1; i5 := 1;

  for i := 2 to n do

    begin

      a[i] := Next(i-1);

      writeln(g,a[i]);

    end;

   close(g);

end;

BEGIN

 Doc; Sinh;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH