Divisez deux entiers sans utiliser les opérateurs de multiplication, de division et de modulo

Dans ce problème, il suffit de diviser deux entiers sans utiliser les opérateurs de multiplication, de division et de modulo. Bien que nous puissions utiliser des opérations d’addition, de multiplication ou de bits.

L'énoncé du problème indique que nous obtiendrons deux entiers x et y. Sans utiliser la multiplication, la division ou l'opérateur modulo, nous devons déterminer le quotient de x divisé par y.

Exemple

Entrée : x=15, y=5

Sortie : 3

Entrée : x=10, y=4

Sortie : 2

Entrée : x=-20, y=3

Sortie : -6

Méthode

Méthode 1 (utiliser des mathématiques simples)

Dans cette méthode, nous utiliserons un algorithme mathématique simple. Vous trouverez ci-dessous des instructions étape par étape sur ce que nous suivrons -

• Nous continuerons à soustraire le diviseur (c'est-à-dire y) du dividende (c'est-à-dire x) jusqu'à ce que x soit supérieur ou égal à y.

• Lorsque y est supérieur à x, c'est-à-dire que le diviseur est supérieur au dividende, le dividende devient le reste et le nombre de soustractions devient le quotient.

• Stockez le nombre de fois que la soustraction est effectuée dans une variable et renvoyez-la, c'est notre résultat souhaité.

Exemple

Ce qui suit est l'implémentation C++ de l'algorithme &minnus;

#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;
}

Sortie

-10737

Complexité temporelle : O(a/b)

Complexité spatiale : O(1)

Méthode 2 (en utilisant des opérations sur les bits)

• Puisque n'importe quel nombre peut être représenté sous la forme de 0 ou de 1, le quotient peut être représenté sous forme binaire à l'aide de l'opérateur de décalage.

• Utilisez une boucle for pour parcourir les positions de bits du diviseur de 31 à 1.

• Trouvez le premier bit où le diviseur, c'est-à-dire b<<
• Lors de la vérification de la position suivante, ajoutez le résultat à la variable temp pour vous assurer que temp+(b<<
• Mettez à jour le quotient à chaque fois en calculant le quotient

  OR 1<<

• Retournez au quotient après avoir mis à jour le symbole correspondant.

Exemple

Ce qui suit est l'implémentation C++ de la méthode ci-dessus -

#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;
}

Sortie

9
-3

Complexité temporelle : O(log(a))

Complexité spatiale : O(1), car il n'utilise aucun espace supplémentaire.

Méthode 3 (en utilisant la fonction logarithmique)

Dans cette méthode, nous utiliserons une simple fonction logarithmique pour calculer le quotient.

Comme nous le savons tous,

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

peut être encore modifié en

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

C'est donc l'idée de base pour résoudre le problème donné en utilisant cette méthode efficace.

Voici les instructions étape par étape pour la méthode que nous suivrons -

• Si l'un d'eux (c'est-à-dire le dividende ou le diviseur) est 0, nous renverrons 0.

• Maintenant, nous allons vérifier le symbole à l'aide de la fonction OU exclusif (XOR) pour stocker le symbole dans une variable.

• Si le diviseur est 1, le dividende est restitué directement.

• Maintenant, déclarez une variable et utilisez la fonction

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

• Log et exp sont des fonctions intégrées en C++. La fonction log renvoie le logarithme népérien du nombre d'entrée et exp renvoie une valeur égale à e plus la valeur d'entrée.

Exemple

Ce qui suit est l'implémentation C++ de la méthode ci-dessus -

#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;
}

Sortie

-5

Complexité temporelle : O(1), , car il faut un temps constant pour effectuer l'opération.

Complexité spatiale : O(1), car il n'utilise aucun espace supplémentaire.

Conclusion

Dans cet article, nous apprenons à diviser deux entiers sans utiliser d'opérateurs de multiplication, de division ou de modulo. Nous avons appris à résoudre les problèmes de différentes manières avec différentes efficacités. Ils utilisent des mathématiques simples, des opérations sur bits et des fonctions logarithmiques. Parmi elles, l’utilisation de la fonction logarithmique est la méthode la plus efficace car sa complexité temporelle est O(1), qui est la plus petite de toutes les méthodes.

J'espère que cet article vous a aidé à résoudre tous les concepts concernant ce sujet.

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!