フィボナッチ数列
問題分析
プログラムの再帰呼び出しと戻りを正しく実装するには、パラメータの受け渡しと戻りアドレスの問題を解決する必要がある。具体的には、呼び出しを行う際に、再帰が発生するたびにすべてのパラメータ変数に対して新しい記憶領域を割り当て、前回の呼び出し時の実引数と今回の呼び出し後の戻りアドレスを保持しなければならない。
アルゴリズム設計
アルゴリズムの説明は以下の通りです：
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;
}
いつまた一杯の酒を飲み、細かい論文を議論するのか。