问题不得不再发一遍.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次即可得到结果,但是有没有更好的算法呢?希望大家踊跃参与.如果有说的不明白的地方大家尽管提问.
(数字N中 任意一个数字Y 除以 这个最大公约数X得结果不得超过 15)
首先这个条件
如果给定2个数是10和2560,
精确最大公约数显然是10
但是近似最大公约数是什么?不存在?因为2560/10=256>15所以我觉得楼主是不是写错了
应该是(数字N中 任意一个数字Y 除以 这个最大公约数X得余数不得超过 15)
也就是差距
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);
如果要快 最快的效率会是多少。n*logn貌似吧。
/// 计算差距
/// </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
公约数：82; 差距：54(2,-38,14);方向：-22
公约数：83; 差距：56(3,-37,16);方向：-18
公约数：84; 差距：58(4,-36,18);方向：-14
公约数：85; 差距：60(5,-35,20);方向：-10
公约数：86; 差距：62(6,-34,22);方向：-6
公约数：87; 差距：64(7,-33,24);方向：-2
公约数：88; 差距：66(8,-32,26);方向：2
公约数：89; 差距：68(9,-31,28);方向：6
公约数：90; 差距：70(10,-30,30);方向：10
公约数：91; 差距：72(11,-29,32);方向：14
公约数：92; 差距：74(12,-28,34);方向：18
公约数：93; 差距：76(13,-27,36);方向：22
公约数：94; 差距：78(14,-26,38);方向：26
公约数：95; 差距：80(15,-25,40);方向：30
公约数：96; 差距：82(16,-24,42);方向：34
公约数：97; 差距：84(17,-23,44);方向：38
公约数：98; 差距：86(18,-22,46);方向：42
公约数：99; 差距：88(19,-21,48);方向：46
公约数：100; 差距：90(20,-20,50);方向：50
公约数：101; 差距：89(21,-19,-49);方向：-47
公约数：102; 差距：88(22,-18,-48);方向：-44
公约数：103; 差距：87(23,-17,-47);方向：-41
公约数：104; 差距：86(24,-16,-46);方向：-38
公约数：105; 差距：85(25,-15,-45);方向：-35
公约数：106; 差距：84(26,-14,-44);方向：-32
公约数：107; 差距：83(27,-13,-43);方向：-29
公约数：108; 差距：82(28,-12,-42);方向：-26
公约数：109; 差距：81(29,-11,-41);方向：-23
公约数：110; 差距：80(30,-10,-40);方向：-20
公约数：111; 差距：79(31,-9,-39);方向：-17
公约数：112; 差距：78(32,-8,-38);方向：-14
公约数：113; 差距：77(33,-7,-37);方向：-11
公约数：114; 差距：76(34,-6,-36);方向：-8
公约数：115; 差距：75(35,-5,-35);方向：-5
公约数：116; 差距：74(36,-4,-34);方向：-2
公约数：117; 差距：73(37,-3,-33);方向：1
公约数：118; 差距：72(38,-2,-32);方向：4
公约数：119; 差距：71(39,-1,-31);方向：7
公约数：120; 差距：70(40,0,-30);方向：10
公约数：121; 差距：71(41,1,-29);方向：13
公约数：122; 差距：72(42,2,-28);方向：16
公约数：123; 差距：73(43,3,-27);方向：19
公约数：124; 差距：74(44,4,-26);方向：22
公约数：125; 差距：75(45,5,-25);方向：25
公约数：126; 差距：76(46,6,-24);方向：28
公约数：127; 差距：77(47,7,-23);方向：31
公约数：128; 差距：78(48,8,-22);方向：34
公约数：129; 差距：79(49,9,-21);方向：37
公约数：130; 差距：80(50,10,-20);方向：40
-------------
数据不好找规律