2

すべてのエントリが正(> = 0)の整数である長さmの配列があります。エントリの合計を0modnにします。

エントリの2乗の合計がkよりも小さいすべてのそのような配列のリストが必要です。

どうすればよいですか?そのような配列をすべて見つける方法は考えられません。そのうちのいくつかだけです。

Pythonで書いたものを表示することはできますが、メソッドに欠陥があり、最初からやり直す必要があるため、要求されない限り表示しません。

4

2 に答える 2

2

今のところ、非常に力強い解決策しか思い浮かびません。実数で例を挙げましょう。m = 4、n = 5、k = 25 とします。したがって、すべての配列を反復処理し、位置ごとに 1 から指定された範囲uまでのすべての数値をテストします。このuの計算のために、私はこれについて考えました。この最悪のケースでは、次のようになります。

[1 1 1 う]

これは、3 + u**2 が k よりも小さくなければならないことを意味します。したがって、uを int(sqrt(k - (m-1))) として使用します。

from math import sqrt

array = [1, 2, 3, 4]
comb = [0 for i in range(m)]
u = int(sqrt(k-m+1))

all_combs(comb, 0, 0, 0)

def all_combs(comb, pos, sum, square_sum):
    global n, m, u, k

    if (square_sum > k):
        # Invalid case
        return
    if (pos == m):
        if (sum % n == 0):
            print comb
        return

    for i in range(1,u+1):
        comb[pos] = i
        all_combs(comb, pos + 1, sum + i, sum_square + i**2)

それは明らかですか?

于 2013-03-04T18:57:58.153 に答える
0

あなたに役立つ3つの観察は次のとおりです。

  1. 配列に対する制約は、配列の要素の順序とは無関係です。したがって、 と仮定しa_0 <= a_1 <= ... <= a_m-1ます。

  2. [a_0,...,a_m-1]非負の整数の配列は、 の0 mod n場合にのみ合計を持ち-a_m-1 = a0 + ... + a_m-2 mod nます。したがって、最初のm-1エントリは無料ですが、最後のエントリは固定されています。

  3. 条件a_0^2 + ... + a_m-1^2 < kは、エントリのサイズを制限します。したがって、ループは有限です。

解決策は次のようになります。

array := [0,...,0];
sqsum := sum_{j=0..m-1} array[j]^2;
for i := m-2...1 do {
  array[i]++;
  for j from i+1 to m-2 do
    array[j] := array[i];
  L := sum_{j=0..m-2} array[j] mod n;
  array[m-1] := n-L;
  sqsum := sum_{j=0..m-1} array[j]^2;
  while sqsum < k do {
    print(array);
    sqsum := sqsum + 2*array[m-1]n+n^2;
    array[m-1] := array[m-1]+n;
  }
}  
于 2013-03-05T05:20:11.127 に答える