循序搜尋(Sequential Search)
問題:判斷x這個key是否位於含有n個key的陣列S中。
輸入(參數):正整數n，由n個key所構成的陣列(引所值由1到n)，key x。
輸出:location，x在S中的位置(x不再S回傳0)
虛擬碼:
void seqsearch(int n, const keytype S[], keytype x, index& location)
{
location=1
while(location<= n && s[n] !=x )
location++;
if(location > n)
location=0;
}
二元搜尋法(Binary Search)
問題:判斷x這個key是否位於含有n個key的以排序陣列S中。
輸入:正整數n，由n個key所構成的以排序陣列(遞減，由1到n)，x這個key。
輸出:location, x在S中的位置(x不在S輸出0)。
虛擬碼:
void binsearch(int n, const keytype S[], keytype x, index& location)
{
index low, high, mid;
low=1; high=n;
location=0;
while(low <= high && location == 0)
{
mid=((low+hight)/2)
if(x == S[mid])
location=mid
else if(x < S[mid])
high=mid-1;
else
low=mid+1;
}
二元搜尋法的搜尋次數是log n+1，下面比較一下循序跟位元搜尋法的搜尋次數，陣列越大越能看出之間的差異。
費布那西數列(Fibonacci Sequence)
f0=0
f1=1
fn=fn-1+fn-2 n>=2
f2=f1+f0=1+0=1
f3=f2+f1=1+1=2
f4=f3+f2=2+1=3
問題:求費布那西數列的第n項(遞迴版)
輸入:非負整數n
輸出:第n項的值
虛擬碼:
int fib(int n )
{
if(n<=1)
return n;
else
return fib(n-1)+fib(n-2);
}
下面是遞迴的呼叫，可以發現fib(3)被計算了2次，fib(2)被計算了3次，這樣是很沒有效率的。
問題:求費布那西數列的第n項(迭代版)
輸入:非負整數n
輸出:第n項的值
int fib(int n)
{
int i;
int f[0~n];
f[0]=0;
if(n>0)
{
f[1]=1;
for(i=2;i<=n;i++)
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
費布納西數列的迭代會比遞迴好，看虛擬碼就可以知道了。
留言列表