首页 > 其他 > 详细

搜索体

时间:2017-07-23 18:59:09      阅读:259      评论:0      收藏:0      [点我收藏+]

 

 

给定一个数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;
}

 

搜索体

原文:http://www.cnblogs.com/CLGYPYJ/p/7225515.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!