4月 23, 2009

【解題】You can say 11

@
ACM Volume CIX 10929 - You can say 11


The Problem

Your job is, given a positive number N, determine if it is a multiple of eleven.


Input

The input is a file such that each line contains a positive number. A line containing the number 0 is the end of the input. The given numbers can contain up to 1000 digits.


Output

The output of the program shall indicate, for each input number, if it is a multiple of eleven or not.


Sample Input

112233
30800
2937
323455693
5038297
112234
0


Sample Output

112233 is a multiple of 11.
30800 is a multiple of 11.
2937 is a multiple of 11.
323455693 is a multiple of 11.
5038297 is a multiple of 11.
112234 is not a multiple of 11.


解題思考

  雖然這一題只需要判斷某數字是否為 11 的餘數,但是由於輸入的數字會高達 1000 位數,所以「直接將輸入值存入整數變數,再求得除以 11 的餘數以判斷是否為 11 的倍數」這個方法是勢必行不通的。

  取而代之的,我們需要用字串的方式來儲存輸入的數字。所以接下來的問題就是:該如何判斷這個數字是否為 11 的倍數?

  在這裡,我們需要用到一個關於 11 倍數的小常識,那就是:11 倍數的「奇數位數字和」與「偶數位數字和」兩者的差必定為 11 的倍數。

  因此,採用迴圈的方式來計算奇數位數與偶數位數的和,再利用這個概念來判斷兩者的差是否為 11 的倍數,就能順利得出答案了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string s;
    while (1)
    {
        cin >> s;
        if (s == "0") { break; }

        // 計算奇數位與偶數位的和
        long sum[2] = {0, 0};
        for (int i = 0; i < s.length(); i++)
        {
            sum[i % 2] += s[i] - '0';
        }

        bool multiple = !((sum[0] - sum[1]) % 11);
        cout << s << " is " << (multiple ? "" : "not ");
        cout << "a multiple of 11." << endl;
    }

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

1 回覆:

莊侑穎 提到...

sum[i % 2] += s[i] - '0';
請問這邊是問甚麼要 -'0' 啊?

張貼留言