推 D0496000:原來如此 真是太妙了! 01/27 16:17
→ D0496000:我看到printf("%d\n",x)裡有個換行字元就以為它一定要輸 01/27 16:25
→ D0496000:出當層的最後一個數字 01/27 16:27
推 FY4:太神了 02/05 23:04
遙望去年成績單（演算法30），這是我唯一會寫的兩題之一
結果我竟然忘記當年我是怎麼想出正確答案的了 囧
※ 引述《killersky (killersky)》之銘言：
: ※ 引述《D0496000 (ZEN)》之銘言：
: : 題目在此
: : http://www.lib.ntu.edu.tw/exam/graduate/99/99405.pdf
: : 請問第二題...
: : 明明題意清楚但就是不會...
: for(i=0;i<20;i++){
: if( ( x = peek() ) == 0 )
: insert(0);
: printf("%d\n",x);
: insert( delete() + peek() );
: }
沒錯，這個解答是對的！
不過真要講「要怎麼想出這個答案」卻是一件有點困難的事情...
題目給了我們一個Queue，而且在一開始的時候放了一組0,1
如果我們只要第一層的答案（就是只有0,1）
一開始x=peek()，印完之後delete()就算作完了
所以在這裡可以做出第一個假設：
「Output的順序和Queue中數字排隊的順序會恰好一致」
所以問題就變成「我們要怎麼從第一層陸續往下推出下幾層的答案呢？」
回顧一下「Pascal三角形」這個東西：我們要從「前面的結果」去推後面的結果
所以在這裡作第二個假設：
「我們拿了值之後，要用得到的值去算出新的值放進Queue裡」
在第一個假設之下，我們的Queue就會是這樣排：
0 1 0 1 1 0 1 2 1 0 1 3 3 1 ...
在這裡關鍵來了，根據Pascal三角形
1
/ \
1 1
/ \ / \
1 2 1
每一層都是0+第一個值, 第一個值+第二個值, 第二層+第三個值 ... , 最後一個值+0
因此猜正確的作法可能是「每次把Queue最前面的兩項相加放入後，拿掉最前面的一項」
「然後，也因為有0，所以要對0作特別的處理」
好，最後來列出這個想法下該如何運作吧
假設隊伍最前面在左邊，一開始是這樣：
0 1
下一個應該要是 0，所以別無他策，補0：
0 1 0
0 + 1 = 1，好，把1加進隊伍裡，把0拿出來：
（為求方便，直接塗灰表示他已經離開隊伍了）
0 1 0 1
1 + 0 = 1，把1加進去，前面的1拿出來：
0 1 0 1 1
（至此為止第二層算完！）
所以第三層在這樣的流程下也會算出正確的結果：
先補一個0
0 1 0 1 1 0
0 + 1 = 1
0 1 0 1 1 0 1
1 + 1 = 2
0 1 0 1 1 0 1 2
1 + 0 = 1
0 1 0 1 1 0 1 2 1
沒錯，這樣是對的！最後，整理想法，把答案填進空格裡：
首先，「遇到0的時候補一個0進去」
所以前面是 if ((x = peak()) == 0) { insert(0); }
接下來，觀察他的printf會把當時Queue中最前面的一項印出來，所以沒問題
最後，「把最前面兩項相加後，拿掉最前面一項」
這相當於拿掉最前面一項->peak新的最前面一項->最後相加
所以就是 insert(delete() + peak());，結束！ :)
---
實際上當時我這題想了超過半小時... Orz
放0這個技巧真的很有趣！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.127.177.56