您现在的位置：程式碼之家 >> 編程語言 > >> .NET 網頁程式設計 >> C# >> 關於C#

C# 經典演算法：計算 1¹ + 2² + 3³ + ... + nⁿ

編輯：關於C#

題目

輸入正整數 n，計算 S = Σ(i=1 to n) iⁱ。

直接迴圈實作


public long CalculateSum(int n)
{
    long sum = 0;
    for (int i = 1; i <= n; i++)
    {
        long term = 1;
        for (int j = 1; j <= i; j++) // 計算 i^i
        {
            term *= i;
            // 溢位檢查 (可選)
            if (term < 0) throw new OverflowException($"i={i} 時超出 long 範圍");
        }
        sum += term;
        if (sum < 0) throw new OverflowException($"累加超出 long 範圍");
    }
    return sum;
}

優化：快速冪 (Exponentiation by Squaring)

計算 i^i 從 O(i) 降為 O(log i)。


private long Pow(long baseVal, int exp)
{
    long result = 1;
    while (exp > 0)
    {
        if ((exp & 1) == 1) result *= baseVal;
        baseVal *= baseVal;
        exp >>= 1;
    }
    return result;
}

public long CalculateSumFast(int n)
{
    long sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += Pow(i, i);
    }
    return sum;
}

BigInteger 支援任意大整數 (C# 4.0+)


using System.Numerics;

public BigInteger CalculateSumBig(int n)
{
    BigInteger sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += BigInteger.Pow(i, i);
    }
    return sum;
}
// 範例：n=20 即超出 long，BigInteger 可正確計算

效能比較 (n=10000)

方法	時間複雜度	備註
雙重迴圈	O(n²)	n=10000 明顯緩慢
快速冪	O(n log n)	顯著加速
BigInteger	O(n log n) × 大整數乘法	正確性最高，效能可接受

數學性質補充

此數列 OEIS A001923：1, 5, 32, 288, 3413, 50069, 873612, 17650828...
無簡化閉合公式，需迴圈累加。
模運算應用：sum % m 可在累加過程中每步取模，避免大數運算。

完整主程式


static void Main()
{
    Console.Write("請輸入正整數 n: ");
    if (int.TryParse(Console.ReadLine(), out int n) && n > 0)
    {
        var sw = Stopwatch.StartNew();
        BigInteger result = CalculateSumBig(n);
        sw.Stop();
        Console.WriteLine($"1^1 + 2^2 + ... + {n}^{n} = {result}");
        Console.WriteLine($"耗時: {sw.ElapsedMilliseconds} ms");
    }
    else
    {
        Console.WriteLine("輸入無效");
    }
}

掌握快速冪與 BigInteger，即能高效、正確解決冪次累加問題。