資料結構實驗：堆疊應用——十進制轉 R 進制（2 ≤ R ≤ 9）

題目需求

• 輸入十進制整數 a 與基數 R (2 ≤ R ≤ 9)。
• 輸出 a 的 R 進制表示。
• 多組測資，至 EOF。

堆疊解法（標準教學做法）

#include <cstdio>
#include <stack>
using namespace std;

int main()
{
    int a, r;
    while (scanf("%d %d", &a, &r) != EOF) {
        stack<int> S;
        while (a > 0) {
            S.push(a % r);
            a /= r;
        }
        while (!S.empty()) {
            printf("%d", S.top());
            S.pop();
        }
        putchar('\n');
    }
    return 0;
}

關鍵點

1. 除基取餘法：反覆 a % r 得到最低位，a /= r 縮減數值。
2. 堆疊反序：餘數產生順序為低位→高位，堆疊 LIFO 特性恰好反轉順序。
3. 邊界：a = 0 時輸出 0（本題隱含 a > 0，否則需特判）。

C 風格手動堆疊（無 STL）

#include <stdio.h>

int main()
{
    int a, r;
    char s[100];   // 足夠存放 32-bit 整數任意進制
    while (scanf("%d %d", &a, &r) != EOF) {
        int top = 0;
        if (a == 0) { putchar('0'); putchar('\n'); continue; }
        while (a > 0) {
            s[top++] = '0' + (a % r);
            a /= r;
        }
        while (top--) putchar(s[top]);
        putchar('\n');
    }
    return 0;
}

庫函式捷徑

#include <stdlib.h>  // itoa 非標準但常見
// 或
#include <stdio.h>   // sprintf 通用
sprintf(buf, "%d", a);  // 僅支援 8/10/16 進制
// 任意進制仍需手動實現

複雜度分析

• 時間：O(log_R a)，迴圈次數等於結果位數。
• 空間：O(log_R a)，堆疊/陣列大小同樣為位數。

延伸：任意進制（R > 9）

需引入數字符號表 0-9A-Z：

const char *digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
s[top++] = digits[a % r];

本題限制 R ≤ 9，故直接 '0' + remainder 即可。