/* ------------------------------------------------------ */
/* FUNCTION  int_part_no :                                */
/*    Given an integer n, this function computes the      */
/* number of partitions of the input integer.  NOTE that  */
/* this function computes the number only and does not    */
/* generate the corresponding partition.  For the second  */
/* purpose, see program INTPART.C please.                 */
/*                                                        */
/* Copyright Ching-Kuang Shene               July/23/1989 */
/* ------------------------------------------------------ */

unsigned long  compute(int, int);
unsigned long  int_part_no(int);

unsigned long  int_part_no(int n)
{
     return compute(n, n);    /* convert to another form */
}

/* ----------------------------------------------------- */
/* FUNCTION  compute :                                   */
/*    The computation routine.  It accepts number-the    */
/* number to be partitioned, and maximum-the maximum     */
/* value in any partition of number, then returns the    */
/* number of partitions subject to number and maximum.   */
/* ----------------------------------------------------- */

unsigned long  compute(int number, int maximum)
{
     if (number == 1 || maximum == 1)
          return 1;
     else if (number < maximum)
          return compute(number, number);
     else if (number == maximum)
          return 1 + compute(number, maximum-1);
     else
          return compute(number,maximum-1) +
                 compute(number-maximum,maximum);
}

/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>

void  main(void)
{
     int  n;
     char line[100];

     printf("\nNumber of partitions of an Integer");
     printf("\n==================================");
     printf("\n\nN --> ");
     gets(line);
     n = atoi(line);
     printf("\nThere are %lu partitions.", int_part_no(n));
}


各位大虾帮忙看看呗！

英语查估计看不懂．．．或者就根本不想看．．呵呵

主要还得连翻译再做,差之毫厘,逆之千里呀!

什么啊 输入个数都没反应...

我分析了一下这个代码，这个代码的意思是，一个整数N，它可以表示为k个正整数Mi的和，
用式子表示为：N=M0+M1+...+M(k-1); (Mi>0)
如果Mi中的最大值记为m，则称m为该分解的模（我的临时定义）。即m=max{Mi}; (i=0,1,...,k-1)

compute(n,m)，返回值的意义是n的所有模小于等于m的分解个数。注意Mi之间的元素是无序的，即组合，而不是排列。例如4的分解中，{1,3}和{3,1}我们认为这是同一个分解。

这道题目求的是一个整数n的所有分解有多少个，即compute(n,n)，我们把compute(n,n)称为n的分解量，记为part(n).
例如part(4)=5,它的5个分解是：
{1,1,1,1},{1,1,2},{1,3},{2,2},{4}.

结论是通过猜测并分析上面这个compute函数得到的。我们可以想象一下如何求解分解数呢，我们用的是递归方法。那么我们就要找出compute(n,m)的递归关系。
从回归条件开始分析，什么条件是最简单的case？显然，当n=1时，无论m是多少都只有{1}一个分解。另外当m=1时，无论n多大，也只有一个分解，即n个1，{1,1,1,...,1}。所以回归条件如下：当n或者m为1时，返回1.

我们再分析一般情况，总结出递归关系。显然当m>n时，compute(n,m)=compute(n,n)。因为任何分解中的元素Mi肯定是小于等于n的。
当m=n时，可以分成两种情况，一种是所有的模小于m的分解，即compute(n,m-1)。另一种情况是模等于n的分解，只有一个，即{n}。所以这时
当m=n时，compute(n,m)= 1+compute(n,m-1)；

当m<n时，我们还是分成上面的两种情况，一种是模小于m的分解，即compute(n,m-1)。另一种情况是模等于m的分解。模等于m的分解表示在分解中必定有至少一个数是m，我们把除了m以外的所有数记为{X},因此模等于m的所有分解可以表示为{{X},m}。 所以模等于m的分解的数量实际上就是一共可以找到多少种{X}，而{X}实际上是一个模小于等于m的对（n-m）的分解，即{X}个数=compute(n-m,m)。因此
当m<n时，compute(n,m)=compute(n,m-1)+compute(n-m,m);

综合以上结果，也就是上面的递归函数的代码。分析完毕。

[[it] 本帖最后由 hoodlum1980 于 2008-3-15 22:56 编辑 [/it]]

收到的鲜花

• 死了都要C 于 2008-03-15 22:19 送鲜花  5朵   附言：```很好``不错```

前面那个代码只给出了结果，但没有列出所有分解结果。下面部分的代码是我在网络上搜索到的，是列出分解结果的代码。

/* ------------------------------------------------------ */
/* PROGRAM  integer partition :                           */
/*    Given a positive integer n, this program lists all  */
/* partition of n in anti-lexical order.                  */
/*                                                        */
/* Copyright Ching-Kuang Shene               July/21/1989 */
/* ------------------------------------------------------ */

#include  <stdio.h>
#include  <stdlib.h>          /* for atoi()               */

#define   MAXSIZE   20

void  display(int [], int [], int);

void  main(void)
{
     int  partition[MAXSIZE+1]; /* the actuall partition  */
     int  mult[MAXSIZE+1];      /* multiplicity           */
     int  part_no;              /* no. of parts           */
     int  sum, size, remainder, count;
     int  n;
     char line[100];

     printf("\nPartition of Integer");
     printf("\n====================");
     printf("\n\nInput a Positive Integer --> ");
     gets(line);
     n = atoi(line);

     partition[1] = n;        /* at the biginning, we have*/
     mult[1]      = part_no = count = 1; /* only one part.*/
     display(partition, mult, part_no);

     do {                     /* size one sum in 'sum'    */
          sum  = (partition[part_no]==1) ? mult[part_no--]+1 : 1;
          size = partition[part_no] - 1; /* dec. size     */
          if (mult[part_no] != 1)  /* last part with mul=1*/
               mult[part_no++]--;  /* NO, cut this part   */
          partition[part_no] = size; /* set new part=size */
          mult[part_no]      = sum/size + 1; /* fill other*/
          if ((remainder = sum % size) != 0) {
               partition[++part_no] = remainder;
               mult[part_no]        = 1;
          }
          count++;
          display(partition, mult, part_no);
     } while (mult[part_no] != n);
     printf("\n\nThere are %d partitions in anti-lexical order",
                 count);
      getch();
}


/* ------------------------------------------------------ */
/* FUNCTION display :                                     */
/*    This routine displays the given partition.          */
/* ------------------------------------------------------ */

void  display(int partition[], int mult[], int part_no)
{
     int  i, j;

     printf("\n");
     for (i = 1; i <= part_no; i++)      /* for each part */
          for (j = 1; j <= mult[i]; j++) /* and its mult. */
               printf("%3d", partition[i]); /* show them  */
}

例如：当输入n=6时，程序输出结果：

  6
  5  1
  4  2
  4  1  1
  3  3
  3  2  1
  3  1  1  1
  2  2  2
  2  2  1  1
  2  1  1  1  1
  1  1  1  1  1  1

There are 11 partitions in anti-lexical order

一个单元加的题目..
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{ int data;
  struct node *next;
} st;
st *top=NULL,*p=NULL;

void print()
{ while(p)
  { printf("%d ",p->data);
    p=p->next;
  }
  printf("\n");
}

void fun(int m,int n)
{ if(m==n)
  { p=(st *)malloc(sizeof(st));
    p->next=top;
    p->data=n;
    print();
    free(p);return;
  }
  else if(m>n) return;
  else
  { int i;
    p=(st *)malloc(sizeof(st));
    p->next=top;
    top=p;
    for(i=m;i<=n/2;i++)
    { top->data=i;fun(i,n-i);
    }
    if(top->next)
    { top->data=n;p=top;print();
      p=top;top=top->next;free(p);
    }
  }
}

void main()
{ int n;
  printf("Please type a number(>=2):");
  scanf("%d",&n);
  printf("\n");
  fun(1,n);
}

谢谢大家的帮忙！我一定好好看看。

我计算的时候最后都剩一个compute (0,x)
然后就不知道该怎么办了，这个是不是不用计算？