費波那契數列
問題分析
要正確實現程序的遞迴調用和返回，必須解決參數的傳遞和返回地址問題。具體地說，進行調用時，每遞迴一次都要給所有參變量重新分配儲存空間，並要把前一次調用的實參和本次調用後的返回地址保留。
演算法設計
演算法描述如下：
int Fib(int n){
int fib;
if(n==0) fib=0;
else if(n==1) fib=1;
else fib=Fib(n-1)+Fib(n-2);
return fib;
}
資料結構設計
用堆疊去分配和管理儲存空間，系統在每次執行呼叫過程的語句時需要開闢一個「工作記錄」，用以保存呼叫前過程中所有參變數的值及呼叫後的返回位址，將此工作記錄存於堆疊中，以便在返回時能在堆疊頂端找到正確的資訊。
除錯過程
在每次呼叫函數的時候，將傳入的參數進行輸出，可以更直觀地看到堆疊的呼叫過程。 以最開始Fib（2）的遞迴呼叫為例，程式先將Fib（5）、Fib（4）…Fib（1）儲存到堆疊中，當n==1時，將值返回上一個位址中，同理也將n==0時的值返回，這樣Fib（2）的值便有了，再返回到Fib（2）的上一個層級Fib（3）中。
輸出結果
原始碼
#include<bits/stdc++.h>
using namespace std;
int Fibonacci(int n){
int fib;
if(n==0){
fib=0;
}else if(n==1){
fib=1;
}else if(n==2){
fib=2;
}else{
fib=Fibonacci(n-1)+Fibonacci(n-2);
}
return fib;
}
int main(){
int n=0;
cout<<"請輸入n:";
start:
cin>>n;
cout<<"第n個Fibonacci數為"<<Fibonacci(n)<<endl;
cout<<"是否繼續計算(y/n):";
char choice;
choice:
cin>>choice;
if(choice=='y'||choice=='Y'){
goto start;
}else if(choice=='n'||choice=='N'){
return 0;
}else{
cout<<"輸入錯誤,請重新輸入:";
goto choice;
}
return 0;
}
劃分子集問題
問題分析
問題要求我們將一個集合中劃分成互不相交的子集，使任何子集上的元素無任何衝突，且劃分的子集數較少。此類問題常用在日程安排上。
演算法設計
衝突關係首先透過一個二維陣列表示出來，有衝突關係則賦值1，無衝突則賦值0。透過循環篩選法對其劃分，即從第一個元素開始，先將元素1單獨拿出，逐個判斷其他元素是否和拿出的所有元素有衝突關係，無衝突則拿出元素，並劃為一組。這樣循環一周，所有互相無衝突關係的已被劃為一組，循環此操作，即可完成劃分要求。
資料結構設計
透過一個循環佇列來儲存資料，每次循環一週，不斷迭代資料，不需要開闢新的儲存空間。
除錯過程
輸出結果
原始碼
#include<bits/stdc++.h>
using namespace std;
int newr[9];
void DivideIntoGroup(int n,int R[][9],int cp[],int result[])
{
int front,rear,group,pre,I,i;
front=n-1;
rear=n-1;
for(i=0;i<n;i++)
{
newr[i]=0;
cp[i]=i+1;
}
group=1;
pre=0;
do
{
front=(front+1)%n;
I=cp[front];
if(I<pre)
{
group=group+1;
result[I-1]=group;
for(i=0;i<n;i++)
{
newr[i]=R[I-1][i];
}
}
else
{
if(newr[I-1]!=0)
{
rear=(rear+1)%n;
cp[rear]=I;
}
else
{
result[I-1]=group;
for(i=0;i<n;i++)
{
newr[i]+=R[I-1][i];
}
}
}
pre=I;
}while(rear!=front);
}
int main(){
int result[9],cp[9];
int R[9][9]=
{
{0,1,0,0,0,0,0,0,0},
{1,0,0,0,1,1,0,1,1},
{0,0,0,0,0,1,1,0,0},
{0,0,0,0,1,0,0,0,1},
{0,1,0,1,0,1,1,0,1},
{0,1,1,0,1,0,1,0,0},
{0,0,1,0,1,1,0,0,0},
{0,1,0,0,0,0,0,0,0},
{0,1,0,1,1,0,0,0,0},
};
DivideIntoGroup(9,R,cp,result);
for(int i=0;i<9;i++)
{
cout<<i+1<<" ";
}
cout<<endl;
for(int i=0;i<9;i++)
{
cout<<result[i]<<" ";
}
return 0;
}
何時一樽酒，重與細論文。