代码之家 › 专栏 › 技术社区 › A-Dubb

求2个小于2个整数a和b的最大数的算法,这些整数可被对方整除。

algorithm .net c#

A-Dubb · 技术社区 · 15 年前

所以这里是挑战。给定2个名为a和b的整数:

//找到两个最大的数,小于a和b,它们可以被对方整除。

//输入:A:102,B:53 //输出:(102,51)

//输入:A:7,B:4 //输出:(6,3)

//输入:A:3,B:2 //输出:(2,2)

关键是,我不想野蛮地强迫它。我想结果是O(N_2)。

这里是方法的签名:

static Tuple<int, int> Analyze(int a, int b)
{
    if (a % b == 0)
        return new Tuple<int, int>(a, b);
    else
        // Hereâs where the algorithm kicks in
}

这里是一个示例实现:

static Tuple<int, int> Analyze(int left, int right)
{
    if (left % right == 0)
        return new Tuple<int, int>(left, right);
    else
    {
        for (int i = left; i >= right; i--)
        {
            for (int j = right; j >= 0; j--)
                if (i % j == 0)
                    return new Tuple<int, int>(i, j);
                else
                    i--;
        }
    }

    return null;
}

这里是测试客户端:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(Analyze(102, 53));
        Console.WriteLine(Analyze(6, 4));
        Console.WriteLine(Analyze(3, 2));
    }
}

我的实现显然有问题,但它对初学者来说并不坏。例如,当我使用106和54作为参数时,如果我没有减少outter循环变量(i——在else块中),我发现了与106和53的匹配。相反,我找到了一个匹配的104和52,这并不完全正确,但相对接近期望的结果。但是,我的示例实现比强制方法快得多,因为I_d从未循环过B次,使其成为O(B)。思想,投入?

2 回复 | 直到 15 年前

Stephen 15 年前

我认为这是可行的,而且非常简单,如果我不困惑的话,它应该找到最大的 sum(a,b) :

static Tuple Analyze(int a, int b)
{
    if (a % b == 0)
        return new Tuple(a, b);
    else {
        // The algorithm starts here.
        // This is fairly easy to implement with tail recursion, but not optimal:
        // There are two cases to worry about:
        //   1) 'b' will never divide into 'a' evenly, but 'b-1' might.
        //   2) 'a' doesn't divide evenly by 'b', but 'a-1' might.
        if (a < b*2) return Analyze(a, b-1);
        else return Analyze(a-1, b);
    }
}

从词典编纂学的角度寻找最大的词是微不足道的。只是循环从 b 向下 1 .

显然,如果你跳不止一个,你就能做得更好。下面是Python中的一个示例(假设 a>b ,如果不是,交换它们):

>>> def analyze(a, b):
...   if 0 == a%b: return (a,b)          # If b is a factor, return them.
...   if a < b*2: return analyze(a,a/2)  # If b can't factor, adjust 'b' to next.
...   return analyze(a-(a%b),b)          # Otherwise, adjust 'a' to next.
... 
>>> map(lambda p: analyze(*p), [(102, 53), (6, 4), (3,2)])
[(102, 51), (6, 3), (3, 1)]

Kjartan Þór Kjartansson 15 年前

你看过吗 Wolfram 关于最大公约数和一个小谷歌的文章,我为你找到了一个很好的Java代码,它实现了一个很好的GCD算法,你可以根据你的目的修改它。 here