TopCoder Inv 2001 R1 - SquareDigits | 小殘的程式光廊

資訊

路徑：Tournament \ 1-16 \ 1 - Inv 2001 R1 \ SquareDigits
分數：500

題目

程式介面

Class Name: SquareDigits
Method Name: smallestResult
Parameters: int
Returns: int

說明

輸入一數字 n，找到 T(x) 包含 n 的最小 x。

定義

S(x)：表示 x 的數字逐字幕次和，例如 S(3) = 3 * 3 = 9 和 S(230) = 2 * 2 + 3 * 3 + 0 * 0 = 13。
T(x)：表示重複執行 S(x) 直到出現重複結果，例如 T(37)，
S(37) = 58
S(58) = 89
S(89) = 145
S(145) = 42
S(42) = 20
S(20) = 4
S(4) = 16
S(16) = 37
S(37) <- 重複
T(37) = { 58, 89, 145, 42, 20, 4, 16, 37 }

系統保證輸入

0 - 199

範例

輸入：0
輸出：0
註：n = 0, T(0) 包含 0。

輸入：2
輸出：11
註：n = 2, T(11) 包含 2。

輸入：10
輸出：500
註：n = 10, T(7) 包含 10。

輸入：1
輸出：1

輸入：19
輸出：133

輸入：85
輸出：5

輸入：112
輸出：2666

解法

此題目明確的說明了 S(x) 和 T(x) 的演算法，所以很容易就能寫出對應的函式，此題目沒有特別需要注意的地方。

語法

採用較易理解的寫法，效能並非最好

using System;
using System;
using System.Collections.Generic;
using System.Text;

namespace SquareDigits
{
    class SquareDigits
    {
        public int smallestResult(int n)
        {
            int x = 0;
            while (true)
            {
                List<int> t = T(x);
                if (t.Contains(n))
                    return x;
                ++x;
            }
        }

        private int S(int x)
        {
            int sum = 0;
            while (x > 0)
            {
                sum += (int)Math.Pow((double)(x % 10), (double)2);
                x /= 10;
            }
            return sum;
        }

        public List<int> T(int x)
        {
            List<int> result = new List<int>();
            int s = S(x);
            while (!result.Contains(s))
            {
                result.Add(s);
                s = S(s);
            }
            return result;
        }
    }
}