算法——威佐夫博弈
2021/8/17 22:06:03
本文主要是介绍算法——威佐夫博弈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
------------------------------------------小游戏--------------------------------------- 描述 富婆和大力去西天取经的路上遇见了两堆石子,数量任意,可以不同。他们觉得旅途太无聊于是决定开始玩一场激情 的小游戏,游戏开始后由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意 多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的 数目,(因为富婆极其霸道)所以每次都是富婆先取,假设双方都采取最好的策略,问最后富婆是胜者还是败者。 输入 输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都 不大于1,000,000,000。 输出 输出对应也有若干行,每行为win或者lose,如果最后富婆是胜者,则为win,反之则为lose。 输入样例 1 2 1 输出样例 1 lose 输入样例 2 8 4 输出样例 2 win 输入样例 3 4 7 输出样例 3 lose
#include<iostream> #include<cmath> #include<algorithm> using namespace std; const double d=(sqrt(5.0)+1.0)/2.0; int main() { long long int a,b,c; cin>>a>>b; if(a<b) swap(a,b); c=a-b; if(b==int(d*(double)c)) cout<<"lose"<<endl; else cout<<"win"<<endl; }
(1)状态是单调递增的
(2)状态的石子数量的差是个等差数列(公差为1),这个序列为:0,1,2,3,4,5,6,7,8,9,10,11…
(3)状态的第一个数字是之前没有出现过的第一个数字。比如说第二个状态的第一个数字1,就是前几个状态没有出现的数字。
(4)每个状态的第一个数字竟然是这个状态的两堆石子数量的差*根号五加一除以二。
总而言之,只要大的那个数等于差值乘以根号五加一除以二向下取整,先手就一定输
这篇关于算法——威佐夫博弈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现