20200420 刷题,不可懈怠
1.抛硬币
甲乙双方互相投掷硬币,先得正面者获胜,问先投掷者获胜的概率?
答案:2/3 理由如下: 甲先投,考虑甲乙各投一次的概率,甲获胜的概率为1/2,乙获胜的概率为1/4;剩余1/4进入下一轮。下一轮又重复以上过程,即取极限可得甲获胜的概率为乙的两倍;因而先投者获胜概率为2/3。
2.Nim游戏
题目详见leetcode。
属于博弈问题。
答案:只要该数不能被4整除,我就能赢。 例子给出如果有4块石头,那么我是必输的,理由很明显。那么如果只有m=1、2、3块石头,我一次取完便可获胜,如果有4+m(m=1,2,3)块石头,我只要取走m块,让对方陷入只剩4块石头的必输局面;相反,如果有4*n块石头,我任意取走m(1,2,3)块,对方只要取走4-m块,一直重复先去,最后始终会让我面临只剩4块的必输局,因而在被4整除时,我必输。
3.移动石子直到连续
这里是引用
此处注意
1)输入一定排好序
2)认真审题!左右移动石子可以直接跨过中间石子。
4.飞机座位分配概率
这里是引用
答案: f(1)=1; f(n)=0.5;n>1
分析: 此题和给定纸币面额,纸币找零最少张数类似。
因为第一个人忘带票了,其随机选座,因而分类讨论:
1)如果第一个人正好坐在自己的位置,那么之后所有的人都会坐在自己的位置。
2)如果第一个人正好坐在第n个人的位置,那么第n个人没可能坐在自己的位置。
3)如果第一个人坐在除了自己位置以及第n个人的位置之外的n-2个位置,设为i。如果i=2,那么第二个人将随机选座,如果i不等于2,那么2-i个人将正确入座,直到第i个人面临被占坐局面,随机选座,????
总结:
1)分类讨论、数学归纳
2)递推、动态规划
5.灯泡开关
难度:中等
答案:sqrt(n)
平方数常亮