当前位置: 首页 > news >正文

四川省建设质量工程协会网站logo设计在线生成免费商标

四川省建设质量工程协会网站,logo设计在线生成免费商标,深圳推广公司是什么,wordpress建立个人博客戳蓝字“CSDN云计算”关注我们哦#xff01;如何用程序实现大整数相乘呢#xff1f;在上一篇文章 漫画#xff1a;如何实现大整数相乘#xff1f;#xff08;上#xff09; 当中#xff0c;我们介绍了两种思路#xff1a;1.像列竖式一样#xff0c;把两整数按位依次相… 戳蓝字“CSDN云计算”关注我们哦如何用程序实现大整数相乘呢在上一篇文章  漫画如何实现大整数相乘上 当中我们介绍了两种思路1.像列竖式一样把两整数按位依次相乘这个思路的时间复杂度是On^2。2.利用分治法把每个大整数分成高位和低位两部分转化成四个较小的乘积。这个思路的时间复杂度同样是On^2。那么有什么样的优化方案可以使时间复杂度优于On^2呢我们今天一起来研究下。如何做调整呢其实很简单连小学生都会这样一来原本的4次乘法和3次加法转变成了3次乘法和6次加法。这样一来时间复杂度是多少呢假设两个长度为n的大整数相乘整体运算规模是T(n) 。刚才我们说过两个大整数相乘可以被拆分成三个较小的乘积所以在第一次分治时T(n)和T(n/2)有如下关系T(n) 3T(n/2) f(n)其中f(n)是6次加法的运算规模f(n)的渐进时间复杂度很明显是O(n)。此时让我们回顾一下master定理设常数a 1b 1如果一个算法的整体计算规模 T(n)   a T(n / b) f(n)那么则有如下规律对于T(n) 3T(n/2) f(n)这个关系式来说 a3 b2。把a和b的值以及f(n)的时间复杂度带入到master定理的第一个规律也就是下面的规律发现正好符合条件。怎么符合条件呢推导过程如下所以我们的平均时间复杂度是2 和 1.59 之间的差距看似不大但是当整数长度非常大的时候两种方法的性能将是天壤之别。下面展示一下实现代码。我们的代码非常复杂在这里只作为参考最重要的还是解决问题的思路/** * 大整数乘法 * param bigNumberA  大整数A * param bigNumberB  大整数B */public static String bigNumberMultiply(String bigNumberA, String bigNumberB) {    boolean isNegative false;    if ((bigNumberA.startsWith(-) bigNumberB.startsWith(-))            || (!bigNumberA.startsWith(-) !bigNumberB.startsWith(-))) {        // 两数同符号的情况        bigNumberA bigNumberA.replaceAll(-, );        bigNumberB bigNumberB.replaceAll(-, );    } else if ((bigNumberA.startsWith(-) !bigNumberB.startsWith(-))            || (!bigNumberA.startsWith(-) bigNumberB.startsWith(-))) {        // 两数不同符号的情况        bigNumberA bigNumberA.replace(-, );        bigNumberB bigNumberB.replace(-, );        isNegative true;    }    // 如果两数长度之和小于10直接相乘返回    if (bigNumberA.length() bigNumberB.length() 10) {        // 计算乘积        int tmp (Integer.parseInt(bigNumberA) * Integer.parseInt(bigNumberB));        if (tmp 0) {            return 0;        }        String value String.valueOf(tmp);        if(isNegative){            value - value;        }        return value;    }    // 公式 AC * 10^n((A-B)(D-C)ACBD) * 10^(n/2)BD当中的a,b,c,d    String a, b, c, d;    if (bigNumberA.length() 1) {        a 0;        b bigNumberA;    } else {        if (bigNumberA.length() % 2 ! 0) {            bigNumberA 0 bigNumberA;        }        a bigNumberA.substring(0, bigNumberA.length() / 2);        b bigNumberA.substring(bigNumberA.length() / 2);    }    if (bigNumberB.length() 1) {        c 0;        d bigNumberB;    } else {        if (bigNumberB.length() % 2 ! 0) {            bigNumberB 0 bigNumberB;        }        c bigNumberB.substring(0, bigNumberB.length() / 2);        d bigNumberB.substring(bigNumberB.length() / 2);    }    // 按最大位数取值以确定补零数目    int n bigNumberA.length() bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();    //t1,t2为中间运算结果t3为乘法运算完毕的结果    String t1, t2, t3;    String ac bigNumberMultiply(a, c);    String bd bigNumberMultiply(b, d);    //t1(A-B)(D-C)    t1 bigNumberMultiply(bigNumberSubtract(a, b), bigNumberSubtract(d, c));    //t2(A-B)(D-C)ACBD    t2 bigNumberSum(bigNumberSum(t1, ac), bd);    //t3 AC * 10^n((A-B)(D-C)ACBD) * 10^(n/2)BD    t3 bigNumberSum(bigNumberSum(Power10(ac, n), Power10(t2, n/2)), bd).replaceAll(^0, );    if (t3 )        return 0;    if(isNegative){        return - t3;    }    return t3;}/** * 大整数加法 * param bigNumberA  大整数A * param bigNumberB  大整数B */public static String bigNumberSum(String bigNumberA, String bigNumberB) {    if (bigNumberA.startsWith(-) !bigNumberB.startsWith(-)) {        return bigNumberSubtract(bigNumberB, bigNumberA.replaceAll(^-, ));    } else if (!bigNumberA.startsWith(-) bigNumberB.startsWith(-)) {        return bigNumberSubtract(bigNumberA, bigNumberB.replaceAll(^-, ));    } else if (bigNumberA.startsWith(-) bigNumberB.startsWith(-)) {        return - bigNumberSum(bigNumberA.replaceAll(^-, ), bigNumberB.replaceAll(^-, ));    }    //1.把两个大整数用数组逆序存储数组长度等于较大整数位数1    int maxLength bigNumberA.length() bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();    int[] arrayA new int[maxLength1];    for(int i0; i bigNumberA.length(); i){        arrayA[i] bigNumberA.charAt(bigNumberA.length()-1-i) - 0;    }    int[] arrayB new int[maxLength1];    for(int i0; i bigNumberB.length(); i){        arrayB[i] bigNumberB.charAt(bigNumberB.length()-1-i) - 0;    }    //2.构建result数组数组长度等于较大整数位数1    int[] result new int[maxLength1];    //3.遍历数组按位相加    for(int i0; iresult.length; i){        int temp result[i];        temp arrayA[i];        temp arrayB[i];        //判断是否进位        if(temp 10){            temp - 10;            result[i1] 1;        }        result[i] temp;    }    //4.把result数组再次逆序并转成String    StringBuilder sb new StringBuilder();    //是否找到大整数的最高有效位    boolean findFirst false;    for (int i result.length - 1; i 0; i--) {        if(!findFirst){            if(result[i] 0){                continue;            }            findFirst true;        }        sb.append(result[i]);    }    return sb.toString();}/** * 大整数减法 * param bigNumberA  大整数A * param bigNumberB  大整数B */public static String bigNumberSubtract(String bigNumberA, String bigNumberB) {    int compareResult compare(bigNumberA, bigNumberB);    if (compareResult 0) {        return 0;    }    boolean isNegative false;    if (compareResult -1) {        String tmp bigNumberB;        bigNumberB bigNumberA;        bigNumberA tmp;        isNegative true;    }    //1.把两个大整数用数组逆序存储数组长度等于较大整数位数1    int maxLength bigNumberA.length() bigNumberB.length() ? bigNumberA.length() : bigNumberB.length();    int[] arrayA new int[maxLength1];    for(int i0; i bigNumberA.length(); i){        arrayA[i] bigNumberA.charAt(bigNumberA.length()-1-i) - 0;    }    int[] arrayB new int[maxLength1];    for(int i0; i bigNumberB.length(); i){        arrayB[i] bigNumberB.charAt(bigNumberB.length()-1-i) - 0;    }    //2.构建result数组数组长度等于较大整数位数1    int[] result new int[maxLength1];    //3.遍历数组按位相加    for(int i0; iresult.length; i){        int temp result[i];        temp arrayA[i];        temp - arrayB[i];        //判断是否进位        if(temp 0){            temp 10;            result[i1] -1;        }        result[i] temp;    }    //4.把result数组再次逆序并转成String    StringBuilder sb new StringBuilder();    //是否找到大整数的最高有效位    boolean findFirst false;    for (int i result.length - 1; i 0; i--) {        if(!findFirst){            if(result[i] 0){                continue;            }            findFirst true;        }        sb.append(result[i]);    }    String value sb.toString();    if (isNegative) {        value - value;    }    return value;}// 比较大小private static int compare(String x, String y) {    if (x.length() y.length()) {        return 1;    } else if (x.length() y.length()) {        return -1;    } else {        for (int i 0; i x.length(); i) {            if (x.charAt(i) y.charAt(i)) {                return 1;            } else if (x.charAt(i) y.charAt(i)) {                return -1;            }        }        return 0;    }}// 扩大10的n次方倍public static String Power10(String num, int n) {    for (int i 0; i n; i) {        num 0;    }    return num;}public static void main(String[] args) {    String x 1513143;    String y 9345963;    System.out.println(bigNumberMultiply(x, y));}需要注意的是这段实现代码只适用于两个大整数长度相等的情况。如果想求解长度不等的整数相乘只需要对代码做微小的改动有兴趣的小伙伴没有试一试。文章转自程序员小灰1.微信群添加小编微信color_ld备注“进群姓名公司职位”即可加入【云计算学习交流群】和志同道合的朋友们共同打卡学习2.征稿投稿邮箱liudancsdn.net微信号color_ld。请备注投稿姓名公司职位。推荐阅读下一次 IT 变革边缘计算Edge computing为什么 ofo 彻底凉了| 畅言AI in 美团吃喝玩乐背后的黑科技无业务不技术那些誓用区块链重塑的行业发展怎么样了Windows 成“弃子”Linux 终上位突发12306 脱库 410 万用户数据究竟从何泄漏可替代Android的6大开源移动操作系统程序员求助被领导强行要求写Bug该怎么办网友的回答让我笑翻程序员抢票姿势 ↓交朋友还能抢票为交流学习请备注姓名公司职位学校专业点击“阅读原文”打开 CSDN App 阅读更贴心
http://www.pierceye.com/news/392699/

相关文章:

  • 教着做美食的网站wordpress 无法安装主题
  • 只选设计师的网站牛商网是干什么的
  • 网站设计中新闻版块怎么做乐清新闻联播
  • 网站开发维护员挣钱吗全球电子商务公司排行
  • 祥云县住房和城乡建设网站百度热议排名软件
  • 网站开发攻克时间网站模版制作教程
  • 遵义一般做一个网站需要多少钱菲斯曼售后服务中心
  • 教务系统网站建设模板下载东莞企业高端网站建设
  • 淮南建设公司网站网站建设对教育解决方案
  • 泰兴建设局网站wordpress资料图片不显示
  • 外贸推广免费网站图片 网站源码
  • 博客推广那个网站列好邢台网红桥
  • 艺之都网站建设微信app开发腾讯视频分享到wordpress
  • 洛阳最好的做网站的公司哪家好建网站需要哪些文件夹
  • 舟山企业网站建设导出wordpress用户
  • 肇庆新农村建设内容在哪个网站有关天猫网站开发的论文
  • 网站建设代码生成器php网站开发专员招聘
  • 视频教学网站cms陕西网站备案查询
  • 湖州网站设计浙北数据wordpress自定义搜索页面
  • 昆明公司网站开发流线型的网站建设
  • 南京建设网站企业泊头市建设网站
  • 前端跟后端哪个就业难北京网站建设seo优化
  • 简述网站开发建设的基本流程做一个京东这样的网站需要多少钱
  • 与通信工程专业做项目的网站微信开发显示wordpress
  • 自己做链接网站萍乡做网站哪家好
  • 做网站最适合用多大的图片医院 网站建设 新闻
  • 网站开发职业分析产品展示的手机网站
  • 精通网站建设pdf网上自学电脑课程
  • 一站式网站建设业务沈阳网站建设 熊掌号
  • 58同城网站建设目的劳务公司怎么注册需要什么要求