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

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

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

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

Q&A

解決済

3回答

1385閲覧

再帰のプログラムについて

tsukacchan

総合スコア17

Ruby

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

0グッド

0クリップ

投稿2017/11/11 01:13

再帰の勉強中である問題を解いているのですが解答を見ても分かりません。
分かる方おしえていただけないでしょうか?

問題
長さn(cm)の1本の棒を1(cm)単位に切り分けることを考えます。ただし1本の棒を一度に切る
ことができるのは1人だけです。切り分けられた棒が3本あれば、同時に3人で切ることができます。
最大m人の人がいるとき、最短何回で切り分けられるかを求めてください。

解答
def cutbar(m, n, current) #current 現在の棒の数
if current >= n then
0 #切り終えた
elsif current < m
1 + cutbar(m, n, current * 2) #次は現在の2倍になる
else
1 + cutbar(m, n, current + m) #はさみの数だけ追加
end
end

puts cutbar(3, 20, 1)
puts cutbar(5, 100, 1)

質問は次の2つです。

まず3行目ですが0とはいったい何をしているのでしょうか?
よく再帰の例題にある階乗を求める問題などではreturn文などが
書いてありますが、return文の省略と考えていいのでしょうか?
次に5行目の1 + cutbar(m, n, current * 2)
の1の意味が分かりません。この1は何の意味があるのでしょうか?

分かる方教えてください。
よろしくお願いいたします。

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

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

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

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

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

guest

回答3

0

ベストアンサー

Ruby

1def cutbar(m, n, current) #current 現在の棒の数 2 if current >= n then 3 0 #切り終えた 4 elsif current < m 5 1 + cutbar(m, n, current * 2) #次は現在の2倍になる 6 else 7 1 + cutbar(m, n, current + m) #はさみの数だけ追加 8 end 9end 10 11puts cutbar(3, 20, 1) 12puts cutbar(5, 100, 1)

ご質問の際、コードは上のように囲み、(方法はヘルプをお読みください)
回答者が見やすいようにしてください。ご協力お願いします。
なお、インデントは手動で付けました。


3行目ですが0とはいったい何をしているのでしょうか?

再帰の停止条件部分です。再帰でループを書く場合、
ループを止めるために、上のif文とともに、こう書くのがパターンです。

return文の省略と考えていいのでしょうか?

微妙に違っていて、Rubyはメソッドの内で最後に評価された値を、
そのメソッドのreturn値にする、という暗黙のルールがあります。

0の行自体にreturnが省略されているわけではなく、
0の後は「if~elsif~else~end」の部分を抜けて、
さらにdefに対応したendで抜けます。

この1は何の意味があるのでしょうか?

棒を切る回数を足しています。


関数型プログラミングに慣れてないと、
少ないコードでも読むのが難しいかもしれません。

理解するためには、最初のうちは逐次で、次はどこの行に飛ぶのか、
一行ずつ追って読むことをオススメします。
そのとき、再帰のループ構造を意識してください。

p current

また、たとえば冒頭「def」の行の下に上のような
「p」メソッドを入れてプリント文デバッグをするとか、
プログラムなのだから書き足して情報量を増やすと、
複雑な問題の理解を助けると思います。

投稿2017/11/11 02:33

LLman

総合スコア5592

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

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

0

長さn(cm)の1本の棒を1(cm)単位に切り分けることを考えます。ただし1本の棒を一度に切る

ことができるのは1人だけです。切り分けられた棒が3本あれば、同時に3人で切ることができます。
最大m人の人がいるとき、最短何回で切り分けられるかを求めてください。

トンチのクイズかな?
初期の棒が2cmなら何人居ようとハサミ1回。
初期の棒が101cmなら何人居ようとハサミ100回。

つまり、n - 1を返す関数にすれば解決。
いやいや、1行で済んで良かったね。


でもまぁ、これだと再帰使う意味ないし、
下記のように言い換えてみたら問題としては納得出来るんだけど…

1人の作業者は1秒に1度のペースでハサミを入れる事ができます。

m人の作業者で切り分けると最低何秒かかるでしょう?

これかなり複雑だね。

作業者は1回ハサミを入れる度に倍の人数(1, 2, 4, 8...)が投入出来るようになるわけだね。
でも5人ならどうするの?
2回ハサミ入れたら次は4人で、1人余ってる状態になるから…
もし100cmを5人で担当するなら初手で40cm地点にハサミを入れないと綺麗な5等分にはできない。

うーん……再帰は棒の分割に注力というロジックならいけるか?
引数は下記の3個

  • 経過時間: 0秒
  • 担当人数: (自分含めて)5人 ← でもハサミを入れられるのは自分だけ
  • 棒の長さ: 100cm

担当人数が5人なので(100 * (5 / 2).floor / 5).ceilの位置にハサミをいれて棒を分断、
下記2つの配列を作成してそれぞれ再帰関数にかける。
そして受け取った経過時間秒数のMAXを返させる。
(二回目以降は配列っぽく記載、経過時間, 担当人数, 棒の長さの順)

  • [1, 2, 40] -> [[2, 1, 20], [2, 1, 20]]
  • [1, 3, 60] -> [[2, 1, 20], [2, 2, 40]]

次のループも同じ事をやり、それぞれ下記条件の配列になりループが回る
担当人数が1人になったら長さ-1回だけハサミを入れてバラバラにすればいい

  • [2, 1, 20] -> 2 + (20 - 1) = 21s
  • [2, 1, 20] -> 2 + (20 - 1) = 21s
  • [2, 1, 20] -> 2 + (20 - 1) = 21s
  • [2, 2, 40] -> [[3, 1, 20], [3, 1, 20]] -> [22s, 22s] -> 22s

お、これなら確かに再帰で書けるね。
もし待ち作業担当者がまだ居る状態で棒が1cmになってしまったら今の経過時間をそのまま返せば良い。


でも、持ち替えNGとは書いてないんだよね。
なら毎秒一番長い順から順番に担当者に半分にカットさせていくと、
最終的に2cmの棒きれが50個弱出来るから、2cmの棒きれ50個弱を5人皆がそれぞれ手にとって半分にカットしていく光景が見れるわけだね。

でもそうなると、5人揃うまでに3秒かかるから、1 + 2 + 4 = 7回ハサミを入れることが可能。
100cmの棒きれは99回ハサミを入れれば1cm毎になるので、後92回ハサミを入れればバラバラになる。
つまり3秒+ (92回 / 5人).ceilで答えが出てしまう。

なんてことだ……やはり再帰は不要だったのだ!
あ、でもでも3秒で7回刻むロジックは再帰で書くのが一番スッキリするね!
そこかよ!って感じで正直微妙だけど…

投稿2017/11/11 08:33

編集2017/11/11 13:15
miyabi-sun

総合スコア21158

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

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

0

まず3行目ですが0とはいったい何をしているのでしょうか?

これは再帰についての質問とは言えないようです。Rubyのプログラムで

ruby

1def func(n) 2 if n > 0 then 3 1 4 elsif n < 0 5 -1 6 else 7 0 8end

これで1, -1, 0が何を表しているかを尋ねているだけですよね?
rubyではif文も「式」の一つで結果を持ちます。また関数の最後に書かれている式の値が関数の値(戻り値)になります。

1の意味が分かりません

この関数が何を返すのかを考えてください。切る回数ではないでしょうか?逆に1を足さない場合結果がどうなってしまうのかを考えてみるとよいと思います。

投稿2017/11/11 02:17

KSwordOfHaste

総合スコア18392

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問