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

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

ただいまの
回答率

87.49%

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

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 1,014

score 17

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

問題
長さ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は何の意味があるのでしょうか?

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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

+2

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)

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


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

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

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

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

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

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

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


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

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

p current

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

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

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

def func(n)
  if n > 0 then
    1
  elsif n < 0
    -1
  else
    0
end


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

1の意味が分かりません

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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回刻むロジックは再帰で書くのが一番スッキリするね!
そこかよ!って感じで正直微妙だけど…

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 87.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る