Maison > Article > développement back-end > 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.
Entrée : x=15, y=5
Sortie : 3
Entrée : x=10, y=4
Sortie : 2
Entrée : x=-20, y=3
Sortie : -6
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é.
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)OR 1
#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)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 -
exp et la fonction log.
#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.
ConclusionJ'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!