切換
舊版
前往
大廳
主題

ZeroJudge - e155: 10935 - Throwing cards away I 解題心得

Not In My Back Yard | 2019-04-12 22:26:48 | 巴幣 0 | 人氣 296

題目連結:


題目大意:
給定一正整數 N (N ≦ 50 , N = 0 時停止程式),代表現在有 N 張卡。卡的編號依序為 1 ~ N ,且這N張牌排成一疊。(編號 1 在最上面,編號 2 在 1 下面……編號 N 在最下面)

當一個卡牌的堆疊還有兩張牌以上(含)時,就做以下的事:
丟掉現在最上面的牌,並將剩下的最上面的牌(丟棄最上面的牌前的第二張牌)放到最下面。

求依序被丟棄的卡牌之編號,以及最後剩下的牌的編號。輸出格式參見範例輸出。



範例輸入:
7
19
10
6
0


範例輸出:
Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4


解題思維:
淺顯易懂的流程模擬題。

現在有 N 張牌,每次要丟棄之前就把要丟棄的牌之編號輸出。且紀錄下丟棄前的第2張牌之編號。接著,把第 3 張牌的編號覆蓋到第 1 張上(用一陣列 A 表示的話即:A[0] = A[2])、把第 4 張牌的編號蓋到第 2 張牌……以此類推。

經過以上操作後,原本的最後一張牌在陣列裡往前移了兩格。最後將剛剛記錄下來原本第二張牌的編號放到現在最後一張牌的後面。然後將 N 減去 1 。即完成了一次題目要求的動作。

做到 N = 1 為止。最後就把最後一張牌的編號按照輸出格式輸出即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
這就是 Josephus Problem 啊...
2019-04-13 17:54:52
Not In My Back Yard
是沒錯,但是本人對這種問題一直很不擅長。而且 N 的範圍很小,所以就直接做XD
2019-04-13 18:04:49

相關創作

更多創作