一个剩余算法的分析
在博客园上看到一个小牛发啦一个剩余算法的分析:
一个婚宴,安排来客,5个人一桌剩余4人,7个人一桌剩6桌,9个人一桌剩余8人,11个人一桌正好,当时看到那个哥们又是剩余算法又是加密算法的,最后抽象出一个算法,如下:
import junit.framework.TestCase;
public class ShareTest1 extends TestCase {
/** *//**
* Return the greatest common divisor.
*/
public static long gcd( long a, long b )
{
if( b == 0 )
return a;
else
return gcd( b, a % b );
}
// Internal variables for fullGcd
private static long x;
private static long y;
/** *//**
* Works back through Euclid's algorithm to find
* x and y such that if gcd(a,b) = 1,
* ax + by = 1.
*/
private static void fullGcd( long a, long b )
{
long x1, y1;
if( b == 0 )
{
x = 1;
y = 0;
}
else
{
fullGcd( b, a % b );
x1 = x; y1 = y;
x = y1;
y = x1 - ( a / b ) * y1;
}
}
/** *//**
* Solve ax == 1 (mod n), assuming gcd( a, n ) = 1.
* @return x.
*/
public static long inverse( long a, long n )
{
fullGcd( a, n );
return x > 0 ? x : x + n;
}
public static long china(long[] n, long[] a) {
// TODO Auto-generated method stub
long n_total = 1L;
final int len = n.length;
for(int i=0;i<len;i++){
n_total *= n[i];
}
long []m = new long[len];
for(int i=0;i<len;i++){
m[i] = n_total / n[i];
}
long []c = new long[len];
for(int i=0;i<len;i++){
c[i] = m[i] * inverse(m[i],n[i]);
}
long a_total = 0L;
for(int i=0;i<len;i++){
a_total += (a[i]*c[i]) % n_total;
}
a_total %= n_total;
return a_total;
}
/** *//**
* @param args
*/
public void test() {
// TODO Auto-generated method stub
long n[] = {5,7,9,11};
long a[] = {4,6,8,0};
//long n[] = {3,5,7};
//long a[] = {2,3,2};
System.out.println(china(n,a));
}
}
我用单元测试一下使用时间:
[img]Finished after 0.005 seconds[/img]
我的算法不会,但是我也是软件工程出生的,略有稍懂,就自己写啦几句实现:
import junit.framework.TestCase;
public class ShareTest extends TestCase{
public void test() {
System.out.println(Long.MAX_VALUE);
for(int i=0;i<Long.MAX_VALUE;i++){
if(i%5==4 && i%7==6 && i%9==8 && i%11==0){
System.out.println("The number is :" + i);
break;
}
}
}
}
我用单元测试一下使用时间:
[img]Finished after 0.005 seconds[/img]
得出的结果竟然惊人的一样,不知道是他分析的算法有问题,还是现在java虚拟机进行拉算法的优化,他在哪撤啦半天的算法,也没有看到效率,哈哈......
