有關(guān)砝碼,砝碼,鑄鐵砝碼設(shè)計(jì)前的準(zhǔn)備工作

上海眾淵砝碼廠規(guī)劃發(fā)展

2017.06.23

上海眾淵砝碼廠介紹--砝碼設(shè)計(jì)前的準(zhǔn)備工作：

設(shè)有一個(gè)沒有刻度的天平，可以用來稱量

　　任務(wù)一：設(shè)計(jì)n個(gè)砝碼的重量，用它們能稱出盡可能多的連續(xù)整數(shù)重量。例如n=2時(shí)，設(shè)計(jì)兩個(gè)砝碼的重量分別為1和3，可稱重為1、2、3、4的連續(xù)重量。

　　任務(wù)二：給出一個(gè)重量x(能在上面的優(yōu)方案下的n個(gè)砝碼稱出)，試給出稱出x的方案。如在上例中，要稱出x=2的方案，方法為2+1：3；稱出x=4的方案，方法為：4:1+3，稱出x=1的方案為1:1.注意物體放在左邊。

 輸入輸出格式 Input/output

輸入格式：
鍵盤輸入一行，包括兩個(gè)數(shù)n和x，中間用一個(gè)空格隔開。
輸出格式：
屏幕輸出兩行，一行為n個(gè)砝碼的重量（從小到大，每個(gè)數(shù)之間用一個(gè)逗號隔開），第二行為稱出x的方案。

 輸入輸出樣例 Sample input/output

樣例測試點(diǎn)#1

輸入樣例：

2 2
輸出樣例：

1,3

2+1:3

樣例測試點(diǎn)#2

輸入樣例：

2 4
輸出樣例：

1,3

4:1+3

思路：
①從這題的任務(wù)一中不難推導(dǎo)：當(dāng)n=1時(shí)，砝碼優(yōu)解為1；當(dāng)n=2時(shí)，砝碼優(yōu)解為1、3；當(dāng)n=3時(shí)，砝碼優(yōu)解為1、3、9，通過三個(gè)例子，我們大概可以得到這樣一個(gè)結(jié)論：砝碼的優(yōu)解與n有很緊密的相關(guān)性，砝碼重量為3的0到n-1次方，接下來就用實(shí)踐檢驗(yàn)這個(gè)結(jié)論。

②由于我們的砝碼只有n個(gè)，并且重量為3的0到n-1次方，所以x然要用這些砝碼表示，不與其他數(shù)字有關(guān)，并且只能用這些砝碼的和或差表示，例如7=1+9-3；2=3-1。當(dāng)初我初的想法是用DFS，搜索完每一個(gè)砝碼，判斷是用減號還是加號，后記錄優(yōu)解，但由于這題數(shù)據(jù)范圍不確定，n太大了會時(shí)，況且這和數(shù)論關(guān)系不大，所以須要想一個(gè)簡單點(diǎn)的方法。

③通過觀察可以發(fā)現(xiàn)，當(dāng)x除以3時(shí)，如果余數(shù)是1，意味著要在砝碼盤放上1這個(gè)砝碼；當(dāng)x除以3時(shí)，如果余數(shù)是2，意味著要在物盤放上1這個(gè)砝碼；如果除以3余數(shù)為0，就不用放1這個(gè)砝碼。同理，把x除以3后四舍五入后再除以3，根據(jù)余數(shù)判斷3這個(gè)砝碼的位置；再把x除以3后四舍五入再除以3后加余數(shù)判斷9這個(gè)砝碼的位置，以此類推…

上海眾淵砝碼廠。