首页 > 代码库 > 搜索体
搜索体
给定一个数S,找任意个正整数a1,a2,…,an,使得它们的和恰好等于S,且它们的倒数之和与1的差不超过10^-6。 输出任意一种方案或者输出无解。 S<=65536
#include<iostream> #include<cstdio > #include<queue> #include<algorithm> #include<cstring> #include<math.h> using namespace std; int s; int ans[70000]; double sep=0.000001; void wout(int x) { for(int i=1;i<=x;i++) printf("%d ",ans[i]); return ; } void dfs(int tot,double all,int x,int last) { ans[x]=last; //剪枝 if(tot==s&&fabs(all-1)<=sep) {wout(x);exit(0);} if(all+1.0/last*(((s-tot)/last)+1)<1-sep) return; if(all+1.0/(s-tot)>1+sep) return ; for(int i=last;i<=s-tot;i++) dfs(tot+i,all+(double)(1.0/i),x+1,i); } int main() { cin>>s; dfs(0,0.0,0,2); return 0; }
搜索体
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。