アルゴリズム編——入門レベルのアルゴリズム


今日から、各種のアルゴリズムを復習して、毎日いずれも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が見つかるまで.
  • 最小公倍数の実現原理lcm=a*b/gcd(式)
  • コード実装
    #include 
    #include 
    #include 
    #include 
    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;i0] = c[i][i] = 1;
            for(int j = 1;j1][j] + c[i-1][j-1];
            }
        }
    }
    void Test1(){
        Com();
        printf("gcd==%d
    "
    ,gcd(12,3)); printf("lcm==%d
    "
    ,lcm(4,3)); printf("fast===%d
    "
    ,Fast(2,3)); printf("Com===%d
    "
    ,c[12][3]); }