資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學不用乘法、除法和取模運算子來除兩個整數
在這個問題中，我們只需要不用乘法、除法和取模運算子來除兩個整數。雖然我們可以使用加法、乘法或位操作。
問題陳述指出，我們將得到兩個整數 x 和 y。不用乘法、除法或取模運算子，我們需要確定 x 除以 y 後的商。
示例
輸入：x=15 , y=5
輸出: 3
輸入：x=10 , y=4
輸出: 2
輸入：x=-20 , y=3
輸出: -6
方法
方法一（使用簡單的數學方法）
在這種方法中，我們將使用一個簡單的數學演算法。以下是我們將遵循的步驟的逐步說明：
我們將不斷從被除數 x 中減去除數 y，直到 x 大於或等於 y。
當 y 大於 x（即除數大於被除數）時，被除數變成餘數，減法的次數變成商。
將減法執行的次數儲存在一個變數中並返回它，這就是我們想要的輸出。
示例
以下是上述演算法的 C++ 實現：
#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;
}
輸出
-10737
時間複雜度：O(a/b)
空間複雜度：O(1)
方法二（使用位操作）
由於任何數字都可以表示為 0 或 1 的形式，因此可以使用移位運算子以二進位制形式表示商。
使用 for 迴圈迭代除數的從 31 到 1 的位位置。
找到除數 (b<
在驗證下一個位置時，將結果新增到 temp 變數中，以確保 temp+(b<
每次透過計算商 OR 1<
更新相應的符號後返回商。
示例
以下是上述方法的 C++ 實現：
#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;
}
輸出
9 -3
時間複雜度：O(log(a))
空間複雜度：O(1)，因為它不使用額外的空間。
方法三（使用對數函式）
在這種方法中，我們將使用一個簡單的對數函式來計算商。
眾所周知，
$$\mathrm{In(\frac{a}{b})\:=\:In(a)\:-\:In(b)}$$
這可以進一步修改為
$$\mathrm{\frac{a}{b}\:=\:e^{(In(a)\:-\:In(b))}}$$
所以這是使用這種有效方法解決給定問題的基本思想。
以下是我們將遵循的方法的逐步說明：
如果被除數或除數為 0，我們將返回 0。
現在，我們將使用異或函式 (XOR) 檢查符號並將符號儲存在一個變數中。
如果除數為 1，則只需返回被除數。
現在，宣告一個變數，並使用 **exp** 函式和 **log** 函式將 $\mathrm{e^{(In(a)\:-\:In(b))}}$ 的值儲存在其中。
Log 和 exp 是 C++ 中的內建函式。Log 函式返回輸入數字的自然對數值，exp 返回等於 e 的輸入值次方的值。
示例
以下是上述方法的 C++ 實現：
#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;
}
輸出
-5
時間複雜度：O(1)，因為執行操作需要常數時間。
空間複雜度：O(1)，因為它不使用額外的空間。
結論
在本文中，我們學習了不用乘法、除法或取模運算子來除兩個整數。我們學習了用不同方法解決問題，效率也不同。它們是使用簡單的數學方法、使用位操作和使用對數函式。在所有這些方法中，使用對數函式是最有效的方法，因為它具有 O(1) 的時間複雜度，這是所有方法中最低的。
我希望這篇文章能幫助你解決所有關於這個主題的概念。
5K+ 次瀏覽
