。。。。。

Programmer2.x

浏览: 10889 次
性别:
来自: 杭州

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (6)

社区版块

存档分类

算法 C C++C#

。。。。。

分享到：

。。。。。 | 。。。。。

2008-12-30 22:35
浏览 807
评论(8)
论坛回复 / 浏览 (8 / 663)
分类:企业架构
查看更多

8 楼 donnki 2008-12-31

怎么重复发了次。。。麻烦斑猪删一条谢谢。
main函数在最后
调用strAdd(bignumber1, bignumber2)实现超大数相加
调用multiply(bignumber1, bignumber2)实现超大数相乘

7 楼 donnki 2008-12-31

刚翻出很多以前写的一段代码。

之所以import java.math.BigInteger是为了验证程序正确性，实际算法里不包含BigInteger类


import java.math.BigInteger;
import java.util.*;
public class MyBigIntegerAdd {
/**
 * 实现超大整数相加、相乘。
 */
	private static int[] str2int(String bigNumber) {
		//System.out.println(bigNumber.length());
		int[] array;
		if (bigNumber.length() < 10) {
			array = new int[1];
			array[0] = Integer.parseInt(bigNumber);
		} else {
			array = new int[bigNumber.length() % 9 == 0 ? bigNumber.length() / 9 : (bigNumber.length() / 9 + 1)];
			StringBuffer buf = new StringBuffer(bigNumber);
			buf.reverse();

			for (int i = 0; i < array.length; i++) {
				array[i] = Integer
						.parseInt((new StringBuffer(buf.substring(i * 9,
								(i + 1) * 9 > bigNumber.length() ? bigNumber
										.length() : (i + 1) * 9)).reverse())
								.toString());
				// System.out.println(array[i]);
			}
		}
		return array;
	}

	
	private static String add(int[] a, int[] b) {
		int t = 0;
		int[] larger = (a.length > b.length ? a : b);
		int[] lower = (a.length > b.length ? b : a);
		int[] tmp = new int[larger.length];
		for (int i = 0; i < tmp.length; i++) {
			if (i < lower.length) {
				if (a[i] + b[i] + t > 1000000000 -1 ) {
					tmp[i] = a[i] + b[i] + t - 1000000000;
					t = 1;

				} else {
					tmp[i] = a[i] + b[i] + t;
					t = 0;
				}
			}else if(i > lower.length){
				tmp[i] = larger[i] + t;
			}
		}
		StringBuffer buf = new StringBuffer();
		for (int i = tmp.length - 1; i >= 0; i--) {
			StringBuffer str = new StringBuffer(Integer.toString(tmp[i]));
			int strlen = str.length();
			if(strlen != 9 && i!=tmp.length-1){
				for(int x=0; x<9-strlen; x++){
					str.insert(0, "0");
				}
			}
			buf.append(str.toString());
		}
		return buf.toString();
	}
	public static String strAdd(String a, String b){
		int[] a1 = str2int(a);
		int[] b1 = str2int(b);
		return add(a1,b1);
	}
	
	private static String multiplyNumber(String bigNumber, int number){
		if(number == 0){
			return "0";
		}
		String tmp = bigNumber;
		
		while(number-- > 1){
			tmp = strAdd(tmp, bigNumber);
		}
		return tmp;
	}

	public static String multiply(String a1, String a2){
		ArrayList<String> list = new ArrayList<String>();
		StringBuffer buf = new StringBuffer(a1).reverse();
		for(int i=0; i<buf.length(); i++){
			Character c = buf.charAt(i);
			int number = Integer.parseInt(c.toString());
			StringBuffer tmp = new StringBuffer(multiplyNumber(a2, number));
			for(int t=0; t<i; t++){
				tmp.append("0");
			}
			list.add(tmp.toString());
		}
		String tmpStr = list.get(0);
		for(int i=1; i<list.size(); i++){
			tmpStr = strAdd(list.get(i), tmpStr);
		}
		
		return tmpStr;
	}
	public static void main(String[] args) throws Exception{
		Long startTime = System.currentTimeMillis();
		String s1 = "1111111111111111111111111111111111111111111111111111111111111111111111111111";
		String s2 = "1111111111111111111111111111111111111111111111111111111111111111111111111111";
		System.out.println(multiply(s1, s2));
		Long endtime = System.currentTimeMillis();
		System.out.println("Cost Time:" + (endtime-startTime) + "ms.");
		
		startTime = System.currentTimeMillis();
		BigInteger b1 = new BigInteger("1111111111111111111111111111111111111111111111111111111111111111111111111111");
		BigInteger b2 = new BigInteger("1111111111111111111111111111111111111111111111111111111111111111111111111111");
		System.out.println(b1.multiply(b2));
		
		endtime = System.currentTimeMillis();
		System.out.println("Cost Time:" + (endtime-startTime) + "ms.");
	}
}

6 楼 donnki 2008-12-31

刚翻出很多以前写的一段代码。

之所以import java.math.BigInteger是为了验证程序正确性，实际算法里不包含BigInteger类


import java.math.BigInteger;
import java.util.*;
public class MyBigIntegerAdd {
/**
 * 实现超大整数相加、相乘。
 */
	private static int[] str2int(String bigNumber) {
		//System.out.println(bigNumber.length());
		int[] array;
		if (bigNumber.length() < 10) {
			array = new int[1];
			array[0] = Integer.parseInt(bigNumber);
		} else {
			array = new int[bigNumber.length() % 9 == 0 ? bigNumber.length() / 9 : (bigNumber.length() / 9 + 1)];
			StringBuffer buf = new StringBuffer(bigNumber);
			buf.reverse();

			for (int i = 0; i < array.length; i++) {
				array[i] = Integer
						.parseInt((new StringBuffer(buf.substring(i * 9,
								(i + 1) * 9 > bigNumber.length() ? bigNumber
										.length() : (i + 1) * 9)).reverse())
								.toString());
				// System.out.println(array[i]);
			}
		}
		return array;
	}

	
	private static String add(int[] a, int[] b) {
		int t = 0;
		int[] larger = (a.length > b.length ? a : b);
		int[] lower = (a.length > b.length ? b : a);
		int[] tmp = new int[larger.length];
		for (int i = 0; i < tmp.length; i++) {
			if (i < lower.length) {
				if (a[i] + b[i] + t > 1000000000 -1 ) {
					tmp[i] = a[i] + b[i] + t - 1000000000;
					t = 1;

				} else {
					tmp[i] = a[i] + b[i] + t;
					t = 0;
				}
			}else if(i > lower.length){
				tmp[i] = larger[i] + t;
			}
		}
		StringBuffer buf = new StringBuffer();
		for (int i = tmp.length - 1; i >= 0; i--) {
			StringBuffer str = new StringBuffer(Integer.toString(tmp[i]));
			int strlen = str.length();
			if(strlen != 9 && i!=tmp.length-1){
				for(int x=0; x<9-strlen; x++){
					str.insert(0, "0");
				}
			}
			buf.append(str.toString());
		}
		return buf.toString();
	}
	public static String strAdd(String a, String b){
		int[] a1 = str2int(a);
		int[] b1 = str2int(b);
		return add(a1,b1);
	}
	
	private static String multiplyNumber(String bigNumber, int number){
		if(number == 0){
			return "0";
		}
		String tmp = bigNumber;
		
		while(number-- > 1){
			tmp = strAdd(tmp, bigNumber);
		}
		return tmp;
	}

	public static String multiply(String a1, String a2){
		ArrayList<String> list = new ArrayList<String>();
		StringBuffer buf = new StringBuffer(a1).reverse();
		for(int i=0; i<buf.length(); i++){
			Character c = buf.charAt(i);
			int number = Integer.parseInt(c.toString());
			StringBuffer tmp = new StringBuffer(multiplyNumber(a2, number));
			for(int t=0; t<i; t++){
				tmp.append("0");
			}
			list.add(tmp.toString());
		}
		String tmpStr = list.get(0);
		for(int i=1; i<list.size(); i++){
			tmpStr = strAdd(list.get(i), tmpStr);
		}
		
		return tmpStr;
	}
	public static void main(String[] args) throws Exception{
		Long startTime = System.currentTimeMillis();
		String s1 = "1111111111111111111111111111111111111111111111111111111111111111111111111111";
		String s2 = "1111111111111111111111111111111111111111111111111111111111111111111111111111";
		System.out.println(multiply(s1, s2));
		Long endtime = System.currentTimeMillis();
		System.out.println("Cost Time:" + (endtime-startTime) + "ms.");
		
		startTime = System.currentTimeMillis();
		BigInteger b1 = new BigInteger("1111111111111111111111111111111111111111111111111111111111111111111111111111");
		BigInteger b2 = new BigInteger("1111111111111111111111111111111111111111111111111111111111111111111111111111");
		System.out.println(b1.multiply(b2));
		
		endtime = System.currentTimeMillis();
		System.out.println("Cost Time:" + (endtime-startTime) + "ms.");
	}
}

5 楼 Programmer2.x 2008-12-31

感谢朋友们的回复。。

4 楼 Programmer2.x 2008-12-31

gembler 写道

你想表达什么呢？

btw:

Programmer2.x 写道

if (i > 0) {
    System.out.println();
}

这里好恶心

题目里有这么一行：Output a blank line between two test cases.

我暂时是这么处理的，请问您有何高见？

3 楼 xuyao 2008-12-31

看意思，楼主好像要表达，两个int相加超过范围的问题，是啊，java很简单，biginteger。可以先向左移位，高4位和低四位。

2 楼 superdandy 2008-12-31

没看懂。这里有什么很复杂的地方么？用java的话，BigInteger， BigDecimal都为你解决了。

用C来实现，方是你的本事

1 楼 gembler 2008-12-30

你想表达什么呢？

btw:

Programmer2.x 写道

if (i > 0) {
    System.out.println();
}

这里好恶心

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

。。。。。

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

。。。。。

评论

发表评论

相关推荐

最近访客更多访客>>