Pourquoi mon code ne s'arrête-t-il pas?

J'essaie de résoudre Problem #5 dans Project Euler. Le code fonctionne pour l'exemple, quand je vérifie les nombres de 1 à 10, j'obtiens en conséquence 2520, ce qui est juste. Mais quand je vérifie les nombres de 1 à 20, le code n'arrête pas de fonctionner.Pourquoi mon code ne s'arrête-t-il pas?

Ici, il est:

num = 0 

while true 

    num += 1 
    check = true 

    for i in 1..20 

     break unless check 

     check = num%i==0 

    end 

    break if check 

end 

File.open("__RESULT__.txt", "w+").write num

Source

2010-06-04 Vincent

Marc a déjà donné une réponse parfaite. Alternativement: Comme chaque nombre doit être divisible par 20, 'num + = 20' vous donnera une accélération de 20x. En outre, utilisez 'for i in 2..20' car chaque nombre est divisible par 1 – schnaader

Comme une note de style: Votre code pourrait être écrit plus idiomatiquement comme' inf = 1.0/0.0; num = (1..inf) .find {| n | (1.20) .all? {| i | x% i == 0}} '- mais cela ne changerait pas le fait que cela soit trop long à calculer. – sepp2k

Juste vérifié ma version légèrement optimisée proposée dans Ruby. Cela prend environ 1 minute ici ce qui est difficile à la limite de Project Euler et beaucoup plus lent que ma version C++ qui fait la même chose en 2 secondes. – schnaader

La solution à ce problème ne peut pas être trouvé par le calcul simplement toutes les solutions possibles. La solution est si grande, qu'il faudra des jours (peut-être des années) pour calculer.

Il existe une solution plus intelligente utilisant les nombres premiers pour écrire les nombres.

L'exemple qui est donné (2520 est le plus petit nombre qui est divisible par les numéros 1 à 10) peut être écrit comme ceci:

1 = 1 (can be skipped) = 2^0 * 3^0 * 5^0 * 7^0 
2 = 2 (prime)   = 2^1 * 3^0 * 5^0 * 7^0 
3 = 3 (prime)   = 2^0 * 3^1 * 5^0 * 7^0 
4 = 2^2     = 2^2 * 3^0 * 5^0 * 7^0 
5 = 5 (prime)   = 2^0 * 3^0 * 5^1 * 7^0 
6 = 2 * 3    = 2^1 * 3^1 * 5^0 * 7^0 
7 = 7 (prime)   = 2^0 * 3^0 * 5^0 * 7^1 
8 = 2^3     = 2^3 * 3^0 * 5^0 * 7^0 
9 = 3^2     = 2^0 * 3^2 * 5^0 * 7^0 
10= 2 * 5    = 2^1 * 3^0 * 5^1 * 7^0

Maintenant, le plus petit nombre qui peut être divisé par ceux-ci, peut être calculée en utilisant la puissance maximale qui est utilisé sur chaque prime:

2^3 * 3^2 * 5^1 * 7^1 = 2520

la même chose peut être réalisée (même à la main) sur les numéros de 1 à 20

Dernière touche: la réponse est plus grande que 100.000.000 mais moins qu'un milliard, il peut être calculée en quelques minutes si elle est faite efficacement

Source

2010-06-04 12:36:32 Marc

Merci! Je l'ai d'abord fait à la main (après avoir lu notre réponse) et puis optimisé mon code, maintenant les deux façons fonctionnent! – Vincent

La question vous demande essentiellement de trouver le PPCM des 20 premiers numéros. ..

lcm = 1 
for i = 2 to 20 
    lcm = (i * lcm)/gcd(lcm,i)

Source

2010-06-09 09:22:36 st0le

Une solution beaucoup plus simple serait d'utiliser votre algorithme, mais par incrément 2520 plutôt que 1, voici ma solution C++.

#include <iostream> 
using namespace std; 

int main() 
{ 
    int check = 2520; 
    int i = 11; 
    while (i != 20) 
    { 
     i ++; 
     if (check % i != 0) 
     { 
      check +=2520; 
      i = 1; 
     } 
    } 
    cout << check << endl; 
    return 0; 
}

Comme vous pouvez le voir ci-dessus, je commence aussi au numéro 2520, et je plaçai à égaler 11. Nous pouvons faire ces optimisations, comme nous l'avons donné les informations nécessaires à la question.

Source

2010-09-29 12:42:40 ajnatural

Pourquoi mon code ne s'arrête-t-il pas?

Répondre

Questions connexes