Comment trouver le multiple le moins commun d'une série de nombres?
Donné un tableau de deux nombres, les laisser définir le début et la fin d'une série de nombres. Par exemple, [2,6]
s'entend de la gamme 2,3,4,5,6. Je veux écrire du code javascript pour trouver le plus petit commun multiple de la plage. Mon code ci-dessous fonctionne pour les petites plages, pas quelque chose comme [1,13]
(qui correspond à la plage 1,2,3,4,5,6,7,8,9,10,11,12,13), ce qui provoque un débordement de pile. Comment puis-je efficace de trouver le plus petit commun multiple de gamme?
function leastCommonMultiple(arr) {
var minn, max;
if ( arr[0] > arr[1] ) {
minn = arr[1];
max = arr[0];
} else {
minn = arr[0];
max = arr[1];
}
function repeatRecurse(min, max, scm) {
if ( scm % min === 0 && min < max ) {
return repeatRecurse(min+1, max, scm);
} else if ( scm % min !== 0 && min < max ) {
return repeatRecurse(minn, max, scm+max);
}
return scm;
}
return repeatRecurse(minn, max, max);
}
source d'informationauteur john chau
Vous devez vous connecter pour publier un commentaire.
Je pense que ce que le travail soit fait.
de la console.log( leastCommonMultiple([1, 13]) )
Bien joué sur la solution. Je pense que j'en ai eu un qui peut être abit plus courte juste pour référence future, mais mal sans hésiter regard dans le vôtre
Vous pourriez avoir eu à l'origine un débordement de la pile en raison d'une faute de frappe: vous avez changé entre
min
etminn
dans le milieu derepeatRecurse
(vous l'aurais pris que sirepeatRecurse
n'avait pas été définie dans la fonction externe). Avec qui fixe,repeatRecurse(1,13,13)
retourne 156.La réponse la plus évidente pour éviter un débordement de la pile est de transformer une fonction récursive dans une situation de non-fonction récursive. Vous pouvez l'obtenir en faisant:
Mais peut-être vous pouvez voir l'erreur en ce point: vous n'êtes pas veiller à ce que
scm
est toujours divisible par les éléments qui sont venus avantmin
. Par exemple,repeatRecurse(3,5,5)=repeatRecurse(4,5,15)=20
. Au lieu d'ajoutermax
vous voulez remplacerscm
avec son petit commun multiple avecmin
. Vous pouvez utiliser rgbchris du pgcd (pour les entiers,!b
est la même chose queb===0
). Si vous voulez garder la queue d'optimisation (bien que je ne pense pas qu'un moteur javascript a la queue d'optimisation), vous vous retrouvez avec:Ou sans la récursivité:
C'est essentiellement équivalent à rgbchris de la solution. Un de plus élégant méthode peut être diviser pour régner:
Je recommanderais éloigne de l'original argument un tableau de deux nombres. Pour une chose, il finit par entraîner vous parler de deux tableaux:
[min,max]
et la gamme de tableau. D'autre part, il serait très facile de passer d'un tableau plus et ne se rendent jamais compte que vous avez fait quelque chose de mal. Il est également besoin de plusieurs lignes de code pour déterminer le min et le max, lorsque ceux-ci devraient avoir été déterminé par l'appelant.Enfin, si vous allez travailler avec vraiment de grands nombres, il peut être mieux de trouver le plus petit multiple commun à l'aide de la factorisation des nombres.
Voici ma solution. J'espère que vous le trouverez facile à suivre:
Voici un autre non récursives pour boucle solution