美文网首页
小算法集锦 : 20行代码实现大数相乘

小算法集锦 : 20行代码实现大数相乘

作者: Xinxing_Li | 来源:发表于2018-12-01 01:42 被阅读0次

1.大数相乘

1.1 js 版本 (不计算注释只需要20行)

   /**
   * 大数乘法
   * 思路:逐位相乘,不算进位;最后算进位并拼接字符串
   * @param {number} a 被乘数
   * @param {number} b 乘数
   */
  var LargeNumberTimes = function (a, b) {
    var result = []
    // 转换为整型数组
    a = a.toString().split('').map(t => parseInt(t))
    b = b.toString().split('').map(t => parseInt(t))
    // 逐位相乘,不算进位,与计算方向无关
    for (var i = 0; i < b.length; i++) {
      for (var j = 0; j < a.length; j++) {
        if (!result[i + j])
          result[i + j] = 0
        result[i + j] += b[i] * a[j]
      }
    }
    // 右边的高位向左边低位进位, 在0处无需进位
    for (var i = result.length - 1; i > 0; i--) {
      var more = parseInt(result[i] / 10)
      if (more > 0) {
          result[i - 1] += more;
      }
      result[i] = result[i] % 10;
    }
    return result.join('');
  };

  // 可在 Google 输入框进行验证,如果输入的乘数大小超过了范围
  // (或js会转换为科学计数法),需要以字符串传入
  // Result: 999999999998000000000001
  //console.log( LargeNumberTimes(999999999999, 999999999999) );

1.2 C语言 大数相乘 无依赖

#include <stdio.h>
#define max_length 1000
int strlen(char *a){
    int i;
    for( i=0; a[i] != '\0' ;i++);
    return i;
}
void printIntArray(int a[]){
    for(int i=0;i<max_length*2;i++){
        if(a[i] == -1){
            break;
        }
        printf("%d",a[i]);
    }
    printf("\n");
}
char* LargeNumberTimes(char *a, char *b) {
    
    // 转换为整型数组 , 用 -1 代替 js 的 undefined
    int aArr[max_length],bArr[max_length];
    int resultInt[max_length *2];
    for(int i =0 ;i<max_length;i++){
        aArr[i] = -1 ; bArr[i] = -1 ; resultInt[i] = -1; resultInt[i+max_length] = -1;
    }
    int aLen= strlen(a);
    int bLen= strlen(b);
    for(int i = 0 ; i < aLen ;i++){
        aArr[i] = a[i] - '0';
    }
    for(int i = 0 ; i< bLen ;i++){
        bArr[i] = b[i] - '0';
    }
    
    // 逐位相乘,不算进位,与计算方向无关
    for (int bIndex=bLen-1; bIndex>=0; bIndex--) {
        for (int aIndex=aLen-1; aIndex>=0; aIndex--) {
            if(resultInt[bIndex + aIndex] == -1) {
                resultInt[bIndex + aIndex] = 0 ;
            }
            resultInt[bIndex + aIndex] += bArr[bIndex] * aArr[aIndex];
        }
    }
    printIntArray(resultInt);
    int resultLength =0;
    for(int i =0;i<max_length;i++){
        if(resultInt[i] == -1){
            resultLength = i;
            break;
        }
    }
    // 因为是从左到右的计算顺序,所以进位要反向
    // (也方便最高位进位时,数组可扩)。
    //reverse
    for(int  i = 0; i< resultLength /2 ; i++){
        int t = resultInt[i];
        resultInt[i] = resultInt[resultLength -1 - i];
        resultInt[resultLength -1 - i] = t;
    }
    printIntArray(resultInt);

    // 最高位可能会进位,所以每次循环重新计算length。
    for (int i=0; i< resultLength ; i++) {
        int more;
        if(resultInt[i] == -1) {
            resultInt[i] = 0 ;
        }
        more = resultInt[i] / 10;
        if (more > 0) {
            if(i+1 >= resultLength){
                resultLength ++ ;
            }
            if(resultInt[i+1] == -1) {
                resultInt[i+1] = 0 ;
            }
            resultInt[i + 1] += more;
        }
        resultInt[i] = resultInt[i] % 10;
    }
    char resultStr[max_length*2] ;
    for(int  i = 0; i< resultLength ; i++){
        resultStr[i] = resultInt[resultLength-1-i] + '0';
    }
    resultStr[resultLength] = '\0';
    printf("%s\n",resultStr);
    return resultStr;
}

int main(){
    printf("hello\n");
    printf("%s\n", LargeNumberTimes("5000000", "5000000"));
}

简单的 js 转 c 想法:

  • 函数之间参数传递用 char * ,内部接收后再转 int 计算
  • undefined+ 动态数组 : 使用一个较大的数组初始化为-1,延长长度时就把-1改为0

2. 阿拉伯数字和英文互转

/* 数字转英文 */
function numToEn(str){
    str = str + ''
    var s3 = ['','thousand','million','billion']
    var res = []
    while(str > 0){
        res.push(s3.shift())
        res.push(below1000(str.slice(-3)))
        str = str.slice(0,-3)
    }
    return res.reverse().join(' ')
    
}
function below1000(str){
        str = str - 0;
        var under20 = ['','one','two','three','four','five','six','seven','eight','nine','ten','eleven','twelve','thirteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen','twenty']
        var res = '';
        if(str / 100 >=1) res += under20[Math.floor(str/100)] + " hundred and";
        str = str % 100 
        
        if(str > 20){
            var ten = Math.floor(str / 10)
            res += ' ' + ['','',"twenty","thirty","fourty","fifty","sixty","seventy","eighty","ninety"][ten]
            res += ' ' + under20[str % 10]
        }else { res += ' ' + under20[str] }
        return res;
    }
/* 英文转数字 */
function enToNum(str){
    str = str.split(/\s+/).concat('$')
    var under20Map = ['','one','two','three','four','five','six','seven','eight','nine','ten','eleven','twelve','thirteen','fourteen','fifteen','sixteen','seventeen','eighteen','nineteen','twenty'].reduce((sum,x,index)=>{ sum[x]=index; return sum }, {})
    var s3Map = ['$','thousand','million','billion'].reduce((sum,x,index)=>{ sum[x]=Math.pow(1000,index); return sum }, {})
    var tensMap = ['','ten',"twenty","thirty","fourty","fifty","sixty","seventy","eighty","ninety"].reduce((sum,x,index)=>{ sum[x]=index*10; return sum }, {})
    var res = 0, now = 0
    str.forEach(x=>{
        if(x === "hundred") now *= 100
        if(x in tensMap) now += tensMap[x]
        else if(x in under20Map) now += under20Map[x]
        if(x in s3Map){
            res += now*s3Map[x]
            now = 0
        }
    })
    return res 
}
/* 测试代码 */
function test(count = 10){
    window.logs = []
    window.errors = []
    for(var i=0;i<count;i++){
        var testNum = Math.floor(Math.pow(10, 10)*Math.random())
        testNum = Math.abs(testNum)
        var log = { num : testNum, str : numToEn(testNum), status : true }
        log.retNum = enToNum(log.str)
        if(log.retNum != testNum){
            log.status = false
            window.errors.push(log)
        }
        window.logs.push(log)
    }
}
/* 测试结果 */
test(10)
window.errors // [ ]

字符串格式如下图, 可自行对其中空格或逗号进行增删


相关文章

网友评论

      本文标题:小算法集锦 : 20行代码实现大数相乘

      本文链接:https://www.haomeiwen.com/subject/zrqlcqtx.html