算法设计与分析：欧几里得游戏

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

提示: 作者被禁止或删除内容自动屏蔽

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

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

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

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

欧几里得游戏算法.rar (4.43 KB, 下载次数: 4)

冰尘。 · 发表于 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个数；再比如12 3 这两个数，它们的最大公约数为**(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

提示: 作者被禁止或删除内容自动屏蔽

账号		自动登录	找回密码
密码			立即注册

elyric elyric 当前离线 UID 300 日志相册贡献荣誉积分 124 狗仔卡头像被屏蔽	发表于 2011-4-26 16:16:57 \| 显示全部楼层 \|阅读模式提示: 作者被禁止或删除内容自动屏蔽
	想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
	回复使用道具举报置顶卡千斤顶显身卡

elyric elyric 当前离线 UID 300 日志相册贡献荣誉积分 124 狗仔卡头像被屏蔽	楼主\| 发表于 2011-7-22 23:00:58 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽
	想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
	回复支持反对使用道具举报显身卡