B3619题解

kuangfengzhixi · 2024-01-19 16:57:19 · 个人记录

B3619题解

原题

话说kkk出题都挺言简意赅的哈？

很好的题目，使我的栈爆炸。

首先，看题：

给定一个十进制整数 n 和一个小整数 x。

确认过眼神，好的，我们可以知道这是一道 [数据结构-栈] 的题目。为什么呢，因为如果要求一个十进制整数 n 转成 x 进制，需要用到短除法。

举个栗子，把 38 转成三进制：

把每个式子的余数 2 0 1 1 倒过来可得 1 1 0 2，故把十进制数 38 转成三进制为 1102。

因为最后一步需要倒着输出，不难想到要用栈来解决。

数据结构-栈

堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。——摘自《百度百科》

明白了栈怎么用，下一步就需要实现栈。

核心代码 Core code

while(n>0){
    top++;//压栈
    stk[top]=n%a;//短除法
    n/=a;
}
while(top>=0){
    if(stk[top]<10){
        cout<<stk[top];
        top--;//弹/出栈
    }
    else{
        cout<<char(stk[top]-10+'A');//超过十进制的数用 A,B,C......
        top--;//弹/出栈
    }
}

完整代码 Full Code

#include<bits/stdc++.h>
using namespace std;
int top=-1,stk[109];
int main()
{
    int n,a;
    cin>>n>>a;
    while(n>0){
        top++;//压栈
        stk[top]=n%a;//短除法
        n/=a;
    }
    while(top>=0){
        if(stk[top]<10){
            cout<<stk[top];
            top--;//弹/出栈
        }
        else{
            cout<<char(stk[top]-10+'A');//超过十进制的数用 A,B,C......
            top--;//弹/出栈
        }
    }
}