算法基础: 大数除法-二分法

涉及到加减除乘法。
主要思想是二分，具体看代码吧。

package com.younfor.oj;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.atomic.AtomicLong;

public class ThreadPool {
    public static int comp(int[] a,int []b)
    {
        //颠倒后
        if(a.length>b.length)
            return 1;
        if(a.length<b.length)
            return -1;
        for(int i=a.length-1;i>=0;i--)
        {
            if(a[i]>b[i])
                return 1;
            if(a[i]<b[i])
                return -1;
        }
        return 0;
    }
    public static int[] add(int []to,int []from)
    {
        //颠倒后
        int len1=to.length,len2=from.length;
        int d[]=new int[Math.max(len1,len2)];
        //进位
        int c=0,i=0;
        while(i<len1&&i<len2)
        {
            int r=to[i]+from[i]+c;
            d[i]=r%10;
            c=r/10;
            i++;
        }
        while(i<len1)
        {
            int r=to[i]+c;
            d[i]=r%10;
            c=r/10;
            i++;
        }
        while(i<len2)
        {
            int r=from[i]+c;
            d[i]=r%10;
            c=r/10;
            i++;
        }
        if(c>0)
        {
            int m[]=new int[d.length+1];
            System.arraycopy(d,0,m,d.length);
            m[m.length-1]=1;
            return m;
        }
        return d;

    }
    public static int[] del(int []a,int []b)
    {
        //颠倒后
        int len1=a.length,len2=b.length;
        //进位
        int c=0,i=0;
        while(i<len1&&i<len2)
        {
            int r=a[i]-b[i]+c;
            if(r<0)
            {
                c=-1;
                r+=10;
            }else
                c=0;
            a[i]=r;
            i++;
        }
        while(i<len1)
        {
            int r=a[i]+c;
            if(r<0)
            {
                c=-1;
                r+=10;
            }else
                c=0;
            a[i]=r;
            i++;
        }
        //去掉多余的0
        while(a[len1-1]==0&&len1>1) len1--;
        int n[]=new int[len1];
        System.arraycopy(a,n,len1);
        return n;
    }
    public static int [] reverse(int []s)
    {
        int len=s.length;
        for(int i=0;i<len/2;i++)
        {
            int t=s[i];
            s[i]=s[len-i-1];
            s[len-i-1]=t;
        }
        return s;
    }
    public static int [] mutiple(int a[],int b[])
    {
        //土方法
        /** * 1 2 3 * 4 5 */
        int len1=a.length,len2=b.length;
        a=reverse(a);
        b=reverse(b);
        int []result=new int[len1+len2];
        int c=0;
        for(int i=0;i<len1;i++)
        {
            int j;
            for(j=0;j<len2;j++)
            {
                c+=result[i+j]+a[i]*b[j];
                result[i+j]=c%10;
                c/=10;
            }
            while(c>0)
            {
                result[i+j++]+=c%10;
                c/=10;
            }
        }
        //去除首位的0
        int rlen=result.length;
        while(result[rlen-1]==0&&rlen>1) rlen--;
        int n[]=new int[rlen];
        System.arraycopy(result,rlen);
        return n;
    }
    public static int[] div(int []a,int b[])
    {
        //颠倒
        int big[]=reverse(a);
        int small[]=reverse(b);
        int []base=small.clone();
        int ans[]=new int[]{0};
        while(comp(big,base)>=0)
        {
            int count[]=new int[]{1};
            small=base.clone();
            //
            int twosmall[]=add(small,small);
            while(comp(big,twosmall)>=0)
            {
                small=twosmall;
                twosmall=add(small,small);
                count=add(count,count);
            }
            big=del(big,small);
            ans=add(ans,count);
        }
        System.out.print(" =余数:");
        for(int i:reverse(big))
            System.out.print(i);
        System.out.print(" 商: ");
        return ans;
    }
    public static void main(String args[])
    {
        //乘法
        int c[]={1,2};
        int d[]={1,1};
        for(int i:c)
            System.out.print(i);
        System.out.print(" 乘以 ");
        for(int i:d)
            System.out.print(i);
        System.out.print(" =");
        for(int i:reverse(mutiple(c,d)))
            System.out.print(i);
        System.out.println("");
        //除法
        int a[]={1,2,3,4,5,6,7,8,9,1,0};
        int b[]={3,5};
        for(int i:(a))
            System.out.print(i);
        System.out.print(" 除以 ");
        for(int i:(b))
            System.out.print(i);
        for(int i:reverse(div(a,b)))
            System.out.print(i);

    }
}

12 乘以 11 =132 123456789012345678901234567890 除以 345 =余数:15 商: 357845765253175880873143675