原 最大公约数

代码:

穷举法

        //穷举法
        public static Int32 GetMaxCommonDivisorWithExhaustion(Int32 biggerNum, Int32 smallerNum)
        {
            Int32 maxDivisor = 0;
            for (int index = 1; index < smallerNum / 2; index++)
            {
                if (biggerNum % index == 0 && smallerNum % index == 0)
                {
                    maxDivisor = index;
                }
            }
            return maxDivisor;
        }

更相减损法

        //更相减损法(递归)
        public static Int32 GetMaxCommonDivisorWithGxjsRecursionRecursion(Int32 biggerNum, Int32 smallerNum)
        {
            return biggerNum != smallerNum ? (smallerNum > (biggerNum - smallerNum) ? GetMaxCommonDivisorWithGxjsRecursionRecursion(smallerNum, biggerNum - smallerNum) : GetMaxCommonDivisorWithGxjsRecursionRecursion(biggerNum - smallerNum, smallerNum)) : biggerNum;
        }
        //更相减损法(非递归)
        public static Int32 GetMaxCommonDivisorWithGxjsRecursionNorecursion(Int32 biggerNum, Int32 smallerNum)
        {
            while (biggerNum != smallerNum)
            {
                if (smallerNum > biggerNum - smallerNum)
                {
                    int temp = smallerNum;
                    smallerNum = biggerNum - smallerNum;
                    biggerNum = temp;
                }
                else
                {
                    biggerNum -= smallerNum;
                }
            }
            return biggerNum;
        }

辗转相除法

        //辗转相处法 (递归)
        public static Int32 GetMaxCommonDivisorWithGcdRecursion(Int32 biggerNum, Int32 smallerNum)
        {
            return biggerNum % smallerNum == 0 ? smallerNum : GetMaxCommonDivisorWithGcdRecursion(smallerNum, biggerNum % smallerNum);
        }
        //辗转相处法 (非递归)
        public static Int32 GetMaxCommonDivisorWithGcdNorecursion(Int32 biggerNum, Int32 smallerNum)
        {
            while (biggerNum % smallerNum != 0)
            {
                int temp = biggerNum;
                biggerNum = smallerNum;
                smallerNum = temp % smallerNum;
            }
            return smallerNum;
        }

测试代码:

   Stopwatch sw = new Stopwatch();
            sw.Reset();
            sw.Start();
            {
                for (int i = 0; i < 100000000; i++)
                {
                    GetMaxCommonDivisorWithGxjsRecursionRecursion(260, 60);
                }
            }
            sw.Stop();
            Console.WriteLine("更相减损法(递归):" + sw.ElapsedMilliseconds);
            sw.Reset();
            sw.Start();
            {
                for (int i = 0; i < 100000000; i++)
                {
                    GetMaxCommonDivisorWithGxjsRecursionNorecursion(260, 60);
                }
            }
            sw.Stop();
            Console.WriteLine("更相减损法(非递归):" + sw.ElapsedMilliseconds);


            sw.Reset();
            sw.Start();
            {
                for (int i = 0; i < 100000000; i++)
                {
                    GetMaxCommonDivisorWithGcdRecursion(260, 60);
                }
            }
            sw.Stop();
            Console.WriteLine("辗转相除法:" + sw.ElapsedMilliseconds);

            sw.Reset();
            sw.Start();
            {
                for (int i = 0; i < 100000000; i++)
                {
                    GetMaxCommonDivisorWithGcdNorecursion(260, 60);
                }
            }
            sw.Stop();
            Console.WriteLine("辗转相除法:(非递归)" + sw.ElapsedMilliseconds);

            sw.Reset();
            sw.Start();
            {
                for (int i = 0; i < 100000000; i++)
                {
                    GetMaxCommonDivisorWithExhaustion(260, 60);
                }
            }
            sw.Stop();
            Console.WriteLine("穷举法:" + sw.ElapsedMilliseconds);

测试结果:

结论:

更相减损法>辗转相除法>穷举法

非递归普遍比递归表现的更好

更相减损法仍旧有改进的余地,辗转相除法的优势是除了之后余数不会比除数更大,更像减损法减了之后仍旧需要比较。

和我这种写法或许也有关系,进去的值已经判断了大小了,如果换成无序的传进去参数,或许会不一样。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android机动车

设计模式——抽象工厂模式

● 为创建一组相关或依赖的对象提供一个接口,而无需指定他们的具体类型。是工厂方法模式的升级版。

8110
来自专栏Albert陈凯

scala的option和some

对于学习 Scala 的 Java™ 开发人员来说,对象是一个比较自然、简单的入口点。在 本系列 前几期文章中,我介绍了 Scala 中一些面向对象的编程方法,...

29350
来自专栏用户2442861的专栏

2015 华为 校招回忆录---篇(上)

本文由CSDN-蚍蜉撼青松【主页:http://blog.csdn.net/howeverpf】原创,转载请注明出处!

14820
来自专栏LEo的网络日志

冒泡排序

36060
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-day01-代码题

Java基础day01-代码题巩固 ? ? 第一题:分析以下需求,并用代码实现 1.定义一个HelloWold类 2.在类中定义主方法 3.在主方法中使用输出语...

35760
来自专栏海天一树

NOIP 2018提高组初赛C/C++答案详解

分析: 二进制化八进制:从低位(右)往高位(左),每三位直接换成八进制即可。 (1001101011)2 = (10 0110 1011)2 = (26B)...

56340
来自专栏编程

三撩Python

我不求深刻,只求简单。 --三毛 1、起手 我呢,一个咖啡师,咖啡使我忙碌与充实。 每天端起咖啡,香气弥漫,轻轻一口,就在那一刹那,没有时间,没有空间,没有纷纷...

18890
来自专栏申龙斌的程序人生

零基础学编程028:面向对象编程OOP

在《零基础学编程021:获取股票实时行情数据》一节中,我们想获取6支股票的行情数据,在《零基础学编程022:函数的世界》里我们能够把重复性的代码封装为一个函数p...

32160
来自专栏木制robot技术杂谈

谈一谈Python中str()和repr()的区别

前言 在学习BeautifulSoup文档的时候发现了一个以前不常见的Python内建函数repr(),带着好奇对这个内建函数进行了一番搜索和学习。 总结 s...

37640
来自专栏趣谈编程

选择排序

面试官: 聊聊选择排序 选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度 排序思想 一天,小一尘和师傅下山去了,在集市中路经一个水果摊,...

33980

扫码关注云+社区

领取腾讯云代金券