发个题目大家娱乐一下
有N个Int32范围内的正整数，找出N个数两两之间最大公约数的最大值。例如：N = 4，4个数为：9 15 25 16，两两之间最大公约数的最大值是15同25的最大公约数5。N可能会达到5w规模。问题不涉及什么高深的知识，所以比较适合讨论。
[解决办法]
int max = int.MinValue;
for(i = 0; i < data[i]; i++) {
for(j = 0; j < data[j]; j++) {
int p, q;
if(data[i] <= data[j]) {
p = data[i]; q = data[j];
} else {
p = data[j]; q = data[i];
}
int value = 辗转相除法(p, q);
if(max < value) {
max = value;
}
}
}
辗转相除法:
int suv_div(int p, int q) {
r = q % p;
if(r == 0) {
return p;
}
suv_div(r, p);
}
纯属抛砖引玉
[解决办法]
低效的一个算法
static void Main(string[] args)
{
const int count = 500; //整数个数
int[] arry = new int[count];
Random rnd = new Random();
for (int i = 0; i < count; i++)
arry[i] = rnd.Next(Int32.MaxValue-1)+1;
DateTime t1 = DateTime.Now;
int x=0, y=0, z=0;
for (int i = 0; i < count; i++)
{
for (int j = i + 1; j < count; j++)
{
int m = MaxY(arry[i], arry[j]);
if (x < m)
{
x = m;
y = i;
z = j;
}
}
}
DateTime t2 = DateTime.Now;
Console.WriteLine("{0}和{1}这组的最大公约数为：{2},用时{3}毫秒", arry[y], arry[z], x, TimeSpan.FromTicks(t2.Ticks-t1.Ticks).TotalMilliseconds);
Console.ReadLine();
}
static int MaxY(int firstNumber, int secondNumber) //求最大公约数的函数
{
int max = Math.Max(firstNumber, secondNumber);
int min = Math.Min(firstNumber, secondNumber);
int r = max % min;
if (r == 0) //如果把最大的除以最小的数，余数r为0的话，表示min就是最大公约数
{
//Console.WriteLine("最大公约数是{0}", min);
return min;
}
else //如果余数r不等于0，就把先前的min值当成最大值来用，把余数r当成先前的最小值来用
{ //一直不断的相除，直到余数r==0为止，这样就求出最大公约数
while (r != 0)
{
max = min;
min = r;
r = max % min;
}
return min;
}
}
static void Main(string[] args)
{
const int count = 500; //整数个数
int[] arry = new int[count];
Random rnd = new Random();
for (int i = 0; i < count; i++)
arry[i] = rnd.Next(Int32.MaxValue-1)+1;
DateTime t1 = DateTime.Now;
int x=0, y=0, z=0;
for (int i = 0; i < count; i++)
{
for (int j = i + 1; j < count; j++)
{
int max,min;
if(arry[i]>arry[j])
{
max=arry[i];min=arry[j];
}
else
{
max=arry[j];min=arry[i];
}
if(x>=min) continue;
int m = MaxY(min, max);
if (x < m)
{
x = m;
y = i;
z = j;
}
}
}
DateTime t2 = DateTime.Now;
Console.WriteLine("{0}和{1}这组的最大公约数为：{2},用时{3}毫秒", arry[y], arry[z], x, TimeSpan.FromTicks(t2.Ticks-t1.Ticks).TotalMilliseconds);
Console.ReadLine();
}
static int MaxY(int min, int max) //求最大公约数的函数
{
if(min==max)
return min;
int r = max % min;
if (r == 0) //如果把最大的除以最小的数，余数r为0的话，表示min就是最大公约数
{
//Console.WriteLine("最大公约数是{0}", min);
return min;
}
else //如果余数r不等于0，就把先前的min值当成最大值来用，把余数r当成先前的最小值来用
{ //一直不断的相除，直到余数r==0为止，这样就求出最大公约数
while (r != 0)
{
max = min;
min = r;
r = max % min;
}
return min;
}
}
class Program
{
const int count = 50000;
static void Main(string[] args)
{
int[] input = make_array();
print_array(input, 10);
Console.WriteLine();
int[] output = input
.Take(count - 1)
.Select((v, i) => suv_div(input[i], input[i + 1]))
.ToArray();
print_array(output, 9);
Console.WriteLine();
Console.ReadKey();
}
static int suv_div(int p, int q)
{
int r = q % p;
if (r == 0)
{
return p;
}
return suv_div(r, p);
}
static int[] make_array()
{
int[] array = new int[count];
Random rnd = new Random(2013);
for (int i = 0; i < count; i++)
{
array[i] = rnd.Next(Int32.MaxValue - 1) + 1;
}
return array;
}
static void print_array(int[] arr, int count)
{
for (int i = 0; i < count; i++)
{
Console.WriteLine(arr[i]);
}
}
}
int[] output = input
.Take(count - 1)
.Select((v, i) => suv_div(input[i], input[i + 1]))
.ToArray();
// 改装下：
int max = datas.Take(ArrCount-1).Select((v,i) => MaxCommonDivisor(datas[i], datas[i + 1])).Max();
// 这种方法，应该只能是 连续 的两个的比较吧， 等价于
for (int i = 0; i < ArrCount - 1; i++)
{
tmp = MaxCommonDivisor(datas[i], datas[i+1]);
if (tmp > max2)
max2= tmp;
}
