博弈论习题分析

2024-06-07 07:18
文章标签 分析 习题 博弈论

本文主要是介绍博弈论习题分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

博弈论习题分析

      推荐文章论文:http://wenku.baidu.com/view/b0a2421ca76e58fafab00359.html

 

一:URAL1180.取石子游戏

1180.取石子游戏
两个Nikifor在玩一个好玩的游戏。
这里有一堆总数为n的石子。
两个Nikifor轮流从石子堆中取石子。
每一个人可以取任意2的非负整数次幂个石子。
取到最后一个石子的人获胜。
你现在写一个程序来判断谁会赢。

输入

一个整数n(n<=10^250)

输出

如果第一个取石子的Nikifor赢那么在第一行输出1,
同时在第二行输出,保证他赢的情况下第一次最少要取的石子数。
如果第二个Nikifor赢,则只输出2。

样例输入

8

样例输出

1
2

【分析】:

    当n为三的倍数时,第一个Nikifor一定会输,否则当第一个Nikifor第一次取n mod 3 时一定会赢。

    证明:对于n=0,n=1,n=2时,命题显然成立。现证明当对于任意的i(0<=i<=n-1)有命题成立,命题对于n也成立。

    当n不是三的倍数时,由于n mod 3一定为2的非负整数次幂,所以当第一个Nikifor第一次取n mod 3 个石子时,一定可以时当前状态变为必败状态,因为对于任意的i(0<=i<=n-1)有命题成立。当n是三的倍数时,由于前面的必败状态m一定是3的倍数,而 n-m 一定含有质因数3,即n-m一定不是2的整数次幂,因此当前的n一定不能变为必败状态,因此,当前的状态为必败状态。

【代码】:

#include<stdio.h>
#include<string.h>
int main()
{char s[251];scanf("%s",&s);int i,sum=0;for(i=0;i<strlen(s);i++)sum+=(s[i]-48);//if(sum%3==0)printf("2");elseprintf("1\n%d",sum%3);return 0;
}


 

二:URAL/1023Background

 

时间限制:2s内存限制:16MB

Background

Yekaterinburg获得了2032年夏季奥运会的举办权。由于允许俄罗斯(举办国)对竞赛项目进行一些小的修改。现打算修改“Button”这个新项目的规则。规则很简单,在2个对手前有一堆扣子(k个),2人轮流取走扣子,同一时间,某人能取走1至L个扣子。取走最后一个扣子的为胜者。作为奥运会项目,规则应该比通常玩的要难一点。先走者可以设定数K(就是总共有k个扣子),3<=K<=100 000 000.后走者可以设定数 L,2 ≤ L < K

Problem

现在要紧的问题是,请你写一个程序,帮助后走者做出抉择。换言之,当给出K后,你的程序能给出数L,使到后走者能获胜。例如, 如果只有3个扣子,后走者把L定为2,有必胜把握。事实上,如果先走者取了1个扣子,那么后走者可以取剩下的2个扣子,后走者胜。如果先走者取了2个扣子,那么后走者取1个,也是后走者胜。

Input

输入只包含一个整数K,扣子的总数。

Output

输出L。每次最多能取走的扣子总数,要求保证后走者必胜。假如有多个答案,输出最小的。如果不存在保证能必胜的L,则输出0。

Sample Input

3

Sample Output

2

Sample Input

908640443

Sample Output

908640442
 
【其他数据】:
      10    ans:4    
      100   ans:3    
      17    ans:16    
      26    ans:12    
      200   ans:3    
      14    ans:6 
【代码】:
#include<stdio.h>
int n,ans;
int main()
{scanf("%d",&n);for(int i=3;i*i<=n;i++)if(n%i==0){ans=i-1;break;}if(!ans)if(n&1)	ans=n-1;else	ans=n/2-1;if(ans<2)	ans=n-1;printf("%d\n",ans);return 0;//0.953 108 KB}
#include<stdio.h>
int main()
{int i=3,a;scanf("%d",&a);while(a%i!=0)i++;printf("%d",i-1);return 0;
}
//0.015 108 KB 



【分析】:

        这是一道经典的博弈的题目

        首先我们想如果给定了k,l,那么怎么确定第一个人是不是必胜的,如果是的那他第一次应该取几个?显然是 k mod (l+1)个,如果 k mod (l+1)=0那么显然是必输的。我们这样看,第一个人第一次取走k mod (l+1)后,剩下的button(l+1)的倍数,这时无论第二个人取几个(设他取i个),第一个下一次都可以取(l+1-i)个,使剩下的button也是(l+1)的倍数,这样第一个人一定能拿到最后一个。

      所以如果k mod (l+1)=0

      那么第一个人第一次只能取0个,显然是输的。枚举约数的话,我们从1sqrt(k)枚举就可以了,但是按题意3<=(l+1),我们会忽略掉2这个约数(如果k是偶数),也同时会忽略掉 k div 2这个约数,最后要特殊判断一下。

 

转载注明出处:http://blog.csdn.net/u011400953

 

这篇关于博弈论习题分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1038508

相关文章

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

怎样通过分析GC日志来定位Java进程的内存问题

《怎样通过分析GC日志来定位Java进程的内存问题》:本文主要介绍怎样通过分析GC日志来定位Java进程的内存问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、GC 日志基础配置1. 启用详细 GC 日志2. 不同收集器的日志格式二、关键指标与分析维度1.

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

python中Hash使用场景分析

《python中Hash使用场景分析》Python的hash()函数用于获取对象哈希值,常用于字典和集合,不可变类型可哈希,可变类型不可,常见算法包括除法、乘法、平方取中和随机数哈希,各有优缺点,需根... 目录python中的 Hash除法哈希算法乘法哈希算法平方取中法随机数哈希算法小结在Python中,

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

关于MyISAM和InnoDB对比分析

《关于MyISAM和InnoDB对比分析》:本文主要介绍关于MyISAM和InnoDB对比分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录开篇:从交通规则看存储引擎选择理解存储引擎的基本概念技术原理对比1. 事务支持:ACID的守护者2. 锁机制:并发控制的艺

MyBatis Plus 中 update_time 字段自动填充失效的原因分析及解决方案(最新整理)

《MyBatisPlus中update_time字段自动填充失效的原因分析及解决方案(最新整理)》在使用MyBatisPlus时,通常我们会在数据库表中设置create_time和update... 目录前言一、问题现象二、原因分析三、总结:常见原因与解决方法对照表四、推荐写法前言在使用 MyBATis

Python主动抛出异常的各种用法和场景分析

《Python主动抛出异常的各种用法和场景分析》在Python中,我们不仅可以捕获和处理异常,还可以主动抛出异常,也就是以类的方式自定义错误的类型和提示信息,这在编程中非常有用,下面我将详细解释主动抛... 目录一、为什么要主动抛出异常?二、基本语法:raise关键字基本示例三、raise的多种用法1. 抛

github打不开的问题分析及解决

《github打不开的问题分析及解决》:本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意