問題描述

求兩個大的正整數(shù)相除的商。

輸入

第 1 行是測試數(shù)據(jù)的組數(shù)n，每組測試數(shù)據(jù)占 2 行，第 1 行是被除數(shù)，第 2 行是除數(shù)，每行數(shù)據(jù)不超過 100 個字符。

輸出

n 行，每組測試數(shù)據(jù)有一行輸出是相應(yīng)的整數(shù)商。

輸入樣列

3
2405337312963373359009260457742057439230496493930355595797660791082739646
2987192585318701752584429931160870372907079248971095012509790550883793197894
10000000000000000000000000000000000000000
10000000000
5409656775097850895687056798068970934546546575676768678435435345
1

輸出樣例

0
1000000000000000000000000000000
5409656775097850895687056798068970934546546575676768678435435345

解題思路

基本的思想是反復(fù)做減法，看看從被除數(shù)里最多能減去多少個除數(shù)，商就是多少。一個一個減顯然太慢，如何減得更快一些呢？以7546除以23為例來看一下：開始商為0。先減去23的100倍，就是2300，發(fā)現(xiàn)夠減3次，余下646。于是商的值就增加300。然后用646減去230，發(fā)現(xiàn)夠減2次，余下186，于是商的值增加20。最后用186減去23，夠減8次，因此最終商就是328。所以本題的核心是要寫一個大整數(shù)的減法函數(shù)，然后反復(fù)調(diào)用該函數(shù)進(jìn)行減法操作。

算法實現(xiàn)

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];
                //除數(shù)n大于被除數(shù)m輸出0
                if (m.Length < n.Length)
                {
                    Console.WriteLine("0");
                    continue;
                }
                //除數(shù)n小于被除數(shù)m

                //將字符串轉(zhuǎn)為整數(shù)數(shù)組
                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';
                //作除法：實際上就是大整數(shù)的減法函數(shù)
                for (int i = n.Length-1; i < m.Length; i++)
                {
                    int count = 0;//商的值，即所做減法次數(shù)
                    while (true)
                    {
                        bool isEnd = true;//標(biāo)志位，除數(shù)大于被除數(shù)時isEnd為false
                        int j = 0;
                        //大整數(shù)的減法
                        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();
        }
    }
}