0

問題文は次のとおりですN。x1, x2,..を見つける必要がありますxp. N = x1 + x2 + .. + xp, p は最小 (合計の項の数を意味します) でなければならず、また ( のサブセットの合計から 1 から (N-1) までのすべての数値を取得できなければなりません. x1、x2、x3..xp)。セット内の数字も繰り返される場合があります。

たとえば、N=7 の場合。

7 = 1+2+4 そして6= (2,4)、、、5= (4,1)など。4 = (4)_3=(1,2)

例 2: 8 = 1+2+4+1

例 3:(無効) 8 = 1+2+5 ただし、(1,2,5) のサブセットから 4 を取得することはできません。したがって、(1,2,5) は有効な組み合わせではありません。

私のアプローチは、「N」がp項またはp + 1項のいずれかを持つよりも、「N-1」がp項の合計として記述できる場合です。ただし、そのアプローチでは、合計が「N-1」になり、「p」項を持つすべての可能な組み合わせをチェックする必要があります。これ以外のより良い解決策はありますか？

解決策:

ステップ 1: セット内に "K" 個のエントリが答えとしてあると仮定します。したがって、各エントリが合計に表示されるか表示されないため、これらの数値から 2^K の異なる数の合計を取得できます。また、数値が「N」の場合、「1」から「N」までの合計を計算する必要があります。したがって

、(2^K -1) = N

K=log(N+1)

ステップ 2: ステップ1

の後、回答に「K」個のエントリが含まれている必要があることがわかりますが、実際のこれらのエントリは何ですか? エントリが (a1,a2,a3...ak) であるとします。したがって、数 P は P = a1*b1 + a2*b2 + a3*b3....+ ak*bk と書くことができます。ここで、すべての b[i] = 0 または 1 です。ここで、P は 2 進数 (b1 b2 b3 bk) の 10 進表現として表示されるため、a[i] = 2^(i-1) を取ることができます。

4

2 に答える 2

5

すべての数字 1,2,4 ....2^k, N-(1+...+2^k) を取る必要があります。(最後の 1 つは、0 に等しくない場合のみ)

証拠

  1. まず、k数値だけを取得すると、0 を除く最大2^k - 1の異なる合計を取得できます。したがって、 の場合N>=2^k、少なくともk + 1数値が必要です。したがって、数字のグループが正しい場合、サイズによる最小値 (または最小値の 1 つ) であることがわかります。

  2. 2^(k+1) - 10 から最初の数を使用するまでの任意の数を取得できることは簡単にわかります。さらに必要な場合は? より小さいため、最後の番号を取得し2^(k + 1)ます。そして、最初の要素を使用して違いを取得します

于 2013-07-13T02:28:15.367 に答える
0

私はこれについて数を使い果たしていませんが、2 の最初の 3 つの累乗をリストしたという事実に非常に興味を持っているはずです。

より良い解決策を探しているなら、そこから始めます。

于 2013-07-13T02:10:38.213 に答える