最大公約數的算法

          Posted on 2006-11-28 01:54 近似凱珊卓 閱讀(814) 評論(0)  編輯  收藏 所屬分類: 學習筆記

          汗~學過又忘掉的東西。。。那就記錄下來,讓忘卻來得更猛烈些吧!

          //遞歸實現

          int gcd(int m,int n)

          {

          ?????? if (m < n)

          ?????? {

          ????????????? int tmp = m;

          ????????????? m = n;

          ????????????? n = tmp;

          ?????? }

          ?

          ?????? if (n == 0)

          ????????????? return m;

          ?????? else

          ????????????? return gcd(n,m % n);

          }
          ?
          //非遞歸實現

          int gcd2(int m,int n)

          {

          ?????? if (m < n)

          ?????? {

          ????????????? int tmp = m;

          ????????????? m = n;

          ????????????? n = tmp;

          ?????? }

          ?

          ?????? if (n == 0)

          ????????????? return m;

          ??????

          ?????? while (n > 0)

          ?????? {

          ????????????? int tmp = m % n;

          ????????????? m = n;

          ????????????? n = tmp;

          ?????? }

          ?

          ?????? return m;

          }
          ?

          ?????? 這里給出了最大公約數的算法,那怎么求最大公倍數呢?其實知道了最大公約數,最小公倍數的求法就簡單了:

          int gbs(int m,int n)

          {

          ?????? return m*n/gcd(m,n);

          }
          ?


          求最大公約數的stein算法(zz)
          astrophor 發表于 2006-9-9 20:24:00


          在處理大數時比較有效,因為沒有用到大數的除法運算,速度會很快。

          int gcd(int a,int b)
          {
          if (a == 0) return b;
          if (b == 0) return a;
          if (a % 2 == 0 && b % 2 == 0) return 2 * gcd(a/2,b/2);
          else if (a % 2 == 0) return gcd(a/2,b);
          else if (b % 2 == 0) return gcd(a,b/2);
          else return gcd(abs(a-b),min(a,b));
          }


          只有注冊用戶登錄后才能發表評論。


          網站導航:
           

          posts - 9, comments - 0, trackbacks - 0, articles - 0

          Copyright © 近似凱珊卓

          主站蜘蛛池模板: 大同市| 佳木斯市| 托克逊县| 四平市| 蒙山县| 临沂市| 台中市| 芦溪县| 贵定县| 河西区| 林口县| 海盐县| 阿拉善右旗| 巴马| 普洱| 汶川县| 大理市| 平塘县| 西乡县| 高要市| 资兴市| 绍兴市| 玉山县| 娄烦县| 石嘴山市| 潼关县| 绩溪县| 额敏县| 青神县| 潞城市| 彭山县| 孟连| 南召县| 千阳县| 黄浦区| 远安县| 息烽县| 宜君县| 永登县| 陇南市| 曲水县|