日期:2014-05-20  浏览次数:20785 次

今天去华为赛门铁克面试被提到的一个问题(JAVA)
String str = "5673454322...............323223";
str是一个无穷大的数字,一个long都无法放入,假设一个n值是7。
面试官提问:如何使得这个数字可以被n整除???

------解决方案--------------------
Java code

    public static void main(String[] args) {
        BigInteger big = new BigInteger("54354358093245892583457839730957349857394857367935384895");
        System.out.println("余数是"+big.divideAndRemainder(BigInteger.valueOf(7))[1].toString());
    }

------解决方案--------------------
Java code

public static void main(String[] args) {
        String str = "54354358093245892583457839730957349857394857367935384895";
        int n= 7;
        String yushu = "";
        if(str.length()<5){
            yushu=String.valueOf(Integer.parseInt(str)%n);
        }else{
        for (int i = 0; i < str.length()/5; i=i+5) {
            
            String temp = yushu+str.substring(i, i+5);
            int cloum = Integer.parseInt(temp);
            int yu = cloum%n;
            
            if(yu!=0){
                yushu=String.valueOf(yu);
            }else{
                yushu="";
            }
        }
        }
        if(yushu.length()<=0||"0".equals(yushu)){
            System.out.println("可以被整除");
        }else{
            System.out.println("不可以被整除");
        }
        
    }

------解决方案--------------------
题目翻译一下:有不定大小的数字x,求与x之间差值最小的7的公约数,给出差值大小
例:
x = 15
设y,且y%7=0
答案就是 x+(y-x)
小于long长度的数字直接用long计算
大于long长度的算法没想好,哈哈

------解决方案--------------------
探讨

题目翻译一下:有不定大小的数字x,求与x之间差值最小的7的公约数,给出差值大小
例:
x = 15
设y,且y%7=0
答案就是 x+(y-x)
小于long长度的数字直接用long计算
大于long长度的算法没想好,哈哈

------解决方案--------------------
Java code
    public static void main(String[] args) {
        final int leg=18;
        StringBuilder str=new StringBuilder("49793821479387619794872314840");
        int n=7;
        long count=0;
        
        while(true){
            long num;
            if(str.length()<=leg){
                num=Long.parseLong(str.substring(0, str.length()));
                count+=num%n;
                break;
            }else{
                num=Long.parseLong(str.substring(0, leg));
                count+=num%n;
                str.delete(0, leg);
            }
        }
        System.out.println(count%n==0?"可以":"不可以");
    }

------解决方案--------------------
探讨

BigInteger会有多大,String可以直接转成他么,我觉得面试人的问题是说似乎任何类型都不能放下这个数?

------解决方案--------------------
就我的观点来看,这应该是一道大数乘法的变形题,基本思路如下:
将大数从最高位开始截取k位(将这k位转化为数字后应该在long范围之内),然后进行除法运算,再截取k-1位,将其与所得余数连接。依次进行,如果最后一次运算余数为零说明能被n整除。
上面的思路假设了除数在long范围内
------解决方案--------------------


这个是有规律的,之后根据同余定理计算



其中:
i — 从右边数起的第几位数字
xi — 从右边数起第 i 位上的数字值
p — 总共的数字位数
n — 模几
k — 计算结果
 
------解决方案--------------------
楼上的兄弟们都小学没有毕业啊。。。题目也没看懂。。
判断str 是否被n整除,没让判断mod后的值,明显用小学的割尾法去做。。。。
------解决方案--------------------
从高位开始逐个读入字符串,然后mod 7,记录余数,读到下一位时将余数*10+当前的值,继续mod 7,记录余数......

String str = "5673454322...............323223";