整数分解为若干项之和——递归思想

朱雀 2022-09-27 15:19 171阅读 0赞

字节跳动校招内推码: C4BDSMC
    投递链接: https://job.toutiao.com/s/J691fRK
    内推交流QQ群：1049175720

think:  
1借鉴前辈的感悟，之前自己遇到递归总是不知道怎么写出表达式，自己的理解应该出现了偏差，递归思想的目的是将复杂的问题简单化，由强大的计算机来完成复杂的细节处理，自己忽略了宏观框架的构建，导致细节理解理解就理不清条理了，再就是面对问题不自信，细节与细节之间把握不到位，相信自己，一点一点努力！  
2递归思想可以先深入理解一些传统的递归题目的解法，在解题过程中可以借鉴之前题目的思想与解法

[参考博客——来自博客园][Link 1]

1 整数分解为若干项之和 (20分)

将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。

输入格式：  
每个输入包含一个测试用例，即正整数N (0<<<N≤\\le≤30)。

输出格式：  
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1=N\_1=N1=\{n1,n2,⋯n\_1, n\_2, \\cdotsn1,n2,⋯\}和N2=N\_2=N2=\{m1,m2,⋯m\_1, m\_2, \\cdotsm1,m2,⋯\}，若存在iii使得n1=m1,⋯,ni=min\_1=m\_1, \\cdots , n\_i=m\_in1=m1,⋯,ni=mi，但是ni+1<mi+1n\_\{i+1\} < m\_\{i+1\}ni+1<mi+1,则N1N\_1N1序列必定在N2N\_2N2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。

输入样例：  
7

输出样例：  
7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2  
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2  
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3  
7=2+5;7=3+4;7=7

hint:

测试点1 	答案正确 	12/12 	2 	1 	样例等价，多行输出
    测试点2 	答案正确 	3/3 	1 	1 	一行内输出
    测试点3 	答案正确 	1/1 	21 	1 	最小N
    测试点4 	答案正确 	4/4 	26 	1 	最大N

以下为参考后答案正确代码

#include <stdio.h>
    int meo[34], top, n, cnt, sum;
    void ans(int x);
    int main()
    {
    	while(scanf("%d", &n) != EOF)
    	{
    		top = 0, cnt = 0, sum = 0;
    		ans(1);
    	}
    	return 0;
    }
    void ans(int x)
    {
    	int i, j;
    	if(sum == n)
    	{
    		cnt++;
    		printf("%d=", n);
    		for(i = 0; i < top-1; i++)
    			printf("%d+", meo[i]);
    		if(cnt % 4 == 0 || meo[top-1] == n)
    			printf("%d\n", meo[top-1]);
    		else
    			printf("%d;", meo[top-1]);
    		return;
    	}
    	if(sum > n)
    		return;
    	for(j = x; j <= n; j++)
    	{
    		meo[top++] = j;
    		sum += j;
    		ans(j);
    		sum -= j;
    		top--;
    	}
    }

[Link 1]: http://www.cnblogs.com/andywenzhi/p/5738715.html