首页 > 其他 > 详细

大整数相乘

时间:2014-02-25 16:51:02      阅读:342      评论:0      收藏:0      [点我收藏+]

基本思路:

大数用字符串表示,开辟一个数组,数组长度为两个字符串长度之和。后面的就很简单了。

思路一:(利用数组)

	public String multiply(String num1, String num2)
	{
		int len1 = num1.length();
		int len2 = num2.length();
		int[] num = new int[len1+len2];
		for(int i = 0; i < len1; ++i)  
        {  
            int n1 = num1.charAt(len1-1-i) - ‘0‘;  
            int carry = 0; //进位 
            for (int j = 0; j < len2; ++j)  
            {  
                int n2 = num2.charAt(len2-1-j) - ‘0‘;  
                carry = n1*n2 + carry + num[i+j];  
                num[i+j] = carry % 10;  
                carry /= 10;  
            }  
            num[i+len2] = carry;  
        }  
          
        int i = len1 + len2 - 1;  
        while (i > 0 && num[i] == 0) --i;  
        String result = "";  
        while(i >= 0)  
            result += (char)(num[i--] + ‘0‘);  
              
        return result;  
	}

思路二(不利用数组)

	public String multiply(String num1, String num2)
	{
		String rs = "";
		int flag = 0;//进位
		int tmp = 0;
		String tmpStr = "";
		int count = 0;
		for(int i = num2.length()-1;i>=0;i--)
		{
			flag = 0;
			tmpStr="";
			int num = num2.charAt(i)-‘0‘;
			for(int j = num1.length()-1;j>=0;j--)
			{
				tmp = num*(num1.charAt(j)-‘0‘)+flag;
				flag = tmp/10;
				tmp%=10;
				tmpStr+=tmp;
			}
			if(flag>0)
				tmpStr+=flag;
			for(int m = 0;m<count;m++)
				tmpStr = "0"+tmpStr;
			rs = addStr(rs, tmpStr);
			count++;
		}
		tmpStr = "";
		for(int i=rs.length()-1;i>=0;i--)
			tmpStr+=rs.charAt(i);
		return tmpStr;
	}
	
	//加法
	public String addStr(String m,String n)
	{
		if(m.equals(""))
			return n;
		if(n.equals(""))
			return m;
		int flag = 0;//进位
		String str = "";
		int i=0,j=0;
		for(i = 0,j=0;i<m.length()&&j<n.length();i++,j++)
		{
			int oneNum = m.charAt(i)-‘0‘;
			int twoNum = n.charAt(j)-‘0‘;
			int result = oneNum+twoNum+flag;
			flag = result/10;
			result%=10;
			str+=result;
		}
		if(i<m.length())
		{
			for(;i<m.length();i++)
			{
				int result = m.charAt(i)-‘0‘+flag;
				flag = result/10;
				result%=10;
				str+=result;
			}
		}
		if(j<n.length())
		{
			for(;j<n.length();j++)
			{
				int result = n.charAt(j)-‘0‘+flag;
				flag = result/10;
				result%=10;
				str+=result;
			}
		}
		if(flag>0)
			str+=flag;
		return str;
	}


大整数相乘

原文:http://blog.csdn.net/cow__sky/article/details/19840969

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!