【poj2348】Euclid's Game

Categories: 数据结构和算法
Tags:
Comments: No Comments
Published on: 2011 年 04 月 11 日
  给两堆石子(题目中是数,配合一下上文这里说石子),两人依次取石子,规则是:
每次从石子数较多的那堆取(两堆石子数目相等时任选一堆),取的数目只能为石子少的
那一堆的正整数倍。最后取完一堆石子者胜。问给定情况下先手胜负情况。
    确实很像欧几里得,一看就想到递归了,似乎递归也不会太难,但是多列几项就会发
现一个熟悉的身影:斐波拉契数列。最后的结论是如果两个数相等,或者两数之比大于斐
波拉契数列相邻两项之比的极限((sqrt(5)+1)/2),则先手胜,否则后手胜。
当然这道题也能用欧几里得来做,不过相比这个就麻烦不少

#include<stdio.h>  
#include <math.h>  
int main()  
{  
    int a,b;  
    double c=(1.0+sqrt(5.0))/2.0;  
    while(scanf("%d%d",&a,&b)!=EOF && (a ||b))  
    {  
        if(a==b) {printf("Stan wins\n");continue;}  
        if(a<b) {a=a^b;b=a^b;a=a^b;}  
        if((double)a/b>c) printf("Stan wins\n");  
        else printf("Ollie wins\n");  
    }  
} 

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期日, 2017 年 12 月 17 日