Comment trouver le plus petit commun multiple et le plus grand diviseur commun d'un tableau à l'aide de JS

Cette fois, je vais vous montrer comment utiliser JS pour trouver le plus petit commun multiple et le plus grand diviseur commun d'un tableau.Quelles sont les choses. à noter ?. Voici les cas pratiques, regardons.

La méthode provient d'un algorithme de transformation permettant de trouver le plus petit commun multiple de plusieurs nombres (voir l'annexe pour plus de détails)

L'algorithme du plus petit commun multiple est transformé à partir du plus grand commun diviseur. Le plus grand diviseur commun peut être obtenu en procédant comme suit :

(1) Trouver le terme minimal non nul aj parmi a1, a2,...,an S'il existe plusieurs termes minimaux non nuls, choisissez-en un
(2) Tous les autres termes non-0 ak sauf aj sont remplacés par ak mod aj ; s'il n'y a pas d'autres termes non-0 sauf aj, allez à (4)
(3) Allez à (1)
(4) Le plus grand diviseur commun de a1, a2,...,an est aj

J'ai écrit deux versions dejavascriptpour trouver des multiples communs et des diviseurs communs . Je me suis principalement concentré sur l'algorithme et n'y ai pas prêté beaucoup d'attention. Beaucoup écrivent simplement des noms à une seule lettre.

0. Boucle simple et facile à comprendre

function getMin(arr){ var min = Infinity arr.forEach(function(item){ if( item < min && item !=0 ){ min = item } }) return min } function howMuchZero(arr){ var zerocount = 0 arr.forEach( function(item){ item === 0 ? zerocount++ : zerocount } ) if(zerocount === arr.length -1) { return true } else return false } function maxpi(arr){ do { var min = getMin(arr) arr = arr.map((item)=> item===min? item:item%min ) } while (!howMuchZero(arr)) return getMin(arr) } function minMulti(arr){ var totalMulti = arr.reduce((pre,item)=> pre = pre * item ) var brr = arr.map((item)=> totalMulti/item ) var brr_maxpi = maxpi(brr) return totalMulti/brr_maxpi }

1.2. Orienté objet

var arr_minMulti, arr_maxpi function minMulti(arr){ var totalmulti = arr.reduce((multi,curvalue) => multi * curvalue) if (totalmulti === 0) { arr_minMulti = 0 return } var marr = arr.map((item) => totalmulti/item) maxpisor(marr) arr_minMulti = totalmulti / arr_maxpi } function maxpisor(arr){ var min = getMin(arr) if(min === Infinity) { arr_maxpi = min return } var exparr = arr.filter(function(item){ return (item !== min && item !== 0) }) if(exparr.length === 0){ arr_maxpi = min return; } else{ var modearr = arr.map(function(item){ return (item === min||item===0)? item:item%min }) console.log(modearr,'modearr') maxpisor(modearr) } } function getMin(arr){ var min = Infinity arr.forEach(function(item){ if (item && item < min) { min = item } }) return min } arr =[13,20,10,26] minMulti(arr) console.log('最小公倍数',arr_minMulti)

function maxpisor(arr,origin){ this.arr = arr this.min = this._getMin(arr) this.maxpisor = this._getMaxp() if(origin){ this.minMulti = this._getMinMulti() } } maxpisor.prototype._getMin = function(arr) { var min = Infinity arr.forEach(item => min = (item && item < min)? item : min) return min } maxpisor.prototype._getMaxp = function() { var arr_maxpi var self = this, arr = this.arr function maxpisor(arr){ //console.log(self._getMin) var min = self._getMin.call(null,arr) console.log(min,'min') if(min === Infinity) { arr_maxpi = 0 return ; } var exparr = arr.filter( item => (item !== min && item != 0) ) if(exparr.length === 0){ arr_maxpi = min return; } else{ var modearr = arr.map(item => (item === min || item === 0)? item : item % min ) maxpisor(modearr) } } maxpisor(this.arr) return arr_maxpi } maxpisor.prototype._getMinMulti = function(){ var arr = this.arr, arr_minMulti var totalmulti = arr.reduce((multi,curvalue) => multi * curvalue) if (totalmulti === 0) { return 0 } else { var marr = arr.map((item) => totalmulti/item), b = new maxpisor(marr,false) arr_minMulti = totalmulti / b.maxpisor return arr_minMulti } } var a = new maxpisor([12,9,6],true) console.log(a)

Soit [a1,a2,..,an] représente le plus petit commun multiple de a1,a2,..,an, (a1,a2,..,an ) représentent a1,a2,.., le plus grand diviseur commun de an, où a1, a2,...,an sont des entiers non négatifs. Pour deux nombres a, b, [a, b] = ab/(a, b), le plus petit commun multiple des deux nombres peut donc être calculé en utilisant leur plus grand commun diviseur. Mais pour plusieurs nombres, [a1,a2,..,an]=M/(a1,a2,..,an) n'est pas valable, et M est le produit de a1,a2,..,an. Par exemple : [2,3,4] n'est pas égal à 24/(2,3,4). Autrement dit, la relation entre le plus grand commun diviseur et le plus petit commun multiple de deux nombres ne peut pas être simplement étendue au cas de n nombres.La relation entre le plus petit commun multiple de plusieurs nombres et le plus grand commun diviseur de plusieurs nombres est discutée ici. Étendre la relation entre le plus grand commun diviseur et le plus petit commun multiple de deux nombres au cas de n nombres. Sur cette base, l'algorithme de transformation vectorielle pour trouver le plus grand commun diviseur de n nombres est utilisé pour calculer le plus petit commun multiple de plusieurs nombres.

Soit p le facteur premier d'un ou plusieurs nombres dans an, a1, a2, .., les degrés de an par rapport à p sont respectivement r1, r2, .., rn. La valeur maximale parmi r1, r2, .., rn est rc1=rc2=..=rcm=rmax, et la valeur minimale est rd1=rd2=. ..=rdt=rmin, c'est-à-dire que le degré de p contenu dans m nombres dans r1, r2,..,rn est la valeur maximale, et le degré de p contenu dans t nombres est la valeur minimale. Par exemple : les degrés du facteur premier 2 dans 4, 12 et 16 sont respectivement 2, 2 et 4. Il y a un nombre qui contient le degré 2 comme valeur maximale, et il y a 2 nombres qui contiennent le degré. de 2 comme valeur minimale ; concernant les nombres premiers, les degrés du facteur 3 sont respectivement 0, 1 et 0. Un nombre contient le degré de 3 comme valeur maximale, et il y a 2 nombres contenant le degré de 3 comme valeur minimale.Pour le plus grand diviseur commun, il inclut uniquement les facteurs premiers contenus dans a1, a2,...,an, et le degré de chaque facteur premier est le degré le plus bas du facteur premier dans a1, a2,. ..,an , le degré le plus bas est 0, ce qui signifie qu'il ne contient pas [1].

Pour le plus petit commun multiple, il inclut uniquement les facteurs premiers contenus dans a1, a2,..,an, et le degré de chaque facteur premier est le degré le plus élevé du facteur premier dans a1,a2,. .,un[ 1].

Théorème 1 : [a1,a2,..,an]=M/(M/a1,M/a2,..,M/an), où M est a1,a2,..,an Le produit de a1, a2,...,an est un entier positif.

Par exemple : pour 4,6,8,10, il y a [4,6,8,10]=120, et M=4*6*8*10=1920, M/(M/ a1, M/a2,..,M/an) =1920/(6*8*10,4*8*10,4*6*10,4*6*8)=1920/16=120.

Démontrer :

Le degré de p dans M/a1, M/a2,..,M/an est supérieur ou égal à r1+r2+..+rn-rmax, et a le degré de p Égal à r1+r2+..+rn-rmax. C'est parce que

(1) Le degré de p dans M/ai est r1+r2+..+rn-ri, donc le degré de p dans M/a1, M/a2,.., M/ an est le plus petit est r1+r2+..+rn-rmax.

(2) Pour l'élément aj (un ou plusieurs éléments) avec le plus grand degré de p dans a1, a2,..,an, le degré de p dans M/aj est r1+r2+..+ rn-rmax.

Ou pour le terme aj avec le plus grand degré de p dans a1, a2,..,an, le degré de p dans M/aj est inférieur ou égal à M/ak, où ak est dans a1 ,a2,..,an Un des n-1 termes sauf aj, et le degré de p dans M/aj est r1+r2+..+rn-rmax.

Par conséquent, le degré de p dans (M/a1,M/a2,..,M/an) est r1+r2+..+rn-rmax, donc M/(M/a1,M/ a2 ,..,M/an) le degré de p est rmax.

Le p ci-dessus n'impose aucune restriction. Puisque tous les facteurs premiers contenus dans a1, a2,..,an sont du plus haut degré dans a1,a2,..,an dans M/(M/a1,M/a2,..,M/an), donc, [a1,a2,..,an]=M/(M/a1,M/a2,..,M/an) est établi.

Obtenez une certification.

Le théorème 1 pour le cas de 2 nombres est [a,b]=ab/(ab/a,ab/b)=ab/(b,a)=ab/(a,b), c'est-à-dire [ une, b]=ab/(une,b). Par conséquent, le théorème 1 est une extension de la formule multiple la moins courante de deux nombres [a, b] = ab/(a, b). Le théorème 1 peut être utilisé pour transformer la recherche du plus petit commun multiple de plusieurs nombres en la recherche du plus grand commun diviseur de plusieurs nombres.

2. Implémentation d'un algorithme du plus grand commun diviseur de plusieurs nombres

Selon le théorème 1, la recherche du plus petit commun diviseur de plusieurs nombres peut être transformée en la recherche du plus grand commun diviseur de plusieurs nombres. La méthode traditionnelle pour trouver le plus grand diviseur commun de plusieurs nombres (a1, a2,..,an) consiste à trouver le plus grand diviseur commun de deux nombres plusieurs fois, c'est-à-dire

(1) Utilisez l'équation euclidienne méthode de division [2] Calculer le plus grand diviseur commun de a1 et a2 (a1, a2)

(2) Utilisez la méthode euclidienne pour calculer le plus grand diviseur commun de (a1, a2) et a3, et obtenir ( a1, a2, a3)

(3) Utilisez la division euclidienne pour calculer le plus grand diviseur commun de (a1, a2, a3) et a4, et obtenez (a1, a2, a3, a4)

(4) Répétez ceci, jusqu'à ce que (a1,a2,..,an)

soit obtenu, la méthode ci-dessus nécessite n-1 opérations de division euclidienne.

Cet article étend la méthode de division euclidienne de deux nombres à la méthode de division euclidienne de n nombres, c'est-à-dire en utilisant la méthode de division euclidienne de n nombres à la fois pour calculer le plus grand diviseur commun de n nombres. La méthode consiste à utiliser la division euclidienne répétée. Le nombre minimum modulo d'autres nombres est calculé sur la base du théorème 2 suivant.

Théorème 2 : Nombres entiers non négatifs multiples a1, a2,..,an, si aj>ai, i n'est pas égal à j, alors remplacez aj par aj-ai dans a1, a2,.., an , son plus grand diviseur commun reste inchangé, soit (a1,a2,..,aj-1,aj,aj+1,..an)=(a1,a2,..,aj-1,aj-ai, aj+ 1,..an).

Par exemple : (34,24,56,68)=(34,24,56-34,68)=(34,24,22,68).

Preuve :

D'après la loi commutative et le rapport associatif du plus grand diviseur commun, il y a

(a1,a2,..,aj-1,aj, aj+1, ..an)= ((ai,aj),(a1,a2,..,ai-1,ai+1,..aj-1,aj+1,..an)) (i> j cas), Ou

(a1,a2,..,aj-1,aj,aj+1,..an)= ((ai,aj),(a1,a2,..,aj -1,aj +1,..ai-1,ai+1,..an)) (i

Et pour (a1,a2,..,aj-1,aj-ai,aj+1,..an), il y a

(a1,a2,..,aj - 1,aj-ai,aj+1,..an)= ((ai, aj-ai),( a1,a2,..,ai-1,ai+1,.. aj-1,aj+1 , ..an)) (i>j cas), ou

(a1,a2,..,aj-1,aj-ai,aj+1,..an)= ((ai, aj - ai),( a1,a2,..,aj-1,aj+1,.. ai-1,ai+1,..an)) (i

Alors prouvez simplement (ai, aj) = (ai, aj-ai).

Puisque (aj-ai) = aj-ai, tout facteur commun de ai, aj doit aussi être un facteur de (aj-ai), c'est-à-dire qu'il est aussi un facteur commun de ai, ( aj -ai). Puisque aj = (aj-ai)+ai, tout facteur commun de ai, (aj-ai) doit aussi être un facteur de aj, c'est-à-dire qu'il est aussi un facteur commun de ai, aj. Par conséquent, le plus grand diviseur commun de ai, aj et le plus grand diviseur commun de ai, (aj-ai) doivent être égaux, c'est-à-dire que (ai, aj) = (ai, aj-ai) est valable.

Obtenez une certification.

Le théorème 2 est similaire à la transformation élémentaire d'une matrice, c'est-à-dire

Que le plus grand commun diviseur d'un vecteur soit le plus grand commun diviseur de chaque composante du vecteur. Pour les vecteurs , transformation : soustrayez un composant d'un autre composant, et le nouveau vecteur est égal au plus grand diviseur commun du vecteur d'origine.

Pour trouver le plus grand diviseur commun de plusieurs nombres, utilisez la méthode de modulation répétée d'autres nombres avec le plus petit nombre, c'est-à-dire soustrayez plusieurs fois les autres nombres avec le plus petit nombre jusqu'à ce qu'un reste plus petit que le plus petit nombre soit gauche. Soit n entiers positifs a1, a2,...,an. L'algorithme permettant de trouver le plus grand diviseur commun de plusieurs nombres est décrit comme :

(1) Trouver le plus petit nombre non nul parmi a1, a2. ,...,un terme nul aj, s'il y a plusieurs termes minimum non nuls, choisissez-en un

(2) Tous les autres termes non nuls ak sauf aj sont remplacés par ak mod aj s'il y en a ; il n'y a pas d'autres termes non nuls sauf aj , alors passez à (4)

(3) Allez à (3)

(4) le plus grand diviseur commun de a1, a2,.. ., an est aj

Par exemple : pour 5 nombres 34, 56, 78, 24, 85, il y a

(34, 56, 78, 24, 85)=(10, 8,6,24,13)=(4, 2,6,0,1)=(0,0,0,0,1)=1,

Pour les 6 nombres 12, 24, 30 , 32, 36, 42, il y a

(12, 24, 30, 32, 36, 42)=(12,0,6,8,0,6)=(0,0,0, 2,0,6)=(0,0,0 ,2,0,0)=2.

3. Implémentation de l'algorithme du multiple commun minimum de plusieurs nombres

L'algorithme pour trouver le multiple commun minimum de plusieurs nombres est :

( 1) Calcul m=a1*a2*..*an

(2) Remplacez tous les éléments ai dans a1, a2,..,an par m/ai

(3) Trouver a1 , a2,.., le terme minimum non nul aj dans an, s'il y a plusieurs termes minimum non nuls, choisissez-en un

(4) Tous les autres termes non nuls aj sauf aj sont remplacés par ak mod aj ; S'il n'y a pas d'autres éléments non nuls sauf aj, allez à (6)

(5) Allez à (3)

(6) Le multiple le moins commun est m/aj

L'algorithme ci-dessus a été programmé dans un langage de haut niveau dans l'environnement VC à travers plusieurs groupes d'exemples pour trouver le multiple le plus petit commun de 5 aléatoires. chiffres, il a été comparé à la méthode standard. Comparez et vérifiez son exactitude. La méthode de calcul standard est la suivante : trouver le plus petit commun multiple de 5 nombres aléatoires est obtenu en trouvant le plus petit commun multiple de deux nombres 4 fois, et le plus petit commun multiple de deux nombres est obtenu en trouvant le plus grand commun diviseur des deux nombres.

5. Conclusion

Le calcul du plus petit commun multiple de plusieurs nombres est une opération de base courante. Le plus petit commun multiple de n nombres peut être exprimé comme le plus grand commun diviseur de n autres nombres, il peut donc être calculé en trouvant le plus grand commun diviseur de plusieurs nombres. Pour trouver le plus grand diviseur commun de plusieurs nombres, vous pouvez utiliser l’algorithme de conversion vectorielle pour le trouver en même temps.

Je pense que vous maîtrisez la méthode après avoir lu le cas dans cet article. Pour des informations plus intéressantes, veuillez prêter attention aux autres articles connexes sur le site Web chinois de php !

Lecture recommandée :

Comment utiliser Angular pour implémenter des requêtes de données

Comment utiliser le nœud et utiliser l'async pour contrôler concurrence

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!