寻找不同的数

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皆不相等。