C 語言數列求和：重複數字疊加序列 a + aa + aaa + aaaa + ... (位運算構造)

編輯：關於C語言

問題描述

給定一位數字 a (1-9) 和項數 n，計算 S = a + aa + aaa + ... + n 位 a 組成的數。如 a=3, n=4：3 + 33 + 333 + 3333 = 3702。核心考點：數字構造遞推、位移累加思想、輸入驗證。

原代碼分析


#include <stdio.h>

int main() {
    int i, num, a, b = 0, k = 10, sum = 0;
    printf("請輸入一位數字 (1-9): ");
    scanf("%d", &a);
    printf("請輸入項數: ");
    scanf("%d", &num);

    if (a <= 0 || a >= 10) { printf("輸入不符合要求!\n"); return 0; }

    for (i = 0; i < num; i++) {
        b = b * k + a;   // 核心：左移一位(×10)加新數字
        sum += b;
    }
    printf("結果: %d\n", sum);
    return 0;
}

核心遞推關係：數字構造器

項 1: b₁ = a
項 2: b₂ = b₁ × 10 + a = aa
項 3: b₃ = b₂ × 10 + a = aaa
...
bₖ = bₖ₋₁ × 10 + a
Sₙ = Σ bₖ

這正是有限狀態機構造數字的標準模式，應用於字符串轉整數、流式數字解析等場景。

數學閉式公式 (O(1) 計算)

觀察規律：

a = a × 1
aa = a × 11
aaa = a × 111
...
n 位 a = a × (10ⁿ - 1) / 9  (等比數列求和)

總和 Sₙ = a × Σₖ₌₁ⁿ (10ᵏ - 1)/9
= a/9 × [ Σ10ᵏ - n ]
= a/9 × [ 10(10ⁿ - 1)/9 - n ]
= a × [ 10(10ⁿ - 1) - 9n ] / 81


long long sum_closed_form(int a, int n) {
    long long pow10 = 1;
    for (int i = 0; i < n; i++) pow10 *= 10;  // 10ⁿ
    // 或用 pow(10, n) 但浮點轉換需謹慎
    return a * (10 * (pow10 - 1) - 9 * n) / 81;
}

溢出邊界與類型選擇

n	最大項值	總和量級	建議類型
9	999,999,999	~4×10⁹	long long
10	9,999,999,999	~4×10¹⁰	long long
18	~10¹⁸	~10¹⁹	unsigned long long
19	溢出 64位	-	大整數/字符串

工程化完整版：輸入驗證 + 大整數支持


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 字符串大整數加法
void str_add(char *a, char *b, char *res) {
    int carry = 0, i = strlen(a)-1, j = strlen(b)-1, k = 0;
    char tmp[100];
    while (i >= 0 || j >= 0 || carry) {
        int da = (i >= 0) ? a[i]-'0' : 0;
        int db = (j >= 0) ? b[j]-'0' : 0;
        int s = da + db + carry;
        tmp[k++] = '0' + (s % 10);
        carry = s / 10;
        i--; j--;
    }
    for (int x = 0; x < k; x++) res[x] = tmp[k-1-x];
    res[k] = '\0';
}

// 字符串大整數乘小整數 (×10 等價於左移+加0)
void str_mul10_add(char *num, int digit, char *res) {
    // num × 10 + digit
    int len = strlen(num);
    for (int i = 0; i < len; i++) res[i] = num[i];
    res[len] = '0' + digit;
    res[len+1] = '\0';
}

void compute_big(int a, int n) {
    char term[200] = "0", sum[200] = "0", next[200];
    for (int i = 0; i < n; i++) {
        str_mul10_add(term, a, next);
        strcpy(term, next);
        str_add(sum, term, next);
        strcpy(sum, next);
    }
    printf("大整數結果: %s\n", sum);
}

int main() {
    int a, n;
    printf("輸入數字 a (1-9) 和項數 n: ");
    if (scanf("%d %d", &a, &n) != 2 || a < 1 || a > 9 || n < 1) {
        printf("無效輸入\n");
        return 1;
    }

    if (n <= 18) {
        long long term = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            term = term * 10 + a;
            sum += term;
        }
        printf("結果 (long long): %lld\n", sum);
    } else {
        compute_big(a, n);
    }
    return 0;
}