电子商务网站建设任务分解,试剂网站建设,广州网站建设骏域,母婴用品网站建设题目描述 请实现整数数字的乘法、减法和除法运算#xff0c;运算结果均为整数数字#xff0c;程序中只允许使用加法运算符和逻辑运算符#xff0c;允许程序中出现正负常数#xff0c;不允许使用位运算。 你的实现应该支持如下操作#xff1a;
Operations() 构造函数minus…题目描述 请实现整数数字的乘法、减法和除法运算运算结果均为整数数字程序中只允许使用加法运算符和逻辑运算符允许程序中出现正负常数不允许使用位运算。 你的实现应该支持如下操作
Operations() 构造函数minus(a, b) 减法返回a - bmultiply(a, b) 乘法返回a * bdivide(a, b) 除法返回a / b
示例
Operations operations new Operations();
operations.minus(1, 2); //返回-1
operations.multiply(3, 4); //返回12
operations.divide(5, -2); //返回-2提示
你可以假设函数输入一定是有效的例如不会出现除法分母为0的情况单个用例的函数调用次数不会超过1000次
解题思路与代码 这道题属实是一道中等难度的题。需要你有一定的思考量才可以做出来。 题目的要求是不允许我们使用位运算符除了 法以外的算术运算符去实现两个数之间的减法乘法除法函数。 也就是说我们可以使用 法运算符关系运算符 , , , 还有逻辑运算符 ! , , ||去实现这些函数。 这道题建议大家不要抖机灵使用各种没有意义的库函数来简便运算。还有这道题也不要去使用vector这种数据结构。因为vector的模板类在实现时涉及到位运算符和减法运算符的。
接下来其实我们就要思考一个问题。乘法除法的本质是什么
那其实是不是就是加法乘法的本质是加法与减法除法的本质是减法呢那也就是说要实现除法函数首先得实现减法函数。
那我们在来思考一个问题减法的本质是什么
那是不是加上一个相反数呢所以要实现减法函数首先我们还需要去实现一个取反函数。
其实这道题还有一个隐藏的条件那就是提示单个用例的函数调用次数不会超过1000次。
也就是说这道题出题人不想你太容易去解决这个问题。问你如何优化流程也就是缩短时间复杂度。假如说我们要用累加去实现取反过程你想想时间复杂度是不是O(n),那有没有一种办法可以优化累加的时间复杂度呢当然有。我们可以通过事先创建两个数组分别去存储正负2的多少次方的值是多少。到时候我们可以用循环的方式去累加预定值这样是不是就将时间复杂度O(n)缩短到O(logn)了呢
OK这道题讲到这里大家应该心里很有谱了才对。做这道题首先我们要创建两个内置数组去存储可能出现的2的次方值。然后先实现取反函数。再实现减法函数再实现乘法函数最后实现除法函数。
实现的过程中需要大家注意溢出问题。因为虽然题目给的值的范围不会超过int的最大最小范围。但是两个数相减相乘相除的过程中如果处理不好是会发生溢出问题的。
具体的实现请看代码
class Operations {int posN[31]; // 放正数2的n次方int negN[31]; // 放负数2的n次方//取相反数函数int oppN(int num){if(!num) return 0;int res 0;if(num 0){ // 从2^30次方开始检查for(int i 30; i 0; i (-1)){if(num negN[i] 0) continue;num negN[i];res negN[i];}}else{ // 从 - 2^30次方开始检查for(int i 30; i 0; i (-1)){if(num posN[i] 0) continue;num posN[i];res posN[i];}}return res;}
public:Operations() {int p 1;int n -1;posN[0] p;negN[0] n;// 初始化次方数组for(int i 1; i 31; i){p p;posN[i] p;n n;negN[i] n;}}int minus(int a, int b) {return a oppN(b);}int multiply(int a, int b) {if(!a || !b) return 0;if(a 1) return b;if(b 1) return a;if(b 0) return oppN(multiply(a,oppN(b))); // 统一b的正负int res a;int count 1;while(count posN[30] count count b ){res res;count count;}res multiply(a,minus(b,count));return res;}int divide(int a, int b) {if(!a) return 0;int res 1;if(a 0){if(b INT_MIN) return 0;if(b 0) return oppN(divide(a,oppN(b))); // 统一ab的正负if(a b) return 0;int count b;while(count posN[30] a count count){res res;count count;}res divide(minus(a,count),b);}else{if(b 1) return a;if(b 0) return oppN(divide(a,oppN(b)));if(a b) return 0;int count b;while(count negN[30] a count count){res res;count count;}res divide(minus(a,count),b);}return res;}
};复杂度分析 下面是这个代码中各个函数的时间复杂度和空间复杂度分析 oppN(int num)时间复杂度为 O(log(num))因为它在最坏情况下需要遍历数组 posN 或 negN 中的所有元素共 31 个这与输入数字的二进制表示长度成正比。空间复杂度为 O(1)因为它使用了固定数量的额外存储空间。 Operations() 构造函数时间复杂度为 O(1)因为它只需要遍历 31 个元素并执行一定数量的操作。空间复杂度为 O(1)因为它只使用了固定大小的 posN 和 negN 数组。 minus(int a, int b)时间复杂度为 O(log(b))因为它调用了 oppN 函数。空间复杂度为 O(1)因为它没有使用额外的存储空间。 multiply(int a, int b)时间复杂度为 O(log(a) * log(b))因为它使用递归实现每次递归调用都会减小 b 的值递归深度为 O(log(b))而每次递归调用都会调用 minus 函数时间复杂度为 O(log(a))。空间复杂度为 O(log(b))因为递归深度与空间复杂度成正比。 divide(int a, int b)时间复杂度为 O(log(a) * log(b))因为它也是使用递归实现每次递归调用都会减小 a 的值递归深度为 O(log(a))而每次递归调用都会调用 minus 函数时间复杂度为 O(log(b))。空间复杂度为 O(log(a))因为递归深度与空间复杂度成正比。
总的来说这个实现的时间复杂度主要取决于输入数字的二进制表示长度而空间复杂度主要取决于递归深度。
总结 这道题的意义在于考察编程能力、逻辑思维和对基本运算的理解。 它要求我们在限制条件下仅使用加法运算符和逻辑运算符实现整数数字的减法、乘法和除法运算。这种问题有助于锻炼思考能力强化对计算机基本原理的理解以及提高解决问题的灵活性。 同时这种问题也有助于理解计算机是如何处理基本的算术运算的以及为什么某些优化方法例如位运算是有效的。通过解决这种问题你可以加深对计算机科学和编程原理的理解。 最后的最后如果你觉得我的这篇文章写的不错的话请给我一个赞与收藏关注我我会继续给大家带来更多更优质的干货内容。
