Bahagi dua integer tanpa menggunakan pengendali pendaraban, pembahagian dan modulo

Dalam masalah ini, kita hanya perlu membahagi dua integer tanpa menggunakan operator darab, bahagi dan modulo. Walaupun kita boleh menggunakan operasi tambah, darab atau bit.

Penyataan masalah menyatakan bahawa kita akan mendapat dua integer x dan y. Tanpa menggunakan pendaraban, pembahagian, atau operator modulo, kita perlu menentukan hasil bagi x dibahagikan dengan y.

Contoh

Input: x=15, y=5

Output: 3

Input: x=10, y=4

Output: 2

Input: x=-20, y=3

Output: -6

Kaedah

Kaedah 1 (guna matematik mudah)

Dalam kaedah ini kita akan menggunakan algoritma matematik yang mudah. Di bawah adalah arahan langkah demi langkah tentang perkara yang akan kami ikuti -

• Kami akan terus menolak pembahagi (iaitu y) daripada dividen (iaitu x) sehingga x lebih besar daripada atau sama dengan y.

• Apabila y lebih besar daripada x, iaitu, pembahagi lebih besar daripada dividen, dividen menjadi baki, dan bilangan tolak menjadi hasil bahagi.

• Simpan bilangan kali penolakan dilakukan dalam pembolehubah dan kembalikannya, ini adalah output yang kita inginkan.

Contoh

Berikut ialah pelaksanaan C++ bagi algoritma di atas &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;
}

Output

-10737

Kerumitan masa: O(a/b)

Kerumitan ruang: O(1)

Kaedah 2 (menggunakan operasi bit)

• Memandangkan sebarang nombor boleh diwakili sebagai 0 atau 1, hasil bagi boleh diwakili dalam bentuk binari menggunakan operator syif.

• Gunakan gelung for untuk mengulang kedudukan bit pembahagi dari 31 kepada 1.

• Cari bit pertama di mana pembahagi, iaitu, b<

• Apabila mengesahkan kedudukan seterusnya, tambahkan hasil pada pembolehubah temp untuk memastikan bahawa temp+(b<

• Kemas kini hasil bagi setiap kali dengan mengira hasil bagiATAU 1<

• Kembali ke hasil bahagi selepas mengemas kini simbol yang sepadan.

Contoh

Berikut ialah pelaksanaan C++ bagi kaedah di atas -

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

Output

9
-3

Kerumitan masa: O(log(a))

Kerumitan ruang: O(1), kerana ia tidak menggunakan ruang tambahan.

Kaedah 3 (menggunakan fungsi logaritma)

Dalam kaedah ini, kita akan menggunakan fungsi logaritma mudah untuk mengira hasil bahagi.

Seperti yang kita sedia maklum,

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

boleh diubah suai lagi kepada

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

Jadi, inilah idea asas untuk menyelesaikan masalah yang diberikan menggunakan kaedah yang cekap ini.

Berikut adalah arahan langkah demi langkah untuk kaedah yang akan kami ikuti -

• Jika salah satu daripadanya (iaitu dividen atau pembahagi) adalah 0, kami akan mengembalikan 0.

• Sekarang kita akan menyemak simbol menggunakan fungsi OR eksklusif (XOR) untuk menyimpan simbol dalam pembolehubah.

• Jika pembahagi 1, dividen dipulangkan terus.

• Sekarang, isytiharkan pembolehubah dan gunakan fungsi exp< 将等于 $mathrm{e^{(In(a):-:In(b))}}$ 的值存储在其中/b> dan fungsi log.

• Log dan exp ialah fungsi terbina dalam dalam C++. Fungsi log mengembalikan logaritma asli nombor input, dan exp mengembalikan nilai yang sama dengan e ditambah nilai input.

Contoh

Berikut ialah pelaksanaan C++ bagi kaedah di atas -

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

Output

-5

Kerumitan masa: O(1), , kerana ia memerlukan masa yang berterusan untuk melaksanakan operasi.

Kerumitan ruang: O(1), kerana ia tidak menggunakan ruang tambahan.

Kesimpulan

Dalam artikel ini, kita belajar membahagi dua integer tanpa menggunakan pengendali pendaraban, pembahagian atau modulo. Kami belajar untuk menyelesaikan masalah dengan cara yang berbeza dengan kecekapan yang berbeza. Mereka menggunakan matematik mudah, operasi bit, dan fungsi logaritma. Antaranya, menggunakan fungsi logaritma adalah kaedah yang paling cekap kerana kerumitan masanya ialah O(1), iaitu yang paling kecil di antara semua kaedah.

Saya harap artikel ini membantu anda menyelesaikan semua konsep berkenaan topik ini.

Atas ialah kandungan terperinci Bahagi dua integer tanpa menggunakan pengendali pendaraban, pembahagian dan modulo. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!