Số độ cao h

Số độ cao h

               Độ cao của một số tự nhiên là tổng các chữ số của số đó. Sinh toàn bộ các số tự nhiên có tối đa ba chữ số và có độ cao h cho trước. Ghi kết quả vào một tệp văn bản có tên cho trước.

Thuật toán - gia sư tin học

Bài toán này có cách phát biểu khác và tổng quát như sau: có n cốc nước dung tích 9 thìa mỗi cốc. Cho một bình đựng  h  thìa nước. Hãy xác định mọi phương án chia nước vào các cốc.

Ta xét lời giải với n = 3. Ta có h = 0..27.

1. Các số cần tìm y có dạng y = abc, a + b + c = h và a biến thiên từ mina đến maxa, trong đó mina là lượng nước ít nhất trong cốc đầu tiên a, maxa là lượng nước lớn nhất trong cốc a. Nếu đổ đầy hai cốc b và c, mỗi cốc 9 thìa nước thì lượng nước còn lại sẽ là tối thiểu cho cốc a. Ngược lại, nếu tổng cộng chỉ có h < 9 thìa nước thì lượng nước tối đa trong cốc a phải là h. Ta có

if h £ 18 then mina := 0 else mina := h-18;

if h ³ 9 then maxa := 9 else maxa := h;

2. Với mỗi a = mina..maxa ta tính

2.1. bc = h-a (biến bc chứa tổng các chữ số b và c).

2.2. Giải bài toán nhỏ với n = 2.

if bc £ 9 then minb := 0 else minb := bc-9;

if bc ³ 9 then maxb := 9 else maxb := bc;

2.3. Với mỗi b = minb..maxb ta tính

         y = 100*a + 10*b + (bc – b).

Ghi số này vào tệp.

(* Pascal  *)

(*-=-----------------------------

  Sinh cac so khong qua 3 chu so

  co do cao h va ghi vao tep fn

--------------------------------*)

program HGen;

uses crt;

function Gen(fn:string;h:integer): integer;

var f: text;

a,b,bc,mina,maxa,minb,maxb: integer;

x,y,d: integer;

       begin {tong 3 chu so toi da la 27, toi thieu la 0 }

      if (h < 0) OR (h > 27) then exit;

assign(f,fn); rewrite(f);

d:= 0; {dem so luong cac so do cao h}

  if h <=  18 then mina := 0 else mina := h-18;

        if h >= 9 then maxa := 9 else maxa := h;

for a := mina to maxa do

         begin

            x := 100*a;

         bc := h-a;

if bc <= 9 then minb := 0 else minb := bc-9;

         if  bc >= 9 then maxb := 9 else maxb := bc;

         for b := minb to maxb do

begin

y := x + 10*b + (bc - b);

write(f,y:4);

inc(d); { Ghi moi dong 10 so }

if d mod 10 = 0 then writeln(f);

end;

         end;

close(f);

Gen := d;

end;

procedure Test;

var n: integer;

begin

n := Gen('HEIGHT.NUM',10);

write('Tong cong ’,n,' so');

readln;

end;

BEGIN

Test;

END.

Chú ý

1. Có thể giải bài toán trên bằng phương pháp vét cạn dùng ba vòng for như sau:

for a := 0 to 9 do

         for b := 0 to 9 do

               for c := 0 to 9 do

                     if a+b+c = h then

                       write(f,a,b,c,#32);

2. Phương pháp vét cạn đòi hỏi 10*10*10 = 1000 lần duyệt trong khi với h = 10 chỉ có 63 số thoả mãn điều kiện của đầu bài. Dùng phương pháp sinh ta nhận được đúng 63 số cần tìm, không phải duyệt thừa số nào