数据结构班 第10课 博弈论 概率 数论


第10课 博弈论 概率 数论

博弈论

定义

  • 游戏论(Game Theory)
  • 定义:双人(多人)做出多轮决策,每一次决策将影响之后的决策,规则和目标明确。
  • 一般假设所有人都足够聪明
  • 求先手(后手)必胜策略
  • 公平 vs 非公平
  • 平衡态:与终态有一样的性质,无论对手做什么,己方都可以做出相应的决策,将终态留给对手。


博弈论:取石子游戏1
  • 有一个堆石子,\(N\) 个。两个人轮流取 \(1\) ~ \(K\) 个石子,取到最后一个者赢,请问先手是否有必胜策略。
  • 关键: 每一步保证自己能取,终态(平衡态)留给对手。
  • 先手必胜策略:开始取 \(N \mod (K + 1)\) 个,之后对手取 \(X\) 个,己方取 \(K + 1 - X\) 个,保持余数为 \(0\)(平衡态)。
  • 如果是取到最后一个输呢?


需要每一轮消耗 \(P = K+1\) 个。

当 \(N \mod (K + 1) = 0\) 时,先手必败。

异或操作:XOR,二进制加法。

概率

当一个实验,次数足够多的时候,会收敛到一个常数,叫做 概率

数论

  • 讨论范围一般为整数


将 \(N\) 质因素分解

  • (1)从小到大查找 \(N\) 在[2,Sqrt(\(N\))]上的因数。
  • (2)查找到的第一个因数为N的最小质因数P。
  • (3)N = N / P,跳回(1)。
  • 时间复杂度:O(Sqrt(n))。
  • 空间复杂度:O(1)。


class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num == 1) return false;
        int sum = 0;
        for (int i = 2; i < sqrt(num); i++)
            if (num \mod  i == 0) {
                sum += i;
                if (i != num / i) {
                    sum += num / i;
                }
            }
        sum++;
        return sum == num;
    }
};

  • 整除,余数,最大公约数(因数),最小公倍数
  • 辗转相除法
  • 目标:求最大公约数
  • 起源:辗转相减法
  • \(GCD(a,b)=GCD(a,b–a), b>a\)
  • 证:设 \(t\) 为 \(a, b\) 的任意一个公约数,则有 \(tp = a, tq = b\)。
  • b – a = t(q – p), 公约数仍在


伪代码(递归写法)

int gcd(int a, int b)
    if (a == 0) return b;
    return gcd(b \mod  a, a); //可以看做多次减法

  • 时间复杂度: \(O(\log n)\)

  • 最小公倍数: \(LCM(a, b) = a * b / GCD(a, b)\)

  • 筛法


求[2, N]范围内所有质数

  • (1) 将[2, \(N\)]所有整数加入集合 \(A\)
  • (2) 取出最小的整数 \(P\),删去 \(A\) 中 \(P\) 的倍数
  • (3) P一定是 \(A\) 内最小质数,跳回(2)
  • 时间复杂度: \(O(NlnlnN)\)
  • 空间复杂度: \(O(N)\)


质因数分解。

$${N = \prod_i a_i ^{p_i}}$$
$${Ans=\prod_i (p_i+1)}$$
  • 求约数个数


Mod 运算的一些性质

  • \((a+b) \mod m=(a \mod m+b \mod m) \mod m\)
  • \((a \times b) \mod m=(a \mod m) \times (b \mod m) \mod m\)
  • 交换律:\((a+b) \mod m=(b+a) \mod m\) 乘法
  • 结合律:\((a+b+c) \mod m=(a+(b+c)) \mod m\) 乘法
  • 分配率:\((a+b) \times c \mod m=(ac+bc) \mod m\)
已邀请:

要回复问题请先登录注册

返回顶部