【博弈论】因数-数字游戏 | 石子游戏

墨蓝 2024-03-25 08:56 85阅读 0赞

## 因数-数字游戏 ##

### 题目 ###

小Q的柠檬汁做完了，掏出了自己的数字卡牌，想要和别人做数字游戏，可是她又不想要输掉游戏。她制定好规则，每次每个人只能把这个牌换成它的因子的某个牌，但是这个因子不能是1或者整数本身。现在给出整数n，两个人开始做游戏，谁无法再给出因子牌则该人胜利。如果该整数无因子牌直接视为先手胜利。请判断先手在最优策略状态下能否必胜，如果能则输出1，不能则输出2。

### 示例 ###

### 分析 ###

首先要分析一下用例，是开始游戏后，没有牌出的人获胜。以6为例，我们出用2替换，那么后手没有可出的了，后手赢了。

对于30，先手出6，后手无论出2或者3，这样先手就没有出的了，先手就赢了，输出1.

是这样一个规则。

采用的策略是博弈论，怎么样才能赢？我们给对手留下一个两个质数的积，这样对手只能选择一个质数，留下另一个质数，等再轮到我的时候，我就没得出了，就赢了。

所以问题就转化为了，这个初始的数有多少个质数因数（质因数）。

*  如果这个数就是质数因数，先手没得替换，先手赢。
 *  如果这个数有2个质数因数，先手替换掉一个，后手没得替换，后手赢。
 *  如果这个数有3个以上质数因数，先手用其中2个质数的乘积去替换这个原始的数，后手只能用其中的1个质数去替换这个乘积，因此先手赢。

因此问题就转化成了找1个数，到底有多少个质数的问题了。

### 思路 ###

思路还是蛮复杂的，一个数的因数很好找，从2开始枚举就可以了，但是1个数的质因数并不是很好去想，这里我也借鉴了一些大佬的思路。总结在这里，其中关键代码已经注释，可以阅读代码去理解。  
其中需要补充一点知识，就是任何一个数都可以拆分成**一系列质数的乘积**。

证明如下1：

> 首先，2是素数。其次，设我们已经证明2到k的所有整数都能表示为素数的乘积。
> 
> 考虑k+1：
> 
> ① 如果k+1是素数，那么得证
> 
> ② 如果k+1是合数，由合数的定义，存在大于1的整数m、n，使得nm=k+1。
> 
> 显然，n和m都小于k+1，则n和m能分解为素数的乘积，所以k+1也能。

因此，我们通过以下程序求解到的都是质因数（否则，如果除尽的不是质数因数，那么它可以分解成比他小的质数的乘积，前面就while到头了，所以不存在不是质因数的情况的），如果找到3个及以上质数因数（可以是一样的质因数，比如8，对应着  2 × 2 × 2 2\\times2\\times2 2×2×2，3个一样的质因数）我可以取其中的 2 个（ 2 × 2 = 4 2\\times2=4 2×2=4），甩给对手，对手只能回2，我没得替换，就赢了。

#include <iostream>
    #include <string>
    #include <sstream>
    #include <vector>
    #include <math.h>
    using namespace std;
    int solution(long int n) {
        
    	int result;
    	// TODO:
    	result = 0;
    	int flag = 0;
    	long int sq = (long int)sqrt(n);
    	for (long int i = 2; i <= sq + 1; i++) {
        
    		while (n % i == 0) {
        		// 从小到大寻找质因数，统计质因数个数
    			n /= i;
    			flag++;
    		}
    		if (flag == 2 && n == 1) {
        	// 只有2个质因数
    			result = 2;
    			return result;
    		}
    		if (flag >= 3) {
        			// 如果有超过3个质因数，先手可以通过乘积转化为只剩2个，因为不能选 1 和 本身 后手只能选择其中一个，先手再来一个，后手输
    			result = 1;
    			return result;
    		}
    	}
    	if (flag == 1 || result == 0) {
        
    		result = 1;
    	}
    	return result;
    }
    
    int main() {
        
    	long int n;
    	std::cin >> n;
    	int result = solution(n);
    	std::cout << result << std::endl;
    	return 0;
    }

在此有一点感想，博弈论题目有点难，后面再多积累补充一下吧！

## 石子游戏 ##

### 题目 ###

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles\[i\] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

### 示例数据 ###

示例 1：

> 输入：piles = \[5,3,4,5\]  
> 输出：true  
> 解释：  
> Alice 先开始，只能拿前 5 颗或后 5 颗石子 。  
> 假设他取了前 5 颗，这一行就变成了 \[3,4,5\] 。  
> 如果 Bob 拿走前 3 颗，那么剩下的是 \[4,5\]，Alice 拿走后 5 颗赢得 10 分。  
> 如果 Bob 拿走后 5 颗，那么剩下的是 \[3,4\]，Alice 拿走后 4 颗赢得 9 分。  
> 这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

示例 2：

> 输入：piles = \[3,7,2,3\]  
> 输出：true

> 提示：  
> 2 <= piles.length <= 500  
> piles.length 是 偶数  
> 1 <= piles\[i\] <= 500  
> sum(piles\[i\]) 是 奇数

class Solution {
        
    public:
        bool stoneGame(vector<int>& piles) {
        
            return true;
        }
    };

--------------------

1.  https://www.zhihu.com/question/480441244/answer/2066572898 ↩︎