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

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

ただいまの
回答率

90.48%

  • Ruby

    7919questions

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

  • ループ

    53questions

    ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

  • 再帰

    29questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。

2重の再帰はスタック配列を使わないとループに直せませんか?

解決済

回答 3

投稿

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

f_acid

score 31

再帰関数saikiを再帰しないnot_saikiに直したらメモリ不足で落ちました。
配列を使わなければもっといけるような気がするのですが…
どうにかなりませんか?数学には疎いので…

#saiki.rb
def saiki a,b,c
  if c==1
    return a*b
  elsif b==1
    return a
  else
    return saiki a, saiki(a, b-1, c), c-1
  end
end

def not_saiki a,b,c
  stack = []
  loop do
    if c==1
      b *= a
      return b if stack.empty?
      c = stack.pop
    elsif b==1
      b = a
      c = stack.pop
    else
      b -= 1
      stack << c-1
    end
  end
end

puts not_saiki *ARGV.map{|s|s.to_i}
$ ruby saiki.rb 3 3 9
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

checkベストアンサー

+2

回答ではありませんが、すこし調べてみたことを書きます。

ruby saiki,rb 3 3 1  => 9  = 3 * 3 = 3 ^ 2   
ruby saiki,rb 3 3 2  => 27 = 3 * (3 * 3) = 3 ^ 3
ruby saiki,rb 3 3 3  => 7625597484987 = 3 ^ 27 = 3 ^ (3 ^ 3)

確信はできませんが、 saiki(3, 3, 4) が 3 ^ (3 ^ (3 ^ 3)) となるとすると、
これ時点ですでに 通常のコンピュータ言語で扱える数の範囲を超えます。

7625597484987 を google 検索すると グラハム数というものが出てきます。
グラハム数

ruby コードから 再帰性を取り除くだけでは この関数の 一般項は結果の数が大きくなりすぎ 計算できないと思います。
(関数が呼ばれる回数も大変なことになってます。
 saikie 関数の先頭に puts "#{a}, #{b}, #{c}" をいれて プログラムを実行すると、とんでもない回数の呼び出しが発生することがわかります。

備考1
 ruby saiki.rb 3 3 4 は私の環境では ... 7267 levels のエラーがでました。
おそらく再帰のネストの限界が 7264  なのだとおもわれます。
ruby の再帰の深さ制限は制御が可能です。
$ export RUBY_THREAD_VM_STACK_SIZE=100000000
$ ruby saiki.rb 3 3 4
とすると、... 694457 levels... のエラーになります。

質問;
 この関数定義はどこから入手したものですか?
 この関数定義には なんらかの背景があるものと思います。
 その背景を知りたいです。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2015/05/10 17:30

    こんにちは。自分も、saiki(3,3,3)を紙と鉛筆で追って、3^(3^3)にたどり着きました。グラハム数なんていうのがあるのですね。勉強になりました!

    キャンセル

0

この再帰関数は,ある値以上で極めて巨大な数になるというアッカーマン関数に似た関数になっています.
通常のコンピュータでは到底扱えないくらいの桁数の数を生成するので,
単に再帰でないものに書きなおせるとは思えません.

この問題で問われていることはなんでしょうか?

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

どちらをベストアンサーにしようか迷ったのですが、結局自分がしたかったのは、
saiki(3,3,9)を、途中まででいいのでできるだけ計算したかったのです。
数学的手法を使って、なんとかメモリ不足にならないように出来ないか・・・?と思って質問しました。

この再帰関数は適当に計算量が大きくなりかつ計算が終わりそうなものを考えました。


・・・ただ今、様々な試行錯誤の結果、saiki(a,b,c)=a→b→c、なことが判明しました。
ものすごく先を越されてましたしこのsaikiただの劣化版ですね。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

  • 解決済

    Ruby FizzBuzzプログラム

    今までPHPでプログラムを書いていた者で、Rubyは初心者です。 まだ始めたばかりなのに、RubyでFizzBuzzを作ろうと思っています。 しかし、forなどを使って書いていると

  • 解決済

    Ruby FizzBuzzのプログラムを書き換えたい

    以前のFizzBuzzのプログラムは ifとelsifで条件分岐してコードを書いていたのですが、 他の書き方とかありましたら教えてください。 宜しくお願いします。

  • 解決済

    Ruby 問題

    Ruby初心者です。 まだRubyをはじめて本日で3日目の者です。 今までPHPで開発してきたのですが、Rubyを勉強することにしてみました。 FizzBuzzなどその他の問題をや

  • 受付中

    rubyの少し難しい問題です

    (,),(、)という4つの文字を要素とした配列があります。 この配列に対してカッコが正しく対応しているかどうかを調べるメソッドを定義してください。 下のコードは一体何をしているので

  • 解決済

    ruby にて "no method error"が出ます

    ruby にて2分木を作るアルゴリズムを書いています(参考:紀平拓男、春日伸弥「アルゴリズムとデータ構造」SoftbankCreative)まず Binary_Tree_Node 

  • 解決済

    バイナリーサーチに関して

    皆様、質問がございます。 よろしくお願い申し上げます。 下記のコードはバイナリーサーチ(二分探索)の処理を表しています。 下記のコードに"何かしら"の不備はあるのでしょうか??

  • 解決済

    任意の数字以外を入力した時に"無効な値です"と返す方法

    じゃんけんができるプログラムをRubyで以下のように組みました。 def janken   puts "[0]:グー\n[1]:チョキ\n[2]:パー"   player_han

  • 解決済

    ruby 文法(条件判定をメソッドにする方法)に関して教えて下さい。。

    1~50の数字で3で割り切れる時FIZZ,5で割り切れる時BUZZ,3と5で割り切れる時にはFIZZBUZZと出力されるように。 条件) FIZZ, BUZZ, FIZZBUZZ

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

  • Ruby

    7919questions

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

  • ループ

    53questions

    ループとは、プログラミングにおいて、条件に合致している間、複数回繰り返し実行される箇所や、その制御構造を指します

  • 再帰

    29questions

    情報工学における再帰とは、プログラムのあるメソッドの処理上で自身のメソッドが再び呼び出されている処理の事をいいます。