整數分割

三、整數分割（Parition of Integer），如：4 = 4、3+1、2+2、2+1+1、1+1+1，共五種不重複分割方法，輸入任意數 n，列出所有分割方式和共有幾種分割方法。

input:
4

output:
1+1+1+1
1+1+2
2+2
3+1
4
共5種

困難度：**
時間複雜度：c1((1+5^(1/2))/2)^n + c2((1-5^(1/2))/2)^n，
　　　　　　c1+c2 = 0，(c1(1+5^(1/2))/2)+(c2(1- 5^(1/2))/2)=1
程式語言：C++
預估時間：2 小時

解題原理：
1. 先取得使用者輸入欲分割的正整數
2. 任意正整數 n 必可寫為 n 個 1 連加，暫存在陣列 A[n]
3. 由左而右開始，一次處理鄰近二個數，讓右邊的數=右邊的數+左邊的數，之後把左邊的數設為零
4. 將目前陣列元素進行由小排到大，暫存排序後的陣列 B，印出不重複的陣列 B[n] 非零的數連加字串
5. 重複步驟 3，直到開始處理的位置到 n-1
6. 完成

程式下載

原碼下載

參考來源：長榮大學2007校內程式設計競賽複賽 試題 三