3つのC言語の例はあなたを連れて再帰方法論を掌握します

2316 ワード

再帰:
再帰(英語:Recursion)は、再帰と訳され、数学とコンピュータ科学では、関数の定義に関数自体を使用する方法を指す.
コンピュータの分野では、再帰はアルゴリズムポリシーとして特定の問題を解決するためによく用いられる.再帰アルゴリズムで解決するのに適した問題はどれですか.
再帰的手法を用いて解決するのに適した問題は、以下の2つの特徴を備えている.
  • この問題は、
  • を解決するために、より小さいが同じ形式のサブ問題に分解することができる.
  • この問題を最後まで分解すると、再帰することなく問題を解決できる基準状況が得られる
  • .
    コンピュータの分野では,再帰問題を解決することは,再帰関数によって実現される.再帰関数は自身を呼び出す関数であり、再帰関数は通常以下の形態を備えている.
        (  )
    {
        if (     )
            return          
           =              
        return     (  )
    }
    

    このプロジェクトは3つのC言語のプログラミングの例を通じて、再帰を利用して実際の問題を解決する過程で再帰を学び、その核心思想を掌握させます.一反三を挙げて、再帰を使って他の実際の問題を解決する方法を知っています.
    どの3つのC言語のプログラミングの例ですか?
    上記の3つのC言語のプログラミング例によって再帰的な使用を習得した3つの例は以下の通りである.
  • 再帰を使用して数学の問題を解決する-フィボナッチ数列(再帰の古典的な例);
  • Cプログラムを使用して、知的ゲームであるハノータを解決します.
  • フィボナッチ数列をより効率的に解決する.

  • 私たちは一人一人見てみましょう.
    1、再帰的に数学問題を解決する——フィボナッチ数列
    数学では、フィボナッチ数列は、再帰的な古典的な例である.次の列を確認します.
    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 ……
    

    数列の0番目と1番目の値は、それぞれ:0と1です.続くN番目の値は、N−1番目の値とN−2番目の値の和である.これがフィボナッチ数列です.数学的にフィボナッチ数列の定義には、再帰的な定義方式が採用されています.
    ここに画像の説明を入力します
    上記のフィボナッチ数列の数学的定義によれば,フィボナッチ数列上のN番目の項の値を求める再帰関数を容易に実現できる.
    /*
    * file name: fabonacciv1.c
    */
    #include 
    #include 
    
    //            ,      
    long long fabonacci(int n)
    {
        if (n == 0) return 0; //      0
        else if (n == 1) return 1;//      1
        else return fabonacci(n-1) + fabonacci(n-2); //           
    }
    
    int main(int argc, char *argv[])
    {
        if (argc != 2) {
            fprintf(stderr, "Usage: %s N.
    ", argv[0]); return 0; } int n = atoi(argv[1]); fprintf(stdout, "The %dth item in the Fibonacci sequence is %lld.
    ",n,fabonacci(n)); return 0; }

    コンパイルコマンド:
    $ gcc -o fibonacciv1 fibonacciv1.c
    

    結果:
    ここに画像の説明を入力します
    上記のプレゼンテーションでは,入力が50であると,プログラムがなかなか結果を出すことができず,プログラムの実現に問題があるようだ.
    上記の例は、再帰を学ぶ興味に打撃を与えるかもしれません.再帰で問題を解くことができますが、値が少し大きいと我慢できないほど遅くなります.こんなに効率が悪いのに、再帰しても何の役にも立たないようですね.この問題は再帰の頭を責めるわけにはいかない.この問題は実は私たちが適切な方法で再帰を使用していないからだ.読者の皆さんはまず、この問題をどのように解決するかを考えて、私たちは後で解決策を提供します.
    2、Cプログラムを使って知的ゲームを解決する--ハノータ
    3、もっと効率的にフィボナッチ数列を解決する
    後の2つの例については、紙面が限られているため、コードと手順を一つ一つ書かない.見たいのは、「3つのC言語の例が再帰方法論を身につける」をクリックして勉強することができ、具体的な実現手順とコードの詳細がある.