想必大家经过三天的练习,已经对递归有了深入的理解吧,那么今天的题解就不“保姆式教学了”,想必大家也都能理解的(也可以理解成题解人想要偷懒)
将一个正整数N分解成几个正整数相加,可以有多种分解方法,例如7=6+1,7=5+2,7=5+1+1,…。编程求出正整数N的所有整数分解式子。
输入格式:
每个输入包含一个测试用例,即正整数N (0<N≤30)。
输出格式:
按递增顺序输出N的所有整数分解式子。递增顺序是指:对于两个分解序列N1?? ={n?1?? ,n?2?? ,?}和N?2?? ={m?1?? ,m?2?? ,?},若存在i使得n?1?? =m?1?? ,?,n?i?? =m?i?? ,但是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<bits/stdc++.h>//万能头文件
using namespace std;
int n;
int s[33];
int ans=0;//记录满足结果的个数
void dfs(int x,int cur,int sum){
/*
x为当前要加的数,cur为s数组中要加
数的下标 ,sum为目前相加的数的总和
*/
if(sum>n)return ;//剪枝
if(sum==n){//如果当前的和等于n 输出
ans++;//结果个数++,为了输出要求的格式
cout<<n<<"="<<s[0];
for(int i=1;i<cur;i++){
cout<<"+"<<s[i];
}
if(ans%4!=0&&x!=n){
/*
除了行末都要输出“; ”,注
意最后一行的最后一个不能有“; ”
*/
cout<<";";
}
if(ans%4==0){//每4个答案换一次行
cout<<endl;
}
}
for(int i=x;i<=n;i++){
s[cur]=i; //将i加入数组
dfs(i,cur+1,sum+i);
/*
等待加入的数组下标往后移一
位,此时的总和加上i;
*/
}
}
int main(){
cin>>n;
dfs(1,0,0);
return 0;
}
从 1~n 这 n 个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围
1≤n≤15
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
这里附上一张我嫖来的图,觉得有了图挺容易理解的
本题运用的是二叉树递归
每个数有三种状态,0表示待考虑,1表示选择,2表示不选
#include<iostream>
#include<cstring>
using namespace std;
int n;
int s[15];
/*
s数组记录每个数的状态,0表示待考虑,
1表示选择,2表示不选
*/
void f(int k) {
if (k > n) {
for (int i = 1; i <= n; i++) {
//如果是1,就输出该数
if (s[i] == 1) {
cout << i << " ";
}
}
cout << endl;
return;
}
s[k] = 2;
f(k + 1);//第一个分支,不选
s[k] = 1;
f(k+1);//第二个分支,选择
}
int main() {
cin >> n;
f(1);
return 0;
}
最后附上本题我借鉴的大佬题解的链接:https://blog.csdn.net/qq_41575507/article/details/108200053?utm_source=app&app_version=4.5.2
背景 该问题来自某客户,据描述,他们在部署 MySQL 主从复制时,有时候仅在主库...
代码实现方式: 复制代码 代码如下: !DOCTYPE html head title New Document /ti...
1月25日消息 外媒 Windows Latest 报道,微软 Windows 10 即将迎来的最大视觉更...
说明:将textarea值中的回车换行 复制代码 代码如下: %=内容值%.Replace("\r\n",...
在php中preg_match()函数是用来执行正则表达式的一个常用的函数。正则表达式几乎...
本文转载自网络,原文链接:https://www.toutiao.com/a6864892090686374412/...
Spring AOP 基于注解详解及实例代码 1.启用spring对@AspectJ注解的支持: beans x...
复制代码 代码如下: '返回指定文件夹中文件的数目,传入值为被检测文件夹的硬盘...
经常提到数据库的事务,那你知道数据库还有事务隔离的说法吗,事务隔离还有隔离...
写这篇文章是因为之前有一次删库操作,需要进行批量删除数据,当时没有控制好删...