PTA--整数拆分

刺骨的言语ヽ痛彻心扉 2022-12-27 12:36 158阅读 0赞

将一个正整数拆分成若干个正整数的和。

输入格式:  
一个正整数n

输出格式:  
若干行，每行一个等式（每个数或者等号间都有一个空格，第一个数前没有空格，最后一个数后面没有空格，数与数之间要求非降序排列）。最后一行给出解的总个数

输入样例:  
在这里给出一组输入。例如：  
4

输出样例:  
在这里给出相应的输出。例如：

4 = 1 + 1 + 1 + 1  
4 = 1 + 1 + 2  
4 = 1 + 3  
4 = 2 + 2  
4

#include <iostream>
    #include <cstring>
    using namespace std;
    int n,num;
    int a[1000];
    void backtrack(int k,int sum){
        
         int i,j,m;
           j=0;
           if(sum>n)
              return;
           if(sum==n)
    	   {
        
               printf("%d = ",n);
               for(m=0;;m++)
                  if(a[m]==0)
                    break;
               for(i=0;i<m;i++){
        
                    if(i)
                    printf(" + ");
                    printf("%d",a[i]);
    		   }
             printf("\n");
             num++;
             return;
     }
            for(i=k;i<n;i++){
        
                while(1)
    			{
        
                  if(a[j]==NULL){
        
                    a[j]=i;
                    break;
    			  }
               j++;
    			}
               backtrack(i,sum+i);
               a[j]=NULL;
     }
    }
    int main()
    {
        
     scanf("%d",&n);
     backtrack(1,0);
     printf("%d\n",num);
     return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关 343. 整数拆分

343. 整数拆分给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1

川长思鸟来/ 2024年03月26日 18:11/ 0 赞/ 81 阅读

相关整数拆分(c++,java)

整数拆分一个整数总可以拆分为 2 的幂的和。例如：7可以拆分成 7=1+2+4,7=1+2+2+2,7=1+1+1+4,7=1+1+1+2+2, 7=1+1+1

一时失言乱红尘/ 2024年03月25日 20:38/ 0 赞/ 85 阅读

相关 343. 整数拆分

343. 整数拆分题干描述解题思路动态规划 1. 确定dp数组（dp table）以及下标的含义

小咪咪/ 2023年10月16日 16:05/ 0 赞/ 35 阅读

相关求解整数拆分问题

求将正整数n无序拆分成最大数为k的拆分方案个数，要求所有的拆分方案不重复。例如：设n=5,k=5 对应的拆分方案如下：（1）5=5 （2）5=4+1 （3）5=3+

墨蓝/ 2023年10月11日 16:35/ 0 赞/ 71 阅读

相关 343. 整数拆分

[343. 整数拆分][343.] 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。示例 1: 输入

た入场券/ 2023年03月03日 08:45/ 0 赞/ 8 阅读

相关 PTA--整数拆分

将一个正整数拆分成若干个正整数的和。输入格式: 一个正整数n 输出格式: 若干行，每行一个等式（每个数或者等号间都有一个空格，第一个数前没有空格，最后一个数后面没

刺骨的言语ヽ痛彻心扉/ 2022年12月27日 12:36/ 0 赞/ 159 阅读

相关 343. 整数拆分

> 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。返回你可以获得的最大乘积。 > > 示例 1: > > 输入: 2 > 输出: 1

青旅半醒/ 2022年10月07日 00:50/ 0 赞/ 133 阅读

相关 leetcode 343 整数拆分

前言题目：[343. 整数拆分][343.] 参考题解：[整数拆分-代码随想录][-] -------------------- 提交代码题目：给定一个正

灰太狼/ 2022年08月28日 05:48/ 0 赞/ 184 阅读

相关拆分实数的整数与小数部分--PTA

本题要求实现一个拆分实数的整数与小数部分的简单函数。函数接口定义： \\void splitfloat( float x, int intpart, float fr

ゝ一世哀愁。/ 2022年02月09日 07:53/ 0 赞/ 439 阅读

相关 190512 | 整数拆分

题目描述一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1

淩亂°似流年/ 2022年01月31日 23:43/ 0 赞/ 234 阅读