7月 16, 2008

【解題】Primary Arithmetic

@
ACM Volume C 10035 - Primary Arithmetic


The Problem

Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the "carry" operation - in which a 1 is carried from one digit position to be added to the next - to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.


The Input

Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0.


The Output

For each line of input except the last you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.


Sample Input

123 456
555 555
123 594
0 0


Sample Output

No carry operation.
3 carry operations.
1 carry operation.


解題思考

  這一題要求我們判斷,兩個數字相加之後,總共進位多少次。

  首先,由於兩個數字的長度不見得相同。因此,在程式執行加法之前,我們必須要使 a 大於等於 b,以確定 a 的數字長度恆大於等於 b。

  接下來,我們不直接將兩數字相加(因為如此便得不到共進位幾次了),而是在迴圈中取出兩數字中的同一位數字作相加。

  若是有進位,除了需要將用以計算「共進位多少次」的變數遞增加一之外,還需要將這個進位的數字存起來,以加在下一位數的相加結果中(就像一般的加法那樣)。

  最後,只需要根據題目要求,輸出結果就可以了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    while (1)
    {
        int a, b;
        cin >> a >> b;

        if (!a && !b) { break; }

        // 使 a >= b
        if (a < b)
        {
            int temp = a;
            a = b;
            b = temp;
        }

        // 判斷 a + b 的第 i 位是否進位
        int carry = 0, time = 0;
        while (b)
        {
            int r = a % 10 + b % 10 + carry;

            a /= 10;
            b /= 10;

            if (carry = r / 10)
            {
                time++;
            }
        }

        // 判別剩餘的進位是否使 a 進位
        while (a)
        {
            if (carry = (a % 10 + carry) / 10)
            {
                time++;
            }
            else { break; }

            a /= 10;
        }

        // 根據進位次數決定輸出文字
        switch (time)
        {
            case 0:
                cout << "No carry operation." << endl;
                break;

            case 1:
                cout << time << " carry operation." << endl;
                break;

            default:
                cout << time << " carry operations." << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

6 回覆:

kgame 智涵 提到...

case 1:
可以省去 << time
直接把1寫在字串裡

kgame 智涵 提到...

可以直接while (a)算到完
只是b到最後會有幾次白除的

小參 提到...

我個人覺得有沒有把 1 寫到字串沒什麼差耶....

不過直接 while (a) 是個好建議

匿名 提到...

if (carry = r / 10)
{
time++;
}

這一段似乎不需要if吧 .. 因為carry是被修改為r / 10
完全沒有需要判斷的部分..應該是吧!?

匿名 提到...

阿..不好意思 看錯了 上面的回覆可以刪掉@@
我想問if(carry=r/10)這句意思是:如果需要讓carry變數的話..
才執行time++這句嗎!?
如果carry原本就等於r/10..下面的time++就直接略過的意思嗎?

小參 提到...

在 C / C++ 中,賦值運算子(=)會先將右方的值賦與左方的變數,再傳回左方變數的值。

因此,這段程式可以看作:
carry = r / 10;
if (carry) { time++; }

由於將 carry 放入 if 判別式中會被視為布林值。
也就是以 0 為 false,其餘非零值為 true。

所以整段程式的意思是:
先讓 carry = r / 10,再判斷 carry 是否不等於零。
假如成立,就執行其中 time++ 的動作。

張貼留言