Algorithmus - Russische Multiplikation

Ein nicht zum Mainstream gehörender Algorithmus zur Multiplikation zweier positiver Ganzzahlen

Angenommen, n und m sind zwei positive ganze Zahlen, berechnen Sie n*m ​​und verwenden Sie nun die Eingabe von n als Maß für die Instanzgröße.

Angenommen, n ist eine gerade Zahl, muss eine Instanz mit halber Originalgröße n/2 verarbeiten, n*m=n/2 * 2m

Angenommen, n ist eine ungerade Zahl, müssen Sie nur eine einfache Anpassung der Formel vornehmen: n*m=(n-1)/2 * 2m

Und verwenden Sie 1*m=m als Beendigungsbedingung.

Wenn wir ein Beispiel aufschreiben, werden wir feststellen, dass wir, wenn alle aktuellen n-Werte ungerade sind, nur die entsprechenden m-Werte addieren müssen, um das Produkt von n*m zu erhalten.

Zum Beispiel: 50*65=25*130=12*260 (+130)=6*520=3*1040=1*2080===2080+1040+130=3250

Lassen Sie uns mit der Code-Implementierung beginnen:
#include <iostream><br> unter Verwendung des Namensraums std;</iostream>

int main()
{
int n,m,mul=0;
cin>>n>>m;
for(int i=n>>1;i>=1;i=i>>1)
{
m=m

Das obige ist der detaillierte Inhalt vonAlgorithmus - Russische Multiplikation. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!