寻找不同的数

mathtime

看你们闲的无事出个题目给你们考虑: 设有一整数集{0,1,2...,255}, 先人工在其中选出了两个数 a=71,b=201 再人工选一个不会等于a和b的数x, 问题: 现在用程序再选一个不会等于a,b,x的数y，如前所述a,b ,x值是确定的。 求最高效的选一个y的办法。

shuzimi

设数组A[254]，分别1，2，......，254，255 这254个数，其中不含 71 和 201。 1. 从这254个单元中任取一个数 x； 2.从这254个单元中再任取一个数； 3.将取出来的数与x比较； 4.比较结果相同则再从2.逐步执行，结果不相同则结束；

mathtime

这种算法显的很臃肿, 好点的算法如:排序 a、b、x，找出最大最小值。如a是最大值并且a<255,则令y=a+1即符合要求。 我可以给个更高效的思路但目前我没实现：即找到四者一个关系式比如： 令y=a+b+x , 或许y符合要求, 但事实证明这个关系式不行，但我想存在这样符合要求的等式，这是我出此题的目的。

mathtime

我燥动的脑筋又想到了或许是回忆起另一种看似有点名堂的办法,就是随机产生一个数y,拿y比较a、b、x 若等则继续随机得到y再比较，若都不等则得到结果，但仔细想了下产生随机数内部也是要公式的并不一定最好。 看来查找关系式的算法应该仍是目前最好的想法。如果是这样前面对这个问题的罗嗦描述可以如下简洁描述： 在数域{0,1,2...,255}中，请找一个函数y=f(a,b,x)，使得y 不等于任何参数a、b、x 。

hujunhua

y=85a+51b+120x+1(mod255) 如果所得y=0(mod255), 就随便取为0或者255

hujunhua

还可以更广一点： y=85a+51b+120x+r(mod255), r任取于255的缩余系，即Gcd(255,r)=1 如果所得y=0(mod255), 就随便取为0或者255

mathtime

看来你有点数学底子，搬上了一些高级的东西。 不过我还在验算，看来我也要用些理论的东西了，不能光验算 我希望有人给出上式的证明，免得我花时间检验，下班了只能等明天

wayne

9# mathtime

看来你有点数学底子，搬上了一些高级的东西。

额,这个这个, , 黑色的幽了一默 =============== 不知道这个是否可行 y= a+b+x+GCD(a,b,x) (mod 256)

mathtime

这个公式用手工验算已无法完成,因为它们相互关联了，我要复习下数论来重新认识下这个问题。虽然我想到了似乎是更好的算法，这个在有必要时再提出，因为我觉得这里用函数的方法适用性更强实用价值更大，值得探讨下去（所以暂时不想引入思路到其他分支）。

hujunhua

不过我还在验算，看来我也要用些理论的东西了，不能光验算我希望有人给出上式的证明，免得我花时间检验，下班了只能等明天mathtime 发表于 2012-12-12 16:58

排列数P(256,3)=16581120, 要用手工直接验算是行不通的，除非你运气好很快找到反例。但不幸的是，5#和6#的表达式是没有反例的（我试着用Mathematica9验算5#，费时107秒）。 5#的表达式是“中国剩余定理”解出来的，构造起来不难，反过来证明更简单。 记n≡85a+51b+120x+1(mod 255), 注意255=3·5·17，85=5·17≡1(mod 3)，51=3·17≡1(mod 5)，120=3·5·8≡1(mod 17)，易得 n≡a+1(mod 3)≡b+1(mod 5)≡x+1(mod 17), 所以n与a, b, x皆不相等。