反復方法と再帰方法について話す

(一)反復法
反復法は転がり法とも呼ばれ,変数の古い値を絶えず新しい値に繰り返す過程である.反復アルゴリズムは、コンピュータの演算速度が速く、繰り返し操作に適しているという特徴を利用して、コンピュータに命令のセット(または一定のステップ)を繰り返し実行させ、この命令のセット(またはこれらのステップ)を実行するたびに、変数の元の値から新しい値を押し出し、コンピュータで問題を解決する基本的な方法である.
反復常用サイクル実装.
例1:次のプログラムの機能を分析する

int main(void)
{
          int x;
          cin>>x;
          while(x>0)
          {
                   cout<

歩いて調べると、xの逆シーケンス数が出力されていることがわかります.例えば、入力されたx値は358であり、出力は853である.
ループでは、反復のたびにxの数値が小さくなり、0になるまでループが終了し、反復では、毎回現在の最後のビット数出力が取り出され、xの各ビット数は、後ろの方が先に出力され、最終的にはxの逆シーケンス数が出力されます.
考え:例の10を2、8、16に変えたら?
出力される結果は、xに対応する2、8または16進数の逆シーケンス数である.
10進数を他の進数に変換する方法を連想します.2進数に変換する例では、2を除いて余剰をとる方法であり、最後に得られる余剰は前にあるべきである.前の反復プロセスを少し修正し,配列暫定残高を導入してこの問題を解決した.
参考手順は次のとおりです.

int main(void)
{
          int x, n=0, a[50];
          cin>>x;
          while(x>0)
          {
                   a[n]=x%2;
                   x=x/2;
                   n++;
       }
          for(int i=n-1;i>=0; i--)
                   cout<

近似反復法という反復法もあり、弦断法のような数値計算で方程式を解くのによく用いられる(p 106例4.9).例では、|f(x)|<ξ(ξ非常に小さな正数)までであるが,このときf(x)≒0と考え,f(x)=0の近似解xを得た.このプロセスは反復です.
f(x)が任意の方程式であり、呼び出されるときはf(x 1)とf(x 2)の異号を保証する関数を参照してください.

double root(double x1, double x2)   
{
          double x,y,y1;
          y1=f(x1);
          do
          {
                   x=xpoint(x1,x2); 
                   y=f(x);                     
                   if(y*y1>0)
                   {        y1=y;
                            x1=x;
                   }
                   else
                            x2=x;
          }while(fabs(y)>=0.00001);
          return x;
}

まとめ:反復アルゴリズムを用いて問題を解決するには、以下の3つの方面の仕事をしっかりと行う必要がある[1].
1、反復変数を決定します.反復アルゴリズムで解決できる問題では、少なくとも1つの直接的または間接的に古い値から新しい値を繰り返し出す変数が存在し、この変数が反復変数である.
2、反復関係式を確立する.反復関係式とは、変数の前の値から次の値をどのように出すかの式(または関係)を指します.反復関係式の確立は反復問題を解決する鍵であり、通常、繰返しまたは逆プッシュの方法を使用して達成することができる.
3、反復プロセスを制御する.反復プロセスはいつ終了しますか?これは反復プログラムを記述する上で考慮しなければならない問題である.反復プロセスを絶え間なく繰り返し実行させることはできない.反復プロセスの制御は通常2つの状況に分けることができる:1つは必要な反復回数が決定された値であり、計算することができる.もう1つは、必要な反復回数が決定できないことです.前者の場合、反復プロセスの制御を実現するために固定回数のサイクルを構築することができる.後者の場合,反復プロセスを終了するための条件をさらに解析する必要がある.
 
(二)再帰法
再帰はコンピュータ科学における重要な方法である.
再帰的に記述できるアルゴリズムは、通常、規模Nの問題を解くために、規模の小さい問題に分解しようとし、これらの小さな問題の解から大きな問題の解を容易に構築し、これらの規模の小さい問題も同様の分解と総合方法で規模の小さい問題に分解することができるという特徴がある.これらのより小さな問題の解から規模の大きい問題の解を作り出した.特に、規模N=1の場合、直接的に解くことができる.
例えばnを求めます!n!=n*(n-1)!,そして1!=1、次の関数を簡単に書きます.

long fact(int n)
{
         long f;
       if (n==1)
                   f=1;
       else
                   f=n*fact(n-1);                 
       return f;                          
}

再帰関数は実行過程において,fact(n)を求めてfact(n−1)を求め,fact(n−1)を求めてfact(n−2)を求める繰返し過程がある.fact(1)=1を求めた後、戻ってfact(2)、fact(3)......をfact(n)が得られるまで求める.再帰は,再帰と回帰の2段階からなる.
再帰は、このような形式の問題を計算するために使用できるだけではありません.実際には、反復で完了できるすべてのタスクは再帰的にも完了し、再帰的に完了したすべてのタスクは反復的に完了することもできます.一般に、再帰は表現しやすく(人間の効率)、反復の実行効率はより高い(機械の効率).再帰プログラムの実行効率が低いのは、ノック用関数のたびにコンピュータ内に関連する実行環境を保存する必要があり、時間とスペースがかかり、特に多くの「階層」を実行する必要がある再帰があるためです.だから実践の中で、よく再帰して問題をはっきり分析して、反復プログラムを書いて解きます.
再帰的な考え方で問題を解くには,このような再帰と回帰の過程を見つける必要がある.
スケール1に対して,同じ機能の再帰的実装を与えた.

int main(void)
{
         int x, n;
         cin>>x;
     f(x);
         cout<

自分で分析してください.入力xの値は358で、出力は?
十進法からバイナリへの変換を実現しようとすると,2に対して残数を取った後,逆順に取り出すことを保証するには,(1),(2)の2つの文を位置を変える必要がある.次のようになります.

void f(int a)
{
         if (a==0)
                   return;
         else
       {
                   f(a/2);                //(2)
                   cout<

どうして?歩いて調べればわかる.
最後にまとめ、再帰の基本概念と特徴[1]:
プログラム呼び出し自体のプログラミングテクニックを再帰(recursion)と呼ぶ.
1つのプロセスまたは関数は、その定義または説明の中で直接または間接的に自身を呼び出す方法であり、通常、大規模で複雑な問題の階層を元の問題に似た規模の小さい問題に変換して解き、再帰戦略は少量のプログラムで問題を解くプロセスに必要な複数回の繰り返し計算を記述することができ、プログラムのコード量を大幅に減少させる.再帰的な能力は、有限な文でオブジェクトの無限の集合を定義することです.再帰的な考えで書かれたプログラムは往々にして簡潔で分かりやすい.
一般に、再帰には境界条件、再帰前進セグメント、再帰帰還セグメントが必要である.境界条件が満たされない場合、再帰的に前進する.境界条件が満たされると、再帰的に返されます.
注意:
(1)再帰はプロセスや関数で自身を呼び出すことである.
(2)増分帰ポリシーを使用する場合、再帰出口と呼ばれる明確な再帰終了条件が必要である.
 
[1]プログラミング入門ネットワークからの参照http://www.bianceng.cn/Programming/sjjg/200901/11200.htm