漸化式を求めたいがうまくかけない

Question

1 3 7 15・・・という数列のn番目の項を求めたいです。(2^(n-1)ずつ値が増える)

def get_total(n):
    if n == 1:
        return 1
    else:
      for i in range(n):
        x = 2 ** (n-1)
        y = 1 + x
        get_total(x)
        return y

とコードを書いたのですが、nが１番目ではない時のelse以下の表現が思いつきません。再帰呼び出しを使おうと思ったのですが・・・。どのようにかけますか？

Answer 1

a[1] = 1
a[n] = a[n - 1] + 2^(n - 1)

という漸化式を使うのが一つです。
または漸化式を再帰的に適用していくと一般解が導けそうですね

a[n] = 2 ^ (n - 1) + 2 ^ (n - 2) + 2 ^ (n - 3) ・・・ + 1

したがって
**a[n] = 2 ^ n - 1 **
ですね。プログラムで計算する必要なしです。べき乗記号は^としました。

Comments

[anndonut]

まー、あなたの言いたいことはわかるんですけどね。問題に、(2^(n-1)ずつ値が増える)と書いてあるのだからそれを愚直に表現してやればいいじゃないですか。最初のうちは楽しくプログラミングできればいいのですよ。

[_Victorique__]

ここは考えの押し付けをする場所ではありません。いろいろな回答があって良い場所です。質問者への気づきにもなります。

[anndonut]

おっしゃるとおりだと思います。すみませんでした。

Answer 2

３通りの方法で計算し、値を比較するようにしてみました。

xxx.py

# 繰り返し計算
def get_total_loop(n):
    sum = 1
    for i in range(2, n + 1):
        sum += 2 ** (i - 1)
    return sum

# 再帰で計算
def get_total(n):
    if n == 1:
        return 1
    else:
        return get_total(n - 1) + 2 ** (n - 1)


# 漸化式を解いた結果で計算
def get_total_c(n):
    return 2 ** n - 1

for i in range(1, 10):
    print(str(get_total_loop(i)) + ", " +
          str(get_total(i)) + ", " +
          str(get_total_c(i)))

実行結果：

$ python xxx.py
1, 1, 1
3, 3, 3
7, 7, 7
15, 15, 15
31, 31, 31
63, 63, 63
127, 127, 127
255, 255, 255
511, 511, 511

Answer 3

漸化式は、a[1] = 1, a[n+1] = a[n] + 2^nですね。
だから、コードはこんな感じになります。

def get_total(n):
    if n == 1:
        return 1
    else:
        return get_total(n-1) + 2 ** (n-1)

print([get_total(i) for i in range(1, 5)])

Answer 4

すみません、上の方の回答が正しかったようです。
追記します。

追記
差別化を図るために簡略化したものを書きました。

def get_n(n):
    return 1 if n == 1 else get_n(n-1)+2**(n-1)

Comments

[anndonut]

コードは書いたらきちんと実行させましょう。
あと、get_totalをget_total(n)に直して1~4項目を表示させたら[2, 3, 5, 9]になりました。

[anndonut]

まさかreturn 2**n - 1と言いたかったのでは？

[_Victorique__]

結果的にはそういう事ですね。再帰を使うならそちらが正しいと思います。