安徽省青少年信息學奧林匹克競賽中學組試題(doc 11頁)

安徽省青少年信息學奧林匹克競賽中學組試題內容提要：
搬磚頭（rock）
小可可一直對中國五千年的古老文明非常感興趣，學習曆史知識之餘，他報名參加了少年考古隊，跟隨正式的考古隊進行考古發掘，通過實踐來更好的領會書本知識。這次考古隊發現了一個非常巨大的古墓，具有非常高的考古價值，小可可隨隊來到了考古現場。經過緊張的發掘，古墓的墓道終於顯露出來，但是它被一塊塊方磚封住了，現在小可可的任務就是幫助考古隊將這些方磚移走，打通墓道。由於這些保存完好的古代方磚也是珍貴的文物，所以規定一次最多隻能搬三塊磚。小可可在搬磚的過程中一直在思考一個問題，他很想知道將這些磚頭搬走共有多少種不同的搬法。
例如，現在總共有4個磚頭，那麼可以選擇的方法有以下7種：
1，1，1，1（分4次搬完，每次搬一個磚頭）
1，2，1（分3次搬完，第一次搬一個，第二次搬兩個，第三次搬一個）
1，1，2（分3次搬完，第一次搬一個，第二次搬一個，第三次搬兩個）
2，1，1（分3次搬完，第一次搬兩個，第二次搬一個，第三次搬一個）
2，2（分2次搬完，第一次搬兩個，第二次搬兩個）
1，3（分2次搬完，第一次搬一個，第二次搬三個）
3，1（分2次搬完，第一次搬三個，第二次搬一個）
你能不能幫助小可可解決這個問題呢？
輸入：共一行。是一個1～1000的正整數N，表示共有Ｎ塊磚頭。
輸出：共一行。輸出一個正整數表示N塊磚頭移動的方法數。

..............................