elyric 发表于 2011-4-26 16:16:57

dawawa1234 发表于 2011-5-9 17:23:02

只要考虑大点的那个数的奇偶性就能知道先行，还是后动了。

最后的期待 发表于 2011-5-10 07:11:06

楼上说的简单了点吧，应该要分成好几类情况啊。我在word里也写了下，呵呵，看看吧，如不对请指正

冰尘。 发表于 2011-7-8 00:56:26

我也不同意2L的。。比如6和3。。6和2   较大数一样。。但是结果明显是不一样的。。。

鱼C# 发表于 2011-7-14 06:47:22

交互递归的问题

yulin3192 发表于 2011-7-16 13:15:13

:funk:不懂:o:'(

鱼C# 发表于 2011-7-18 14:31:48

首先：如果两个数m和n是互质,这样的话就是不是很好办了，从1到较大数max(m,n)之间的所有数字都有可能，所有还可以写max(n,m)-2个数；那么不是质数呢？不是质数，可不可以用质数的角度去思考呢？可以！就求它们的最大公约数嘛
我是这样想的，既然不是质数就把它变成质数！设x = **(a,b),即x为a，b的最大公约数。那么m = ax, n = bx、 此时，a，b就是质数了吧！

鱼C# 发表于 2011-7-18 14:45:45

（还没说完呢 ，继续啊！ 因为刚刚不小心按了个ctrl+enter了、 聊qq习惯了、我设置的qq换行是这样换的）刚刚说的不够准确啊，说a，b两个数，意思是a,b互质！这里的a、b可以算出来的 小学就学过。。那么从互质的角度考虑1到较大数max(a,b)之间的所有数字都有可能，所有还可以写max(a,b)-2个数；
如果从m,n的角度就是x,2x,3x ,4x......max(a,b)*x这些数是可以取到的。
举个例子 比如说互质的两个数7 3 那从1-7的每个数字都可以出现在黑板上，共有1,2,4,5,6个数；再比如123 这两个数，它们的最大公约数为**(12,3) = 3，所以用得到a = 4，b = 1。看较大的那个为4，所以从1*x - 4*x。 因此得到有1*3=3，2*3=6， 3*3=9， 4*3 =12这四个数必定出现在黑板上，且只有这四个数。

鱼C# 发表于 2011-7-18 14:50:53

两种情况总结可以一点就是： 用短除法求得它们最大公约数 x 即可，（因为互质的两个数最大公约数为1嘛），然后用较大的那个数除以m/x 减去本身存在的两个数就是仍然需要写的数字的个数。 即 还需要的数个数：max（m，n) /**(m,n) - 2 个。 其中max（m,n）表示取大的那个数， **(m,n)表示最大公约数

elyric 发表于 2011-7-22 23:00:58

页: [1]
查看完整版本: 算法设计与分析：欧几里得游戏