Wie berechnet man Elemente aus einer Schleife?

Question

I haben folgende Daten: y-n-y-y-n-n-n Dies wiederholt sich unendlich, wie: y-n-y-y-n-n-n-y-n-y-y-n-n-n-y-n-y-y-n-n-n ...

Ich habe 5 "x". "x" bleibt nur bei "y". Bedeutung, wenn ich x auf der Schleife oben verteilen, wird es sein: y-n-y-y-n-n-n-y-n-y-y-n-n-n x---x-x-----x-x

Ich möchte zählen, wie viele der Elementschleife I 5 x über zu verbreiten verwenden benötigt, und die Antwort ist 10.

Wie berechne ich es mit einer Formel?

Answer 1

Ich nehme an, was Sie sagen, ist, dass Sie die ersten 10 Elemente der unendlichen Liste verarbeiten müssen, um 5 Y zu erhalten, die mit den 5 Xs übereinstimmen, die Sie haben.

y-n-y-y-n-n-n-y-n-y-y-n-n-n-y-n-y-y-n-n-n... 
x-_-x-x-_-_-_-x-_-x 
       ^
        L____ 10 elements read from the infinite list to place the 5 x's. 

Ich nehme an, dass Ihre Frage ist: die Eingabe von 5 Xs gegeben, was die Anzahl der Elemente, die Sie in der unendlichen Liste zu verarbeiten, müssen diese 5 Xs entsprechen.

Man könnte es mit einer Schleife wie der folgenden Pseudo-Code berechnen:

iElementsMatchedCounter = 0 
iXsMatchedCounter = 0 
iXLimit = 5 
strElement = "" 

if (InfiniteList.IsEmpty() == false) 
{ 
    do 
    { 
     strElement = InfiniteList.ReadNextElement() 

     if (strElement == "y") 
     { 
      iXsMatchedCounter += 1 
     } 

     iElementsMatchedCounter += 1 

    } while ((InfiniteList.IsEndReached() == false) AND (iXsMatchedCounter < iXLimit)) 
} 

if (iXsMatchedCounter = iXLimit) 
    then Print(iElementsMatchedCounter) 
    else Print("End of list reached before all X's were matched!") 

Der Nachteil des obigen Ansatzes ist, dass Sie tatsächlich lesen die unendliche Liste sind, was nicht bevorzugt sein könnte.

Wenn Sie wissen, dass Ihre Liste eine sich unendlich wiederholende Folge der gleichen Elemente y-n-y-y-n-n-n ist, müssen Sie nicht einmal die gesamte Liste durchlaufen, sondern nur die Unterliste y-n-y-y-n-n-n bearbeiten.Der folgende Algorithmus beschreibt, wie:

Gegeben Ihr Ausgangseingang:

• iNumberOfXs = 5 (Sie haben 5 Xs zu entsprechen)
• iNumberOfYsInSubList = 3 (Sie haben 3 Ys in der Unterliste, die Gesamtliste wird unendlich wiederholt)
• iLengthOfSubList = 7 (Sie haben 7 Elemente in der Unterliste ynyynnn)

Wir dann Zwischenergebnisse haben, die berechnet werden:

• iQuotient
• iPartialLengthOfList
• iPendingXs
• iPendingLengthOfList
• iResult

Die follo wing Schritte sollte das Ergebnis geben:

1. unterteilen den iNumberOfXs durch iNumberOfYsInSubList. Hier gibt uns 5/3 = 1.666 ....
2. Verwerfen Sie den Rest des Ergebnisses (die 0.666 ...), so dass Sie mit 1 als iQuotient verlassen werden. Dies ist die Anzahl der vollständigen Unterlisten, die Sie durchlaufen müssen.
3. Multiplizieren dieser Quotient 1 mit iLengthOfSubList Sie 1 * 7 = 7 als iPartialLengthOfList geben. Dies ist die Teilsumme des Ergebnisses und die Anzahl der Elemente in den vollständigen Unterlisten, die Sie durchlaufen.
4. auch den Quotienten mit iNumberOfYsInSubList, multiplizieren und dieses Produkt aus iNumberOfXs, dh iNumberOfXs subtrahieren - (iQuotient iNumberOfYsInSubList *) = 5 - (1 * 3) = 2. Speichern dieser Wert 2 als iPendingXs, die ist die Anzahl der noch nicht übereinstimmenden X-Werte.
5. Beachten Sie, dass iPendingXs immer geringer sein wird als iLengthOfSubList (das heißt, es ist ein Modulo, iPendingXs = iNumberOfXs MODULO iNumberOfYsInSubList).
6. Jetzt haben Sie das triviale Problem der Übereinstimmung von 2 X (d. H. Der Wert iPendingXs oben berechnet) in der Unterliste von y-n-y-y-n-n-n.
7. die anhängige Artikel (gezählt als iPendingLengthOfList) auf Übereinstimmung ist:
   • Gleich iPendingXs wenn iPendingXs 0 oder 1
   • Gleich iPendingXs + 1 Andernfalls (das heißt, wenn iPendingXs ist größer als 1)
   • In diesem Fall iPendingLengthOfList = 3, weil iPendingXs größer als 1.
8. Die Summe iPartialLengthOfList (7) und iPendingLengthOfList (3) ist die Antwort, nämlich 10.

Im Allgemeinen, wenn Sie Ihre Unter list ynyynnn ist nicht vordefiniert, dann können Sie die Regel in Schritt 6 nicht fest codieren, sondern müssen stattdessen nur die Unterliste durchlaufen, um die Ys und Elemente zu zählen, ähnlich dem oben angegebenen Pseudocode.

Wenn es um tatsächlichen Code geht, können Sie ganzzahlige Division und Modulo-Arithmetik verwenden, um schnell zu den Operationen in den Schritten 2 bzw. 4 zu gelangen.

iQuotient = iNumberOfXs/iNumberOfYsInSubList  // COMMENT: here integer division automatically drops the remainder 
iPartialLengthOfList = iQuotient * iLengthOfSubList 

iPendingXs = iNumberOfXs - (iQuotient * iNumberOfYsInSubList) 
// COMMENT: can use modulo arithmetic like the following to calculate iPendingXs 
// iPendingXs = iNumberOfXs % iNumberOfYsInSubList 

// The following IF statement assumes the sub-list to be y-n-y-y-n-n-n 
if (iPendingXs > 1) 
    then iPendingLengthOfList = iPendingXs + 1 
    else iPendingLengthOfList = iPendingXs 

iResult = iPartialLengthOfList + iPendingLengthOfList