//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện, Giáo trình chuyên Tin học 10, Đề huấn luyện theo tuần

Tài liệu giáo khoa chuyên Tin học – lớp 10 -Bài tập 23

Đề bài


Nam quyết định đánh số trang cho quyển sách của anh ta từ 1 đến N. Hãy tính toán số lượng chữ số 0 cần dùng, số lượng chữ số 1 cần dùng, … , số lượng chữ số 9 cần dùng.
INPUT: Tệp DIGIT.INP gồm một đòng duy nhất chứa một số N (N<= 10100).
OUTPUT: Tệp DIGIT.OUT có dạng gồm 10 dòng,

  • Dòng thứ nhất là số lượng chữ số 0 cần dùng,
  • Dòng thứ hai là số lượng chữ số 1 cần dùng,
  • Dòng thứ 10 là số lượng chữ số 9 cần dùng.

Ví dụ


 


Thuật toán


Xử lý số nguyên lớn

Bài giải


[Tải bài giải]

USES Math;
CONST
nmax = 101;
base = trunc(1e7);
Maxpt = 20;
TYPE
ArrBigNum = record
sl: longint;
h: array[1..Maxpt] of longint;
end;
VAR
n  : longint;
s: string;
res: array [0..9] of ArrBigNum;
F: array[0..nmax, 0..nmax] of ArrBigNum;
a,b,c: ArrBigNum;
input, output: Text;

PROCEDURE XuatArrBigNum(a: ArrBigNum);
var i: byte;
begin
writeln(‘So da nhap co ‘,a.sl,’ doan.’);
for i:= a.sl downto 1 do
write(a.h[i]);
writeln;
end;

FUNCTION ArrAdd(a,b: ArrBigNum): ArrBigNum;
var
i, s, hold: longint;
c: ArrBigNum;
begin
c.sl:= max(a.sl, b.sl);
hold:= 0;
for i:= a.sl+1 to c.sl do a.h[i]:= 0;
for i:= b.sl+1 to c.sl do b.h[i]:= 0;
for i:= 1 to c.sl do
begin
s:=a.h[i]+b.h[i] + hold;
c.h[i]:= s mod base;
hold:= s div base;
if hold>0 then
begin
inc(c.sl);
c.h[c.sl]:= hold;
end;
end;
exit(c);
end;
FUNCTION ArrMul(a: ArrBigNum;b: longint): ArrBigNum;
var
i,s,hold: longint;
c: ArrBigNum;
begin
c.sl:= a.sl;
hold:= 0;
for i:=1 to c.sl do
begin
s:= a.h[i] * b + hold;
c.h[i]:= s mod base;
hold:= s div base;
end;
while hold>0 do
begin
inc(c.sl);
c.h[c.sl]:= hold mod base;
hold:= hold div base;
end;
exit(c);
end;

PROCEDURE Init;
var
i, j : longint;
begin
F[0][0].sl:= 1;
F[0][0].h[1]:=1;
for i:=1 to n do
for j:= 0 to i do
begin
F[i][j]:= Arrmul(F[i-1][j],9);
if j>0 then F[i][j]:= Arradd(F[i][j], F[i-1][j-1]);
end;
end;

FUNCTION Cal(digit, sum: longint): ArrBigNum;
var
i, j, cur, ch: longint;
sol: ArrBigNum;
begin
sol.sl:= 0;
for i:=1 to n do
begin
cur:= ord(s[i]) – 48;
for ch:= 0  to cur – 1 do
if (ch= digit) and (sum>0) then sol:= Arradd(sol,F[n-i][sum-1])
else
if ch<> digit then sol:= Arradd(sol, f[n-i][sum]);
sum:= sum – ord(cur-digit);
if sum < 0 then break;
end;
exit(sol);
end;
FUNCTION Cal0 (digit, sum: longint): ArrBigNum;
var
i, j, cur, ch, ss : longint;
sol: ArrBigNum;
begin
sol.sl:= 0;
ss:= sum;
for i:= 1 to n do
begin
cur:= ord(s[i]) – 48;
for ch:= 0 to cur – 1 do
if (ch>0) or (i>1) then
begin
if (ch = digit) and (sum >0) then
sol:= Arradd(sol,F[n-i][sum-1])
else
if ch<> digit then sol:= Arradd(sol,F[n-i][sum]);
end;
sum:= sum – ord(cur=digit);
if sum < 0 then break;
end;
sum:= ss;
for i:= 2 to n do
if n-i > sum then sol:= Arradd(sol, Arrmul(F[n-i][sum],9));
exit(sol);
end;

PROCEDURE PrintResult(s: ArrBigNum);
var
i, j, d : longint;
begin
if s.sl= 0 then
begin
writeln(0);
exit;
end;
write(s.h[s.sl]);
for i:= s.sl-1 downto 1 do
if s.h[i] = 0 then write(‘0000000’)
else
begin
j:= s.h[i];
d:=0;
while j>0 do
begin
inc(d);
j:= j div 10;
end;
for j:= 1 to 7 do write(‘0′);
write(s.h[i]);
end;
writeln;
end;
PROCEDURE Process;
var
i, j, u, v : longint;
sol: ArrBigNum;
begin
readln(input,s);
n:= length(s);
Init;
for i:=1 to 9 do
for j:= 1 to n do
begin
sol:= cal(i,j);
res[i]:= Arradd(res[i], Arrmul(sol,j));
end;
for i:=1 to n do
begin
sol:= cal0(0,i);
res[0]:= Arradd(res[0], Arrmul(sol,i));
end;
for i:= 1 to n do
begin
j:= ord(s[i]) – 48;
res[j]:= Arradd(res[j],F[0][0]);
end;
for i:= 0 to 9 do PrintResult(res[i]);
end;
BEGIN
assign(input,’d:\digits.inp’);
reset(input);
assign(output,’d:\digits.out’);
rewrite(output);
Process;
readln;
END.

 

 

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 148,992 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: