3

与えられた配列 arr[ ]={4,6,8,3,6} 配列のすべての要素の合計 = 27. 次に、配列に対して操作を実行しましょう:-

すべての i < length(arr)-1 について、arr[i]=arr[i]-arr[i+1]

したがって、配列は {-2,-2,5,-3} になり、配列のすべての要素の合計 = -2

同じ操作をもう一度実行すると、配列は {0,7,-8} になり、配列のすべての要素の合計 = 1

したがって、次のことがわかります。

0 回目の反復後、arr[ ]={4,6,8,3,6}。配列のすべての要素の合計 = 27

1 回目の反復後、arr[ ]={-2,-2,5,-3}。配列のすべての要素の合計 = -2

2 回目の反復後、arr[ ]={0,-7,8}。配列のすべての要素の合計 = 1

3 回目の反復後、arr[ ]={7,-15}。配列のすべての要素の合計 = -8

整数 N が与えられた場合、問題は、N 回目の反復後の配列のすべての要素の合計を決定することです。

私はブルートフォースアプローチをうまく試しましたが、明らかに時間の複雑さは2次です。可能であれば、時間の複雑さが改善され、できれば線形であるアプローチを探しています。

4

1 に答える 1

11

1 回の反復の後、配列の要素の合計は次のようになります。

a[0]-a[1] + a[1]-a[2] + ... + a[n-1]-a[n] = a[0] - a[n]

したがって、問題は、N-1 回の反復後に配列の最後と最初の要素を見つけることになります。

我々は持っています：

N       First element
1       a[0]-a[1]
2       a[0]-a[1]-(a[1]-a[2])              = a[0]-2a[1]+a[2]
3       a[0]-2a[1]+a[2]-(a[1]-2a[2]+a[3])  = a[0]-3a[1]+3a[2]-a[3]

パターンが現れます: 最初の要素は (-1) k C(N,k) a[k]の合計で、k は 0 から N までです (C(n,k) は二項係数です) 。

二項係数を計算するための O(1) アルゴリズムがある場合、線形時間で N-1 回の反復後にリストの最初と最後の要素を計算でき、N 回の反復後のリストの合計はそれらの差にすぎません。

于 2013-06-03T14:11:25.913 に答える