1
私は方程式の解の数を計算したいと思っていましたが、私はリードを得ることができません。式は次のとおりです。制約があるn個の変数を持つ方程式の解の数
私が得ることができるすべては、のような何かをすることによって、ある
しかし、私はこの上で続行する方法がわかりません。
私は方程式の解の数を計算したいと思っていましたが、私はリードを得ることができません。式は次のとおりです。制約があるn個の変数を持つ方程式の解の数
私が得ることができるすべては、のような何かをすることによって、ある
しかし、私はこの上で続行する方法がわかりません。
私はdynamic programmingを使ってこれを解決しようとしています。
ここであなたが始めるためにいくつかの擬似コードです:
Procedure num_solutions(n, k, m):
# Initialize memoization cache:
if this function has been called for the first time:
initialize memo_cache with (n+1)*(k+1)*(m+1) elements, all set to -1
# Return cached solution if available
if memo_cache[n][k][m] is not -1:
return memo_cache[n][k][m]
# Edge case:
if m is equal to 1:
# Solution only exists if 1 <= m <= k
if n >= 1 and n <= k, set memo_cache[n][k][m] to 1 and return 1
otherwise set memo_cache[n][k][m] to 0 and return 0
# Degenerate case: No solution possible if n<m or n>k*m
if n < m or n > k * m:
set memo_cache[n][k][m] to 0 and return 0
# Call recursively for a solution with m-1 elements
set sum to 0
for all i in range 1..k:
sum = sum + num_solutions(n - i, k, m - 1)
set memo_cache[n][k][m] to sum and return sum
は、幾何学的合計は、二項定理と分母のための二項シリーズを適用します。 – LutzL