Un algorithme destiné à diviser une séquence de sous-séquences, également espacées non conflictuelles

Question

Je suis arrivé à ce problème que je ne peux pas résoudre algorithmiquement.

Disons que j'ai une capture vidéo qui capture toujours des images vidéo à un taux fixe F (disons 30 images par seconde).

Ce que je veux est de « diviser » cette séquence d'images n (par exemple quatre) de séquences. Chaque sous-séquence a sa fréquence d'images fn, qui est évidemment

(0s sont des cadres qui ne sont pas belogn à la sous-séquence, 1s sont des cadres qui font):

100 (in 1 second it will repeated like: 100100100100100100100100100100)

ou

010 (again, in 1 sec it will go like: 010010010010010010010010010010)

ou, pour F = 30 et f = 8:

100000001

(et il faudrait MCD (30,8) = 120 images avant qu'un second redémarrage avec un "1").

Le problème est que ne peuvent pas entrer en collision sousséquences, donc si F = 30, f1 = 10 images par seconde (tous les trois cadres) et f2 = 5 images par seconde (tous les six cadres), cette séquence est ok:

102100 (again, in a second: 102100102100102100102100102100)

Mais si l'on ajoute f3 = 6 images par seconde

132100 (1 AND 3) <--- collides! 02100102100102100102100

ou

102103102130102 (1 AND 3) <--- collides! 00102100102100

Le troisième serait-séquence entrer en collision avec le premier.

La question est:

• Est-il possible de trouver tous combinaison des framerate du n (avec n <= 4) qui ne sousséquences entrer en collision et serait équidistants?

(je dois le cas général, mais dans ce cas particulier, je besoin de toutes les combinaisons valides pour une séquence unique (trivial), toutes les combinaisons valides pour deux séquences, toutes les combinaisons valides de trois séquences, et tout pour quatre séquences).

quelqu'un Hope pourrait éclairer mon esprit. Merci!

Answer 1

Si vous avez un oeil à taux vous, vous allez remarquer que:

• Il y a k dans N (entiers> = 0) telle que f1 = k * f2
• Il n'y a pas k dans N tel que f1 = k * f3

Plus au point, F1 et F2 sont spéciaux dans ce f2 vous donne une suite de ce que f1 donnerait à partir du même point. Ensuite, depuis deux séquences f1 ne jamais se croiser si elles ne commencent pas au même point (pensez parallèle), puis ne va pas naturellement f2 traverser f1 soit!

Vous pouvez voir que le contraire détient, puisque f3 n'est pas une séquence de f1 (c.-à-f3 est pas un diviseur de f1), alors il i existe, j en Z (entiers) tels que i f1 + j f3 = 1, bien que je ne me souviens pas que le théorème est de ce. Cela signifie que je peux effectivement trouver une collision quelle que soit la position de deux séquences de départ.

Cela signifie alos que vous pourriez sortir avec f1 = 29 et f3 = 27 si vous pouviez seulement eu quelques images, mais finalement ils vont entrer en collision si vous continuez assez longtemps (bien que la prédiction et non calcul est au-delà de moi à le moment).

---

En bref: l'élection d'un « maître » fréquence (le plus rapide de tous ceux que vous voulez) et seulement ramasser de ce diviseurs et vous frequence être bien quelle que soit la longueur de votre vidéo

.

Answer 2

Je crois que ce serait le faire pour le cas 4 cours d'eau, et il devrait être évident que faire pour les moins de cas de flux.

for a in range(1,31):
    for b in range(a,31):
        for c in range(b,31):
            for d in range(c,31):
                if (1.0/a+1.0/b+1.0/c+1.0/d)<=1.0 and gcd(a,b,c,d)>=4:
                    print a,b,c,d

En fait, quelle que soit les fréquences que vous envisagez, 1) ils ne peuvent pas prendre plus que la totalité du courant 2) si leur plus grand dénominateur commun est <4, vous ne pouvez pas trouver un arrangement d'entre eux qui ne sera pas conflit. (Par exemple, considérons le cas de deux nombres premiers, PGCD (p1, p2) est toujours 1, et ils vont toujours dans les conflits <= p1 * cadres de p2, quelle que soit la façon dont vous les compensez)