洛谷 P2404 自然数的拆分问题
2024-10-16 13:52:53
洛谷 P2404 自然数的拆分问题
题目链接
<font face="Comic Sans Ms"size=5>https://www.luogu.org/problemnew/show/P2404
题目背景
木有......
题目描述
任何一个大于1的自然数n,总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n,要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列,其中字典序小的序列需要优先输出。
输入输出格式
输入格式:
输入:待拆分的自然数n。
输出格式:
输出:若干数的加法式子。
思路
用搜索和回溯做吧......比那个输出素数环还要简单的啦
这道题属于回溯的一道板子题,还是比较好做的
可以一路搜到底得到一种方案,然后在这次的方案排列完毕后,回溯,继续搜索下一方案
代码
#include<bits/stdc++.h>
using namespace std;
int a[10086]= {1};
int n,total;
int search(int,int);
int print(int);
int main() {
scanf("%d",&n);
search(n,1);
return 0;
}
int search(int s,int t) {
for(int i=a[t-1]; i<=s; i++) {
if(i<n) {
a[t]=i;
s-=i;
if(s==0)print(t);
else search(s,t+1);
s+=i;
}
}
}
int print(int t) {
for(int i=1; i<=t-1; i++) {
cout<<a[i]<<"+";
}
cout<<a[t]<<endl;
}
最新文章
- 跨域的jsonP
- python 集合set
- gdb 远程调试 android native 程序
- 从零开始写一个武侠冒险游戏-7-用GPU提升性能(2)
- Ubuntu 14.10 下安装中文输入法
- Add Two Numbers ---- LeetCode 002
- cdev_系列函数
- Fast特征检测
- 与内存有关的那些事儿(数组分配空间不够,导致缓冲区溢出,从而strcpy会出现异常)
- HDU3537-Daizhenyang&;#39;s Coin(博弈SG-打表)
- C++ 复制功能
- Shiro基础学习(一)&mdash;权限管理
- coreCLR系列随笔 之ClrJit项目之alloc.cpp文件分析(1)
- Spring中ApplicationContext加载机制
- Mongodb中 Documents文档说明
- devmem读写物理内存和devkmem读取内核虚拟内存
- 解决用低版本的客户端ORACLE 12提示ORA-28040的异常
- centos 安装php laravel框架
- db2调优
- 基于canvas的电子始终
热门文章
- 基于Docker的TensorFlow机器学习框架搭建和实例源码解读
- loadrunner&#160;脚本录制-Protocol&#160;Advisor协议分析器的使用
- Android内存优化(三)详解内存分析工具MAT
- java----八种排序算法
- shell编程-输入/输出重定向(十一)
- C#解析XML 例子二
- ugui中toggle.isOn的属性笔记
- python爬虫之天气预报网站--查看最近(15天)的天气信息(正则表达式)
- 修改linux 默认SHELL
- php快速定位当前调用的类的位置