質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

Q&A

解決済

4回答

2206閲覧

再帰的定義がよくわかりません

Dach

総合スコア17

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

0グッド

0クリップ

投稿2015/10/28 08:28

再帰定義を理解しようと努力しているのですが、どのサイトを見てもわかりやすい説明がされておらず、理解が難しいです。
現在再帰定義を使って、素数判定(入力した数字をtrueかfalseで判定)をしようと思うのですが、道筋も見えず困っております。
考え方だけでもご教授いただければ幸いです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

2つの方法を書いてみました。

  1. prime?(n)
    2 .. n の平方根のどの数でも割り切れないなら 素数。
  2. prime2?(n)
    n を割り切る最大の数が 1 なら 素数。

10000 までの数で ruby の Prime#prime? と判定結果が同じ事も確認しています。

参考情報:

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

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

素数の判定だったら、調べる対象の数をnとして

nmで割り切れるか調べる。
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

ozwk

総合スコア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
hirohiro

総合スコア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

srsnsts

総合スコア480

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問