Dividieren Sie zwei ganze Zahlen, ohne die Multiplikations-, Divisions- und Modulo-Operatoren zu verwenden

Bei diesem Problem müssen wir nur zwei ganze Zahlen dividieren, ohne Multiplikations-, Divisions- und Modulo-Operatoren zu verwenden. Obwohl wir Additions-, Multiplikations- oder Bitoperationen verwenden können.

Die Problemstellung besagt, dass wir zwei ganze Zahlen x und y erhalten. Ohne Multiplikation, Division oder den Modulo-Operator müssen wir den Quotienten von x dividiert durch y bestimmen.

Beispiel

Eingabe: x=15, y=5

Ausgabe: 3

Eingabe: x=10, y=4

Ausgabe: 2

Eingabe: x=-20, y=3

Ausgabe: -6

Methode

Methode 1 (einfache Mathematik verwenden)

Bei dieser Methode verwenden wir einen einfachen mathematischen Algorithmus. Nachfolgend finden Sie eine Schritt-für-Schritt-Anleitung, was wir befolgen werden –

• Wir subtrahieren so lange den Divisor (d. h. y) vom Dividenden (d. h. x), bis x größer oder gleich y ist.

• Wenn y größer als x ist, das heißt, der Divisor größer als der Dividend ist, wird der Dividend zum Rest und die Anzahl der Subtraktionen wird zum Quotienten.

• Speichern Sie die Häufigkeit, mit der die Subtraktion durchgeführt wird, in einer Variablen und geben Sie sie zurück. Dies ist unsere gewünschte Ausgabe.

Beispiel

Das Folgende ist die C++-Implementierung des obigen Algorithmus −

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long division(long long a,long long b) // where a is dividend and b is divisor
{
   long long sign=1;
   if((a<0) ^( b<0))  // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = +
   {
      sign=-1; 
   }
   long long m=abs(a);
   long long n=abs(b);
   long long count=0; // for storing the quotient 
   while(m>=n){
      m=m-n;
      count++;
   }
   if(sign==-1) // when sign is negative
   {
      count=-count;
   }
   return count;
} 
int main(){
   long long a=-21474;
   long long b=2;
   long long val=division(a,b);
   cout<<val<<endl;
   return 0;
}

Ausgabe

-10737

Zeitliche Komplexität: O(a/b)

Raumkomplexität: O(1)

Methode 2 (mit Bitoperationen)

• Da jede Zahl als 0 oder 1 dargestellt werden kann, kann der Quotient mithilfe des Schiebeoperators in binärer Form dargestellt werden.

• Verwenden Sie eine for-Schleife, um die Bitpositionen des Divisors von 31 bis 1 zu iterieren.

• Suchen Sie das erste Bit, bei dem der Divisor, also b<<
• Wenn Sie die nächste Position überprüfen, fügen Sie das Ergebnis zur temporären Variablen hinzu, um sicherzustellen, dass temp+(b<<
• Aktualisieren Sie den Quotienten jedes Mal, indem Sie den Quotienten

  OR 1<< berechnen

• Kehren Sie zum Quotienten zurück, nachdem Sie das entsprechende Symbol aktualisiert haben.

Beispiel

Das Folgende ist die C++-Implementierung der oben genannten Methode -

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long division(long long a,long long b) // where a is dividend and b is divisor
{
   long long sign=1;
   if((a<0) ^( b<0))  // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = +
   {
      sign=-1; 
   }
   long long m=abs(a);
   long long n=abs(b);
   long long count=0; // for storing the quotient 
   long long temp=0;
   for (int j = 31; j >= 0; --j){
   
      if (temp + (n << j) <= m){
         temp += n << j;
         count |= 1L << j;
      }
   }
   if(sign==-1) // when sign is negative
   {
      count=-count;
   }
   return count;
   
} 
int main(){
   long long a=49;
   long long b=5;
   long long val=division(a,b);
   cout<<val<<endl;
   a=-18,b=5;
   cout<<division(a,b);
   
   return 0;
}

Ausgabe

9
-3

Zeitliche Komplexität: O(log(a))

Raumkomplexität: O(1), weil es keinen zusätzlichen Platz beansprucht.

Methode 3 (mit logarithmischer Funktion)

Bei dieser Methode verwenden wir eine einfache logarithmische Funktion, um den Quotienten zu berechnen.

Wie wir alle wissen,

$$mathrm{In(frac{a}{b}):=:In(a):-:In(b)}$$

kann weiter geändert werden zu

$$mathrm{frac{a}{b}:=:e^{(In(a):-:In(b))}}$$

Das ist also die Grundidee, das gegebene Problem mit dieser effizienten Methode zu lösen.

Hier finden Sie die Schritt-für-Schritt-Anleitung für die Methode, der wir folgen werden –

• Wenn einer davon (d. h. Dividende oder Divisor) 0 ist, geben wir 0 zurück.

• Jetzt prüfen wir das Symbol mit der Exklusiv-ODER-Funktion (XOR), um das Symbol in einer Variablen zu speichern.

• Wenn der Divisor 1 ist, wird die Dividende direkt zurückgegeben.

• Deklarieren Sie nun eine Variable und verwenden Sie die Funktion

  exp und die Funktion < 将等于 $mathrm{e^{(In(a):-:In(b))}}$ 的值存储在其中/b>log.

• Log und exp sind integrierte Funktionen in C++. Die Log-Funktion gibt den natürlichen Logarithmus der Eingabezahl zurück und exp gibt einen Wert zurück, der e plus dem Eingabewert entspricht.

Beispiel

Das Folgende ist die C++-Implementierung der oben genannten Methode -

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
long long int divide(long long int a,long long int b){
   long long int sign=1;
   if(a==0||b==0) // when a is zero or b is zero
   {
      return 0;
   }
   if((a>0) ^ (b>0)) // - ^ - = +,+ ^ - = - , - ^ + = - , + ^ + = +
   {
      sign=-1;
   }
   if(b==1) // when b is 1 then it will return a example 51/1 = 51
   {
      sign==-1?-a:a;
      return a;
   }
   long long int m=abs(a);
   long long int n=abs(b);
   
   //log function return the logarithmic value of the entered value with base e i.e. natural log of the entered value
   //exp function return the value equal to e^(entered value)
   long long int ans =exp(log(m) - log(n)) + 0.0000000001; 
   
   // if it gives the value in decimal we will add from 0.0000000001 to account for accuracy errors
   if(sign==-1) // when sign is negative return the negative ans
   {
      return -ans;
   }
   return ans;
   
}
int main(){
   long long int ans=divide(47,-9);
   cout<<ans<<endl;
   
   return 0;
}

Ausgabe

-5

Zeitliche Komplexität: O(1), , da die Ausführung der Operation eine konstante Zeit benötigt.

Raumkomplexität: O(1), weil es keinen zusätzlichen Platz beansprucht.

Fazit

In diesem Artikel lernen wir, zwei ganze Zahlen zu dividieren, ohne Multiplikations-, Divisions- oder Modulo-Operatoren zu verwenden. Wir haben gelernt, Probleme auf unterschiedliche Weise und mit unterschiedlicher Effizienz zu lösen. Sie verwenden einfache Mathematik, Bitoperationen und logarithmische Funktionen. Unter diesen ist die Verwendung der logarithmischen Funktion die effizienteste Methode, da ihre Zeitkomplexität O(1) beträgt, was die kleinste aller Methoden ist.

Ich hoffe, dieser Artikel hat Ihnen geholfen, alle Konzepte zu diesem Thema zu lösen.

Das obige ist der detaillierte Inhalt vonDividieren Sie zwei ganze Zahlen, ohne die Multiplikations-, Divisions- und Modulo-Operatoren zu verwenden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!