Algorithm to find the 2 largest numbers smaller than 2 integers a and b, that are divisible by each other
So here’s the challenge. Given 2 integers named a and b:
// Find the 2 largest numbers, smaller than a and b, that are divisible by each other.
// input: a:102,b:53 // output: (102,51)
// input: a:7,b:4 // output: (6,3)
// input: a:3,b:2 // output: (2,2)
The catch is, I don’t want to brute force it. I think it comes out to O(n²).
Here’s the signature for the method:
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
}
Here’s a sample implementation:
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;
}
Here’s the test client:
class Program
{
static void Main(string[] args)
{
Console.WriteLine(Analyze(102, 53));
Console.WriteLine(Analyze(6, 4));
Console.WriteLine(Analyze(3, 2));
}
}
There are obviously problems with my implementation, but it’s not bad for starters. For instance when I use 106 and 54 for my arguments, had I not decremented the outter loop variable (i-- in the else block), I’d have found a matc开发者_开发百科h with 106 and 53. Instead I find a match a 104 and 52, which isn’t quite right but is relatively close to the desired result. However, my sample implementation is much faster than a brute forced approach because I’d never loop anymore than b times, making it O(b). Thoughts, inputs?
I think this would work, and be pretty straightforward, if I'm not confused, it should find the largest 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);
}
}
Finding the largest lexicographically is trivial. Just loop from b
downto 1
.
You'll be able to do better if you jump by more than one, obviously. Here's an example in python (assuming a>b
, if it's not, swap them):
>>> 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)]
Have you looked at the Wolfram article on Greatest Common Divisor and with a little google-ing I found for you a nice java code that implements a good GCD algorithm that you can modify for your purposes here
精彩评论