0025-大整数除法

问题描述

求两个大的正整数相除的商。

输入

第 1 行是测试数据的组数n，每组测试数据占 2 行，第 1 行是被除数，第 2 行是除数，每行数据不超过 100 个字符。

输出

n 行，每组测试数据有一行输出是相应的整数商。

输入样列

3
2405337312963373359009260457742057439230496493930355595797660791082739646
2987192585318701752584429931160870372907079248971095012509790550883793197894
10000000000000000000000000000000000000000
10000000000
5409656775097850895687056798068970934546546575676768678435435345
1

输出样例

0
1000000000000000000000000000000
5409656775097850895687056798068970934546546575676768678435435345

解题思路

基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。

算法实现

using System;

namespace Questions{
    class Program{
        public static void Main(string[] args){
            int N = int.Parse(Console.ReadLine());
            while(N!=0){
                N--;
                string m = Console.ReadLine();
                string n = Console.ReadLine();
                int[] result = new int[100];
                //除数n大于被除数m输出0
                if (m.Length < n.Length)
                {
                    Console.WriteLine("0");
                    continue;
                }
                //除数n小于被除数m

                //将字符串转为整数数组
                int[] divisor = new int[n.Length];
                int[] dividend = new int[m.Length];
                for (int i = 0; i < m.Length; i++) 
                    dividend[i] = m[i] - '0';
                for (int i = 0; i < n.Length; i++)
                    divisor[i] = n[i] - '0';
                //作除法：实际上就是大整数的减法函数
                for (int i = n.Length-1; i < m.Length; i++)
                {
                    int count = 0;//商的值，即所做减法次数
                    while (true)
                    {
                        bool isEnd = true;//标志位，除数大于被除数时isEnd为false
                        int j = 0;
                        //大整数的减法
                        for (j = 0; j < n.Length; j++)
                        {
                            int temp = dividend[i - j] - divisor[n.Length - 1 - j];
                            if (temp < 0)
                            {
                                bool flag = true;
                                int k = 0;
                                for ( k = j + 1; k < n.Length; k++)
                                {
                                    int tempk = dividend[i - k] - 1;
                                    if (tempk >= 0)
                                    {
                                        flag = false;
                                        break;
                                    }
                                }
                                if ((k== n.Length) || flag)
                                {
                                    isEnd = false;
                                    break;
                                }
                                dividend[i - j - 1] -= 1;
                                dividend[i - j] = temp + 10;
                            }
                            else
                                dividend[i - j] = temp;
                        }
                        if (isEnd)
                            count++;
                        else
                            break;
                    }

                    result[m.Length - 1 - i] = count;
                }
                //输出
                int l = 100;
                while (result[l - 1] == 0)
                    l--;
                for (int i = l - 1; i >= 0; i--)
                    Console.Write(result[i]);
                Console.WriteLine();
            }
            Console.ReadKey();
        }
    }
}