#include <cstdio>
#include <cstring>
bool Quick_Read(int &N) {
N = 0;
int op = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')
op = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
N = (N << 1) + (N << 3) + (c ^ 48);
c = getchar();
}
N *= op;
return N != 0;
}
void Quick_Write(int N) {
if(N < 0) {
putchar('-');
N = -N;
}
if(N >= 10)
Quick_Write(N / 10);
putchar(N % 10 + 48);
}
const int MAXN = 1e5 + 5;
int ans[MAXN];
int limit;
bool flag;
int n;
void Id_Dfs(int nowdepth) {
if(nowdepth > limit || flag)//达到层数不在恋战或找到答案,直接跳出
return;
if(ans[nowdepth] == n) {//满足题意
flag = true;
return;
}
for(int i = nowdepth; i >= 1; i--) {
for(int j = nowdepth; j >= i; j--) {//两两搭配,且答案越大越容易找到解,故而到着找
if(ans[i] + ans[j] <= n && ans[i] + ans[j] > ans[nowdepth]) {//满足题意1,2两点的搜索
int now;//找到下一项
ans[nowdepth + 1] = now = ans[i] + ans[j];
for(int k = nowdepth + 2; k <= limit; k++)
//从nowdepth + 1这一项开始,后面最大时也就是now不停扩大2倍,若最大都达不到n,舍去不求
now <<= 1;
if(now < n)
continue;
Id_Dfs(nowdepth + 1);//搜索下一层
if(flag)//找到答案
return;
}
}
}
}
void Work() {
for(; !flag; limit++)//直到找到答案时停止搜索
Id_Dfs(1);
for(int i = 1; i < limit; i++) {//输出
Quick_Write(ans[i]);
putchar(' ');
}
putchar('\n');
}
void Init() {
limit = 1;
int test = 1;
while(test < n) {//找到最小层数
test <<= 1;
limit++;
}
ans[1] = 1;
flag = false;
}
int main() {
while(Quick_Read(n)) {//多组输入输出,到0为止
Init();
Work();
}
return 0;
}
没有合适的资源?快使用搜索试试~ 我知道了~
迭代加深搜索.zip
共1个文件
cpp:1个
0 下载量 90 浏览量
2024-04-24
22:45:37
上传
评论
收藏 1KB ZIP 举报
温馨提示
算法是解决特定问题或执行特定任务的一系列步骤或规则的有序集合。在计算机科学中,算法通常用来指导计算机执行特定的任务或解决问题。良好设计的算法能够有效地解决问题,并且在给定的输入下能够产生正确的输出。 常见的算法包括但不限于以下几种: 排序算法:排序算法是将一组数据按照一定的顺序排列的算法。常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。 搜索算法:搜索算法用于在数据集中查找特定元素的算法。常见的搜索算法包括线性搜索、二分搜索等。 图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂问题的算法。常见的动态规划问题包括背包问题、最长递增子序列、编辑距离等。 贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法。常见的贪心算法包括最小生成树算法中的Prim算法、Dijkstra算法等。 字符串匹配算法:字符串匹配算法用于在一个字符串(文本)中查找一个子串(模式)的出现位置。常见的字符串匹配算法包括暴力匹配、KMP算法、Boyer-Moore算法等。 这些是计算机科学中常见的算法类型,每种算法都有不同的应用场景和解决问题的方法。在实际编程中,选择合适的算法对于提高程序效率和性能至关重要。
资源推荐
资源详情
资源评论
收起资源包目录
迭代加深搜索.zip (1个子文件)
迭代加深搜索
迭代加深搜索.cpp 2KB
共 1 条
- 1
资源评论
枫蜜柚子茶
- 粉丝: 6247
- 资源: 4641
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功