算法————大数减法，大数除法

灰太狼 2022-04-08 14:21 269阅读 0赞

# 算法————大数减法，大数除法 #

### 文章目录 ###

*  算法————大数减法，大数除法
 *   *   *  一.前言
         *  二.前置函数
         *   *  1.置后函数
             *  2.输出函数
             *  3.比较函数
         *  三.大数减法
         *   *  1.思想
             *  2.代码实现
             *  3.包装
         *  四.大数除法
         *   *  1.思想
             *  2.代码实现
             *  3.减法的改动

### 一.前言 ###

在之间的时候，写了另一篇大数相关的算法：，后来一直忙于其他事，没有继续写大数其他的算法，现在就来看看大数其他算法的实现。

在之前的数据结构相关的博客里，一直都是用c语言实现的，现在处于面试已经方面的考虑，之后算法的实现都改为java。

### 二.前置函数 ###

#### 1.置后函数 ####

作用：将数字字符串改为数组，并将字符串放在数组尾部。这样做是方便减法和除法的处理。  
例:将"123456",8–>00’1’‘2’‘3’‘4’‘5’‘6’.

/**
         * 置后函数
         * @param str 需要置后的字符串
         * @param n 申请单数组空间大小
         * @return 置后的数组
         */
        public static char[] postpone(String str,int n) {
         
            char[] a = new char[n];
            int al = str.length();
    
            for (int i = 0; i < al; i++) {
        
                a[n - al + i] = str.charAt(i);
            }
    
            return a;
        }

#### 2.输出函数 ####

作用：将存放结果的数组，去掉前面多余的’0’和0,并将结果转换成字符串。  
例：00’1’‘2’‘3’‘4’‘5’‘6’–>“123456”.

/**
         *  转换函数
         * @param a 需要输出的数组
         * @return
         */
        public static String eliminate(char a[]) {
          
    
            int n = a.length;
            StringBuilder sb = new StringBuilder();
            int i;
            for (i = 0; (a[i] == 0 || a[i] == '0') && i < n; i++) {
        
    
            }
    
            for (; i < n; i++) {
        
                sb.append(a[i]);
            }
            return sb.toString();
        }

#### 3.比较函数 ####

作用：比较数字字符串a，b的大小  
返回：a>b–>1 ,a==b–>0,a< b–>-1

/**
         * 比较函数
         * @param a
         * @param b
         * @return
         */
        public static int compare(String a, String b) {
          //比较两个数的大小
            if (a.length() > b.length()) {
        
                return 1;
            } else if (a.length() < b.length()) {
        
                return -1;
            } else {
        
                for (int i = 0; i < a.length(); i++) {
        
                    if (a.charAt(i) > b.charAt(i)) {
        
                        return 1;
                    } else if (a.charAt(i) < b.charAt(i)) {
        
                        return -1;
                    }
                }
    
            }
    
            return 0;
        }

### 三.大数减法 ###

#### 1.思想 ####

大数减法的思想和加法类似。只不过在计算前，先比较两个数的大小，保证是大数减小数。

在具体减的过程中，要考虑借位的情况，就是模拟具体的手工减法的过程。

例 193 - 79 （c存储结果，f表示借位）  
1.0 f = 0  
1.1 num = 3 - 9 + 0 = -6  
1.2 c\[3\] =-6+10 = 4,f = -1

2.0 f = -1  
2.1 num = 9 - 7 + -1=1  
2.2 c\[2\] = 1,f=0

3.0 f = 0  
3.1 num = 1-0+0 =1  
3.2 c\[1\] = 1,f=0

结果：114

#### 2.代码实现 ####

/**
         * 大数 - 小数 （a - b = c）
         * @param a 被减数和减数中大者
         * @param b 被减数和减数中小者
         * @param n 申请单数字长度
         * @param c 存放结果的数组
         */
        private static void subtraction(char a[], char b[],int n, char c[]) {
        
    
            int num, fi = 0;
    
            for (int i = n - 1; a[i] != 0 || b[i] != 0 || fi != 0; i--) {
        
                a[i] = a[i] == 0 ? '0' : a[i];
                b[i] = b[i] == 0 ? '0' : b[i];
    
                num = (a[i] - '0') - (b[i] - '0') + fi;
                //System.out.println("i=" + i + " a[i]=" + a[i] + " b[i]=" + b[i] + " fi =" + fi + " num=" + num);
                if (num >= 0) {
        
                    c[i] = (char) (num + '0');
                    fi = 0;
                } else {
        
                    c[i] = (char) (num + 10 + '0');
                    fi = -1;
                }
            }
    
        }

#### 3.包装 ####

处理小数 - 大数，以及字符串和数组之间的转换

/**
         * 减法
         * @param a 减数
         * @param b 被减数
         * @return 商
         */
    public static String subtraction(String a, String b) {
        
            int alen = a.length();
            int blen = b.length();
            int n = alen > blen ? alen + 2 : blen + 2;
    
            int result = compare(a, b);
    
            if (result == 0) {
        
                return "0";
            } else if (result == 1) {
        
                char[] c = new char[n];
                subtraction(Util.postpone(a,n), Util.postpone(b,n),n,c); //转换并调用上面的函数
                return Util.eliminate(c); //转换结果
            }else {
        
                char[] c = new char[n];
                subtraction(Util.postpone(b,n), Util.postpone(a,n),n,c); //转换并调用上面的函数
                return "-"+Util.eliminate(c);//转换结果
            }
        }

### 四.大数除法 ###

#### 1.思想 ####

大数减法的思想也很简单，就是不停的调用减法，每成功减一次，就对商+1.

但时间成本有些太高，比如9999/1,就要进行9999次除法。所以进行改进。

9999 先减1000，减9次，结果为999，再减100，减9次，直到最后减9次1.计算出结果。

例：  
9876/ 1000 = 9  
876 /100 = 8  
76 /10 = 7  
6 /1 = 6  
最终的结果：9876

#### 2.代码实现 ####

这个在调用减法是对上面减法的改进，当被减数 < 减数时返回0

public static String division(String a, String b) {
        
            int alen = a.length();
            int blen = b.length();
            int n = alen > blen ? alen + 2 : blen + 2;
    
            if(b.equals("0")){
        
                return "除0错误";
            }
            char[] result = new char[alen - blen+1];
            for (int i= 0 ;i<alen-blen+1;i++){
        
    
                StringBuilder c = new StringBuilder(b);
                for (int j = i; j < alen-blen; j++) {
        
                    c.append('0');
                }
    
                int num = 0;
                while (Util.compare(a,c.toString())>=0){
        
                    a = subtraction(a,c.toString()); //调用减法
                    num++;
                }
                result[i]= (char) (num+'0');
                //System.out.println("a = "+a+" b="+b+" c="+c +" num="+num +" result="+ new String(result));
    
            }
    
            return Util.eliminate(result);
        }

#### 3.减法的改动 ####

public static String subtraction(String a, String b) {
        
            int alen = a.length();
            int blen = b.length();
            int n = alen > blen ? alen + 2 : blen + 2;
    
            int result = Util.compare(a, b);
    
            if (result == 0) {
        
                return "0";
            } else if (result == 1) {
        
                char[] c = new char[n];
                subtraction(Util.postpone(a,n), Util.postpone(b,n),n, c);
                return Util.eliminate(c);
            } else {
        
                return "0"; // 被减数 小于减数时 返回0
            }
        }