[PAT A1019]General Palindromic Number
题目描述
1019 General Palindromic Number (20 分)A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.
Although palindromic numbers are most often considered in the decimal system, the concept of palindromicity can be applied to the natural numbers in any numeral system. Consider a number N>0 in base b≥2, where it is written in standard notation with k+1 digits a?i?? as ∑?i=0?k??(a?i??b?i??). Here, as usual, 0≤a?i??<b for all i and a?k?? is non-zero. Then N is palindromic if and only if a?i??=a?k?i?? for all i. Zero is written 0 in any base and is also palindromic by definition.
Given any positive decimal integer N and a base b, you are supposed to tell if N is a palindromic number in base b.
输入格式
Each input file contains one test case. Each case consists of two positive numbers N and b, where 0<N≤10?9?? is the decimal number and 2≤b≤10?9?? is the base. The numbers are separated by a space.
输出格式
For each test case, first print in one line Yes if N is a palindromic number in base b, or No if not. Then in the next line, print N as the number in base b in the form “a?k?? a?k?1?? … a?0??”. Notice that there must be no extra space at the end of output.
输入样例1
27 2
输出样例1
Yes
1 1 0 1 1
输入样例2
121 5
输出样例2
No
4 4 1
解析
- 题目的意思很简单,意思就是要给你一个N和b,N表示一个数,b表示一个基数,我们首先要做的就是得到以b为基数的N的表示形式,然后判断该数是不是回文数,如果是,输出Yes,并输出回文数,如果不是,输出No并输出回文数
- 我使用的方法,比较繁琐,就是使用了stack建立了一个栈,通过不断压栈得到对应的回文数,然后输出到一个vector中保存,最后使用判断回文数的方法比较即可
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main()
{
int N, b;bool is_true = true;stack<int> st;vector<int> v;cin >> N >> b;do{
st.push(N%b);N /= b;} while (N); //不断压栈得到倒过来的回文数while (!st.empty()){
v.push_back(st.top()); //将其输出到vector中st.pop();}for (int i = 0, j = v.size()-1; i < j; i++, j--) //判断结果是不是回文数{
if (v[i] != v[j]){
is_true = false;break;}}cout << ((is_true) ? "Yes" : "No") << endl;for (int i = 0; i < v.size(); i++){
cout << v[i];if (i != v.size()-1) cout << " ";}return 0;
}
- 也可以不使用栈,直接输入到数组中判断也可以,这样会省一些代码,输出的时候就要注意,必须从后往前输出了