计算机程序设计艺术的读书笔记
文章目录
卷一：数学知识准备篇
数学归纳法
- 证明P(1)
- 假设P(k)正确 --> 证明P(k+1)
- 证毕，P(n)正确
数学归纳法与程序设计
-
循环累加求和
-
递归求阶乘
-
HZOJ-236递归实现组合型枚举oj.haizeix.com
int main(){ int sum = 0; for(int i = 1; i <= 100; i++){ sum += i; } cout << sum << endl; return 0;}int f(int n){ if(n == 1) return 1; return n * f(n - 1);}int main(){ cout << f(5) << endl; return 0;}void output(int n, int m, int p, vector &buff){//从n个数字中选m个数字，p:当前可以选择的最小数字//buff：当前已经选的数字 if(buff.size() == m){ for(int i = 0; i < m; i++){ if(i != 0) cout << " "; cout << buff[i]; } cout << endl; return; } //buff数量不足m的情况 for(int i = p; i > n >> m; vector buff; output(n, m, 1, buff); return 0;}了解数学归纳法平时更多的是为了保证程序设计的正确性，即使是复杂程序设计也一样。
初等数论基础
素数筛算法
//define MAX_N 10000int prime[MAX_N + 5] = {0};//被标记的i为1，没被标记为0void init_prime(){ for(int i = 2; i * i <= MAX_N; i++){ if(prime[i]) continue;//i被标记了就继续 //用j把i的倍数都标记 for(int j = i * i; j <= MAX_N; j += i) prime[j] = 1; } //prime[0]:记录的是表中素数的个数 prime[0]前面存的是素数表，后面存的是标记信息 for(int i = 2; i <= MAX_N; i++){ //把所有素数整理到prime前半段 if(prime[i] == 0) prime[++prime[0]] = i; } return;}int main(){ init_prime(); cout << "total prime : " << prime[0] <> x){ printf("prime[%d] = %d\n", x, prime[x]); } return 0;}余数
- x + d = y + d (mod n)
- x - d = y - d (mod n)
- x * d = y * d (mod n)
a % b可以写成a - kb- 以及注意逆元的概念 y * y` = 1
欧几里得算法
整数a，b的最大公约数一般表示为gcd(a, b)，终极奥义：gcd(a, b) = gcd(b, a%b)
证明Ⅰ: b和a%b的最大公约数，也是a和b的公约数
证明Ⅱ: b和a%b的最大公约数也是a和b的最大公约数
int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a % b);}int main(){ int a, b; while(cin >> a >> b){ printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b)); } return 0;}扩展欧几里得
- ax 三 1 (mod b)
- ax % b = 1
- ax - kb = 1
- ax + by = 1
int ex_gcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1, y = 0; return a; } int nx, ny;//代表下一层的整数解 int r = ex_gcd(b, a % b, nx, ny); x = ny; y = nx - a / b * ny; return r;}int main(){ int a, b; while(cin >> a >> b){ c = ex_gcd(a, b, x, y); printf("%d * %d + %d * %d = %d\n", a, x, b, y, c); } return 0;}贝祖等式：ax + by = gcd(a, b) = c
int ex_gcd(int a, int b, int &x, int &y){ if(b == 0){ x = 1, y = 0; return a; } int nx, ny;//代表下一层的整数解 int r = ex_gcd(b, a % b, nx, ny); x = ny; y = nx - a / b * ny; return r;}//修改一下变成求逆元的方法int inv(int a, int b){ int x, int y; ex_gcd(a, b, x, y); x %= b; x += b; x %= b; return x;//通过上面三步，x肯定变成了正数 }int main(){ int a, b; while(cin >> a >> b){ printf("%d * %d %% %d = 1\n", a, inv(a, b), b); } return 0;}斐波那契数列
- F(0) = 0, F(1) = 1
- F(n) = F(n-1) + F(n-2)
- 0, 1, 1, 2, 3, 5, 8, 13, 21
- F(n+m) = F(m)F(n+1) + F(m-1)F(n)
//蓝色斜杠是c/c++特殊语法#define TEST(func){\long long b, e;\b = clock();\func;\e = clock();\printf("Run %lld ms\n", (e - b) * 1000 / CLOCKS_PRE_SEC);\}unordered_map f_result; //哈希表long long f(long long n){ if(n 0 非0=>1 if(f_result.find(n) == f_result.end()){ //如果没计算过就重新计算 long long a = n / 2, b = n - a; long long val1 = f(b), val2 = f(a + 1), val3 = f(b - 1),val4 = f(a); f_result[n] = (val1 * val2 + val3 * val4) % 9973; } return f_result[n];}long long normal_f(long long n){ long long a = 0, b = 1; for(int i = 0; i > n){ TEST(printf("f[%lld] = %lld\n", n, normal_f(n))); TEST(printf("f[%lld] = %lld\n", n, f(n))); } return 0;}快速幂算法
int quick_power(int a, int b){ int ans = 1, temp = a; while(b){ if(b % 2) ans *= temp;//b的末尾是奇数时 temp *= temp; b /= 2;//去掉二进制末尾那个值 } return ans;}int main(){ int a, b; while(cin >> a >> b){ printf("%d^%d = %d\n", a, b, quick_power(a, b)); } return 0;}快速乘算法
//适用于 a*b 超界的情况int quick_mul(int a, int b){ int ans = 0, temp = a; while(b){//当b!=0时 if(b % 2) ans += temp;//如果b末尾是1 累加 temp += temp; b /= 2; } return ans;}int main(){ int a, b; while(cin >> a >> b){ printf("%d * %d = %d\n", a, b, quick_mul(a, b)); } return 0;}矩阵快速幂
//解决形如 F(n) = aF(n - 1) + bF(n - 2)class Matrix {//初始化n行m列矩阵public: Matrix(int n, int m, int e = 0) : n(n), m(m) { for(int i = 0; i < n; i++) c.push_back(vector(m, 0)); for(int i = 0; i < n; i++) c[i][i] = 1; } vector &operator[](int ind){ return c[ind];} Matrix &operator%(int x){//矩阵取余 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ c[i][j] %= x; } } return *this; } Matrix operator*(const Matrix &obj){//矩阵乘法 Matrix ret(n, obj.m);//结果矩阵 for(int i = 0; i < n; i++){ for(int j = 0; j < obj.m; j++){ ret[i][j] = 0; for(int k = 0; k < m; k++){ ret[i][j] += c[i][k] * obj.c[k][j]; } } } return ret; }private: int n, m; vector<vector> c;};Matrix quick_power(Matrix a, int b){ Matrix ans(2, 2, 1), temp = a;//两行两列的单位矩阵 while(b){ if(b % 2) ans = ans * temp % 9973; temp = temp * temp % 9973; b /= 2; } return ans;}int main(){ Matrix a(2, 2); //初始化系数矩阵 a[0][0] = 1, a[0][1] = 1, a[1][0] = 1, a[1][1] = 0;int n; while(cin >> n){ Matrix b = quick_power(a, n);//b矩阵等于a矩阵的n次方 printf("f[%d] = %lld\n", n, b[1][0]); } return 0;}练习题：HZOJ.317幸运八
题目：众所周知，八是一个吉利数字。现给定一个数字N，求最短能被N整除的只由8组成的数字的长度
相当于：8(10^x - 1) / 9 - k * n = 0 的最小的x值 (10^x - 1) - k (9n) / 8 = 0 k中和9n都包含一部分8
9n` = 9n / gd(n, 8)
(10^x - 1) - k(9n`) = 0
10^x = 1 (mod 9n`)
gd(10, 9n`) = 1
long long gcd(long long a, long long b){ if(b == 0) return a; return gcd(b, a % b);}long long phi(long long n){ long long i = 2, x = n; while(i * i >= 1; } return ans;}long long quick_mod(long long a, long long b, long long c){//快速幂 long long ans = 1, temp = a; while(b){ //if(b & 1) ans = ans * temp % c;//这里可能超过范围 需改写 if(b & 1) ans = quick_mul(ans, temp, c);//快速乘 加法 temp = quick_mul(temp, temp, c); b >>= 1; } return ans;}set getSet(long long x){//unordered_set无序 set是有序表 long long i = 2; set h, temp;//两个哈希表 h.insert(1);//初始化表 while(i * i <= x){ while(x % i == 0){ for(auto y : h) temp.insert(y * i);//遍历哈希表中的所有数字 乘以i 并且重新插入到哈希表中 for(auto y : temp) h.insert(y);//将temp表的数据插入到temp x /= i; } i += 1; } if(x != 1){//说明x自己是素数 temp.clear(); for(auto y : h){ //cout << "insert : " << y * x <> n; n *= 9; n /= gcd(n, 8)//n和8的最大公约数 if(gcd(n, 10) != 1){//没有答案的时候 printf("0\n");//输出0 return 0; } x = phi(n);//欧拉函数值 auto x_set = getSet(x);//获得x所有的因子 //cout << x < 遍历 if(x % i) continue; if(quick_mod(10, i, n) != 1) continue; cout << i << endl; //printf("%lld\n", i); break; } return 0;}
