整数划分-分治法

 1 #include <stdio.h>
 2 
 3 int bufferArray[1000]={0};//缓存数组 
 4 int bufferLenth=0;//缓存数组的当前长度 
 5 int outputSignal=-1;//当前输出的控制信号 
 6 int total=0;//划分的总数 
 7 
 8 //划分整数 ，number=要划分的数字,tempNumber=划分的数字 
 9 void dividedInt(int number,int tempNumber)
10 {
11     if(number<=0)    return ;
12      
13     if(number>=tempNumber)
14     {
15         total++;
16         //输出信号不为-1，当缓存数组长度大于0，且缓存数组的首位不等于输出信号，或者缓存数组为0，且要划分的数字不等于输出信号 
17         if(outputSignal>-1 && ((bufferLenth>0 && bufferArray[0]!=outputSignal) || (bufferLenth==0 && number!=outputSignal)))
18             printf("\n");
19         //否则如果输出信号大于1 
20         else if(outputSignal>1)    printf(",");
21         //输出缓存数组 
22         if(bufferLenth>0)
23         {
24             for(int i=0;i<bufferLenth;i++)    printf("%d+",bufferArray[i]);
25             outputSignal=bufferArray[0];
26         }
27         else
28             outputSignal=number;
29             
30         printf("%d",number);
31         if(tempNumber>0)    printf("+%d",tempNumber);
32         
33         //分治法---当划分的数字大于1
34         if(tempNumber>1)    
35         {
36             bufferArray[bufferLenth++]=number;
37             dividedInt(tempNumber-1,1);    
38             bufferLenth--;        
39         }
40     }
41     //分治法--当要划分的数字小于划分的数字 
42     else
43     {
44         bufferArray[bufferLenth++]=number;
45         dividedInt(number,tempNumber-number);
46         bufferLenth--;
47     }
48     //分治法--当要划分的数字大于1 
49     dividedInt(number-1,tempNumber+1);
50 }
51 
52 int main()
53 {
54     int number;
55     
56     scanf("%d",&number);
57     printf("开始划分：\n");
58     dividedInt(number,0);
59     printf("\n总数：%d",total);
60     
61     return 0;
62 }