C++程序 查找商和余数
在这里,我们将看到如何使用C++程序查找商和余数。
示例:
输入: 被除数=17,除数=5
输出: 商=3,余数=2
输入: 被除数=23,除数=3
输出: 商=7,余数=2
取余运算符将用于计算余数,而除法运算符将用于计算商。
商 = 被除数/除数;
余数 = 被除数%除数;
以下是查找商和余数的C++程序:
// C++ program to find quotient
// and remainder
#include<bits/stdc++.h>
using namespace std;
// Driver code
int main()
{
int Dividend, Quotient,
Divisor, Remainder;
cout << "Enter Dividend & Divisor: ";
cin >> Dividend >> Divisor;
Quotient = Dividend / Divisor;
Remainder = Dividend % Divisor;
cout << "The Quotient = " <<
Quotient << endl;
cout << "The Remainder = " <<
Remainder << endl;
return 0;
}
输出:
时间复杂度: O(1)
辅助空间: O(1)
注意: 如果除数为“0”,则会显示算术异常错误。
方法:“位运算除法”
- 从用户读取被除数和除数。
- 将计数器变量初始化为0。
- 当除数小于或等于被除数时,将除数左移一个位置。
- 每次将除数向左移动时,将计数器变量递减。
- 将除数向右移动一个位置。
- 计数器变量的值是商,最后一次移位后的被除数的值是余数。
- 打印商和余数。
#include <iostream>
using namespace std;
int main() {
int dividend = 17, divisor = 5, quotient = 0, remainder;
int temp_divisor = divisor;
while (temp_divisor <= dividend) {
temp_divisor <<= 1;
quotient++;
}
while (quotient > 0) {
temp_divisor >>= 1;
if (dividend >= temp_divisor) {
dividend -= temp_divisor;
remainder |= 1 << (quotient - 1);
}
quotient--;
}
cout << "商 = " << remainder << endl;
cout << "余数 = " << dividend << endl;
return 0;
}
输出
商 = 3
余数 = 2
此方法的时间复杂度为O(log(D)),其中D是被除数的值。
此程序使用的辅助空间为O(1)
算法:长除法求余数
步骤:
- 输入被除数和除数
-
将商和余数初始化为0
-
如果被除数小于除数,则商为0,余数为被除数
-
否则,执行以下步骤:
a. 将一个名为“dividendIndex”的变量设置为0
b. 当被除数小于除数乘以10的dividendIndex加1次方时,增加dividendIndex
c. 将一个名为“subDividend”的变量设置为被除数除以10的dividendIndex次方
d. 将一个名为“subQuotient”的变量设置为0
e. 当subDividend大于或等于除数时,执行以下操作:
i. 从subDividend中减去除数
ii. 将subQuotient加1
f. 将商增加subQuotient乘以10的dividendIndex次方
g. 将余数增加subDividend乘以10的dividendIndex次方
h. 如果dividendIndex为0,则退出循环。否则,递减dividendIndex并从步骤4b继续。
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int dividend, divisor, quotient = 0, remainder = 0;
// 插入输入
dividend = 17;
divisor = 5;
// 结束输入
if (dividend < divisor) {
quotient = 0;
remainder = dividend;
} else {
int dividendIndex = 0;
while (dividend >= divisor * pow(10, dividendIndex + 1)) {
dividendIndex++;
}
while (dividendIndex >= 0) {
int subDividend = dividend / pow(10, dividendIndex);
int subQuotient = 0;
while (subDividend >= divisor) {
subDividend -= divisor;
subQuotient++;
}
quotient += subQuotient * pow(10, dividendIndex);
remainder += subDividend * pow(10, dividendIndex);
dividend %= (int)pow(10, dividendIndex);
dividendIndex--;
}
}
cout << "商 = " << quotient << ",余数 = " << remainder << endl;
return 0;
}
输出
商 = 3,余数 = 2
时间复杂度:O(D),其中D是被除数的位数
辅助空间:O(1)