//
you're reading...
00 - Chủ đề chung

Tài liệu giáo khoa chuyên Tin học lớp 10 – Chương 2 – Bài tập 24

Đề bài


TAM GIÁC SỐ (Đề thi học sinh giỏi Hà Tây, năm 2006)
b2_2411

Hình trên mô tả một tam giác số có số hàng N = 5. Đi từ đỉnh (số 7) đến đáy tam giác bằng một đường gấp khúc, mỗi bước chỉ được đi từ số ờ hàng trên xuống một trong hai số đứng kề bên phải hay bên trái ở hàng dưới và tính tích các số trên đường đi lại ta được một tích.Ví dụ, đường đi 7, 8, 1, 4, 6 có tích là S = 1344,
đường đi 7, 8, 1, 7, 5 có tích là S = 735.
Yêu cầu: Cho tam giác số, tìm tích của đường đi có tích lớn nhất.INPUT: Tệp văn bản TGS.INP:

  • Dòng đầu tiên chứa số nguyên n, () < n <101);
  • N dòng tiếp theo, từ dòng thứ 2 đến dòng N+1: dòng thứ i có (i-1) số cách nhau bởi dấu cách (các số có giá trị tuyệt đối không vượt quá 100).

OUTPUT: Đưa ra tệp văn bản TGS.OUT có một số nguyên là tích lớn nhất tìm được.


Bài giải


[Mô phỏng theo: IOI’94 – Day 1 – Solution 1: The Triangle] [Source] [Test]

program ioi94day1prb1ver2(input, output, inp, out) ;
{ Tom Verhoeff, Eindhoven University of Technology }
{ Efficient recursive solution with memorization }

{ General Section }

const
Test = true ;

var
inp, out: text ;

procedure Init ;
begin
if Test then
writeln(‘IOI”94 – Day 1 – Problem 1: The Triangle’) ;
assign(inp, ‘input.txt’) ;
reset(inp) ;
assign(out, ‘output.txt’) ;
rewrite(out) ;
if Test then writeln(‘Initialized’)
end { Init } ;

procedure Fini ;
begin
close(inp) ;
close(out)
end { Fini } ;

{ Problem Specific Section }

const
MaxN = 100 ;

type
index = 1..MaxN ;
number = 0..99 ;

var
N: index ; { number of rows }
T: array [index, index] of number ;
{ T[r, p] is the number in row r at position p }
MRS: array [index, index] of integer ;
{ MRS[r, p] is the maximum sum for routes from T[r, p], or -1 if unknown }
m: integer ; { maximum route sum }

procedure ReadInput ;
{ read N and T[r, p] with 1 <= r <= N and 1 <= p <= r } { initialize all relevant MRS[r, p] at -1 } var r, p: index ; begin readln(inp, N) ; if Test then writeln(‘Number of rows is ‘, N:1) ; for r := 1 to N do begin for p := 1 to r do begin read(inp, T[r, p]) ; MRS[r, p] := -1 end { for p } ; readln(inp) end { for r } ; if Test then writeln(‘All input read’) end { ReadInput } ;

procedure ComputeAnswer ; { m := the maximum route sum }

function Max(x, y: integer): integer ;

begin

if x > y then Max := x else Max := y

end { Max } ;

function MaxRS(r, p: index): integer ;
{ return maximum sum over all down routes starting in T[r, p] }
begin
if MRS[r, p] = -1 then
if r = N then MRS[r, p] := T[r, p]
else MRS[r, p] := T[r, p] + Max(MaxRS(r+1, p), MaxRS(r+1, p+1)) ;
MaxRS := MRS[r, p]
end { MaxRS } ;

begin
m := MaxRS(1, 1)
end { ComputeAnswer } ;

procedure WriteOutput ;
begin
writeln(out, m:1) ;
if Test then writeln(‘The maximum route sum is ‘, m:1)
end { WriteOutput } ;

begin
Init ;
ReadInput ;
ComputeAnswer ;
WriteOutput ;
Fini
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ê

  • 149,868 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: