5

これが動的計画法としてタグ付けされた問題です（数Nが与えられ、2つ以上の連続する整数の合計としてそれを書く方法の数を見つけます）そして例15 = 7 + 8、1 + 2 + 3 + 4 + 5、4 + 5 + 6

私はそのような数学で解決しました：

a +（a + 1）+（a + 2）+（a + 3）+ ... +（a + k）= N

（k + 1）* a +（1 + 2 + 3 + ... + k）= N

（k + 1）a + k（k + 1）/ 2 = N

（k + 1）*（2 * a + k）/ 2 = N

次に、Nが（k + 1）と（2 * a + k）で割り切れる場合、O（sqrt（N））時間で答えが見つかることを確認します。

これが私の質問です。動的計画法によってこれをどのように解決できますか？複雑さ（O）は何ですか？

PS：質問が重複している場合は、すみません。検索しましたが見つかりました

4

6 に答える 6

1

Nが奇数の場合、この問題は N が を超えない約数を求めることと同じsqrt(N)です。( Nの場合でも、いくつかのひねりがあります。) そのタスクはO(sqrt(N)/ln(N))、素数のリストにアクセスできる場合に実行されますO(sqrt(N))。

ここで動的計画法がどのように役立つかわかりません。

于 2010-12-27T07:48:31.423 に答える
1

動的計画法を使用して、N までのすべての K について 1+2+3+...+K の合計を計算できます。sum[i]以下は合計 1+2+3+...+i を表します。

sum = [0]
for i in 1..N:
  append sum[i-1] + i to sum

これらの合計を使用すると、合計が N になる連続した整数のすべてのシーケンスをすばやく見つけることができます。合計 i+(i+1)+(i+2)+...j は に等しくなりsum[j] - sum[i] + 1ます。合計が N 未満の場合、 をインクリメントしますj。合計が N より大きい場合、 をインクリメントしますi。合計が N に等しい場合、カウンターと と の両方をインクリメントしiますj。

i = 0
j = 0
count = 0
while j <= N:
  cur_sum = sum[j] - sum[i] + 1
  if cur_sum == N:
    count++
  if cur_sum <= N:
    j++
  if cur_sum >= N:
    i++

ただし、この動的計画法のソリューションを使用するよりも優れた代替手段があります。配列はsum式 k(k+1)/2 を使用して数学的に計算できるため、追加のストレージを必要とせずにオンザフライで計算できます。さらに良いことに、各反復で作業している合計のエンドポイントを最大 1 だけシフトするだけなので、追加/削除された値を加算/減算することで、その場でさらに効率的に計算できます。

i = 0
j = 0
sum = 0
count = 0
while j <= N:
  cur_sum = sum[j] - sum[i] + 1
  if cur_sum == N:
    count++
  if cur_sum <= N:
    j++
    sum += j
  if cur_sum >= N:
    sum -= i
    i++
于 2010-12-27T12:23:50.653 に答える
0

1) For n >= 0 an integer, the sum of integers from 0 to n is n*(n+1)/2. This is classic : write this sum first like this : S = 0 + 1 + ... + n and then like this : S = n + (n-1) + ... + 0 You see that 2*S is equal to (0+n) + (1 + n-1)) + ... + (n+0) = (n+1)n, so that S = n(n+1)/2 indeed. (Well known but is prefered my answer to be self contained).

2) From 1, if we note cons(m,n) the sum m+(m+1)+...(n-1)+n the consecutive sum of integers between posiive (that is >=0) such that 1<=m<=n we see that : cons(m,n) = (0+1+...+n) - (0+1+...+(m-1)) which gives from 1 : cons(m,n) = n*(n+1)/ - m(m-1)/2

3) The question is then recasted into the following : in how many ways can we write N in the form N = cons(m,n) with m,n integers such that 1<=m<=n ? If we have N = cons(m,n), this is equivalent to m^2 - m + (2N -n^2 -n) = 0, that is, the real polynomial T^2 - m + (2N -n^2 -n) has a real root, m : its discriminant delta must then be a square. But we have :

delta = 1 - 3*(2*N - n^2 - n)

And this delta is an integer which must be a square. There exists therefore an integer M such that :

delta = 1 - 3*(2*N - n^2 - n) = M^2

that is 

M^2 = 1 - 6*N + n(n+1)

n(n+1) is always dividible by 2 (it's for instance 2 times our S from the beginning, but here is a more trivial reason, among to consecutive integers, one must be even) and therefore M^2 is odd, implying that M must be odd.

4) Rewrite or previous equation as :

n^2 + n + (1-6*N - M^2) = 0

This show that the real polynomial X^2 + X + (1-6*N - M^2) has a real zero, n : its discriminant gamma must therefore be a square, but :

gamma = 1 - 4*(1-6*N-M^2)

and this must be a square, so that here again, there exist an integer G such that

G^2 = 1 - 4*(1-6*N-M^2)

G^2 = 1 + 4*(2*N + m*(m-1))

which shows that, as M is odd, G is odd also.

5) Substracting M^2 = 1 - 4*(2*N - n*(n+1)) to G^2 = 1 + 4*(2*N + m*(m-1))) yields to :

G^2 - M^2 = 4*(2*N + m*(m-1)) + 4*(2*N -n*(n+1))
          = 16*N + 4*( m*(m-1) - n*(n+1) )
          = 16*N - 8*N (because N = cons(m,n))
          = 8*N

And finally this can be rewritten as :

(G-M)*(G+M) = 8*N, that is

[(G-M)/2]*[(G+M)/2] = 2*N

where (G-M)/2 and (G+M)/2 are integers (G-M and G+M are even since G and M are odd)

6) Thus, at each manner to write N as cons(m,n), we can associate a way (and only one way, as M and G are uniquely determined) to factor 2*N into the product x*y, with x = (G-M)/2 and y = (G+M)/2 where G and M are two odd integers. Since G = x + y and M = -x + y, as G and M are odd, we see that x and y should have opposite parities. Thus among x and y, one is even and the other is odd. Thus 2*N = x*y where among x and y, one is even and the other is odd. Lets c be the odd one among x and y, and d be the even one. Then 2*N = c*d, thus N = c*(d/2). So c is and odd number dividing N, and is uniquely determined by N, as soon as N = cons(m,n). Reciprocally, as soon as N has an odd divisor, one can reverse engineer all this stuff to find n and m.

7) *Conclusion : there exist a one to one correspondance between the number of ways of writing N = cons(m,n) (which is the number of ways of writing N as sum of consecutive integers, as we have seen) and the number of odd divisors of N.*

8) Finally, the number we are looking for is the number of odd divisors of n. I guess that solving this one by DP or whatever is easier than solving the previous one.

于 2013-09-17T17:50:08.660 に答える
0

この問題を解決するために、[1, M] の連続する整数のすべての合計を試します。ここで、M は M(M+1)/2 = N から導出されます。

int count = 0
for i in [1,M]
  for j in [i, M]
    s = sum(i, j) // s = i + (i+1) + ... + (j-1) + j
    if s == N 
       count++
    if s >= N
       break
return count

すべての反復で最初から計算したくないのでsum(i, j)、「メモ化」と呼ばれる手法を使用します。整数の行列を作成し、i + (i+1) + ... + (j-1) + jsum[M+1][M+1]に設定しましょう。sum[i][j]

for i in [1, M]
  sum[i][i] = i



int count = 0
for i in [1, M]
  for j in [i + 1, M]
    sum[i][j] = sum[i][j-1] + j
    if sum[i][j] == N
      count++
    if sum[i][j] >= N
      break
return count

複雑さは明らかに O(M^2)、つまり O(N) です。

于 2010-12-27T11:31:36.473 に答える