//
you're reading...
Bài tập huấn luyện

Số độ cao h


Đề bài



Độ 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

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 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 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 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.

// C#
using System;
using System.Collections.Generic;
using System.Text;
using System.IO;
namespace SangTao1
{
class HGen
{
static void Main(string[] args)
{
string fn = “HGen.txt”;
int h = 10;
Console.WriteLine(“\n File ” + fn);

Sáng tạo trong Thuật toán và Lập trình Tập I 43
Console.WriteLine(” H = ” + h);
int d = Gen(fn,10);
Test(fn,d);
Console.WriteLine(“\n Fini “);
Console.ReadLine();
}
static public int Gen(string fn, int h)
{
int a, b, mina, maxa, minb, maxb,
bc, x, y, d = 0;
StreamWriter f = File.CreateText(fn);
mina = (h <= 18) ? 0 : h-18;
maxa = (h <= 9) ? h : 9;
for (a = mina; a <= maxa; ++a)
{
x = 100*a; bc = h – a;
minb = (bc <= 9) ? 0 : bc-9;
maxb = (bc >= 9) ? 9 : bc;
for (b = minb; b <= maxb; ++b)
{
++d; y=x+10*b+(bc-b); f.Write(y+” “);
if (d % 10 == 0) f.WriteLine();
}
}
f.Close();
return d;
}
// Doc lai file de kiem tra
static public void Test(string fn,int d)
{
Console.WriteLine(“\n Tong cong ” +
d + ” so”);
Console.WriteLine(File.ReadAllText(fn));
}
} // HGen
} // SangTao1

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.

 

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

Fast-flying Falcon

sunset and fishing nets

Force of Life - Pushing Boundaries I

More Photos

Thống kê

  • 81,544 lượt xem

%d bloggers like this: