算法篇——入门级算法

从今天开始，复习各种算法，每天都会去理解一种算法，争取贴出自己对每种算法的理解，今天介绍的是最基础的入门算法，最大公约数，最小公倍数，快速幂（后面会重点介绍），简单并查集（后面会重点介绍），还有排列组合（后面会重点介绍）的算法。

最大公约数和最小公倍数的算法原理

最大公约数gcd的实现原理：

欧几里德定理 若 a=b×r+q 则gcd(a, b) = gcd(b, q).

欧几里德定理的证明 a = b × r + q 设c = gcd(a, b), a = m×c, b= n×c q = a - b× r = (m - n × r)×c 下面证明 m-n×r与n互质： 假设不互质，则存在k使得 m-n×r = x×k, n = y×k. 则: a = m×c = (n×r + x×k)×c = (y×r + x×k)×c×k b = n×c = y×c×k 与 c=gcd(a, b) 矛盾。 辗转相除法的算法实现 a = b × r_1 + q_1 if q_1 = 0 then return b else b = q_1 × r_2 + q_2 if q_2 = 0 then return q_1 else …… 直到找到GCD为止。

最小公倍数的实现原理

lcm=a*b/gcd (公式)

代码实现

#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; #define N 1009 #define inf 0x0f0f0f0f //最大公约数 int gcd(int a,int b){ if(b==0) return a; else return gcd(b,a%b); } //最小公倍数 int lcm(int a,int b){ return a/gcd(a,b)*b; } //快速幂 int Fast(int x,int n){ int tem = x,ans = 1; while(n){ if(n%2==1) ans*=tem; tem *= tem; n >>= 1; } return ans; } //简单并查集 int f[N]; int ans; void init(int n){ for(int i = 1;i<=n;i++) f[i] = i; ans = 0; } int find(int x){ if(f[x]==x) return x; else return f[x] = find(f[x]); } void Union(int a,int b){ int f1 = find(a); int f2 = find(b); if(f1!=f2){ f[f1] = f2; ans++; } } //计算排列组合 int c[N][N]; void Com(){ memset(c,0,sizeof(c)); for(int i = 1;i<N;i++){ c[i][0] = c[i][i] = 1; for(int j = 1;j<i;j++){ c[i][j] = c[i-1][j] + c[i-1][j-1]; } } } void Test1(){ Com(); printf("gcd==%d\n",gcd(12,3)); printf("lcm==%d\n",lcm(4,3)); printf("fast===%d\n",Fast(2,3)); printf("Com===%d\n",c[12][3]); }