Thursday, May 12, 2005

 

Some notes on Algorithm Design Problems - 2

1.
I had never thought that the following problem can be transfered into a linear programming problem. Shame on me!

An improvement on capturing similarity between strings
By Thanh Dao

An improvement on capturing similarity between strings. The algorithm was developed in C#.
http://www.codeproject.com/csharp/ImproveStringSimilarity.asp

reference
http://www.let.rug.nl/~kleiweg/lev/levenshtein.html
http://www.math.uwo.ca/~mdawes/courses/344/kuhn-munkres.html

2.
Another related problem

Efficient Boyer-Moore Search in Unicode Strings
By leseul

An article on implementing Boyer-Moore algorithm for Unicode strings in C#.
http://www.codeproject.com/csharp/bmsearch.asp

more interesting site

EXACT STRING MATCHING ALGORITHMS
Animation in Java
http://www-igm.univ-mlv.fr/~lecroq/string/index.html

3.
what are the time and space complexities of a classical recursion-based Fibonacci algorithm

这个题就不解答了

编写快速计算 Fibonacci algorithm 的程序

http://www.cnblogs.com/lichen/archive/2007/06/19/788835.html

@阿毅
This is the code for Chinese Reminder and Lucas method I implemented some times before. It is in java and I don't remember the detail now. Both CRT and lucas provides O(lgn) and they can be used.

import java.math.*;
import java.util.HashMap;
import java.util.HashSet;
public class Fibonacci {
public static HashMap lucas_number=new HashMap();
public final static BigInteger ZERO=new BigInteger("0");
public final static BigInteger ONE=new BigInteger("1");
public final static BigInteger TWO=new BigInteger("2");


//CRT method
public static BigInteger two_term_crt(BigInteger x){
if(x.equals(ZERO))
return ZERO;
else if(x.equals(ONE))
return ONE;
else if(x.equals(TWO))
return ONE;
BigInteger n=x.divide(TWO).add(ONE);
BigInteger m=x.add(ONE).mod(TWO);
BigInteger k=x.mod(TWO).add(ONE);
BigInteger l= isEven(x)? x.divide(TWO) : x.divide(TWO).add(ONE);

BigInteger f_nm=two_term_crt(n.subtract(m));
BigInteger f_n=two_term_crt(n);
BigInteger f_n2=two_term_crt(n.subtract(TWO));
BigInteger sum=ZERO;
BigInteger f1=TWO.pow(m.intValue()).multiply(f_nm);
if(isEven(k)){
sum=f_n.multiply(f1.add(f_n2));
}
else{
sum=f_n.multiply(f1.subtract(f_n2));
}

if(isEven(l)){
sum=sum.add(ONE);
}
else{
sum=sum.subtract(ONE);
}
return sum;

}

public static boolean isEven(BigInteger x){
byte[] array=x.toByteArray();
if((array[array.length-1]&0x1)>0)
return false;
else
return true;
}
//Lucas method
public static BigInteger lucas_mathod(BigInteger x){

if(x.equals(ZERO))
return ZERO;
else if(x.equals(ONE))
return ONE;

//Check if it is a power of two
if((x.intValue()&(x.intValue()-1))==0){
//X is pow of 2
int k=x.getLowestSetBit();
BigInteger sum=ONE;
for(int i=0;isum=sum.multiply(get_lucas_number(TWO.pow(i)));
}
return sum;
}
else{
//
int i=0;
BigInteger temp=new BigInteger(x.toString());
while(true){
temp=temp.divide(TWO);
if(temp.compareTo(ONE)<0)
break;
i++;

}
int k=x.subtract(TWO.pow(i)).intValue();
BigInteger f_k=lucas_mathod(new BigInteger(String.valueOf(k)));
BigInteger f_k1=lucas_mathod(new BigInteger(String.valueOf(k+1)));
BigInteger f_k2=f_k.add(f_k1);
BigInteger sum=ZERO;
for(int num=2;num<=i;num++){
BigInteger lucas=get_lucas_number(TWO.pow(num-1));
f_k2=f_k2.multiply(lucas).subtract(f_k);

}
return f_k2;
}
}


public static BigInteger get_lucas_number(BigInteger x){
if(x.equals(ZERO))
return TWO;
else if(x.equals(ONE))
return ONE;
else if(lucas_number.containsKey(x))
return (BigInteger)lucas_number.get(x);
else{
BigInteger y=get_lucas_number(x.divide(TWO));
y=y.multiply(y);
int i=x.intValue()/2;
if((i&1)!=0){
y=y.add(TWO);
}
else{
y=y.subtract(TWO);
}
lucas_number.put(x,y);
return y;
}
}
//Classic method
public static BigInteger add_last_two(BigInteger x){
BigInteger f0=ZERO;
BigInteger f1=ONE;
if(x.equals(ZERO)){
return ZERO;
}
else if(x.equals(ONE)){
return ONE;
}
else{
BigInteger z=TWO;
BigInteger sum=null;
while(z.compareTo(x)<=0){
sum=f0.add(f1);
f0=f1;
f1=sum;
z=z.add(ONE);
}
return sum;
}
}

public static void main(String[] args){
BigInteger val=new BigInteger("3");
//BigInteger sum=add_last_two(val);
//BigInteger sum=lucas_mathod(val);
BigInteger sum=two_term_crt(val);
System.out.println(sum.toString());

}
}

呵呵,谁想用 F(n)=(POWER((1+SQRT(5))/2,n)-POWER((1-SQRT(5))/2,n))/SQRT(5) 算,就直接给0分,因为他/她不懂计算精度及power和sqrt的计算方法



<< Home

This page is powered by Blogger. Isn't yours?