HOME»基本情報技術者試験掲示板»平成28年秋期試験午前問題 問7
投稿する
[2077] 平成28年秋期試験午前問題 問7
ニコりんさん(No.1)
以下の解説になっているのですが、modで計算した結果で求めた余り6がなぜ、yの値となるのかが分からないので教えてもらえないでしょうか？
設問の再帰関数 F(231，15) をトレースすると次のようになります。
F(231，15)
＝F(15，231 mod 15)＝F(15，6)
＝F(6，15 mod 6)＝F(6，3)
＝F(3，6 mod 3)＝F(3，0)
＝3
設問の再帰関数 F(231，15) をトレースすると次のようになります。
F(231，15)
＝F(15，231 mod 15)＝F(15，6)
＝F(6，15 mod 6)＝F(6，3)
＝F(3，6 mod 3)＝F(3，0)
＝3
2019.11.13 08:12
ゆいまさん(No.2)
質問の意図を誤解しているかもしれませんが、説明は次の通りです。
「y>0 のとき F(x,y) = F(y, x mod y) 」と決められているということは、
左辺を計算するには(より簡単な)右辺を計算すればよいということです。
すなわち、右辺の第一引数には左辺の第二引数 y を与え、右辺の第二引数
には x mod y の値を与えて計算すればよいわけです。
x=231, y=15 の場合、231 mod 15 = 6 ですから、F(231,15) = F(15,6) です。
この結果、15が新しい x、6が新しい y となります。
この操作を新しい y が0になるまで繰返すことで最終結果が得られます。
参考：これは x と y の最大公約数を求めるユークリッドのアルゴリズムを
再帰関数の形で表現したものです。
「y>0 のとき F(x,y) = F(y, x mod y) 」と決められているということは、
左辺を計算するには(より簡単な)右辺を計算すればよいということです。
すなわち、右辺の第一引数には左辺の第二引数 y を与え、右辺の第二引数
には x mod y の値を与えて計算すればよいわけです。
x=231, y=15 の場合、231 mod 15 = 6 ですから、F(231,15) = F(15,6) です。
この結果、15が新しい x、6が新しい y となります。
この操作を新しい y が0になるまで繰返すことで最終結果が得られます。
参考：これは x と y の最大公約数を求めるユークリッドのアルゴリズムを
再帰関数の形で表現したものです。
2019.11.13 10:15
ニコりんさん(No.3)
分かり易い説明ありがとうございます。感動しました。納得です！！
2019.11.13 13:04
管理人(No.4)
解説が丁寧さに欠けていましたね...。
ゆいまさんの投稿の一部を解説に取り入れさせていただきます。
ゆいまさんの投稿の一部を解説に取り入れさせていただきます。
2019.11.13 15:49
ひろじいさん(No.5)
この投稿は投稿者により削除されました。(2019.11.15 16:09)
2019.11.15 16:09