拆分自然数

任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。

#include <stdio.h>

void fun(int n,int k)
{
    static int s[50];
    if(n==0)
    {
        for(int j=0; j<k; j++)
            printf("%-2d",s[j]);
        putchar('\n');
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            s[k]=i;
            fun(n-i,k+1);
        }
    }
}

int main(int argc, char *argv[])
{
    int n;
    scanf("%d",&n);
    fun(n,0);
    return 0;
}

当 n = 5 时的结果

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

如果设定限制条件,后一个数的大小必定大于或等于前一个数,因为这样做的目的有两个,一是能够避免等式的重复,二是可以减少不必要的搜索,提高程序效率。

#include <stdio.h>

void fun(int n,int start, int k)
{
    static int s[50];
    if(n==0)
    {
        for(int j=0; j<k; j++)
            printf("%-2d",s[j]);
        putchar('\n');
    }
    else
    {
        for(int i=start; i<=n; i++)
        {
            s[k]=i;
            fun(n-i, i ,k+1);
        }
    }
}

int main(int argc, char *argv[])
{
    int n;
    scanf("%d",&n);
    fun(n,1,0);
    return 0;
}

当 n = 5 时的结果

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5
2017年5月23日 | 归档于 趣味问题
标签:
本文的评论功能被关闭了.