Comment trouver les numéros contenant la séquence 666?

Question

pas une question de devoirs, nous sommes toujours en train d'étudier des boucles à l'école rencontré dans un défi de programmation ... Début Le numéro 666 est considéré comme le « nombre de la bête » occulte et est un puits nombre utilisé dans tous les principaux films à grand succès sur le thème de l'apocalypse. Cependant, le numéro 666 ne peut pas toujours être utilisé dans le script, de sorte que des nombres tels que 1666 sont utilisés à la place. Appelons les numéros contenant au moins trois sixes contiguës numéros. Les premiers numéros sont bestiales 666, 1666, 2666, 3666, 4666, 5666 ...

Étant donné un indice 1-n, mon programme devrait retourner le n e numéro bestiale.

Définition

• Classe: ApocalypseSomeday
• Méthode: getNth
  • Paramètres: int
  • Retours: int
  • signature de la méthode: int getNth(int n) (assurez-vous votre méthode est publique)

Contraintes

• n seront entre 1 et 10000, y compris

Exemples

1. 2 retours: 1666
2. 3 retours: 2666
3. 6 retours: 5666
4. 187 retours: 66666
5. 500 retours: 166699

Pas un problème donné par un enseignant. Je l'ai trouvé dans un challenge de programmation C++. Mon progrès jusqu'à présent

public class ApocalypseSomeday 
{ 
    public int getNth(int n) 
    { 
     int i = 0, j = 0,k = 0; 
     int s = 1,c = 1; 
     int r = 666; 
     while (s < n) 
     { 
      k = 0; 
      while ((c % 10000) == 6666 && s < n && k < 10000) 
      { 
       r = c * 10000 - 6000 + k; 
       k++; 
       s++; 
      } 

Answer 1

Comme il n'y a pas de contraintes de performance mentionnées et la taille de l'entrée est assez faible, l'option la plus simple est d'utiliser la force brute: compter à partir de 1 et vérifier chaque numéro pour voir si elle contient 666. Lorsque vous trouvez n ces nombres, retournez le dernier que vous avez trouvé.

La méthode la plus simple (mais lente) pour vérifier si un nombre contient 666 est de le convertir en chaîne et de rechercher la sous-chaîne '666'. Encore une fois, en raison de la taille limitée des intrants et de l'absence de contraintes de performance, cela devrait suffire.

Il est probablement plus rapide d'effectuer cette vérification en utilisant des opérations arithmétiques. En Python, vous pouvez le faire comme ceci:

def contains666(x): 
    while x >= 666: 
     if x % 1000 == 666: 
      return True 
     x /= 10 
    return False 

Si vous avez besoin de votre programme pour être aussi rapide que possible, vous pouvez précalculer la réponse pour chaque valeur possible de n et hardcode la réponse dans votre programme. Ensuite, vous pouvez trouver le résultat pour tout n avec une opération d'indexation simple.

Answer 2

public class ApocalypseSomeday { 
    public int getNth(int n) { 
      int i = 0, j = 0,k = 0; 
      int s = 1,c = 1; 
      int r = 666; 
      while (s < n) { 
       k = 0; 
       while ((c % 10000) == 6666 && s < n && k < 10000) { 
        r = c * 10000 - 6000 + k; 
        k++; 
        s++; 
       } 
       if (s == n) return r; 
       if (k == 10000) { 
        c++; 
        continue; 
       } 
       k = 0; 
       while ((c % 1000) == 666 && s < n && k < 1000) { 
        r = c * 1000 + k; 
        k++; 
        s++; 
       } 
       if (s == n) return r; 
       if (k == 1000) { 
        c++; 
        continue; 
       } 
       k = 0; 
       while ((c % 100) == 66 && s < n && k < 100) { 
        r = c * 1000 + 600 + k; 
        k++; 
        s++; 
       } 
       if (s == n) return r; 
       if (k == 100) { 
        c++; 
        continue; 
       } 
       k = 0; 
       while ((c % 10) == 6 && s < n && k < 10) { 
        r = c * 1000 + 660 + k; 
        k++; 
        s++; 
       } 
       if (s == n) return r; 
       if (k == 10) { 
        c++; 
        continue; 
       } 
       r = c * 1000 + 666; 
       c++; 
       s++; 
      } 
      return r; 
    } 
} 

Answer 3

class ApocalypseSomeday 
{ 
public: 
int getNth(int n) 
{ 
    int cpt = 0; 
    int nbr = 666; 
    while (cpt != n) 
    { 
     if (((nbr % 1000) == 666)) 
     { 
      //printf("nb[%d]:%d\n", cpt, nbr); 
      cpt++; 
      nbr++; 
      continue; 
     } 
     if ((nbr % 10000) - (nbr % 10) == 6660) 
     { 
      //printf("nb[%d]:%d\n", cpt, nbr); 
      cpt++; 
      nbr++; 
      continue; 
     } 
     if ((nbr % 100000) - (nbr % 100) == 66600) 
     { 
      //printf("nb[%d]:%d\n", cpt, nbr); 
      cpt++; 
      nbr++; 
      continue; 
     } 
     nbr++; 
    } 
    return nbr-1; 
} 

};