スレ立てるまでもない質問はここで 113匹目at TECHスレ立てるまでもない質問はここで 113匹目 - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このスレッドのURL■項目テキスト108:デフォルトの名無しさん 11/08/16 06:14:37.64 昭和48年ごろでも、アンモニアの臭いする納豆がいっぱい売られてたなあ 109:デフォルトの名無しさん 11/08/16 14:36:17.44 宿題系なんですが、該当スレがみつからなくて、、ここで教えてください。 F(m ,n) { if (m == 0) { n + 1 } else { if (n == 0) { F(m-1, 1) }else{ F(m-1, F(m, n-1)) } } } 上記のプログラミについて、まず何やってるのかイマイチわかってないのですが問題が出ています。 解答の添削やご意見ください。 (1) 任意の非負数nについて、F(1, n)がn+2である事をしめせ。 nに関する数学的帰納法で示す。まずF(1, 1) == 3である事はプログラムを追うことで明か そしてF(1, n)==n+2を仮定して、F(1, n+1) == n+3を示す。 はじめの関数実行時に、1!=0, n+1!=0であるため、F(1-1, F(1, n+1-1))が実行される。 ここで引数がF(1, n)であるため仮定より、F(0, n+2)となり、プログラムの処理を追いn+3 が戻る事が確認できる。よってF(1, n) == n+2→F(1, n+1) == n+3となり、問の命題が 証明された。 (2) スタックを用いた再帰関数の実現について説明し、O(2, n)で実行する時の必要なスタック領域についてオーダを示せ。 関数内で関数を呼ぶ際に、現在のローカル変数のデータをスタックにつむ。関数から戻った時に積んだデータを取り出す。 このプログラムでローカル変数はm, nのみのため、スタックには常に2つのデータが格納される。またプログラムの解析 によって、木の高さは2n+3であるため、データ量は4n+6でオーダーはO(n) 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch