安徽省青少年信息学奥林匹克竞赛中学组试题(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块砖头移动的方法数。

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