您的位置：程序门 -> .net技术 -> c#

c# 算法题

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

c# 算法题[已结贴,结贴人:luodanyu]

发表于：2007-02-13 21:18:25 楼主

求两个自然数，其和是667，最小公倍数与最大公约数之比是120：1。

（例如：115，552）

-------------------------------------------------------------

我得出的答案是115，552，232，435。

但是觉得自己的算法很繁琐，没有效率。

请问各位有简单一点的算法算这到题吗？

发表于：2007-02-13 21:32:041楼得分:0

我能算出来，已经不错了。无聊时，就想着优化一下。
总会进步的

发表于：2007-02-13 22:38:482楼得分:0

//至少你要把你的算法帖出来，否则我都不知道有没有你的精简

int 最大公约数（int 大数, int 小数)
{
if （小数 == 0) return 大数;
else return （最大公约数（小数, 大数 % 小数));
}

int 最小公倍数（int 大数, int 小数)
{
return 大数 * 小数 / 最大公约数（大数, 小数);
}

private void button2_click（object sender, eventargs e)
{
int sum = 667;

for （int a = 1; a <= sum / 2; a++)
{
int b = sum - a;
if （最小公倍数（a, b) / 最大公约数（b, a) == 120 / 1)
messagebox.show（string.format（ "{0},{1} ", a, b));
}
}

发表于：2007-02-13 22:48:333楼得分:0

int 最大公约数（int 大数, int 小数)
{
if （小数 == 0) return 大数;
else return （最大公约数（小数, 大数 % 小数));
}
private void button2_click（object sender, eventargs e)
{
int sum = 667;

for （int a = 1; a <= sum / 2; a++)
{
int b = sum - a;
int c = 最大公约数（b, a);
if （（a * b) / （c * c) == 120 / 1)
messagebox.show（string.format（ "{0},{1} ", a, b));
}
}

//最后精简成这样，通过数学公式省掉最小公倍数方法

发表于：2007-02-13 22:54:504楼得分:7

首先对667进行因式分解,

667=1*23*29

所以,最小公约数只能是1,23,29三个数其中一个...

于是...循环三次就行了...

发表于：2007-02-13 22:55:595楼得分:0

因式分解的算法就不用我写了吧,一个循环...

发表于：2007-02-13 22:57:016楼得分:0

不好意思打错字了...

所以,最大公约数只能是1,23,29三个数其中一个...

于是...循环三次就行了...

发表于：2007-02-13 23:14:007楼得分:0

楼上高人，写一个瞧瞧
你能通过667进行因式分解
得到结果我再给你100分

发表于：2007-02-13 23:53:248楼得分:5

设最大公约数为x, 则最小公倍数是120x. 那么两数的积为120x^2,又已知两数的和为667

设其中一个数为ax,则另外一个数为（120x/a)

ax+（120x/a) = 667
a + 120/a = 667/x

667进行因数分解得到x只能是 1,23,29其中一个.

循环3次:
1: 1+120/a = 667 无解
23: a +120/a = 29 a = 5
29: a + 120/a = 23 a = 8

然后代入a计算得到上面楼主的结果.

发表于：2007-02-13 23:57:049楼得分:0

确实只需要执行3次循环.

不过667的因数分解也要循环22次（假设没有质数表),或8次（假设有质数表)

发表于：2007-02-14 10:33:3910楼得分:0

不过667的因数分解也要循环22次（假设没有质数表),或8次（假设有质数表)
-----------------------------------------------------------------
恩，不会的，因为除了2以外，其他偶数都不用检查的。。。所以循环只有你说的一半。

发表于：2007-02-14 10:48:2411楼得分:0

发表于：2007-02-14 14:09:2912楼得分:0

//目前代码写成这样，循环20次得到结果
//请syeerzy、shrinerain看看有什么地方可以再次优化？
int sum = 667;
int quo = 120;

for （int i = 2; i < math.sqrt（sum); i += 2)
{
if （sum % i == 0)
{
for （int j = 2; j < math.sqrt（quo); j++)
{
if （quo % j == 0)
{
int x = i;
int a = j;
if （（a * x + （quo * x / a) == sum) &&
（a + quo / a == sum / x))
messagebox.show（string.format（ "{0},{1} ", a * x, quo * x / a));
x = sum / i;
if （（a * x + （quo * x / a) == sum) &&
（a + quo / a == sum / x))
messagebox.show（string.format（ "{0},{1} ", a * x, quo * x / a));
}
if （j == 2) j++;
}
}
if （i == 2) i++;
}

发表于：2007-02-15 16:40:3813楼得分:0

那里有你要求的数啊,题目有点问题啊

发表于：2007-02-15 16:42:4414楼得分:0

那种数字是根本求不出来的啊,对一下题目在发出来给大家解,还差不多啊

发表于：2007-02-15 17:05:3915楼得分:0

mark

发表于：2007-02-15 17:37:4016楼得分:0

发表于：2007-02-15 23:44:0417楼得分:0

厉害啊，各位

你们的讨论让我豁然开朗^_^

努力思考中……

发表于：2007-03-11 18:09:4018楼得分:0

zswang（伴水清清)

math.sqrt（sum) 和 math.sqrt（qum)
为什么要把范围设定在平方根之内，超越了平方根一样会有sum，qum的质因数，是吗？

---------------------------------------------------------------------------

a * x + （quo * x / a) == sum 和 a + quo / a == sum / x

这两条表达式不是一样的吗，为什么要写2个？

我好多不懂啊-_-！

发表于：2007-03-11 18:10:4219楼得分:0

汗！原来快过一个月了，我还不明白……

发表于：2007-03-12 19:04:1520楼得分:0

相隔太久了

///这是分解的两个乘积因子
int x = i; // no.1
//。。。。。
x = sum / i; //no.2

所以x不会大于sqrt（sum)

发表于：2007-03-12 20:36:1421楼得分:0

昏，还是不明白！

i是否667的所有质因数的范围？

发表于：2007-03-12 21:02:0122楼得分:8

i和（sum / i)是667的所有质因数的范围。
...
i * （sum / i) = sum

发表于：2007-03-12 22:27:3223楼得分:0

2*2*2 和 2《3哪个效率更好？？？！
程序的多少不是影响效率的主要因素，编译方式才是。

发表于：2007-03-13 15:56:4424楼得分:0

i see！thanks you very much！！

太高兴了！^-^

下一篇：如何获取本机ip地址？具体说明如下！
上一篇：有无一本书可以查c#的类、方法、属性，类似参考手册的？

其他资讯