ループ指数の収束の原理は？

Question

初めてのポスターです。私の質問です：次の問題の背後にある一般的な数学の原理は何ですか？

例えば、 [3,3,3,3,4,6,3,4,4,5]と、全てが第1のベクトルより小さい値で始まるループインデックスを表す別のベクトルとを含む。 [1,1,1,1,1,1,1,1,1,1]である。各ループインデックスが最初のベクトルの対応するインデックスと等しい場合は、それを1にリセットします。プログラムは、すべてのインデックスが1に等しいときに終了します。

これは整数分解のようですが、これを一般的にどのように表現するのか分かりません。ここではどのような原則が働いていますか？同じ結果を達成するための計算上効率的な方法は何ですか？

ありがとうございます。

import numpy as np 

unityVec = np.ones((10), dtype=np.int) # create a vector of ones 
counter = 1        # initialize counter 

counterVec = np.ones((10), dtype=np.int) # initialize counter array 
counterVec = counterVec + 1    # make counter array > ones array 

littleVec = ([3, 3, 3, 3, 4, 6, 3, 4, 4, 5]) # loop reset values 

while not (np.array_equal(unityVec, counterVec)): # compare counter to ones vector 

    counterVec = counterVec + 1 

    for i in range(10): 
     if counterVec[i] == littleVec[i]: 
      counterVec[i] = 1 # reset counterVec element to 1 once it hits limit 
      #print("Counter: ", counter, "\tIndex: ", i, "\tcounterVec: ", counterVec, "\tlittleVec: ", littleVec) 

    counter = counter + 1 


print("Indices converged after", counter-1, "iterations!") 

期待される結果：最初のベクトルの値の積に等しいかそれより小さい正の整数値。

実験結果：与えられたサンプル値を用いて、インデックスは59回のループ後に収束する。

Answer 1

私にはわかりませんが、私には単純なモジュロ演算のようです。すべてのベクトルから1を減算することができます（また、ゼロにリセットする）ことで、解析が簡単になります。あなたはcounterVec == [a,b,c] == [1,1,1]で始まり、各反復（v == littleVec）

[ (a+1)%v[0], (b+1)%v[1], (c+1)%v[1] ] 

に計算し、このベクトルは[0,0,0]にEQALあるときに停止します。

明らかに、aが整数の倍数v[0]（+1で始まるため、マイナス1）を増分するたびに、最初のコンポーネントがゼロになることは明らかです。一度にすべての要素がゼロになるには、同じ文がtrueでなければなりません。対応する整数の倍数v[i]。

だから結局、あなたは整数(n_a, n_b, n_c)のすべての選択肢についても同様です

[ (1 + n_a * v[0] - 1)%v[0], 
    (1 + n_b * v[1] - 1)%v[1], 
    (1 + n_c * v[2] - 1)%v[2] ] == [ 0, 0, 0 ] 
#^initial value^correction for the initial value 

で終わります。あなたが共同ですべてのベクトル成分をインクリメントするので、そのようないくつかの整数n_iため

X = n_a * v[0] 
    = n_b * v[1] 
    = n_c * v[2] 

その刻みXの最小数がなければなりません。つまり、v[i]で割り切れる最小のXがあります。他の人が指摘しているように、これはすべてv[i]のleast common multipleでなければなりません。あなたの例の数字の場合、it's 60（1で始まり0ではないので、59の反復が表示されます）。ループが停止するまで

だから、

littleVec = ([5, 3, 7, 8, 10, 8, 5, 7, 5, 7]) 

You will get

lcm([5, 3, 7, 8, 10, 8, 5, 7, 5, 7]-1) = 252 

マイナス1回の反復で始まります。