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

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

ただいまの
回答率

88.61%

python 漸化式

解決済

回答 4

投稿

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

basketballpyth

score 17

漸化式を用いて数字を出力したいのですが自分で考えたコードだといちいち答えを出すのに何回も計算しなければなりません。
(例)get_total_xに5を入れるとしたら1/2.*get_total_x(n-1)+1に代入され
get_total_x(5-1)となりget_total_x(4)も計算しなければなりません。その次は3,2,1と計算されていきます。
その場合計算結果としては合っているのですが計算が遅くなってしまうのでスムーズに
一つ前の計算結果を用いて答えを出力したいのですがどのように変更したらよいのでしょうか。

def get_total_x(n):
if n == 0:
return 0
else:
return 1/2.*get_total_x(n-1)+1

def get_total_y(n):
if n == 0:
return 0
else:
return 1/3.*get_total_y(n-1)+2

def get_total_z(n):
if n == 0:
return 0
else:
return 1/4.*get_total_z(n-1)+3

for i in range(0,50):
print(str(get_total_x(i))+","+str(get_total_y(i))+","+str(get_total_z(i)))

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 4

+2

まず、提示コードでは計算時間≒get_total_xの呼び出し回数はn+1回で、漸化式を利用している以上、これより減らすことはできません。
しかしたとえばreturn 1/4.*get_total_x(n-1) + 1/4*get_total_x(n-1) + 1と書いた場合は、nが大きくなるにつれ計算時間は急速に増えます。
実際にまずn=20でやってみてください。さらにn=50だと計算終わらないと思います。

計算時間を抑えるには、一般的にはメモ化という手法をとります。
これは、計算済みの結果をどこかにメモしておき、すでに計算済みならメモしたものを返すことにより同じ計算をしないようにする手法です。

今回の例だと以下のようなコードになります。

def get_total_x(n,memo):

    # すでに計算済み
    if n in memo:
        return memo[n]

    ret = 0
    if n == 0:
        ret = 0
    else:
        ret = 1/4.*get_total_x(n-1,memo)+1/4.*get_total_x(n-1,memo)+1

    memo[n] = ret # メモに記録
    return ret

memo = {} # メモとして辞書を利用
print(get_total_x(50,memo)) # 1.9999999999999982

ちなみにこのメモ化を自動でやってくれるのがLouiS0616さんの回答にあるfunctools.lru_cacheです。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

+1

Python3.2以降であれば、functools.lru_cacheが使えます。
Python2.7のサポートは2020年に終了されますので、乗り換えを強く推奨します。

どうしても古いバージョンを使いたいなら、サードパーティライブラリを利用すると楽です。
StackOverflow - memoization library for python 2.7
GitHub - repoze/repoze.lru

コードの書き方について

teratailには、コードを見やすく表示する機能があります。
質問編集画面を開き、コードを選択した状態で<code>ボタンを押してください。
Python
特にPythonの場合、インデントが崩れるとコードの意味が変わってしまいます。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

checkベストアンサー

0

... 一つ前の計算結果を用いて答えを出力したい ...

メソッドに prev として、一つ前の計算結果を指定できるように書き換えてみました。
さらに get_total_x, get_total_y, get_total_z を別関数でなく、
一つの関数 get_total にまとめてみました。

xyz.py

def get_total(n, k, prev):
    if n == 0:
        return 0
    if prev == None:
        prev = get_total(n - 1, k, None)
    return 1.0 / (k + 1) * prev + k


p1 = None
p2 = None
p3 = None
for i in range(0, 10):
    p1 = get_total(i, 1, p1)
    p2 = get_total(i, 2, p2)
    p3 = get_total(i, 3, p3)
    print(str(i), ": ", p1, ",", p2, ",", p3)

実行例
前半は質問文にあるコードを 0..10 までループにして実行してます。
後半は上のコードを実行してます。
出力書式は異なってなすが、数値は同じになっています。
イメージ説明

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2018/12/08 22:08

    どのように実行されていくか前半のコードの詳しい解説お願いしてもよろしいでしょうか?

    キャンセル

0

(例)get_total_xに5を入れるとしたら1/2.*get_total_x(n-1)+1に代入され
get_total_x(5-1)となりget_total_x(4)も計算しなければなりません。その次は3,2,1と計算されていきます。

漸化式ってそういうものですよね?

一つ前の計算結果を用いて答えを出力したいのですがどのように変更したらよいのでしょうか。

何番目はこの式で求まるという式を導いて、それに当てはめればよいでしょう。
等差数列とか等比数列とかそんな感じですね。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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

関連した質問

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