• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            MyMSDN

            MyMSDN記錄開發新知道

            最大公約數問題

            image

            image

            image

            image

            image 

            image

            image

            image

            image

            以上內容摘自《編程之美》P150-154。

            為了方便使用,下面是可拷貝的代碼:

            Math.h

            #pragma once
            
            class Math
            {
            public:
                Math(void);
                ~Math(void);
            
            public :
                //編程之美P150-154
            
                //求最大公約數,歐幾里德——輾轉相除法
                static int Gcd1(int x, int y);
            
                //求最大公約數,歐幾里德——輾轉相除法(變相將除法變成了減法)
                static int Gcd2(int x, int y);
            
                static int Gcd3(int x, int y);
            
                inline static bool IsEven(int x);
            
                inline static int Absolute(int x);
            };
            

            Math.cpp

            #include "Math.h"
            
            Math::Math(void)
            {
            }
            
            Math::~Math(void)
            {
            }
            
            int Math::Gcd1(int x, int y)
            {
                //y, x%y順序不能錯;
                return y ? Gcd1(y, x % y) : x;
            }
            
            int Math::Gcd2(int x, int y)
            {
                //與Gcd1相同的方式,但由于x%y計算速度較x-y要慢,但效果相同,所以換用x - y
                // 但用減法和除法不同的是,比如和,%20=10,-20=70,也就是-4×=10
                // 也就是說迭代次數較Gcd1而言通常是增加了。
                return y ? Gcd1(y, x - y) : x;
            }
            
            int Math::Gcd3(int x, int y)
            {
                if(x < y)
                    return Gcd3(y, x);
                if(y == 0)
                    return x;
                else
                {
                    if(IsEven(x))
                    {
                        if(IsEven(y))
                            return (Gcd3(x >> 1, y >> 1) << 1);
                        else
                            return Gcd3(x >> 1, y);
                    }
                    else
                    {
                        if(IsEven(y))
                            return Gcd3(x, y >> 1);
                        else
                            return Gcd3(y, x - y);
                    }
                }
            }
            
            bool Math::IsEven(int x)
            {
                return !(bool)x & 0x0001;
            }
            
            int Math::Absolute(int x)
            {
                return x < 0 ? -x : x;
            }

            Main.cpp

            #include <stdafx.h>
            #include <iostream>
            #include "Math.h"
            
            using namespace std;
            int _tmain(const int & arg)
            {
                cout<<"Math::Gcd1(42,30) = "<<Math::Gcd1(42,30)<<endl;
                cout<<"Math::Gcd1(30,42) = "<<Math::Gcd1(30,42)<<endl;
                cout<<"Math::Gcd1(50,50) = "<<Math::Gcd1(50,50)<<endl;
                cout<<"Math::Gcd1(0,0) = "<<Math::Gcd1(0,0)<<endl;
                cout<<"Math::Gcd1(-42,-30) = "<<Math::Gcd1(-42,-30)<<endl;
                cout<<"Math::Gcd1(-42,30) = "<<Math::Gcd1(-42,30)<<endl;
            
                cout<<"------------------------------"<<endl;
            
                cout<<"Math::Gcd2(42,30) = "<<Math::Gcd2(42,30)<<endl;
                cout<<"Math::Gcd2(30,42) = "<<Math::Gcd2(30,42)<<endl;
                cout<<"Math::Gcd2(50,50) = "<<Math::Gcd2(50,50)<<endl;
                cout<<"Math::Gcd2(0,0) = "<<Math::Gcd2(0,0)<<endl;
                cout<<"Math::Gcd2(-42,-30) = "<<Math::Gcd2(-42,-30)<<endl;
                cout<<"Math::Gcd2(-42,30) = "<<Math::Gcd2(-42,30)<<endl;
            
                cout<<"------------------------------"<<endl;
            
                cout<<"Math::Gcd3(42,30) = "<<Math::Gcd3(42,30)<<endl;
                cout<<"Math::Gcd3(30,42) = "<<Math::Gcd3(30,42)<<endl;
                cout<<"Math::Gcd3(50,50) = "<<Math::Gcd3(50,50)<<endl;
                cout<<"Math::Gcd3(0,0) = "<<Math::Gcd3(0,0)<<endl;
                cout<<"Math::Gcd3(-42,-30) = "<<Math::Gcd3(-42,-30)<<endl;
                cout<<"Math::Gcd3(-42,30) = "<<Math::Gcd3(-42,30)<<endl;
            
                return 0;
            }

            不過有一點值得一提,就是所謂性能最好效率最高的Gcd3不支持負數,也就是最后兩行測試代碼無法通過。但是限于對負數的最大公約數并沒有定義,也就是說即便上面的Gcd1和Gcd2好像算出了負數,但它們的結果沒有意義。

            posted on 2009-03-04 23:52 volnet 閱讀(1029) 評論(0)  編輯 收藏 引用 所屬分類: 知識庫(KnowledgeLibrary)

            特殊功能
             
            成人精品一区二区久久久| 久久伊人精品一区二区三区| 成人妇女免费播放久久久| 国产三级观看久久| 久久久免费观成人影院| 久久综合给久久狠狠97色| 欧美日韩精品久久久久| 久久99国产精一区二区三区| 精品多毛少妇人妻AV免费久久 | 久久精品一区二区| 国产精品青草久久久久福利99| 丁香五月综合久久激情| 狠狠精品久久久无码中文字幕| 91久久精品国产91性色也| 久久99亚洲网美利坚合众国| 国产高清国内精品福利99久久| 亚洲va久久久久| 一级a性色生活片久久无少妇一级婬片免费放 | 99久久免费国产精品| 77777亚洲午夜久久多喷| 99国内精品久久久久久久| 亚洲欧美成人综合久久久| 国产激情久久久久久熟女老人| 日韩精品久久久久久| 国内精品久久久久久99蜜桃| 亚洲欧洲精品成人久久曰影片 | 噜噜噜色噜噜噜久久| 日本福利片国产午夜久久| 久久久久亚洲AV片无码下载蜜桃| 久久精品国产亚洲AV蜜臀色欲 | 久久综合给合综合久久| 国产精品成人无码久久久久久 | 久久久这里有精品中文字幕| 久久九九亚洲精品| 99国产欧美久久久精品蜜芽| 欧美亚洲国产精品久久蜜芽| 欧洲精品久久久av无码电影| 午夜精品久久久久久毛片| 久久综合亚洲色一区二区三区| 精品国产乱码久久久久软件| 久久乐国产综合亚洲精品|