← Notedeck
All engines
·
离散数学
en
zh-CN
zh-TW
ja
ko
fr
de
es
pt-BR
tr
it
ar
离散数学
12
engines
埃拉托斯特尼筛法 · 素数筛
Sieve of Eratosthenes
标记合数 · 素数高亮 · π(N) 素数计数
Cross out multiples of each prime; whatever survives is prime
质因数分解 · 因数树
Prime factorization
试除 · n=p^a·q^b · 因子树 · 约数个数 τ
Trial division peels off primes; the factor tree splits n down to primes
欧几里得算法 · 最大公约数
Euclidean algorithm · GCD
辗转相除余数链 · 扩展欧几里得 Bézout
gcd is the last nonzero remainder; extended gives Bézout's a·x + b·y = gcd
Collatz conjecture (3n+1)
Collatz conjecture (3n+1)
偶÷2 奇×3+1 · 轨迹图 · 停止时间 · 峰值
Triple-plus-one on odds, halve on evens, iterate to 1
Continued fractions & convergents
Continued fractions & convergents
[a0;a1,a2…] 展开 · 渐近分数逼近
Expand p/q by the Euclidean algorithm, then build the best rational approximations
卡塔兰数
Catalan numbers
Cₙ=C(2n,n)/(n+1) · 括号/二叉树/格路计数
Exact Cₙ by BigInt · convolution recurrence · lattice-path meaning
图着色 · 贪心着色与色数
Graph coloring · greedy & chromatic number
贪心着色 · 色数 χ · 相邻不同色
Color vertices so no edge is monochromatic; greedy vs. the true χ
欧拉通路与回路
Eulerian path & circuit
度数奇偶判定 · 回路/路径/无 · Hierholzer 追踪
Degree test for existence · Hierholzer trace of the trail
帕斯卡三角(杨辉三角)
Pascal's triangle
C(n,k) 递推 · 行和 2ⁿ · 斐波那契对角线
Binomial coefficients by the additive recurrence · classic patterns highlighted
Nim · combinatorial game theory
Nim · combinatorial game theory
异或 nim-sum · P/N 位置 · 必胜走法
Remove objects from one heap; the nim-sum (XOR of heap sizes) decides who wins
汉诺塔
Tower of Hanoi
最少 2ⁿ−1 步 · 递归解 · 逐步移盘
Move n disks A → C, one at a time · optimal recursion, exactly 2ⁿ − 1 moves
鸽笼原理(抽屉原理)
Pigeonhole principle
n 项入 m 笼 · 至少 ⌈n/m⌉ · 抽屉原理
Put n items into m containers · one box is always forced to ⌈n/m⌉