[算法擂台]求N个数目字的"近似"最大公约数

[算法擂台]求N个数字的"近似"最大公约数.
最大公约数大家都知道吧. 我就不说了.

不知道的话... 我先汗一个,你家小学数学老师被你气死了...

求法大家都知道,其实也很简单,(有人大喊,别整三岁的题目,要整整四岁的题目)

那...现在来个难度+1的.

求近似最大公约数. 啥意思呢?

举例说 大家知道 3 是3,6,12,33,这4个数的最大公约数.

那啥是近似的呢.. 就是除1和0这2个数字以外,近似值.

举例说  7 9 12 最大公约数是1,除0和1以外近似的就是3  假设 7-1=6, 6 9 12 求最大公约数为3 差距为1
7 12 16 最大公约数仍然是1,除0和1以外的近似的就是 4 , 假设 7+1=8, 8 12 16 求最大公约数为4,差距为1
9 12 16 假设最大近似为3 则 差距为1 但是 近似为4 差距也为1 所以取4为近似最大公约数.

编程的话,语言不限.关键看思路,怎么去求更合理,效率更高.
[解决办法]

引用:

引用:
我觉得这种很暴力的题目不给数值范围的话，很难解～


假设为long类型. 

补充建议:最好不要使用除法和求模运算,这个很慢大家都知道的.

我问的是有多少个数～
[解决办法]
我感觉lz的意思是，每个数都可以+1,-1,或保持不变，总数没有限制，n个数，求近似最大公约数，这样的话，结果最小也是3了。可能咱们对题目的理解不同，你可能认为是总共有n次机会。

引用:

引用:

感觉直接枚举的话应该就能算，似乎是O(n)的，并且算到2就可以不用算了

每个数字都要枚举到n, 不能偷懒哦～

[解决办法]
简单写了一个，不知道lz是不是这个意思

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication7
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] items = new long[] {9,12,16};
            Console.WriteLine(SGcd(items));
            Console.ReadKey();
        }

        static long SGcd(long[] items)
        {
            HashSet<long> current = new HashSet<long>();
            HashSet<long> backup = new HashSet<long>();
            current.Add(items[0] - 1);
            current.Add(items[0]);
            current.Add(items[0] + 1);

            for (int i = 1; i < items.Length; i++)
            {
                for (int j = -1; j <= 1; j++)
                {
                    foreach (var item in current)
                    {
                        long gcd = Gcd(item, items[i] + j); 
 
                        if (gcd > 3)
                            backup.Add(gcd);
                    }
                }

                current.Clear();

                if (backup.Count == 0)
                    break;

                HashSet<long> temp = backup;
                backup = current;
                current = temp;
            }

            if (current.Count == 0)
                return 3;
            else
                return current.Max();
        }

        static long Gcd(long i, long j)
        {
            while (j != 0) { long r = j; j = i % j; i = r; }
            return i;
        }
    }
}

查看更多 下一篇