判断很长的字符串能否被一个整数整除

    以前的一个面试题，一直没有解决，今天突然想起来解决的办法了，用java 实现，简单介绍一下。
   比如2335 除以 2  ，可以用第一个 2 % 2 = 0 ; 3 % 2 = 1 ; 余数1 加 3 ,13%2 = 1 ; 15 % 2 = 1 ,  结果余数为1，不能整除。


简单的实现 ，不要见笑
代码如下：

package entity;

import java.util.Scanner;
import java.util.Stack;

public class LongString {
	private String dividend ;
	
	private int divisor ;
	
	private Scanner scanner ;
	
	//余数
	private int remainder ;
	
	//最好使用Deque
	private Stack<Character> stack ;
	
	public LongString(){
		init() ;
	}
	
	public void init(){
		remainder = 0 ;
		stack = new Stack<Character>() ;
		scanner = new Scanner(System.in) ;
		
		System.out.println("                            判断一个无限长的字符串能不能被一个数整除 ：")  ;
		
		//接收参数
		
		System.out.println("请输入被除数 ：")  ;
		
		dividend = scanner.next() ;
		
		System.out.println("请输入除数 ：")  ;
		try{
			divisor  = Integer.parseInt( scanner.next() );
		} catch(Exception e){
			System.out.println("请输入除数 ：")  ;
			divisor  = Integer.parseInt( scanner.next() );
		}
		
		System.out.println("被除数 ："+ dividend + "\n除数      ：" + divisor + "\n") ;

		compute(dividend,divisor) ;
	}
	
	
	//运算
	public void compute(String dividend, int divisor){
		int length = dividend.length() ;
		
		int divisorLength = Integer.toString(divisor).length() ;
		
		//将字符串压入栈,方便进行运算时一个一个的取出来进行运行
		for(int i = dividend.length() - 1 ; i >= 0 ; i --){
			stack.push(dividend.charAt(i) ) ;
		}
		
		//如果被除数的长度小于或等于除数的，直接转换进行运算
		if(length <= divisorLength ){
			 remainder = Integer.parseInt( dividend ) % divisor ;
			 
		} else { //如果被除数长度大于除数的，从高位开始依次进行运算，直到最后
			
			//构建一个临时的被除数
			StringBuilder sbDividendTemp = new StringBuilder() ;
			
			for(int i = 0 ; i < length ; i++){
				sbDividendTemp.append(stack.pop()) ;
				
				//如果临时被除数取出的被除数小于除数，继续从被除数中取
				if( Integer.parseInt( sbDividendTemp.toString() ) < divisor ){
					continue ;
				} 
				//把余数写入被除数，继续判断
				else {
					remainder = Integer.parseInt( sbDividendTemp.toString()) % divisor ;
					
					sbDividendTemp.delete(0, sbDividendTemp.length()) ;
					
					if (remainder != 0 ) {
						sbDividendTemp.append(Integer.toString(remainder));
					}
				}
			}
		}
		
		//对结果进行判断
		if(remainder == 0 ){
			System.out.println(" 可以整除" ) ; 
		} else{
			System.out.println(" 不能整除  ，余数是 ："  + remainder ) ;
		}
	}
	
	public static void main(String[] args){
		new LongString() ;
	}
}

评论

2 楼 chengpan 2012-07-09  

261667318 写道

哥们你这有个bug。  比如被除数  99999995，除数为9。那么最后一个数就被你continue掉了。按照你的算法，是可以被整除的。应该在

if( Integer.parseInt( sbDividendTemp.toString() ) < divisor ){
continue ;
}


加判断，   && i != length -1

罪过罪过 , 我再看看 

1 楼 261667318 2012-07-07  

哥们你这有个bug。  比如被除数  99999995，除数为9。那么最后一个数就被你continue掉了。按照你的算法，是可以被整除的。应该在

if( Integer.parseInt( sbDividendTemp.toString() ) < divisor ){
continue ;
}


加判断，   && i != length -1