日期:2014-05-20  浏览次数:21020 次

算法问题:求N个数字的近似最大公约数
问题不得不再发一遍.

N个数字(假设为400个数字) 分别为1*10 - 256*10之间,每个数字都是10的整倍数. 数字有可能重复

最大公约数X要为1-256之间 求近似最大公约数 (数字N中 任意一个数字Y 除以 这个最大公约数X得结果不得超过 15)

举例说明 N个数字 分别为 80 120 150 则近似最大公约数X为40, 差距为10 原理(80 120 160最大公约数为40,差距0)

差距相等情况下近似最大公约数更大则优先使用

穷举的办法是会.

假设现在 N = 400 最多 尝试运算次数为 400 * 256 次.比较256次即可得到结果,但是有没有更好的算法呢?

希望大家踊跃参与.

如果有说的不明白的地方大家尽管提问.

------解决方案--------------------
瞎写一个
C# code

            int[] x = {30,40,50,60,70,140,400,2300};
            int max = x.Max();
            int mmax = max / 15;
            double comp = max;
            int g = 0;
            for (int i = mmax; i < max; i++)
            {
                double d = 0;
                for (int m = 0; m < x.Length; m++)
                {
                    double j = (double)x[m] / i;
                    int k = (int)j;
                    int h = k + 1;
                    d += j - k > h - j ? (h - j) * i : (j - k) * i;
                }
                if (d < comp)
                {
                    comp = d;
                    g = i;
                }
            }
            Console.WriteLine(g);

------解决方案--------------------
/// <summary>
/// 计算差距
/// </summary>
/// <param name="N">数据</param>
/// <param name="T">公约数</param>
/// <returns>差距</returns>
public int CJ(int N, int T)
{
if (N >= T)
{
//正差距
int zt = T - N % T;
//负差距
int ft = N % T;

if (ft < zt)
return -ft;
else
return zt;
}
else
{
//正差距
return T - N;
}
}
--------------------- 80,120,150 -----
公约数:29; 差距:16(7,-4,-5);方向:-2
公约数:30; 差距:10(10,0,0);方向:10
公约数:31; 差距:22(13,4,5);方向:22
公约数:32; 差距:34(16,8,10);方向:34
公约数:33; 差距:41(-14,12,15);方向:13
公约数:34; 差距:42(-12,16,-14);方向:-10
公约数:35; 差距:35(-10,-15,-10);方向:-35
公约数:36; 差距:26(-8,-12,-6);方向:-26
公约数:37; 差距:17(-6,-9,-2);方向:-17
公约数:38; 差距:12(-4,-6,2);方向:-8
公约数:39; 差距:11(-2,-3,6);方向:1
公约数:40; 差距:10(0,0,10);方向:10
公约数:41; 差距:19(2,3,14);方向:19
公约数:42; 差距:28(4,6,18);方向:28
公约数:43; 差距:36(6,9,-21);方向:-6
公约数:44; 差距:38(8,12,-18);方向:2
公约数:45; 差距:40(10,15,-15);方向:10
公约数:46; 差距:42(12,18,-12);方向:18
公约数:47; 差距:44(14,21,-9);方向:26
公约数:48; 差距:46(16,24,-6);方向:34
公约数:49; 差距:43(18,-22,-3);方向:-7
公约数:50; 差距:40(20,-20,0);方向:0
公约数:51; 差距:43(22,-18,3);方向:7
公约数:52; 差距:46(24,-16,6);方向:14
公约数:53; 差距:49(26,-14,9);方向:21
公约数:54; 差距:50(-26,-12,12);方向:-26
公约数:55; 差距:50(-25,-10,15);方向:-20
公约数:56; 差距:50(-24,-8,18);方向:-14
公约数:57; 差距:50(-23,-6,21);方向:-8
公约数:58; 差距:50(-22,-4,24);方向:-2
公约数:59; 差距:50(-21,-2,27);方向:4
公约数:60; 差距:50(-20,0,30);方向:10
公约数:61; 差距:49(-19,2,-28);方向:-45
公约数:62; 差距:48(-18,4,-26);方向:-40
公约数:63; 差距:47(-17,6,-24);方向:-35
公约数:64; 差距:46(-16,8,-22);方向:-30
公约数:65; 差距:45(-15,10,-20);方向:-25
公约数:66; 差距:44(-14,12,-18);方向:-20
公约数:67; 差距:43(-13,14,-16);方向:-15
公约数:68; 差距:42(-12,16,-14);方向:-10
公约数:69; 差距:41(-11,18,-12);方向:-5
公约数:70; 差距:40(-10,20,-10);方向:0
公约数:71; 差距:39(-9,22,-8);方向:5
公约数:72; 差距:38(-8,24,-6);方向:10
公约数:73; 差距:37(-7,26,-4);方向:15
公约数:74; 差距:36(-6,28,-2);方向:20
公约数:75; 差距:35(-5,30,0);方向:25
公约数:76; 差距:38(-4,32,2);方向:30
公约数:77; 差距:41(-3,34,4);方向:35
公约数:78; 差距:44(-2,36,6);方向:40
公约数:79; 差距:47(-1,38,8);方向:45
公约数:80; 差距:50(0,40,10);方向:50
公约数:81; 差距:52(1,-39,12);方向:-26