首页 > ACM题库 > HDU-杭电 > hdu 3750 Guess Game-数学[解题报告]C++
2015
02-22

hdu 3750 Guess Game-数学[解题报告]C++

Guess Game

问题描述 :

Bob plays the “guess the number right” with Alice recently,the game’s rule is that Alice give Bob a upper limit number N ,then he write any of a number on paper which Bob can’t know what it is and the number must be between 1 and N.Bob has many chances to guess the number and every time when Bob guesses Alice will tell him if his is bigger than the correct number or small than the correct number until he is right.
Now the Bob wanted to use binary search method to guess the right number, because he knows this method is quite fast to find the right number.

输入:

We test the problem in many cases.Each case begin with one integers N( 1<= N <= 100000 ).

输出:

We test the problem in many cases.Each case begin with one integers N( 1<= N <= 100000 ).

样例输入:

2
3

样例输出:

1.50
1.67


菜鸟杯上的一道题

我当时直接按照期望的定义来做的 递归的代码
比赛的时候一直错
很无语 而且浪费了很多时间

现在终于法相当时错的原因了 有点想砍人的冲动……

不过因为这个我学到了一个技巧。

首先说明:
在做要求保留精度的题时 原则是能先整数运算尽量整数运算 最后再四舍五入保留小数。

下面是技巧
比如这题

经过我对此题深入的一番研究
发现:
当输入数据时40时
正确答案是4.57500000 保留2位小数是4.58
我的答案是4.57499999 保留2位小数是4.57

你说能不让人想砍人吗?

这题我是这样AC的
4.5749999先乘以100000–>457499.99再+0.5–>457500.49取整–>457500再除以100000–>4.57500保留2位小数输出–>4.58

这个技巧我觉得还是重要
以后遇到怀疑自己答案精度问题的题时(特别是中途四舍五入了很多次而答案又很像的题) 可以考虑这个技巧
先乘–>四舍五入–>再除回来–>四舍五入输出
当然具体乘多少看题目了
我这次乘的100000 也就是先多保留了5位小数 我试过*10但还是错

总之就是+一个很小的数

我的代码(递归中损失了不少精度 不过排名居然还更高):

#include<stdio.h>  
#define eps 1e-6  
double sum;  
void expect(int now,int n,double s)  
{  
    int d=n/2;  
    if(n==0) return;  
    sum+=s*now/n;  
    s=s*(1-1.0/n);  
    if(n%2)  
        expect(now+1,d,s);  
    else  
    {  
        expect(now+1,d,s*d/(n-1));  
        expect(now+1,d-1,s*(d-1)/(n-1));  
    }  
}  
int main()  
{  
    int n,s;  

    while(~scanf("%d",&n))  
    {  
        sum=0.0;  
        expect(1,n,1.0);  
        printf("%.2lf\n",sum+eps);  
    }  
    return 0;  
}

  1. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept

  2. int L[m+1][n+1];这样定义出错,这个在gcc上可以编译通过 在VS上不行 应该改为new 或者vector

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。