29.两数相除

[wind-jyf]

两数相除

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

解题思路

• 暴力解题法（不可取）

  1. 对除数进行循环累加
  2. 循环的次数便是商
  3. 循环次数过多，超出时间限制

  var sum = 0;
  var num = 0;
  while(sum<dividend){
      sum+=divisor;
      num++;
  }

• 扩大除数倍数

  1. 被除数循环减除数
  2. 循环一次除数就增加一倍
  3. 商便是增加的倍数之和
  4. 当被除数小于除数的时候，就应该把除数置为初值

  while(a>=b){//a为被除数，b为除数
          while(a>=b){
              a=a-b;
              b+=Math.abs(divisor);//除数增倍
              num+=num1;//商为倍数之和
              num1++;//求此时的倍数
          }
          b = Math.abs(divisor);//置初值
          num1 = 1;//倍数置为初值
      }

  28/3      余数    倍数
  28-3=25    3       1
  25-6=19    6       2
  19-9=10    9       3
  10-12//不成立  
  10-3=7     3       1
  7-6=0      6       2
  1-9//不成立
  倍数之和：
  1+2+3+1+2=9

所遇到的问题

1. 最开始的时候就选择了第一种暴力法，结果超时，其实应该更多的去运用算法，而不是选择作弊

2. 通过第二种解决方法，算是理解到了算法蕴含的深意

完整代码

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    if(dividend==0){
        return 0;
    }
    var flag = true;
    var array1 = dividend.toString().split('');
    var array2 = divisor.toString().split('');
    if(isNaN(array1[0])==isNaN(array2[0])){
        flag = true;
    }else{
        flag = false;
    }
    //以上均为判断符号做铺垫
    var a = Math.abs(dividend);
    var b = Math.abs(divisor);
    var num = 0;//存储计算出来的商
    var num1 = 1;//计算倍数
    while(a>=b){
        while(a>=b){
            a=a-b;
            b+=Math.abs(divisor);
            num+=num1;
            num1++;
        }
        b = Math.abs(divisor);
        num1 = 1;
    }
    //以下为对符号的处理
    if(flag == false){
        num= -num;
    }
    if(num<-2147483648||num>2147483647){
        return 2147483647;
    }
    return num;
};

---