本文主要是介绍HDU 1527 取石子游戏 威佐夫博弈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目来源:HDU 1527 取石子游戏
题意:中文
思路:威佐夫博弈 必败态为 (a,b ) ai + i = bi ai = i*(1+sqrt(5.0)+1)/2 这题就求出i然后带人i和i+1判断是否成立
以下转自网上某总结
有公式ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,…,n 方括号表示取整函数)
其中出现了黄金分割数(1+√5)/2 = 1。618…,因此,由ak,bk组成的矩形近似为黄金矩形
由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2]
若a=[j(1+√5)/2],那么a = aj,bj = aj + j
若不等于,那么a = aj+1,bj+1 = aj+1+ j + 1
若都不是,那么就不是奇异势
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{int a, b;while(scanf("%d %d", &a, &b) != EOF){if(a > b)swap(a, b);int k = (sqrt(5.0)-1)/2*(double)a;double t = (double)(sqrt(5.0)+1)/2;if((int)(t*k) == a && (int)(a+k) == b)puts("0");else if((int)(t*(k+1)) == a && (int)(a+1+k) == b)puts("0");elseputs("1");}return 0;
}
这篇关于HDU 1527 取石子游戏 威佐夫博弈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!