Décider d'un algorithme pour 'Jacking Jack'

Le problème est le suivant:

Rechercher le plus petit k code> pour laquelle la somme du premier k code> naturel positif tel que k (k + 1) / 2 = A + B $, où $ n = A - B $. P>

Nous avons un système d'équations: p>

• k (k + 1) / 2 = a + b code> li>
• n = A - B CODE> LI>
• a, b, k code> sont des entiers positifs li> ul>

  Il y a trois inconnues et seulement deux équations. Nous pouvons combiner pour obtenir une équation ciblée pour satisfaire: P>

  • k (k + 1) + 2n = 4a li> ul>

    Nous devons trouver le plus petit «code> k code> k code> tel que cette solution puisse être satisfaite pour l'entier n code>, étant donné que a code> doit être un entier positif. Notons quelques choses: p>

    1. si n code> est même, puis k code> ou k + 1 code> doit être divisible par 4; I.e., k = 0 ou 3 mod 4 code>. li>
    2. Si n code> est impair, alors ni k code> ni k + 1 code> peut être divisible par 4; I.e., k = 1 ou 2 mod 4 code>. li> ol>

       Ceci gère la partie sur tous les nombres étant entiers. Pour gérer la pièce sur k code> et A code> étant positif, nous devons stipuler que p>

       • k> = plancher (sqrt (2n)) code> li> ul>

         ouf. Maintenant, pour un exemple: p>

         dire que n = 7. Ensuite, nous ne connaissons pas non plus k code> k + 1 code> sont divisibles par 4. De même, nous Sachez que k> = 4 code>. Nous pouvons ignorer immédiatement k = 4 code> car nous savons k code> n'est pas divisible par 4. Nous pouvons essayer k = 5 code>; Nous entrons dans notre système: p>

         ----------J------N---
         ---------J-------N--- -1
         -----------J-----N--- +2
         --------J--------N--- -3
         ------------J----N--- +4
         -----------------J--- +5
         

Nous recherchons le montant des numéros nécessaires pour que la somme de 1 à J soit plus grande que le numéro cible et de la même parité.

Voici un code de travail simple à Python 2.7: P>

def numberOfJumps(n):
    n = abs(n)
    j = 0
    while True:
        s = j*(j+1)/2
        if s >= n and not (s - n)%2:
            break
        j += 1
    return j

for i in range(10):
    print i, numberOfJumps(i)

Je voudrais élaborer sur @ solution correcte et rapide de supercat et décrire un algorithme qui calcule une somme de longueur minimale en plus de calculer la longueur d'une telle somme.

algorithme

Trouver le plus petit entier k tel que t_k: = 1 + 2 + 3 + ... + k> = | n | et t_k a la même parité que | n |. Ensuite, retourner les signes des summands de t_k de manière systématique au total n.

Voici les détails. Notez que t_k = k (k + 1) / 2, un nombre triangulaire. Réglage t_k = | n | et la résolution de k donne le plafond (-1 + sqrt (1 + 8 | n |)) / 2. Alors k est égal au plafond ou 1 ou 2 plus il, selon ces trois chiffres a la même parité que n et est moins. Ici nous utilisons le fait que l'ensemble {t, t + s, t + s + (s + 1)} de trois nombres triangulaires consécutifs contient les nombres pairs et impairs pour tous entiers positifs t, s. (Il suffit de cocher les quatre possibilités de parité pour t et s.)

Pour une somme de longueur minimale pour n, on calcule d'abord d: = (t_k - n) / 2. Parce que t_k> = | n | et t_k et n ont la même parité, d se situe dans l'ensemble {0, 1, 2, ..., t_k}. Maintenant soustraire à plusieurs reprises: d = A_K (k) + r_k, r_k = a_ {k-1} (k-1) + r_ {k-1}, ..., r_2 = A_1 (1) + r_1, en choisissant chaque a_i au maximum dans {0, 1}. Par le lemme ci-dessous, r_1 = 0. Alors d = {sum_ i = 1} ^ k i a i. Ainsi, n = t_k - 2d = sum_ {i = 1} ^ ki - sum_ {i = 1} ^ k i = 2a_i sum_ {i = 1} ^ k (1 - 2a_i i) et 1 - 2a_i réside dans {-1 , 1}. Donc, la séquence b_i:. = 1 - 2a_i est un chemin, et par la minimalité de k, b_i est un chemin minimal

exemple l'algorithme

Considérons le nombre cible n = 12. Selon l'algorithme 3, les possibilités de k sont de 5, 6 ou 7. Les valeurs correspondantes de t_k sont de 15, 21 et 28. Etant donné que 28 est le dernier de ceux-ci avec la même parité que n, on voit que k = 7 . Donc, d = (t_k - n) / 2 = 8, que nous écrivons 1 + 7 conformément à l'algorithme. Ainsi, un chemin d'accès le plus court est 12 + 2 + -1 3 + 4 + 5 + 6 -. 7

Je dis a chemin le plus court, car les chemins les plus courts ne sont pas uniques en général. Par exemple, 1 + 2 + 4 -3 -. 5 + 6 + 7 fonctionne également

correct algorithme

Lemme: Soit A_K = {0, 1, 2, ..., t_k}. Puis un mensonge numéro dans A_K si et seulement si elle peut être exprimée comme une somme sum_ {i = 1} ^ k i a i pour certains a_i de séquence dans {0, 1}.

Preuve: Par induction sur k. Tout d'abord, 0 = {sum_ i = 1} ^ 0 1, la somme vide. Maintenant, supposons que le résultat est valable pour tous les k - 1> = 0 et supposons qu'un mensonge nombre d dans A_K. soustraire à plusieurs reprises: d = A_K (k) + r_k, r_k = a_ {k-1} (k-1) + r_ {k-1}, ..., en choisissant chaque a_i = 0 ou 1 au maximum dans {0, 1 } et l'arrêt lorsque les premiers mensonges de r_j dans A_j pour certains j

complexité du temps algorithme

En supposant que des opérations arithmétiques sont constante de temps, il faut O (1) le temps de calcul de k n, et par conséquent la longueur d'un chemin minimal à n. Ensuite, il prend O (k) le temps de trouver une somme de longueur minimale pour d, alors O (k) le temps d'utiliser cette somme pour produire une somme de longueur minimale pour n. Alors O (k) = O (sqrt (n)) tout.