1870789_ac_62ms_28k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 46 行

# include <stdio.h>

int n;
int min;
int output[100], tmp[100];

int search(int x)
{
 int i, j, m;
 if(x >= min) return 0;
 for(i = x - 1; i >= 0; i--)
  for(j = i; j >= 0; j--)
   {
     if(tmp[i]+tmp[j]<=tmp[x-1]) return 0;
     if(tmp[i]+tmp[j]<=n)
     {
      tmp[x] = tmp[i]+tmp[j];
      if(tmp[x]<n&&x<min) search(x+1);
      if(tmp[x]==n&&x<min)
      {
       for(m = 0; m < n; m++)
        output[m] = tmp[m];
        min = x;
        return 0;
      }
     }
   }
   return 0;
}

int main()
{
 int i;
 
 while(scanf("%d",&n)==1&&n)
 {
  if(n==1) {printf("1\n");continue;}
  min = 100;
  tmp[0] = 1;
  search(tmp[0]);
  for(i = 0; i < min; i++)
   printf("%d ",output[i]);
   printf("%d\n",n);
 }
 return 0;
}