51 lines
1.8 KiB
C
51 lines
1.8 KiB
C
/*
|
||
Program: partition-integer.c (Report comments/bugs to chikh@yuntech.edu.tw)
|
||
Function: 以遞迴的方式對給定的某一正整數進行分割，並列出所有可能的分割形式。例如：4 = 4+0
|
||
= 1+3 = 2+2 = 1+1+2 = 1+1+1+1共有5種分法。
|
||
運作理念：設待分割的數為n、max為最大元素值(max<=n，形成分割的每一個元素i<=max)，
|
||
由1開始遞增決定一數值i視為此次所採分解元素，並把i存入堆疊，此時待分割的數即變成
|
||
(n-i)，如此再依上述邏輯繼續分割，直至無法分割(觸底)為止。一旦觸底即把過去儲存
|
||
在堆疊中的元素逐一提取出來並顯示於螢幕。每一次觸底，意味著一種連續分割方式暫告
|
||
一段落，程式應返回至最近啟動連續分割之上層流程位置，再繼續處理未決的部分，直至
|
||
所有可能的分割方式均已探索過，整個問題方告完畢
|
||
Notes: 1) 留意遞迴函數的呼叫方式、參數與順序，有點小複雜但應不難懂，另注意一旦觸底的應
|
||
對機制
|
||
2) 運用堆疊的概念順應遞迴呼叫的特性，逐筆紀錄分割過程所採之分解元素
|
||
3) 參考並修改 https://bit.ly/3dC2mlX 所載版本
|
||
*/
|
||
|
||
#include <stdio.h>
|
||
|
||
int indx = 0; /* 索引，指示堆疊頂端元素位置 */
|
||
int element[100] = {0}; /* 以陣列實作堆疊結構 */
|
||
|
||
void printPartitions(int n, int max, int addend) /* n:待分割的數、max:最大元素、addend:所採用的分解元素 */
|
||
{
|
||
int i;
|
||
|
||
element[indx++] = addend; /* 相當於push()動作 */
|
||
|
||
if (n == 0) { /* 已觸底、無法再分割 */
|
||
for (i = indx-1; i > 0; i--) /* 把推疊紀錄的元素逐一印出 */
|
||
printf("%d ",element[i]);
|
||
printf("\n");
|
||
}
|
||
else /* n > 0，意味著尚可繼續分割 */
|
||
for (i = 1; i <= max && i <= n; i++) /* 由1開始遞增決定一數值i視為此次所採分解元素，待分割的數即變成(n-i) */
|
||
printPartitions(n-i,i,i); //printPartitions(target-i,i,element[indx++]=i);
|
||
|
||
indx--; /* 等同pop()動作 */
|
||
}
|
||
|
||
int main()
|
||
{
|
||
int n;
|
||
|
||
printf("輸入欲分割的正整數 ==> ");
|
||
scanf("%d",&n);
|
||
printf("可能的分割方式如下：\n");
|
||
printPartitions(n,n,0);
|
||
|
||
return 0;
|
||
}
|