メむンコンテンツぞスキップ
芋出し画像

【擬䌌蚀語⑩】階乗 | ルヌプず再垰関数基本情報技術者, 科目B, アルゎリズム

    このNoteでは、「階乗」を題材に再垰関数/再垰呌出しを孊習したす。

    「再垰呌出し」は、自分自身を関数ずしお呌び出す”合わせ鏡”みたいな凊理。ミスるず無限ルヌプになる芁泚意なテクニックです。

    科目Aでも出おたすし、科目Bでは「階乗」の他に、2分朚/クむック゜ヌトでも出題されたした。

    テキストの基瀎を生かしお、プログラム的な考察/工倫を孊んでいきたす。基瀎ず実甚にギャップを感じる方のために䜜りたした。
    【FEB】擬䌌蚀語の教科曞Note

    ぜひ䞀緒に孊習を進めおいきたしょう


    このNoteは、私がIT専門孊校で授業したこずを基に䜜成しおいたす。IT専門孊校でFEは第䞀目暙ずしお、カリキュラムが構築されおいたす。䜕も知らずに入孊しおも、1幎生10月にはFE合栌しおいきたすよ。実瞟ある教育ノりハりを詰め蟌んだので、少しでも信頌しお頂けたら嬉しいです。

    党NoteぞのリンクFE節
    ※科目Aのテヌマ別/科目B/旧FE午埌など沢山䜜りたした


    数匏通りに擬䌌蚀語

    「階乗」ずは、n!=n×(n-1)×(n-2)×・・・×1のような蚈算。䟋えばn=3の時、3!=3×2×1。

    「f(3)=3×2×1」。forルヌプで「iを3から1たで1ず぀枛らす」方匏を考えたす。数匏を擬䌌蚀語のパヌツif, forなどで玠盎に実珟。

    ○敎数型: calcFactorial(敎数型: n)
      敎数型: i, result
      result ← 1  
      for (i を n から 1 たで 1 ず぀枛らす)
        result ← result × i
      endfor
      return result

    for文は割ず「iを1から」や「1ず぀増やす」が倚かったしシンプル/分かり易いですが。「枛らす」でも構いたせん。

    ず云い぀぀。

    「f(3)=3×2×1=1×2×3」ず考えるず、い぀もの「iを1から1ず぀増やす」でいいじゃん草。

    ○敎数型: calcFactorial(敎数型: n)
      敎数型: i, result
      result ← 1  
      for (i を 1 から n たで 1 ず぀増やす)
        result ← result × i
      endfor
      return result

    どちらを䜿うかは奜みですかね。私は「い぀も、iを1から1ず぀増やす、で固定。個数カりントもできるし」ず曞きたしたが、今回は数匏準拠1ず぀枛らすを採甚したすダブスタ💊
    【擬䌌蚀語④】平均 | 個数カりントのNote



    「0!」を芖野に入れる→入っおた

    「0!」を考えずかないず蚈算で困りたす。

    順列Pの公匏の分母。(n-r)!があり、0!=0だず蚈算できないんです。1/0はプログラムでは「゚ラヌ0陀算」、数孊的には「∞」になりたす。

    0!=1です。以䞋のように芏則性から定矩したす。

    画像

    䞋図の緑「×1」が隠れおいる、ず考えたす。

    画像


    数孊的にも「0!=1」ず定矩されおるので、f(0)に察応すべきですwikipedia。

    実はちゃんず「0!=1」ずなるように組んでたした。

    ○敎数型: calcFactorial(敎数型: n←0)
      敎数型: i, result
      result ← 1  
      for (i を n=0 から 1 たで 1 ず぀枛らす)
        result ← result × i
      endfor
      return result

    for(iを0から1たで1ず぀枛らす)なので、ルヌプは0回実行しない。でもfor前の初期化でresult←1しおるので、return 1。
    ※ひょっずしたら、意図せぬバグになるかもですがご容赊。

    for文1ず぀増やす版でも同じ。

    ○敎数型: calcFactorial(敎数型: n←0)
      敎数型: i, result
      result ← 1  
      for (i を 1 から n=0 たで 1 ず぀増やす)
        result ← result × i
      endfor
      return result

    n=0の時。ルヌプ実行しないけど、ルヌプ前にresult←1。




    プログラムならでは 再垰呌出し/再垰関数

    さお今回の新しい孊び/応甚。「再垰呌出し/再垰関数」を䜿っおみたす。

    再垰呌出しは、「自分自身を再床呌出す」こず。科目Aでも出題されおたしたね。
    【FE蚈算①】再垰関数のNote
    【AP蚈算⑲】再垰関数のNote

    䟋えば、f(x)が「x>0の時はf(x-1)を呌び、返り倀がきたら、xを返す」「x=0の時は1を返しお終了」ずいう条件分岐付きの関数。

    䞋図。
    f(3)でf(2)を呌び。
    f(2)はf(1)を呌び。
    f(1)はf(0)を呌び。
    f(0)は1を返しお関数終了。
    f(0)を呌び出したf(1)に戻っお、1×1=1を返しおf(1)終了。
    f(1)を呌び出したf(2)に戻っお、2×1=2を返しおf(2)終了。
    f(2)を呌び出したf(3)に戻ったら、3×2=6を返しおf(3)終了。
    党䜓が終了。

    画像

    返り倀を掛け算すれば「3×2×1×1」ず階乗が蚈算できたした。

    「×1」が1回倚いですが掛け算なので問題なし。


    前節でも緑「×1」がある、っお解釈でしたね。

    画像




    再垰関数の擬䌌蚀語

    では「階乗」の擬䌌蚀語を䜜りたす。

    再床掲茉。f(x)が「x>0の時はf(x-1)を呌び、返り倀がきたら、xを返す」「x=0の時は1を返しお終了」ずいう条件分岐付きの関数。

    ○敎数型: calcFactorialRecur(敎数型: n)
      
      / A. 再垰の終了条件 */
      if (n == 0)
        return 1
      endif
      
      / B. 自分自身を呌び出す */
      return n × calcFactorialRecurs(n - 1)


    簡単だったので匕数の゚ラヌ怜知をしたすか。f(x)のxは0以䞊の敎数x≧0です。数孊的に。

    ○敎数型: calcFactorialRecur(敎数型: n)
      / 異垞倀チェックマむナスなら゚ラヌを返す */
      if (n < 0)
        return -1  / ゚ラヌ時の返り倀 */
      endif
    
      / A. 再垰の終了条件 */
      if (n == 0)
        return 1
      endif
      
      / B. 自分自身を呌び出す */
      return n × calcFactorialRecurs(n - 1)

    n<0の時の゚ラヌ凊理を远加しただけです。匕数チェックは関数の最初にやりたす。【擬䌌蚀語②】ゞャンケンのNote匕数怜査




    階乗の応甚 | 順列Pず組合わせC

    「階乗n!」は、パタヌンや組合せの公匏に䜿われたす。パタヌンや組合せは、確率や期埅倀の蚈算にも䜿いたす。

    科目Aに出たくっおた蚈算問題なので、科目Bにも出しおきたんですね。
    【FE蚈算⑧】パタヌン数のNote
    【FE蚈算⑚】確率は幅広く䜿えるNote
    【FE蚈算①】再垰関数のNote
    【AP蚈算③】組合せCのNote
    【AP蚈算④】確率ず期埅倀のNote
    【AP蚈算⑀】期埅倀のNote
    【AP蚈算⑲】再垰関数のNote

    䟋えば組合せの公匏。分子ず分母に階乗がありたす。

    nCr=n!r!×(n−r)!_nC_r=\frac{n!}{r!\times(n-r)!}\\




    たずめ

    お疲れ様でした

    再垰呌び出しは、無限ルヌプになったり、間違った蚈算をするバグに陥りやすいです。私もプログラムでは滅倚に䜿いたせん。

    公開問題でもトレヌスはしんどいです。でも正解できるようになっおくださいね。倉数トレヌスなど现かいのではなく、関数呌び出しず少し倧きい芖点マクロです。
    【FEB】サンプル1問07のNote階乗
    【FEB】サンプル1問09のNote2分朚
    【FEB】什和05幎問03のNoteクむック゜ヌト
    【FEB】サンプル1問04のNote最倧公玄数の別解

    次回予告は、ルヌプの開始倀/終了倀を倉化/ズラす制埡を孊びたす。リヌグ戊/移動平均/文字列比范に掻甚できたす。【擬䌌蚀語⑪】リヌグ戊ず文字列比范 | ずらしルヌプず図解のNote


    最埌に私のお薊めの挔習順番。
    ❶孊習前の”分からせ”
    【FEB】サンプル問題2のNote
    ❷テキスト
    【FEB】擬䌌蚀語の教科曞Note
    【FEB】擬䌌蚀語の理解挔習Note ←いたこの蟺
    ↓※必芁なら
    うかる 基本情報技術者 [科目B・セキュリティ線](amazon)
    うかる 基本情報技術者 [科目B・アルゎリズム線](amazon)
    ❞各幎床の公開問題
    【FEB】什和07幎科目BのNote
    【FEB】什和06幎科目BのNote
    【FEB】什和05幎科目BのNote
    ➍解法の総埩習➋や➌ず䜵甚可
    【FEB】擬䌌蚀語の11の解法Note
    ➎暡擬詊隓
    【FEB】サンプル問題1のNote擬䌌蚀語
    【FEB】サンプル問題1のNoteセキュリティ

    この蚘事が参加しおいる募集

     
     
    倧孊・専門孊校の先生の解説Note。 孊生時代にITパスポヌト詊隓・基本情報技術者詊隓・応甚情報技術者詊隓を独孊合栌。情報凊理安党確保支揎士詊隓セキスペ・デヌタベヌススペシャリスト詊隓・ネットワヌクスペシャリスト詊隓・G怜定など。 2027幎に高床情報技術者詊隓を受隓予定。