大整数相乘递归分治思想技巧.doc

下载文档 降价啦

471
0
约6.4千字
约 14页
2016-12-25 发布于湖北
举报
版权申诉
保障服务

大整数相乘递归分治思想技巧.doc

1、本文档共14页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

package com.liheng.algorithm; import java.util.Scanner; import java.util.regex.Matcher; import java.util.regex.Pattern /** * 大整数乘法 * * */ public class BigIntMultiply { //规模只要在这个范围内就可以直接计算了 private final static int SIZE = 4; // 此方法要保证入参len为X、Y的长度最大值 private static String bigIntMultiply(String X, String Y, int len) { // 最终返回结果 String SA_B,SD_C; String str = ; int flag=0; // 补齐X、Y，使之长度相同 X = formatNumber(X, len); Y = formatNumber(Y, len); // 少于4位数，可直接计算 if (len = SIZE) { return + (Integer.parseInt(X) * Integer.parseInt(Y)); } // 将X、Y分别对半分成两部分 int len1 = len / 2; int len2 = len - len1; String A = X.substring(0, len1); String B = X.substring(len1); String C = Y.substring(0, len1); String D = Y.substring(len1); // 两字符串长度要相同 int lenM = Math.max(A.length(), B.length()); String A1 = formatNumber(A, lenM); String B1 = formatNumber(B, lenM); int a=Integer.parseInt(A1.substring(0, 1)); int b= Integer.parseInt(B1.substring(0, 1)); if(ab) { SA_B=dudcting(A1,B1); } else { SA_B = dudcting(B1,A1); flag++; } lenM = Math.max(A.length(), B.length()); String C1 = formatNumber(C, lenM); String D1 = formatNumber(D, lenM); int c=Integer.parseInt(C1.substring(0, 1)); int d= Integer.parseInt(D1.substring(0, 1)); if(dc) { SD_C=dudcting(D1,C1); } else { SD_C = dudcting(C1,D1); flag++; } lenM=Math.max(SA_B.length(), SD_C.length()); String ABDC=; if(flag!=1) { ABDC = bigIntMultiply(SA_B, SD_C, lenM); }else { ABDC = bigIntMultiply(SA_B, SD_C, lenM); } String A