TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH

tải về 2.51 Mb.

trang	9/21
Chuyển đổi dữ liệu	24.07.2016
Kích	2.51 Mb.
	#3874

1 ... 5 6 7 8 9 10 11 12 ... 21

4.4 Cân

Olimpic các nước vùng Baltic, 2004

Người ta cần cân một vật có khối lượng là một số tự nhiên n gam bằng một bộ quả cân khối lượng 1, 3, 9, ..., 3^k, ... gam, k = 0, 1, 2, ... , mỗi loại có đúng một quả cân. Vật cần cân được đặt trên đĩa trái. Hãy chọn các quả cân đặt trên hai đĩa để cân thăng bằng.

can.inp

can.out

Giải thích

Input text file: số n; 1  n  1000000000 (1 tỷ).

Output text file: 2 dòng

Dòng 1: số quả cân đặt trên đĩa trái, tiếp đến là các quả cân cụ thể.

Dòng 2: số quả cân đặt trên đĩa phải, tiếp đến là các quả cân cụ thể.

Thí dụ, với khối lượng vật cân n = 69 g đặt trên đĩa trái, ta cần đặt thêm 2 quả cân trên đĩa trái là 3 và 9g; 1 quả cân trên đĩa phải là 81 g. Ta có:

69 + 3 + 9 = 81.

69 2 3 9

1 81

Thuật toán

Đầu tiên ta tạm giả thiết là số lượng quả cân mỗi loại là đủ nhiều để có thể cân mọi khối lượng trong giới hạn cho trước. Khi đó ta biểu diễn n dưới dạng hệ đếm 3 rồi đặt vật cần cân trên đĩa trái và đặt các quả cân tương ứng trên đĩa phải.

Để biểu diễn n dưới dạng hệ b tùy ý ta chia liên tiếp n cho b và ghi nhận các số dư. Trong các phiên bản dưới đây p là mảng nguyên chứa các chữ số trong dạng biểu diễn ngược của số n dưới dạng hệ đếm b, đầu ra của các hàm ToBase là số chữ số trong dạng biểu diễn đó.

type mi1 = array[0..30] of integer;

(* Pascal *)

function ToBase(n: longint; b: integer; var p: mi1): longint;

var i: longint;

begin

fillchar(p, sizeof(p),0);

i := 0;

repeat

p[i] := n mod b;

n := n div b;

inc(i);

until n = 0;

ToBase := i;

end;

// DevC++

int ToBase(int n, int b, int *p) {

int i = 0;

memset(p, 0, sizeof(p));

do {

p[i++] = n % b;

n /= b;

} while (n != 0);

return i;

}

Để tiện lập luận ta tạm qui ước gọi quả cân 3ⁱ là quả cân loại i, tức là ta gọi theo số mũ của hệ số 3. Với thí dụ dã cho n = 69, lời gọi k = ToBase(69, 3, phai) sẽ cho k = 4 và mảng phai[0..3] = (0, 2, 1, 2) chính là các chữ số hệ đếm 3 trong dạng biểu diễn của số 69. Cụ thể là số 69 được biểu diễn ngược trong hệ đếm 3 sẽ là một số gồm k = 4 chữ số lần lượt tính từ chữ số hàng đơn là 0, 2, 1 và 2, cụ thể là:

69 = 0.3⁰ + 2.3¹ + 1.3² + 2.3³ = 2120₃.

Loại quả cân

0 (3⁰=1)

1 (3¹=3)

2 (3²=9)

3 (3³=27)

4 (3⁴=81)

Vật cần cân khối lượng n = 69 được đặt trên đĩa trái. Trên đĩa phải đặt 3 quả cân:

phai[1] = 2 quả cân loại 1, 2.3¹ = 6 g,

phai[2] = 1 quả cân loại 2, 1.3² = 9 g,

phai[3] = 2 quả cân loại 3, 2.3³ = 2.27 = 54 g,

69 = 6 + 9 + 54.

Đĩa trái tạm thời để trống

Đĩa trái (69+...)

0 Đĩa phải

0

2

1

2

0 Vì mỗi loại quả cân chỉ có đúng 1 quả nên ta cần tìm cách thay 2 quả cân cùng loại i bằng tổ hợp khác. Ta có

2.3ⁱ = 3.3ⁱ – 3ⁱ = 3ⁱ⁺¹  3ⁱ.

Hệ thức trên cho ta thấy rằng có thể thay 2 quả cân loại i ở đĩa cân phải bằng cách đặt 1 quả cân loại i+1 trên đĩa phải và 1 quả cân loại i trên đĩa trái. Với thí dụ đã cho, phai[1] = 2 nên ta thay 2 quả cân loại 1 bằng 1 quả cân loại 2 trên đĩa phải và 1 quả cân loại 1 trên đĩa trái. Vì trên đĩa phải đã có sẵn 1 quả cân loại 2 nên số quả cân loại này sẽ được tăng thêm 1 và bằng 2. Ta thu được:

Loại quả cân

0 (3⁰=1)

1 (3¹=3)

2 (3²=9)

3 (3³=27)

4 (3⁴=81)

phai = (0,2,1,2)  (0,0,2,2);

trai = (0,1,0,0).

Đĩa trái (69 g)+1 quả cân loại 1 = 69 + 3 = 72g;

Đĩa phải: 2 quả cân loại 2+ 2 quả cân loại 3 = 2.3²+2.3³ = 2.9 + 2.27 = 18 + 54 = 72g.

Đĩa trái (69+...)

0

1

0 Đĩa phải

0

2

0 Lại thức hiện phép thay 2 quả cân loại 2 trên đĩa phải bằng 1 quả cân loại 2 trên đĩa phải và 1 quả cân loại 3 trên đĩa trái ta thu được:

Loại quả cân

0 (3⁰=1)

1 (3¹=3)

2 (3²=9)

3 (3³=27)

4 (3⁴=81)

phai = (0,0,2,2)  (0,0,0,3);

trai = (0,1,1,0).

Đĩa trái (69g) + 1 quả cân loại 1 + 1 quả cân loại 2 = 69 + 1.3¹ + 1.3² = 69 + 3 + 9 = 81 g;

Đĩa phải: 3 quả cân loại 3 = 3.27 = 81 g.

Đĩa trái (69+...)

0

1

0 Đĩa phải

0

3

0 Cuối cùng ta thay 3 quả cân loại 3 trên đĩa phải bằng 1 quả cân loại 4 là hoàn tất.

phai = (0,0,0,3)  (0,0,0,0,1).

trai = (0,1,1,0).

Kết quả ta thu được: Để cân vật n = 69 g ta đặt vật đó trên đĩa trái và

Đặt tiếp trên đĩa trái 2 quả cân 3 và 9 g;

Đặt trên đĩa phải 1 quả cân 81 g.

Tổng hợp lại ta có thuật toán Replace thực hiện phép thay các quả cân loại i trên đĩa phải như sau:

Nếu trên đĩa phải có 2 quả cân loại i thì thay bằng 1 quả loại i+1 trên đĩa phải và 1 quả loại i trên đĩa trái;
Nếu trên đĩa phải có 3 quả cân loại i thì thay bằng 1 quả loại i+1 trên đĩa phải.

Hàm Replace nhận vào là dãy k quả cân trên đĩa phải p[0..k1], cho ra dãy m quả cản trên đĩa trái t[0..m1]:

(* Pascal *)

function Replace(var p: mi1; var k: integer; var t: mi1): longint;

var m, i: longint;

begin

fillchar(t, sizeof(t),0);

for i := 0 to k do

if p[i] = 3 then begin p[i] := 0; inc(p[i+1]) end

else if p[i] = 2 then

begin p[i] := 0; inc(p[i+1]); inc(t[i]) end;

m := k;

if p[k] > 0 then inc(k);

Replace := m;

end;
// DevC++

int Replace(int * p, int &k, int * t) {

int i, m;

memset(t, 0, sizeof(t));

for (i = 0; i < k; ++i)

if (p[i] == 3) { p[i] = 0; ++p[i+1]; }

else if (p[i] == 2) { p[i] = 0; ++p[i+1]; ++t[i]; }

m = k;

if (p[k] > 0) ++k;

return m;

}

Trước khi ghi file chúng ta cần thu dọn sơ bộ dữ liệu. Ta duyệt các phần tử của hai dãy trái và phải để đếm xem có bao nhiêu quả cân và qui các loại quả cân đó thành giá trị cụ thể, tức là thay vì viết i ta phải viết 3ⁱ.

(* can.pas *)

uses crt;

const fn = 'can.inp'; gn = 'can.out';

mn = 30; bl = #32; nl = #13#10;

type mi1 = array[0..mn] of longint;

function Doc: longint;

var n: longint;

f: text;

begin

assign(f,fn); reset(f);

readln(f,n); close(f);

Doc := n;

end;

function ToBase(n: longint; b: longint; var p: mi1): longint;

var i: longint;

begin

fillchar(p, sizeof(p),0);

i := 0;

repeat

p[i] := n mod b;

n := n div b;

inc(i);

until n = 0;

ToBase := i;

end;

function Replace(var p: mi1; var k: longint; var t: mi1): longint;

var m, i: longint;

begin

fillchar(t, sizeof(t),0);

for i := 0 to k do

if p[i] = 3 then begin p[i] := 0; inc(p[i+1]) end

else if p[i] = 2 then

begin p[i] := 0; inc(p[i+1]); t[i] := 1 end;

m := k;

if p[k] > 0 then inc(k);

Replace := m;

end;

procedure Ghi(var t: mi1; dt: longint; var p: mi1; dp: longint);

var i, v, nt, np: longint;

g: text;

begin

v := 1; nt := 0;

for i := 0 to dt-1 do

begin

if t[i] > 0 then begin inc(nt); t[i] := v; end;

v := v * 3;

end;

v := 1; np := 0;

for i := 0 to dp-1 do

begin

if p[i] > 0 then begin inc(np); p[i] := v; end;

v := v * 3;

end;

assign(g,gn); rewrite(g);

write(g,nt,bl);

for i := 0 to dt-1 do

if t[i] > 0 then write(g,t[i],bl);

write(g,nl,np,bl);

for i := 0 to dp-1 do

if p[i] > 0 then write(g,p[i],bl);

close(g);

end;

procedure Run;

var trai, phai: mi1;

n, dt, dp: longint;

begin

n := Doc;

dp := ToBase(n,3,phai);

dt := Replace(phai, dp, trai);

Ghi(trai,dt,phai,dp);

end;

BEGIN

Run;

write(nl,' Fini');

readln;

END.
// Devcpp Can.cpp

#include

#include

using namespace std;

// D A T A A N D V A R I A B L E

const char * fn = "CAN.INP";

const char * gn = "CAN.OUT";

// P R O T O T Y P E S

int main();

int Doc();

void Ghi(int *t, int n, int *p, int m);

int ToBase(int n, int b, int *p);

int Replace(int *p, int &n, int *t);

void Run();

// I M P L E M E N T A T I O N

int main() {

Run();

cout << endl << endl << " Fini ";

cin.get();

return 0;

}

void Run() {

const int mn = 20;

int phai[mn], trai[mn];

int dp, dt, n;

n = Doc();

dp = ToBase(n, 3, phai);

dt = Replace(phai, dp, trai);

Ghi(trai,dt,phai,dp);

}

int Doc() {

int n;

ifstream f(fn);

f >> n;

f.close();

return n;

}

void Ghi(int *t, int dt, int *p, int dp) {

int i, v, nt, np;//dt,dp: so qua can tren dia trai va phai

nt = np = 0;

for (v = 1,i = 0; i < dt; ++i, v*= 3)

if (t[i] > 0) { ++nt; t[i] = v; }

for (v = 1,i = 0; i < dp; ++i, v*= 3)

if (p[i] > 0) { ++np; p[i] = v; }

ofstream g(gn);

g << nt << " ";

for (i = 0; i < dt; ++i)

if (t[i] > 0) g << t[i] << " ";

g << endl << np << " ";

for (i = 0; i < dp; ++i)

if (p[i] > 0) g << p[i] << " ";

g.close();

}

// Bieu dien so n qua he b

// return i - chieu dai so trong he b

// n = p[0].b^0 + p[1].b^1 + ... + p[i].bi

int ToBase(int n, int b, int *p) {

int i = 0;

memset(p, 0, sizeof(p));

do {

p[i++] = n % b;

n /= b;

} while (n != 0);

return i;

}

int Replace(int * p, int &k, int * t) {

int i, m;

memset(t, 0, sizeof(t));

for (i = 0; i < k; ++i)

if (p[i] == 3) { p[i] = 0; ++p[i+1]; }

else if (p[i] == 2) { p[i] = 0; ++p[i+1]; ++t[i]; }

m = k;

if (p[k] > 0) ++k;

return m;

}

Độ phức tạp: cỡ log₃(n); trong đó log₃(n) + 1 là số chữ số trong dạng biểu diễn của n theo hệ đếm 3.

Каталог: tailieu
tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning
tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm
tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc
tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI
tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1
tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng
tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp
tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc
tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam

tải về 2.51 Mb.

Chia sẻ với bạn bè của bạn:

1 ... 5 6 7 8 9 10 11 12 ... 21

TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH

4.4 Cân

Olimpic các nước vùng Baltic, 2004

can.inp

can.out

Giải thích

Input text file: số n; 1  n  1000000000 (1 tỷ).

Output text file: 2 dòng

Dòng 1: số quả cân đặt trên đĩa trái, tiếp đến là các quả cân cụ thể.

Dòng 2: số quả cân đặt trên đĩa phải, tiếp đến là các quả cân cụ thể.

Thí dụ, với khối lượng vật cân n = 69 g đặt trên đĩa trái, ta cần đặt thêm 2 quả cân trên đĩa trái là 3 và 9g; 1 quả cân trên đĩa phải là 81 g. Ta có:

69 + 3 + 9 = 81.

69

2 3 9

1 81

type mi1 = array[0..30] of integer;

69 = 0.30 + 2.31 + 1.32 + 2.33 = 21203.

Loại quả cân

0

(30=1)

1

(31=3)

2

(32=9)

3

(33=27)

4

(34=81)

Vật cần cân khối lượng n = 69 được đặt trên đĩa trái. Trên đĩa phải đặt 3 quả cân:

phai[1] = 2 quả cân loại 1, 2.31 = 6 g,

phai[2] = 1 quả cân loại 2, 1.32 = 9 g,

phai[3] = 2 quả cân loại 3, 2.33 = 2.27 = 54 g,

69 = 6 + 9 + 54.

Đĩa trái tạm thời để trống

Đĩa trái (69+...)

0

0

0

0

0

Đĩa phải

0

2

1

2

0

Vì mỗi loại quả cân chỉ có đúng 1 quả nên ta cần tìm cách thay 2 quả cân cùng loại i bằng tổ hợp khác. Ta có

2.3i = 3.3i – 3i = 3i+1  3i.

Loại quả cân

0

(30=1)

1

(31=3)

2

(32=9)

3

(33=27)

4

(34=81)

phai = (0,2,1,2)  (0,0,2,2);

trai = (0,1,0,0).

Đĩa trái (69 g)+1 quả cân loại 1 = 69 + 3 = 72g;

Đĩa phải: 2 quả cân loại 2 + 2 quả cân loại 3 = 2.32+2.33 = 2.9 + 2.27 = 18 + 54 = 72g.

Đĩa trái (69+...)

0

1

0

0

0

Đĩa phải

0

0

2

2

0

Lại thức hiện phép thay 2 quả cân loại 2 trên đĩa phải bằng 1 quả cân loại 2 trên đĩa phải và 1 quả cân loại 3 trên đĩa trái ta thu được:

Loại quả cân

0

(30=1)

1

69 = 0.3⁰ + 2.3¹ + 1.3² + 2.3³ = 2120₃.

(3⁰=1)

(3¹=3)

(3²=9)

(3³=27)

(3⁴=81)

phai[1] = 2 quả cân loại 1, 2.3¹ = 6 g,

phai[2] = 1 quả cân loại 2, 1.3² = 9 g,

phai[3] = 2 quả cân loại 3, 2.3³ = 2.27 = 54 g,

2.3ⁱ = 3.3ⁱ – 3ⁱ = 3ⁱ⁺¹  3ⁱ.

(3⁰=1)

(3¹=3)

(3²=9)

(3³=27)

(3⁴=81)

Đĩa phải: 2 quả cân loại 2+ 2 quả cân loại 3 = 2.3²+2.3³ = 2.9 + 2.27 = 18 + 54 = 72g.

(3⁰=1)

(3¹=3)

(3²=9)

(3³=27)

(3⁴=81)

Đĩa trái (69g) + 1 quả cân loại 1 + 1 quả cân loại 2 = 69 + 1.3¹ + 1.3² = 69 + 3 + 9 = 81 g;

Độ phức tạp: cỡ log₃(n); trong đó log₃(n) + 1 là số chữ số trong dạng biểu diễn của n theo hệ đếm 3.