首页 > 代码库 > 一道搜索好题
一道搜索好题
给定一个数S，找任意个正整数a1,a2,…,an，使得它们的和恰好等于S，且它们的倒数之和与1的差不超过10^-6。
输出任意一种方案或者输出无解。
S<=10^7
自由搜索
自己加限制：搜索递增
强效剪枝：
if(sum+1.0/S>eps+1) return;
八位数秒处#include<cmath>#include<cstdio>using namespace std;const double eps=1e-6;int ans[1001];bool ok;void dfs(int S,double sum,int last,int now){ if(ok) return; if(!S) { if(abs(1-sum)<eps) { for(int i=1;i<now;i++) printf("%d ",ans[i]); ok=true; } return; } if(sum+1.0/S>eps+1) return; for(int i=last+1;i<=S;i++) { ans[now]=i; dfs(S-i,sum+1.0/i,i,now+1); if(ok) return; }}int main(){ int S; scanf("%d",&S); dfs(S,0,1,1);}
一道搜索好题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。