算法篇————入门级算法

        

2016-09-14

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

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

  1. 最大公约数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为止。

  2. 最小公倍数的实现原理

    lcm=a*b/gcd (公式)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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]);
}