2

プログラミングコンテストでは、問題は次のとおりでした。

方程式のすべての解を数えますx + 4y + 4z = n。あなたが与えられn、あなたは解決策の数を決定します。x、y、zが正の整数であると仮定します。

トリプルforループ（ブルートフォース）の使用を検討しましたが、効率が悪く、TIMELIMITEXCEEDが発生しました。（nは= 1000,000である可能性があるため）：

int sol = 0;
for (int i = 1; i <= n; i++)
{
 for (int j = 1; j <= n / 4; j++)
 {
  for (int k = 1; k <= n / 4; k++)
   {
      if (i + 4 * j + 4 * k == n)
         sol++;
   }
 }
}

私の友人は問題を解決することができました。私が彼に尋ねたとき、彼はブルートフォースをまったく使用しなかったと言いました。代わりに、彼は方程式を「シリーズ」（つまり合計）に変換しました。私は彼にどうやって私を言うように頼んだが、彼は拒否した:)

方法を教えてもらえますか？

4

3 に答える 3

4

This is particular case of coin change problem, which is solved in general by dynamic programming.

But here we can elaborate simple solution. I consider x,y,z > 0

x + 4*(y+z)=n Let y + z = q = p + 1 (q > 1, p > 0)

x+4*q=n

x+4*p=n-4

There are M = Floor((n-5)/4) variants for x and p, hence there are M possible values of q = 2..M+1 For every q>1 there are (q-1) variants of y and z: q = 1 + (q-1) = 2 + (q-2) +..+(q-1)+1

So we have N=1 + 2 + 3 + ... + M = M * (M + 1)/2 solutions

Example:

n = 15;

M = (15 - 5) div 4 = 2

N = 3

(3,1,2),(3,2,1),(7,1,1)

于 2011-11-23T11:57:34.800 に答える
1

n-xで割り切れなければならない最初の音符4。x取り得る最小値を見つけることから始めます。

start = 4
while ((n - start) % 4 != 0)
{
    start = start + 1
}

これから、 がxから値を取得することがわかります[start, start+4, start+8 ...]。これで、単純なカウント ループでソリューションの数をカウントできます。

count = 0

for (x = start; x < n - 4; x = x + 4)
{
    y_z_sum = (n - x) / 4
    count = count + y_z_sum - 1
}

の選択ごとにx、 の値を計算できますy+z。の各値に対してy+z、y+z-1可能な選択肢があります (y範囲が 1 からであるため、とが両方とも正の整数であるとy+z-1仮定します)。yz

実行時間が O(n 3 )のブルート フォース ソリューションの代わりに、この方法で O(n) を実現できます。

于 2011-11-23T11:31:08.967 に答える
-1

これは古典的な線形代数の問題です。連立一次方程式を解く方法については、線形代数の教科書を参照してください。そのような方法の1つは、ガウスの消去法と呼ばれます。

于 2011-11-23T08:47:40.057 に答える