//
you're reading...
Giáo trình chuyên Tin học 10

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

Đề bài


Có N quả cân với các trọng lượng tương ứng là 1kg, 3kg, . . ., 3N-1kg và một cân bàn. Các quả này được đánh theo số hiệu : 1 , 2, 3, .. N . Ta muốn chỉ dùng cân bàn và N quả cân này để cân túi đường có trọng lượng M kg trong một lần cân. Liệu ta có thể cân đợc không ?
Dữ liệu : Cho trong file văn bản Duong.INP :
Ghi trên một dòng duy nhất hai số N <=15 , và M<=100000000.
Kết quả : Ghi ra file văn bản Duong.Out :

  • Nếu không thể cân đợc thì dòng đầu tiên viết : NO còn nếu cân đợc thì ghi dòng đầu tiên ghi YES và tiếp tục bớc sau
  • Dòng đầu tiên ghi số hiệu các quả cân nếu có ở phía chứa vật ( nếu không có quả cân nào thì để trống)
  • Dòng tiếp ghi số hiệu các quả cân ở phía không có vật .

Ví dụ


Canduong.Inp CanDuong.Out
7 255 YES 6 3 2


Thuật toán


Ta quy định bên chứa vật là (I) còn bên kia là (II) .
Chúng ta thấy đây chỉ là việc chuyển một số nào đó sang hệ cơ số ba mà thôi . Nhng mỗi một mũ ba chỉ có thể có hệ số 1 hoặc 0 :
giả sử số X khi phân tích ra cách cân thì nó có hai bên :
X+3i1+3i2+..3in=3j1+3j2+..+3jm .
Tức là : X:= (3j1+3j2+..+3jm)-( 3i1+3i2+..3in) . (*)
Giả sử số X trong hệ cơ số 3 là :
X:=A1*31+A2*32+…An*3n . (**)
với Ai=0,1,2.

  • Để chuyển biểu thức (**) sang biểu thức (*) thì chúng ta thấy :
  • Nếu Ai=0 thì quả cân thứ i không tham gia trong quá trình cân.
  • Nếu Ai=1 thì để nguyên tức là quả cân thứ i sẽ nằm phía (II .)
  • Nếu Ai=2 thì ta có : 2*3i=3i+1-3i . tức là chúng ta sẽ sử dụng quả thứ i về bên thứ (I) còn đối với quả cân thứ i+1 thì chúng ta sẽ tăng hệ số Ai+1 :=Ai+1+1 ; rồi tiếp tục xét với hệ số của i+1.
  • Nếu Ai =3 ( do trờng hợp vừa rồi tạo nên ) thì chúng ta có :
    3*3i=3i+1 tức là quả cân thứ i không tham gia trong quá trình cân , mặt khác chúng ta tăng hệ số của Ai+1 lên một đơn vị .
  • Cứ nh vậy chúng ta sẽ biết đợc quả cân sẽ nằm bên nào hoặc không tham gia cân . Nhng chúng ta nên nhơ rằng nếu số X>31+32+..+3n = (3n+1-1)/2 thì không tồn tại cách cân .

Bài giải


program canduong ;
uses crt ;
const
fi = 'canduong.inp' ;
fo = 'canduong.out' ;
var
a : array [ 1..20 ] of integer ;
n , m : longint ;
i , dem : longint ;
ok : boolean ;
dem1 , dem2 : longint ;
a1 , a2 : array [ 1..20 ] of integer ;

procedure readfile ;
var
f : text ;
begin
assign ( f , fi ) ;
reset ( f ) ;
read ( f , n , m ) ;
close ( f ) ;
end ;

procedure xuli ;
var
t : longint ;
begin
t := 1 ;
for i := 1 to n + 1 do t := t * 3 ;
if ( t - 1 ) / 2 < m then ok := true else ok := false ;
if not ok then
begin
dem := 0 ;
dem1 := 0 ; dem2 := 0 ;
while m<>0 do
begin
inc ( dem ) ;
a [ dem ] := m mod 3 ;
m := m div 3 ;
end ;
a [ dem + 1 ] := 0 ;
for i := 1 to dem+1 do
case a [ i ] of
1 :
begin
inc ( dem1 ) ;
a1 [ dem1 ] := i ;
end ;
2 :
begin
inc ( a[i+1]);
inc ( dem2 ) ;
a2 [ dem2 ] := i ;
end ;
3 :
inc ( a [ i + 1 ] ) ;
end ;
end ;
end ;

procedure writefile ;
var
f : text ;
begin
assign ( f , fo ) ;
rewrite ( f ) ;
if ok then writeln (f,'NO')
else
begin
writeln ( f ,'YES');
for i := 1 to dem2 do
write ( f , a2 [ i ] : 5 ) ;
writeln ( f ) ;
for i := 1 to dem1 do
write ( f , a1 [ i ] : 5 ) ;
end ;
close ( f ) ;
end ;

begin
readfile ;
xuli;
writefile ;
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 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ả

Danh mục

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

NCT Computer

Flickr Photos

Curved Trees

You Are My Sunshine...

Dawson Road (Townsend's Warbler)

More Photos

Thống kê

  • 135,976 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: