すべてのエントリが正(> = 0)の整数である長さmの配列があります。エントリの合計を0modnにします。
エントリの2乗の合計がkよりも小さいすべてのそのような配列のリストが必要です。
どうすればよいですか?そのような配列をすべて見つける方法は考えられません。そのうちのいくつかだけです。
Pythonで書いたものを表示することはできますが、メソッドに欠陥があり、最初からやり直す必要があるため、要求されない限り表示しません。
すべてのエントリが正(> = 0)の整数である長さmの配列があります。エントリの合計を0modnにします。
エントリの2乗の合計がkよりも小さいすべてのそのような配列のリストが必要です。
どうすればよいですか?そのような配列をすべて見つける方法は考えられません。そのうちのいくつかだけです。
Pythonで書いたものを表示することはできますが、メソッドに欠陥があり、最初からやり直す必要があるため、要求されない限り表示しません。
今のところ、非常に力強い解決策しか思い浮かびません。実数で例を挙げましょう。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)
それは明らかですか?
あなたに役立つ3つの観察は次のとおりです。
配列に対する制約は、配列の要素の順序とは無関係です。したがって、 と仮定しa_0 <= a_1 <= ... <= a_m-1
ます。
[a_0,...,a_m-1]
非負の整数の配列は、 の0 mod n
場合にのみ合計を持ち-a_m-1 = a0 + ... + a_m-2 mod n
ます。したがって、最初のm-1
エントリは無料ですが、最後のエントリは固定されています。
条件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;
}
}