整数划分问题将一个整数划分为一系列正整数之和
例如P(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
要打印出 等式数量 和各个等式(像上面那样)
给你一个参考程序(不是我写的)
/* ------------------------------------------------------ */
/* 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\n",
count);
}
/* ------------------------------------------------------ */
/* 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 */
}