题目链接:
UVA :http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=470
POJ :http://poj.org/problem?id=2248
类型: 回溯, 迭代加深搜索, 减枝
原题:
An addition chain fornis an integer sequencewith
the following four properties:
-
a0= 1
-
am=n
- a0<a1<a2<...<am-1<am
- For eachk() there exist two (not neccessarily different) integersiandj()
withak=ai+aj
You are given an integern. Your job is to construct an addition chain fornwith minimal length. If there is more than one such sequence, any one is acceptable.
For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.
样例输入:
5
7
12
15
77
0
样例输出:
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
题目大意:
给一个数字n, 然后输出一个元素个数最少的从1到n的序列(可能有多种方案,输出其中一种即可)。
其中对于第k个数Ak, 它的值等于Ai+Aj()
。
分析与总结:
这一题是典型的迭代加深搜索+减枝的题目。
迭代加深的搜索(IDS,Iterative Deepening Search):
迭代加深搜索,实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树,若没有发现可行解,再将K+1后重复以上步骤搜索,直到搜索到可行解。
在迭代加深搜索的算法中,连续的深度优先搜索被引入,每一个深度约束逐次加1,直到搜索到目标为止。
迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。既能满足深度优先搜索的线性存储要求,又能保证发现一个最小深度的目标结点。
从实际应用来看,迭代加深搜索的效果比较好,并不比广度优先搜索慢很多,但是空间复杂度却与深度优先搜索相同,比广度优先搜索小很多。
对于这一题,首先可以求出最少需要几个元素可以达到n。按照贪心的策略,对于每个元素的值,都选择让它等于一个数的两倍,即对于每个Ai = Ai-1 + Ai-1, 当Ai>=n时就跳出循环,得到最少元素个数。
然后从最少步数开始迭代加深搜索。 然后再用上一些减枝技巧即可。
// 深度迭代搜索+减枝 Time: UVa 0.012s POJ: 0MS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans[100];
bool flag;
void dfs(int cur, int depth){
if(flag) return;
if(cur==depth){
if(ans[cur]==n) flag=true;
return ;
}
for(int i=0; i<=cur; ++i){
for(int j=i; j<=cur; ++j)if(ans[i]+ans[j] > ans[cur] && ans[i]+ans[j]<=n ){ // 这里也进行减枝
// 下面这个减枝至关重要!!如果从当前一直往下都是选择最大的策略还是不能达到n,跳过
bool ok = false;
int sum=ans[i]+ans[j];
for(int k=cur+2; k<=depth; ++k)
sum *= 2;
if(sum < n) continue;
ans[cur+1] = ans[i]+ans[j];
dfs(cur+1, depth);
if(flag)return;
}
}
}
int main(){
while(scanf("%d", &n),n){
memset(ans, 0, sizeof(ans));
ans[0] = 1;
flag = false;
// 计算出至少需要多少步
int m=1, depth=0;
while(m<n){
m *= 2;
depth++;
}
// 从最少步开始进行迭代加深搜索
while(true){
dfs(0, depth);
if(flag) break;
depth++;
}
printf("%d", ans[0]);
for(int i=1; i<=depth; ++i)
printf(" %d", ans[i]);
printf("\n");
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
Numerical-Methods-for-Structured-Markov-Chains
IEC 60598-2-20-2022 Luminaires - Part 2-20_ Particular requirements - Lighting chains.pdf
电子商务概论英文课件:ch06 E-Supply Chains.ppt
Stability of Markovian processes I_ Criteria for discrete-time chains
电子商务英文课件:ch06 E-Supply Chains,Collaborative Commerce,And Corporate Portals.ppt
06-algorithm-chains-and-pipelines
scope-chains-closures, Javascript作用域链和闭包 workshop 范围链和闭包 workshop正在启动$ npm install -g scope-chains-closures$ scope-chains-closures # or, shorter: sccjs使用箭头
一种具有长程相互作用的自旋链模型的热力学性质,侯吉旋,,我们研究了一种具有平均场型的长程相互作用的自旋-1链模型. 该模型在微正则系综中可以被精确求解并且我们得到了该模型的微正则相�
evm-chains-extended 打包以查询链数据,以及必需的扩展数据。 利用Pedro Gomes的包获取初始数据,然后合并到扩展数据中。 包括某些网络的Block Explorer URL和网络徽标。 注意:这还利用了静默接口模式,在该模式下...
Linux Notification chains--1
ATS区块链 ATS中的区块链,智能合约和数据库实施 关于 目前,该CLI的使用方式如下: 定义矿工/用户 进行交易(有效或其他方式) 编写/执行智能合约 编写/执行查询 决定谁将开采下一个区块 查看用户余额 ...
NodeSchool作用域链关闭 NodeSchool范围链关闭练习从scope-chains-closures软件包中解决:npm install -g scope-chains-closures 感谢
SUMS85 Understanding Markov Chains -- Examples and Applications, 2nd Edition, Nicolas Privault (2018).zip
npm install --save evm-chains # or yarn add evm-chains 原料药 function getAllChains ( ) : IChainData [ ] ; function getChain ( chainId : number ) : IChainData ; function getChainByChainId ( chainId : ...
SUMS58 Understanding Markov Chains -- Examples and Applications, Nicolas Privault (2013).zip
全球港口贸易运输网络及其货运量数据Ports' criticality in international trade and global supply-chains地理计算、社科交通出行。全球港口贸易运输网络及其货运量数据Ports' criticality in international trade ...
Markov Chains -- Models, Algorithms and Applications
资源是OperationsResearch上很经典的一篇论文,希望对大家有所帮助