So finden Sie mit JS das kleinste gemeinsame Vielfache und den größten gemeinsamen Teiler eines Arrays

Dieses Mal zeige ich Ihnen, wie Sie JS verwenden, um das kleinste gemeinsame Vielfache und den größten gemeinsamen Teiler eines Arrays zu finden. Was sind die Dinge? Zu beachten? Hier sind die praktischen Fälle.

Die Methode basiert auf einem Transformationsalgorithmus zum Finden des kleinsten gemeinsamen Vielfachen mehrerer Zahlen (Einzelheiten finden Sie im Anhang).

Der Algorithmus für das kleinste gemeinsame Vielfache wird vom größten gemeinsamen Teiler transformiert. Der größte gemeinsame Teiler kann durch die folgenden Schritte ermittelt werden:

(1) Finden Sie den minimalen Nicht-Null-Term aj unter a1, a2,...,an. Wenn es mehrere minimale Nicht-Null-Terme gibt, wähle einen beliebigen
(2) Alle anderen Nicht-0-Begriffe ak außer aj werden durch ak mod aj ersetzt; wenn es keine anderen Nicht-0-Begriffe außer aj gibt, gehe zu (4)
(3) Gehe zu (1)
(4) Der größte gemeinsame Teiler von a1, a2,...,an ist aj

Ich habe zwei Versionen von Javascript geschrieben, um gemeinsame Vielfache und gemeinsame Teiler zu finden .Ich habe mich hauptsächlich auf den Algorithmus konzentriert und ihm nicht viel Aufmerksamkeit geschenkt, viele schreiben einfach Namen mit einem Buchstaben.

0. Einfache und leicht verständliche Schleife

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. Funktionssatz von Funktionen

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(&#39;最小公倍数&#39;,arr_minMulti)

2 . Objektorientiert Objektorientiert

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,&#39;min&#39;)
    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)

Anhang: Analyse des Prinzips eines Transformationsalgorithmus zum Finden des kleinsten gemeinsamen Vielfachen mehrerer Zahlen

Es sei [a1,a2,..,an] das kleinste gemeinsame Vielfache von a1,a2,..,an, (a1,a2,..,an) der größte gemeinsame Teiler von a1,a2,..,an. Unter ihnen sind a1, a2,...,an nicht negative ganze Zahlen. Für zwei Zahlen a, b, [a, b] = ab/(a, b), sodass das kleinste gemeinsame Vielfache der beiden Zahlen unter Verwendung ihres größten gemeinsamen Teilers berechnet werden kann. Aber für mehrere Zahlen gilt [a1,a2,..,an]=M/(a1,a2,..,an) nicht und M ist das Produkt von a1,a2,..,an. Beispiel: [2,3,4] ist nicht gleich 24/(2,3,4). Das heißt, die Beziehung zwischen dem größten gemeinsamen Teiler und dem kleinsten gemeinsamen Vielfachen zweier Zahlen kann nicht einfach auf den Fall von n Zahlen ausgedehnt werden.

Die Beziehung zwischen dem kleinsten gemeinsamen Vielfachen mehrerer Zahlen und dem größten gemeinsamen Teiler mehrerer Zahlen wird hier diskutiert. Erweitern Sie die Beziehung zwischen dem größten gemeinsamen Teiler und dem kleinsten gemeinsamen Vielfachen zweier Zahlen auf den Fall von n Zahlen. Auf dieser Grundlage wird der Vektortransformationsalgorithmus zum Finden des größten gemeinsamen Teilers von n Zahlen verwendet, um das kleinste gemeinsame Vielfache mehrerer Zahlen zu berechnen.

1． Die Beziehung zwischen dem kleinsten gemeinsamen Vielfachen mehrerer Zahlen und dem größten gemeinsamen Teiler mehrerer Zahlen

Sei p der Primfaktor einer oder mehrerer Zahlen in an, a1, a2, ..., den Graden von an in Bezug auf p sind jeweils r1, r2, .., rn. Der Maximalwert unter r1, r2, .., rn ist rc1=rc2=..=rcm=rmax und der Minimalwert ist rd1=rd2= ..=rdt=rmin, das heißt, der Grad von p, der in m Zahlen in r1, r2,..,rn enthalten ist, ist der Maximalwert und der Grad von p, der in t Zahlen enthalten ist, ist der Minimalwert. Beispiel: Die Grade des Primfaktors 2 in 4, 12 und 16 sind 2, 2 bzw. 4. Es gibt eine Zahl, die den Grad 2 als Maximalwert enthält, und es gibt 2 Zahlen, die den Grad enthalten von 2 als Minimalwert; bei Primzahlen sind die Grade von Faktor 3 jeweils 0, 1 und 0. Eine Zahl enthält den Grad 3 als Maximalwert und es gibt 2 Zahlen, die den Grad 3 als Minimalwert enthalten.

Der größte gemeinsame Teiler enthält nur Primfaktoren, die in a1, a2,...,an enthalten sind, und der Grad jedes Primfaktors ist der niedrigste Grad des Primfaktors in a1, a2,. ..,an, der niedrigste Grad ist 0, was bedeutet, dass er nicht [1] enthält.

Für das kleinste gemeinsame Vielfache umfasst es nur die in a1, a2,..,an enthaltenen Primfaktoren, und der Grad jedes Primfaktors ist der höchste Grad des Primfaktors in a1,a2,. .,an[ 1].

Satz 1: [a1,a2,..,an]=M/(M/a1,M/a2,..,M/an), wobei M a1,a2,..,an ist Das Produkt von a1, a2,...,an ist eine positive ganze Zahl.

Zum Beispiel: Für 4,6,8,10 gibt es [4,6,8,10]=120 und 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.

Beweisen Sie:

Der Grad von p in M/a1, M/a2,..,M/an ist größer oder gleich r1+r2+..+rn-rmax, und hat den Grad von p Gleich r1+r2+..+rn-rmax. Dies liegt daran, dass

(1) der Grad von p in M/ai r1+r2+..+rn-ri ist, also der Grad von p in M/a1, M/a2,.., M/ an ist der kleinste ist r1+r2+..+rn-rmax.

(2) Für das Element aj (ein oder mehrere Elemente) mit dem größten p-Grad in a1, a2,..,an beträgt der p-Grad in M/aj r1+r2+..+ rn- rmax.

Oder für den Term aj mit dem größten Grad von p in a1, a2,..,an ist der Grad von p in M/aj kleiner oder gleich M/ak, wobei ak in a1 ist ,a2,..,an Einer der n-1 Terme außer aj, und der Grad von p in M/aj ist r1+r2+..+rn-rmax.

Daher ist der Grad von p in (M/a1,M/a2,..,M/an) r1+r2+..+rn-rmax, also M/(M/a1,M/ a2 ,..,M/an) der Grad von p ist rmax.

Das obige p stellt keine Einschränkungen dar. Da alle in a1, a2,..,an enthaltenen Primfaktoren den höchsten Grad in a1,a2,..,an in M/(M/a1,M/a2,..,M/an) haben, gilt daher: [a1,a2,..,an]=M/(M/a1,M/a2,..,M/an) wird festgelegt.

Lassen Sie sich zertifizieren.

Satz 1 für den Fall von 2 Zahlen ist [a,b]=ab/(ab/a,ab/b)=ab/(b,a)=ab/(a,b), also [ a, b]=ab/(a,b). Daher ist Satz 1 eine Erweiterung der Formel des kleinsten gemeinsamen Vielfachen zweier Zahlen [a, b] = ab/(a, b). Satz 1 kann verwendet werden, um die Suche nach dem kleinsten gemeinsamen Vielfachen mehrerer Zahlen in die Suche nach dem größten gemeinsamen Teiler mehrerer Zahlen umzuwandeln.

2. Algorithmusimplementierung des größten gemeinsamen Teilers mehrerer Zahlen

Gemäß Satz 1 kann das Finden des kleinsten gemeinsamen Vielfachen mehrerer Zahlen in das Finden des größten gemeinsamen Teilers mehrerer Zahlen umgewandelt werden. Die traditionelle Methode zum Ermitteln des größten gemeinsamen Teilers mehrerer Zahlen (a1, a2,..,an) besteht darin, den größten gemeinsamen Teiler zweier Zahlen mehrmals zu ermitteln, d. h.

(1) unter Verwendung des Euklidischen Divisionsmethode [2] Berechnen Sie den größten gemeinsamen Teiler von a1 und a2 (a1, a2)

(2) Verwenden Sie die euklidische Methode, um den größten gemeinsamen Teiler von (a1, a2) und a3 zu berechnen und erhalten Sie ( a1, a2, a3)

(3) Verwenden Sie die euklidische Division, um den größten gemeinsamen Teiler von (a1, a2, a3) und a4 zu berechnen und erhalten Sie (a1, a2, a3, a4)

(4) Wiederholen Sie dies, bis (a1,a2,..,an)

erhalten ist, erfordert die obige Methode n-1 Räumungen und Divisionsoperationen.

Dieser Artikel erweitert die euklidische Divisionsmethode für zwei Zahlen auf die euklidische Divisionsmethode für n Zahlen, dh die Verwendung der euklidischen Divisionsmethode für n Zahlen auf einmal, um den größten gemeinsamen Teiler von n Zahlen zu berechnen Die Methode besteht darin, eine wiederholte euklidische Division zu verwenden. Die Mindestzahl wird modulo anderer Zahlen berechnet, basierend auf dem folgenden Satz 2.

Theorem 2: Mehrere nichtnegative ganze Zahlen a1, a2,..,an, wenn aj>ai, i nicht gleich j ist, dann ersetzen Sie aj durch aj-ai in a1, a2,.., an , sein größter gemeinsamer Teiler bleibt unverändert, das heißt (a1,a2,..,aj-1,aj,aj+1,..an)=(a1,a2,..,aj-1,aj-ai, aj+ 1,..an).

Zum Beispiel: (34,24,56,68)=(34,24,56-34,68)=(34,24,22,68).

Beweis:

Nach dem Kommutativgesetz und dem Assoziativverhältnis des größten gemeinsamen Teilers gibt es

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

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

Und für (a1,a2,..,aj-1,aj-ai,aj+1,..an) gibt es

(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-Fall) oder

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

Beweisen Sie also einfach (ai, aj) = (ai, aj-ai).

Da (aj-ai) = aj-ai, jeder gemeinsame Faktor von ai, muss aj auch ein Faktor von (aj-ai) sein, das heißt, es ist auch ein gemeinsamer Faktor von ai, ( aj -ai). Da aj = (aj-ai)+ai, muss jeder gemeinsame Faktor von ai, (aj-ai) auch ein Faktor von aj sein, das heißt, er ist auch ein gemeinsamer Faktor von ai, aj. Daher müssen der größte gemeinsame Teiler von ai, aj und der größte gemeinsame Teiler von ai, (aj-ai), gleich sein, d. h. (ai, aj) = (ai, aj-ai) gilt.

Lassen Sie sich zertifizieren.

Theorem 2 ähnelt der elementaren Transformation einer Matrix, das heißt

Der größte gemeinsame Teiler eines Vektors sei der größte gemeinsame Teiler jeder Komponente des Vektors. Transformation für Vektoren : Subtrahieren Sie eine Komponente von einer anderen Komponente, und der neue Vektor ist gleich dem größten gemeinsamen Teiler des ursprünglichen Vektors.

Um den größten gemeinsamen Teiler mehrerer Zahlen zu finden, verwenden Sie die Methode der wiederholten Modulation anderer Zahlen mit der kleinsten Zahl, das heißt, Sie subtrahieren andere Zahlen mit der kleinsten Zahl mehrmals, bis ein Rest kleiner als die kleinste Zahl ist links. Seien n positive ganze Zahlen a1, a2,...,an. Der Algorithmus zum Finden des größten gemeinsamen Teilers mehrerer Zahlen wird wie folgt beschrieben:

(1) Finden Sie die kleinste Zahl ungleich Null unter a1, a2 ,...,ein Null-Term aj, wenn es mehrere minimale Nicht-Null-Terme gibt, wählen Sie einen beliebigen

(2) Alle anderen Nicht-Null-Terme ak außer aj werden durch ak mod aj ersetzt, falls vorhanden Gibt es außer aj keine anderen Terme ungleich Null, dann gehe zu (4)

(3) Gehe zu (3)

(4) der größte gemeinsame Teiler von a1, a2,.. ., an ist aj

Zum Beispiel: für 5 Zahlen 34, 56, 78, 24, 85 gibt es

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

Für die 6 Zahlen 12, 24, 30 , 32, 36, 42, es gibt

(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. Algorithmusimplementierung des kleinsten gemeinsamen Vielfachen von mehreren Zahlen

Der Algorithmus zum Ermitteln des kleinsten gemeinsamen Vielfachen von mehreren Zahlen ist:

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

(2) Ersetzen Sie alle Elemente ai in a1, a2,..,an durch m/ai

(3) Finden Sie a1 , a2,.., der minimale Nicht-Null-Term aj in an, wenn es mehrere minimale Nicht-Null-Terme gibt, wählen Sie einen beliebigen

(4) Alle anderen Nicht-Null-Terme aj außer aj werden durch ersetzt ak mod aj ; Wenn außer aj keine anderen Nicht-0-Elemente vorhanden sind, gehen Sie zu (6)

(5) Gehen Sie zu (3)

(6) Das kleinste gemeinsame Vielfache ist m/aj

Der obige Algorithmus wurde in einer Hochsprache in der VC-Umgebung programmiert und implementiert, indem mehrere Gruppen von Beispielen verwendet wurden, um das kleinste gemeinsame Vielfache von zu finden 5 Zufallszahlen wurden mit der Standardmethode verglichen und auf Richtigkeit überprüft. Die Standardberechnungsmethode lautet: Um das kleinste gemeinsame Vielfache von 5 Zufallszahlen zu ermitteln, erhält man das kleinste gemeinsame Vielfache von zwei Zahlen viermal, und das kleinste gemeinsame Vielfache von zwei Zahlen erhält man, indem man den größten gemeinsamen Teiler der beiden Zahlen ermittelt.

5. Fazit

Die Berechnung des kleinsten gemeinsamen Vielfachen mehrerer Zahlen ist eine häufige Grundoperation. Das kleinste gemeinsame Vielfache von n Zahlen kann als größter gemeinsamer Teiler anderer n Zahlen ausgedrückt werden, sodass es berechnet werden kann, indem der größte gemeinsame Teiler mehrerer Zahlen ermittelt wird. Um den größten gemeinsamen Teiler mehrerer Zahlen zu finden, können Sie den Vektorkonvertierungsalgorithmus verwenden, um alles auf einmal zu finden.

Ich glaube, dass Sie die Methode beherrschen, nachdem Sie den Fall in diesem Artikel gelesen haben. Weitere spannende Informationen finden Sie in anderen verwandten Artikeln auf der chinesischen PHP-Website!

Empfohlene Lektüre:

Wie man Angular bedient, um Datenanforderungen zu implementieren

Wie man einen Knoten betreibt und asynchron zur Steuerung verwendet Parallelität

Das obige ist der detaillierte Inhalt vonSo finden Sie mit JS das kleinste gemeinsame Vielfache und den größten gemeinsamen Teiler eines Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!