当前位置:编程学习 > C/C++ >>

HDU 1517 A Multiplication Game

 
题意:2 个人玩游戏,给定一个数n,从 1 开始,轮流对数进行累乘一个数(2~9中取),
 
直到第一次等于或超过n为赢.

思路:1)找规律

如果n是 2 ~ 9 ,Stan 必胜。

如果输入是 10~18 ,不管第一次Stan 乘的是什么,Stan肯定在 2 ~ 9 之间,

  无论stan乘以什么,Ollie乘以大于1的数都都能超过 10 ~ 18 中的任何一个数。Ollie 必胜。

如果输入是 19 ~ 162,那么这个范围是 Stan 的必胜态。

如果输入是 163 ~ 324 ,这是又是Ollie的必胜态。

............

必胜态是有规律可循的。

如果"我方"首先给出了一个在n不断除18后的得到不足18的

数m,"我方"就可以取得胜利,然而双方都很聪明,所以这样胜负就决定于n了,
 
如果n不断除18后的得到不足18的数m,
 
若1<m<=9则先手胜利,
 
若9<m<=18则后手胜利.
 
[cpp] 
#include<stdio.h> 
int main() 

  double n; 
  while(scanf("%lf",&n)!=EOF) 
  { 
     while(n>18) n/=18; 
     printf(n<=9?"Stan wins.\n":"Ollie wins.\n"); 
  } 
  return 0; 


  2)博弈(给出牛人的解题思路)

先引入必胜点和必败点两个概念:

   必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。

   必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。

算法实现:

   步骤1:将所有终结位置标记为必败点(P点);(终结位置指的是不能将游戏进行下去的位置)

   步骤2:将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)

   步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;

   步骤4:如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。

解题思路:

   由于每次都是从p=1开始的,所以只要判断每个游戏中1为必败点还是必胜点即可。

 (以下各式 / 均为取上整)依照上面所提到的算法,将终结位置,即[n,无穷]标记为必败点;

   然后将所有一步能到达此必败段的点标记为必胜点,即[n/9,n-1]为必胜点;

   然后将只能到达必胜点的点标记为必败点,即[n/9/2,n/9-1]为必败点;

   重复上面2个步骤,直至可以确定1是必胜点还是必败点。

[cpp] 
#include <math.h> 
#include <stdio.h> 
int main() 

    unsigned int n,x; 
    while(~scanf("%u",&n)) 
    { 
        for(x=0;n>1;x++) 
        { 
            if(x&1) 
                n = ceil(n*1.0/2); 
            else 
                n = ceil(n*1.0/9); 
        } 
        puts(x&1?"Stan wins.":"Ollie wins."); 
    } 
    return 0; 

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,