算法题:编程实现大数的乘法

深藏阁楼爱情的钟 2023-07-23 03:32 23阅读 0赞

两个数相乘，结果的最大位数为两个数的位数之和  
比如有两个相乘97*99，  
先把它们的每一位依次相乘  
个位结果=7*9=63  
十位结果为=(9*9+7*9)=144  
百位结果=81  
结果为81 144 63  
然后依次进位  
个位=63%10=3  
十位=(144+63/10) %10=0  
百位=(81+150/10)%10=6  
千位=96/10=9  
然后根据该思想编写算法

package algorithm;
    
    public class Test2 { 
    	public static void main(String[]args) { 
    		String a="689";
    		String b="3";
    		char[]large=null;
    		char[]small=null;
    		if (a.length()>b.length()) { 
    			large=a.toCharArray();
    			small=b.toCharArray();
    		}else { 
    			large=b.toCharArray();
    			small=a.toCharArray();
    		}
    		System.out.println(a.length()+" "+b.length());
    		int[]multi=new int[a.length()+b.length()];
    		for(int i=0;i<small.length;i++) { 
    			for (int j = 0; j<large.length; j++) { 
    				
    				int num1=small[small.length-1-i]-'0';//个位对齐
    				int num2=large[large.length-1-j]-'0';
    				multi[i+j]+=num1*num2;
    				System.out.println(multi[i+j]);
    				
    			}
    		}
    		for (int i = 0; i < multi.length; i++) { 
    			System.out.print(multi[i]+" ");
    		}
    		for (int i = 0; i < multi.length-1; i++) { 
    			if (multi[i]>9) { 
    				multi[i+1]+=multi[i]/10;
    				multi[i]%=10;
    			}
    		}
    		System.out.println();
    		for (int i = 0; i < multi.length; i++) { 
    			System.out.print(multi[i]+" ");
    		}
    		StringBuilder stringBuilder=new StringBuilder();
    		for (int i = 0; i < multi.length; i++) { 
    			stringBuilder.append(multi[multi.length-1-i]);
    		}
    		System.out.println();
    		String result=stringBuilder.toString();
    		if (result.startsWith("0")) { 
    			result=result.substring(1);
    		}
    		System.out.println(result);
    	}
    }