11

したがって、この問題または同様の問題に対するいくつかの解決策を見てきましたが、なぜ 私のものが機能しないのかを本当に知りたいです。私が見つけた多くの解決策よりもはるかに読みやすいので、うまく機能させたいです!

2か月後に繁殖を開始する1組のウサギから始めます。n か月実行すると、ウサギは m か月生きた後に死亡します。'6 3' の入力は 4 を返すはずですが、3 を返します。

#run for n months, rabbits die after m months.
n, m = input("Enter months to run, and how many months rabbits live, separated by a space ").split() 
n, m = int(n), int(m)
generations = [1, 1, 2] #Seed the sequence with the 1 pair, then in their reproductive month.
def fib(i, j):
    count = 3 #we start at the 3rd generation.
    while (count < i):
        if (count < j):
            generations.append(generations[count-2] + generations[count-1]) #recurrence relation before rabbits start dying
        else:                                                               #is just the fib seq (Fn = Fn-2 + Fn-1)
            generations.append((generations[count-2] + generations[count-1]) - generations[(count-j)])  #Our recurrence relation when rabbits die every month
        count += 1                                                          #is (Fn = Fn-2 + Fn-1 - Fn-j)
    return (generations[count-1])


print (fib(n, m))
print ("Here's how the total population looks by generation: \n" + str(generations))

ありがとう=]

4

5 に答える 5

2

これは、SpaceCadets の質問の回答からコピーされ、「未回答」の質問リストから削除するのに役立ちます。

ここでの 2 つの鍵は、ツリーを多数に描画することと、死亡の第 1 世代と第 2 世代のベース ケース チェックを確実に含めることでした (どちらの場合も -1 であり、入力に依存するものです)。

したがって、3つの潜在的なケース。死亡を考慮する必要がない場合の通常の fib シーケンス、再帰関係 Fn-2 + Fn-1 - Fn-(monthsAlive+1) で最終シーケンスを初期化するための第 1 世代と第 2 世代の死亡

これらのチェックの 1 つまたは 2 つをマージしてアルゴリズムをより効率的にする方法があると確信していますが、現時点では、大規模なテスト ケース (90、17) を即座に正しく解決しました。だから私は幸せです。

教訓: ホワイトボード全体を使用する。

#run for n months, rabbits die after m months.
n, m = input("Enter months to run, and how many months rabbits live, separated by a space ").split() 
n, m = int(n), int(m)
generations = [1, 1] #Seed the sequence with the 1 pair, then in their reproductive month.
def fib(i, j):
    count = 2
    while (count < i):
        if (count < j):
            generations.append(generations[-2] + generations[-1]) #recurrence relation before rabbits start dying (simply fib seq Fn = Fn-2 + Fn-1)
        elif (count == j or count == j+1):
            print ("in base cases for newborns (1st+2nd gen. deaths)") #Base cases for subtracting rabbit deaths (1 death in first 2 death gens)
            generations.append((generations[-2] + generations[-1]) - 1)#Fn = Fn-2 + Fn-1 - 1
        else:
            generations.append((generations[-2] + generations[-1]) - (generations[-(j+1)])) #Our recurrence relation here is Fn-2 + Fn-1 - Fn-(j+1)
        count += 1
    return (generations[-1])


print (fib(n, m))
print ("Here's how the total population looks by generation: \n" + str(generations))
于 2013-09-03T01:08:48.827 に答える
1

ここで再帰関係には 2 つのケースがあります。nはシーケンスが実行される月数であり、mはペアが存続する月数であると考えます。

1) シーケンス内のインデックス (0 ベース) がm未満の場合:
通常のフィボナッチ(現在の期間 = 前の期間 + その前の期間)。

2) インデックスがm以上の場合:
現在の用語 = ( m - 1 ) 前の用語の合計 (直前の用語は無視)。

以下は、 Aという名前のシーケンスとm = 5の例です:
A5 = A0 + A1 + A2 + A3 (4 つの用語、つまり m - 1、直前の用語は無視)
。m = 3 の
場合: A3 = A0 + A1 (2 項のみ、m - 1 )

.

以下のコード (Python) には、シーケンスの最初の [1, 1] があるため、オフセットが 2 あります。 

def mortal_rabbits(n, m):
    sequence = [1, 1]

    for i in range(n - 2):
        new_num = 0
        if i + 2 < m:
            #Normal fibonacci - No deaths yet
            new_num = sequence[i] + sequence[i + 1]
        else:
            #Different reoccurence relation - Accounting for death
            for j in range(m - 1):
                new_num += sequence[i - j]

        sequence.append(new_num)

    return sequence
于 2016-01-20T13:31:28.887 に答える
1

合併症を無視すると、世代内のウサギのペアの数の式は次のようになります。

ウサギのペア

リストを使用する場合、これは問題を引き起こします。なぜなら、 の場合n == m、位置 にある値が必要になるため-1です。これは明らかに範囲外です。

def rabbit_pairs(n, m):
    sequence = list()
    for i in range(n):
        if i < 2:
            # Normal Fibonacci initialization
            total = 1
            sequence.append(total)
        elif (i < m) or (m == 0):
            # Normal Fibonacci calculation
            total = sequence[i - 1] + sequence[i - 2]
            sequence.append(total)
        elif i == m:
            # Now we need R(n - (m + 1)), but i - (m + 1) < 0, so we have to
            # provide the missing value
            total = sequence[i - 1] + sequence[i - 2] - 1
            sequence.append(total)
        else:
            # i - (m + 1) >= 0, so we can get the value from the sequence
            total = sequence[i - 1] + sequence[i - 2] - sequence[i - (m + 1)]
            sequence.append(total)
    return total
于 2016-02-26T06:50:57.113 に答える