切換
舊版
前往
大廳
主題

ZeroJudge - e906: 108 p8. 蜂房問題　解題心得

Not In My Back Yard | 2020-03-07 00:14:29 | 巴幣 2 | 人氣 144
題目連結：
題目大意：
給定一正整數 t （1 ≦ t ≦ 50），代表接著有 t 列輸入。每列給定一正整數 n （1 ≦ n ≦ 2 ^ 30），代表有一兩排的蜂巢格子如下圖：
有一蜜蜂於最左下的格子（蜂巢格子往正右方無限延伸）。該蜜蜂每次移動只會往當前格子的左上或是右方的格子移動。

求蜜蜂移動 n 格有幾種移動方式？

範例輸入：
範例輸入一：
1
1

範例輸入二：
2
1
2
範例輸出：
範例輸出一：
2

範例輸出二：
2
3
解題思維：
因為蜜蜂只能往右或是右上。因此，一旦到了上面那一排就無法下去了。

所以可以快速地推得，走到圖上的最左上第一格的方法只有 1 種；其右邊的格子則有 2 種；再右邊的格子有 3 種……第 n 格有 n 種。

而下面那一排，不管到哪格格子都只有一種走法——往右到底。

所以所求為（上面那排蜂巢的第 n 格之走法）＋（下面那排蜂巢的第 n 格之走法）＝ n ＋ 1 。

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
上一篇
下一篇
#程式題目解題心得
留言

創作回應

追蹤 創作集

作者相關創作

作品資料夾

更多創作

追蹤 創作集
其他創作
作品資料夾