精华内容
下载资源
问答
  • [递归] 整数分解为若干项之和一、题目描述1.输入格式:2.输出格式:3.输入样例:4.输出样例:二、思路解析(三)所有代码 一、题目描述 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,...

    一、题目描述

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

    1.输入格式:

    每个输入包含一个测试用例,即正整数N (0<N≤30)。

    2.输出格式:

    按递增顺序输出N的所有整数分解式子。每个式子由小到大相加,式子间用分号隔开,且每输出4个式子后换行。

    3.输入样例:

    7
    

    4.输出样例:

    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
    

    二、思路解析

    根据题目中给出的输入输出样例,可以直观看出,需要采用递归来解决。
    同时,可以看到,分解的因子是从小到大变化,因此,可以考虑加上循环一起来解决。
    核心思路描述如下:

    items数组:存储分解的各项值
    count: 当前items存储的项数
    func(剩余未分解的数值,第1个分解的数值,已分解的项数)
    {
    	if (剩余未分解的数值 > 0 ){
    		for (从第1个分解的数值开始,直到小于剩余未分解的数值,递增)
    		{
    			将第1个分解的数值存入items数组;
    			将(剩余未分解的数值-1个分解的数值)作为剩余未分解的数值,递归调用func函数;
    		}
    	}
    	else {
    		开始打印items数组;
    		如果一行输出了4组分解的式子,则输出换行;
    	}
    }
    

    可以看出,func在递归时,先调用了循环,逐步分解;在分解的同时,将分解的数值存入到items数组中,并使用count记录个数,因此,这两个变量需设置为全局变量。

    三、所有代码

    #include<stdio.h> 
    # define MAX_SIZE 100
    
    int items[MAX_SIZE];//保存每一项的数值
    int count;			//当前输出式子个数 
    int N;				//分解的整数
    
    
    void f(int remain_value, int start, int num) {
    	//remain_value: 表示剩余需要分解的数字
    	// start:表示分解项的第一项
    	//num:表示已经分解了多少项
    	
    	if(remain_value!=0) {
    
    		//还没分解完
    		for(int i=start; i<=remain_value; i++) {
    			items[num] = i;
    			f(remain_value-i, i, num+1);
    		}
    	}else{
    		//remain==0,分解完毕
    		//开始打印当前式子 
    		count++;
    		
    			
    		printf("%d=%d",N,items[0]);//打印式子头部 
    		for(int j=1; j<num; j++){
    			printf("+%d",items[j]);
    		}
    		if(count%4==0) 
    			printf("\n");
            else if(count%4!=0&&items[0]!=N)
            printf(";");	
    	}	
    }
    
    int main(){
    	//题目:分解N 
    	//思路:递归求解 	
    	count=0;
        N = 7;
    	// scanf("%d", &N);
    	f(N, 1, 0);
    	return 0;
    
    }
    
    

    感谢@谢依萍同学提供解题代码!

    展开全文
  • 7-1 整数分解为若干项之和 (20 分) 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正...

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

    将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。
    输入格式:
    每个输入包含一个测试用例,即正整数N (0<N≤30)。
    输出格式
    按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列N​1​​={n​1​​,n​2​​,⋯}和N​2​​={m​1​​,m​2​​,⋯},若存在i使得n​1​​=m​1​​,⋯,n​i​​=m​i​​,但是n​i+1​​<m​i+1​​,则N​1​​序列必定在N​2​​序列之前输出。每个式子由小到大相加,式子间用分号隔开,且每输出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
    下面是代码部分

    #include <stdio.h>
    int a[31],sum=0,n=0,print_count=0;
    //全局变量;数组a用来存储分解后的各项 ,
    //sum用来表示在分解过程中各项的值当前相加的和,print_count 用来表示当前打印了多少次(用于每四次换行)** 
    void Print()
    {
    	print_count++;
    	printf ("%d=",n);
    	for (int i=1;a[i]!=0;++i)
    	{
    		if (a[i+1]==0&&print_count%4==0)printf("%d\n",a[i]);//最后一项的处理 (最后一项输出完需要换行时) 
    		else if (a[i+1]==0&&i==1)printf ("%d",a[i]);//最后一项输出完,以后再没有输出却不需要换行时(即输出n=n时) 
    		else if (a[i+1]==0)printf ("%d;",a[i]);//其他正常情况最后一项处理 
    		else printf ("%d+",a[i]);//非最后一项的处理 
    	 } 
     } 
     void dividing_recursion_f(int j)
     //递归函数:边界有两个 (1) 开始调用时sum的值正好等于n,此时不用往下进行了直接输出然后结束就可以了
     //第二个结束标志是for循环中sum+i值大于n   此时表示第j项以后不会再有符合要求的项了,此时只需结束--返回就行了 
     //参数j用于表示分解的第j项 
     {
     	if (sum==n){
     		Print();//边界(1) 
     		return ;
    	}
     	for (int i=1;i<=n;i++)//for循环用于不断用数去试 
     	{//核心部分 :当sum+i小于n时 且 前一项要比待填入的分解项(i)大时才填入(a[j]=i)(别忘了sum要加起来) 
     	//接下来的操作就是通过递归调用来填入下一分解项(j+1)调用结束后要复原 
     		if (sum+i<=n&&a[j-1]<=i){
     			a[j]=i;sum+=a[j];
     			dividing_recursion_f(j+1);
     			sum-=a[j];a[j]=0;//复原操作 
    		 }
    		else if(a[j-1]>i)continue;//注意这一个判断很重要,用来判断前一项是否大于待插入的项,
    								//大于就continue,循环进行下一次 ;该判断用于处理类似3=1+2;3=2+1等重复的情况 
    		else{//这个else是处理出现了sum+i>n的情况,此时是递归边界(2) 
    			return ;
    		}
    	 }
     }
     int main ()
     {
     	scanf ("%d",&n);
     	dividing_recursion_f(1);
     	return 0;
     }
    
    展开全文
  • 整数分解为若干项之和 Java

    千次阅读 多人点赞 2019-03-25 08:03:48
    编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正整数N (0<N≤30)。 输出格式: 按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列N​1​​={n​1​​,n​2​...

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

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

    输出格式:
    按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列N​1​​={n​1​​,n​2​​,⋯}和N​2​​={m​1​​,m​2​​,⋯},若存在i使得n​1​​=m​1​​,⋯,n​i​​=m​i​​,但是n​i+1​​<m​i+1​​,则N​1​​序列必定在N​2
    ​​序列之前输出。每个式子由小到大相加,式子间用分号隔开,且每输出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 
    
    

    思路解析:
    本题是深度优先搜索遍历的典型应用。在清华大学严蔚敏老师《数据结构》一书,第6章 图的遍历 一节中有涉及到此类遍历算法的讲解。具体内容请各位同学自行翻阅。限于篇幅,笔者仅就本题做出讨论。

    深度优先搜索是一种基于递归思想而产生的一种遍历方法。如对 n = 5进行分解,我们先设计以下方案:

    1 1 1 1 1   成立
    1 1 1 2     成立
    1 1 2 2     不成立
    1 1 3       成立
    1 2         不成立
    1 2 2       成立
    1 3 3       不成立
    1 4         成立
    2 2 2       不成立
    2 3         成立
    3 3         不成立
    4 4         不成立
    5           成立
    
    

    观察可发现,当和大于等于n时,抛弃当前指针位,指针回到前一位并将数值进行自增,每增一次进行一次和校验;当校验结果小于n时,保留原数组,指针再向右移一位同时把前一位的值赋给当前指针位,紧接着再进行校验。直到数组中只剩下一个数且值为n时结束。

    设pos为指针,array为试探数组,储存每组的试探数据,x为当前指针所指的元素。将以上思想用流程图描述如下:

    Created with Raphaël 2.2.0 开始 sum < n ? array[++pos] = array[pos];sum<n? pos--;x++;sum<n? yes no

    基于此我们可将判断+处理功能封装为一个函数,利用递归实现循环,示例代码如下:

    import java.util.Scanner;
    
    public class Main {
    	/*
    	 * 深度优先搜索遍历的应用
    	 */
    	 //定义全局共享变量
    	static int sum = 0;//存放和
    	static int pos = -1;//指针
    	static int n = 0;//初始化n为0
    	static int count = 0;//得到解的次数
    	static int[] reslut;//试探数组
    
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		n = sc.nextInt();
    		reslut = new int[n];
    		DFS(1);
    
    	}
    
    	private static void DFS(int x) {
    		if (sum == n) {// 得到一组解
    			count++;
    			System.out.print(n + "=");
    			for (int i = 0; i < pos; i++) {// 输出前pos-1个元素
    				System.out.print(reslut[i] + "+");
    			}
    			if (count % 4 == 0 || reslut[pos] == n) {// 此时换行,注意换行时不再打印分号。
    			                                        //而且最后一位即 n = n时也不需要打印费分号。
    				System.out.println(reslut[pos]);
    			}else {
    				System.out.print(reslut[pos]+";");//单独处理第pos个元素
    			}
    			return;// 返回上一层
    		}
    
    		if (sum > n) {// 此时是超解的
    			return;// 啥都不干,直接退回上一层
    		}
    
    		for (int i = x; i < n + 1; i++) {//把i的初值赋为x,目的就是保持序列自增,防止出现(x+1)+x情况
    			reslut[++pos] = i;// 要先自增再赋值,也会减少中间变量,节省空间
    			sum += i;
    			DFS(i);// 进入递归,其中一个就是检查作用
    			pos--;// 回到初始位置
    			sum -= i;// 清空该位
    			
    		}
    	}
    }
    
    
    展开全文
  • 整数分解为若干项之和 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正整数N (0<N≤...

    整数分解为若干项之和

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

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

    输入样例:
    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

    #include<bits/stdc++.h>
    using namespace std;
    int a[2222];
    int cou=0;
    int n;
    void dfs(int index,int s,int p)
    {
    	if(s==n)
    	{
    		printf("%d=%d",n,a[0]);
    		for(int i=1;i<p;i++)
    			printf("+%d",a[i]);
    		cou++;
    		if(cou%4==0)
    			cout<<endl;
    		else if(p==1)
    			cout<<endl;
    		else
    			cout<<";";
    		return;
    	}
    	
    	for(int i=index;i<=n;i++)
    	{
    		if(s+i<=n)
    		{
    			a[p]=i;
    			dfs(i,s+i,p+1);
    		}
    		else
    			break;
    	}
    }
    int main()
    {
    	while(cin>>n)
        {
            cou=0;
            dfs(1,0,0);
        }
    
    	return 0;
    }
    
    展开全文
  • 递归 整数分解为若干项之和

    千次阅读 2017-10-29 13:14:48
    7-1 整数分解为若干项之和(20 分)将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。输入格式:每个输入包含一个测试用例,即正整数...
  • 整数分解为若干项之和(C语言)

    千次阅读 多人点赞 2020-02-11 22:15:58
    编程求出正整数N的所有整数分解式子。 要求 时间限制: 800 ms 内存限制: 64 MB 代码长度限制: 16 K 输入格式: 每个输入包含一个测试用例,即正整数N (N>0&&N<=30)。 输出格式: 按递增顺序输出N的...
  • 整数分解为若干项之和 (20 分)

    千次阅读 多人点赞 2019-02-21 11:35:04
    7-10 整数分解为若干项之和 (20 分) 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,...
  • 编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正整数N (0<N≤30)。 输出格式: 按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列 Γ(z)=∫0∞tz−1e−tdt ....
  • 7-7 整数分解为若干项之和 (20 分)

    千次阅读 2019-04-19 23:27:33
    7-7 整数分解为若干项之和 (20 分) 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正...
  • 整数分解为若干项之和 题目作者 DS课程组 单位 浙江大学 题目 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个...
  • PTA 7-37 整数分解为若干项之和 (20 分) 题目要求: 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个...
  • 编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正整数N (0<N≤30)。 输出格式: 按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列N​1 ​​ ={n​1​​ ,n​2...
  • 7-37 整数分解为若干项之和 (20分)将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。输入格式:每个输入包含一个测试用例,即正整数N ...
  • 7-37 整数分解为若干项之和 (20分) 题目 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即...
  • 7- 10 整数分解为若干项之和 (20 分) 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正...
  • 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。
  • 题目链接(组合版):点击...解题思路:此方法仅限于输出组合情况,计数的话会TLE。AC 代码(组合版)#include&lt;bits/stdc++.h&gt; #include&lt;cmath&...#define mem(a,b) memset(a,b,sizeof a) ...typ...
  • 7-37 整数分解为若干项之和 Python 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正整数...
  • 编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正整数N (0<N≤30)。 输出格式: 输入样例: 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...
  • #include&lt;stdio.h&gt; int s[100];//拆分结果保存在这个数组里 int top;...//累加数所求数 int k; void dfs(int index) { int i; if (total == n){ printf("%d=", n); ...
  • 整数分解为若干项之和 (20 分)

    千次阅读 2019-06-10 18:03:57
    编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正整数N (0<N≤30)。 输出格式: 按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列N​1​​ ={n​1​​ ,n...
  • ![以上就是题目内容](https://img-blog.csdnimg.cn/20200421173146545.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODgxMTY3,size_16,...t_...
  • 7-37 整数分解为若干项之和(20 分) 将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。 输入格式: 每个输入包含一个测试用例,即正...
  • think: 1借鉴前辈的感悟,之前自己遇到递归总是不知道怎么写出表达式,自己的理解应该出现了偏差,递归思想的目的是将...参考博客——来自博客园1 整数分解为若干项之和 (20分)将一个正整数N分解成几个正整数相加,

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,112
精华内容 4,844
关键字:

整数分解为若干项之和