再帰定義を理解しようと努力しているのですが、どのサイトを見てもわかりやすい説明がされておらず、理解が難しいです。
現在再帰定義を使って、素数判定(入力した数字をtrueかfalseで判定)をしようと思うのですが、道筋も見えず困っております。
考え方だけでもご教授いただければ幸いです。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答4件
0
2つの方法を書いてみました。
- prime?(n)
2 .. n の平方根のどの数でも割り切れないなら 素数。 - prime2?(n)
n を割り切る最大の数が 1 なら 素数。
10000 までの数で ruby の Prime#prime? と判定結果が同じ事も確認しています。
参考情報:
- http://www.is.tsukuba.ac.jp/~kam/plm2015/function.html のページ中の素数の判定方法の例
ruby
1# See 2# http://www.is.tsukuba.ac.jp/~kam/plm2015/function.html 3# > OCaml での再帰関数 4 5def prime?(n) 6 # n が, 2 から k までのすべての整数で割り切れないかを調べる 7 def notdivall_upto(n, k) 8 if k < 2 9 true 10 else 11 (n % k != 0) && notdivall_upto(n, k - 1) 12 end 13 end 14 15 return false if n < 2 16 # 2 から √n までで割り切れないなら素数 17 notdivall_upto(n, Math.sqrt(n).floor) 18end 19 20def prime2?(n) 21 # n を割りきる数で、 m 以下で最大のものを求める。 22 def largest_factor_upto(n, m) 23 (n % m == 0) ? m : largest_factor_upto(n, m - 1) 24 end 25 # n の最大の約数が 1 なら素数 26 return false if n < 2 27 largest_factor_upto(n, Math.sqrt(n).floor) == 1 28end 29 30# ---- Prime.prime? と判定結果を比較する。 31require 'prime' 32 33(1..9999).each do |n| 34 # puts n if prime?(n) 35 if prime?(n) != Prime.prime?(n) || prime2?(n) != Prime.prime?(n) 36 puts "#{prime?(n)} #{prime2?(n)} #{Prime.prime?(n)}" 37 end 38end
投稿2015/10/28 14:40
総合スコア22324
0
ベストアンサー
素数の判定だったら、調べる対象の数をn
として
n
がm
で割り切れるか調べる。
m=1
の場合はtrue
割り切れた場合はfalse
割り切れない場合はm-1
について調べる。
m=n
を初期値とすればこれが素数判定になることはわかると思います。
(実際はm=√nの整数部
でいいのですが本筋ではないので置いておく)
これを素直に関数に直せば
f(n,m) = true (if m=1) false (else if n%m = 0) f(n,m-1) (otherwise)
使いやすくすると
IsPrime(n) = f(n,n)
考えるコツですが、
「判断つかない場合は次のステップに任せる」ことです。
数列で言う漸化式を作るようにします。
階乗で言えば
fact[n] = n・(n-1)・(n-2)・...・1
という発想ではなく
fact[n] = n・fact[n-1]
ということです。
投稿2015/10/28 09:55
総合スコア13512
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
再帰的定義=>帰納的定義のことでしょうか?
wikipediaによると、素数は再帰的定義で次のように表現できるそうです。
・2は最小の素数である。
・任意の正の整数で、自身より小さい素数で割り切れない数は素数である。
最も高速で効率が良いかはさておき
これに従って再起関数を構築するなら、
ある数nと判定対象のxを与えて、nが素数で無いか、素数であってもxを割り切れない場合nに1を加算して再起呼び出し。nがx/2以上になった場合はtrueを返す。という風に設計すればよいかと思います。
凄い適当ですが、これでも動くと思います。多分
ruby
1def fn(n,x) 2 return true if n > x/2 3 return false if x%n == 0 4 return fn(n+1,x) 5end 6 7puts fn(2,101)
※面倒だったので、nが素数かどうかという判定は省きました。
投稿2015/10/28 09:53
編集2015/10/28 09:56総合スコア2068
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
こんばんわ。
再帰呼び出しについての説明なら、このページの階乗の計算の話がよくできていると思います。
http://www.geocities.jp/m_hiroi/light/abcruby07.html
確認済みならごめんなさい。
素数判定のプログラムを作成するのなら、再帰呼び出しを使う必要は無いですよ。
僕はRubyの文法がわからないので、擬似言語を使って素数判定関数を記述すると
以下のようになります。
//
// 素数判定関数
//
// 引数の整数が素数ならtrueを、素数でないならfalseを返す
//
function is_prime_number(x)
flag = true
for i = 2, x-1, 1
x ÷ i の余りが0の場合、flagにfalseをセットし、ループを抜ける
end for
return flag
end function
投稿2015/10/28 09:02
総合スコア480
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。