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 ai
as the sum of (ai
bi
) for i from 0 to k. Here, as usual, 0 <= ai
< b for all i and ak
is non-zero. Then N is palindromic if and only if ai
= ak-i
for all i. Zero is written 0 in any base and is also palindromic by definition.
Given any non-negative decimal integer N and a base b, you are supposed
to tell if N is a palindromic number in base b.
[编程题]General Palindromic Number (20
- 热度指数：2375 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
Each input file contains one test case. Each case consists of two non-negative numbers N and b, where 0 <= N <= 109 is the decimal number and 2 <= b <= 109 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 "ak ak-1 ... a0". Notice that there must be no extra space at the end of output.
示例1
输入
27 2
输出
Yes<br/>1 1 0 1 1
package go.jacob.day1016; import java.util.ArrayList; import java.util.Scanner; /** * 1019. General Palindromic Number (20) * * @Jacob */ public class Demo1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(), base = sc.nextInt(); ArrayList<Integer> res = decimalToBase(N, base); boolean flag = true; int left = 0, right = res.size() - 1; while (left < right) { //Integer为包装类型，判断是否相等要用equals if (!res.get(left).equals(res.get(right))) { flag = false; break; } left++; right--; } if (flag) System.out.println("Yes"); else System.out.println("No"); System.out.print(res.get(res.size() - 1)); for (int i = res.size() - 2; i >= 0; i--) { System.out.print(" " + res.get(i)); } sc.close(); } /* * 将十进制转成base进制 要考虑N等于0的情况 */ private static ArrayList<Integer> decimalToBase(int N, int base) { ArrayList<Integer> res = new ArrayList<Integer>(); if (N == 0) res.add(0); while (N != 0) { res.add(N % base); N /= base; } return res; } }
发表于 2017-10-16 20:08:59
回复(0)
更多回答
我的代码莫名其妙通不过 2 0 ，然而自己手动测出的答案是对的,PAT也能通过。不知道为什么（牛客OJ怎么这么奇怪？不是精度和别人不一样，就是测试用例用有问题，现在是运行时都有问题吗？）
#include<iostream>
using namespace std;
int main() {
int N,b,a[32]={0};
bool p=true;
cin>>N>>b;
int i;
for(i=0;N!=0;i++){
a[i]=N%b;
N/=b;
}
for(int j=0;j<i;j++){
if(a[j]!=a[i-1-j]){
p=false;
break;
}
}
cout<<(p?"Yes":"No")<<endl;
cout<<a[i-1];
for(int m=i-2;m>=0;m--){
cout<<" "<<a[m];
}
return 0;
}
发表于 2020-01-31 20:16:45
回复(0)
#include <cstdio>
#include <vector>
using namespace std;
// 十进制转r进制
vector<int> ten2n(int n, const int &r) {
vector<int> ans;
do {
ans.push_back(n % r);
n /= r;
} while (n);
return ans; // 逆序的
}
// 判断回文
bool isP(const vector<int> &V) {
for (int i = 0; i < V.size() / 2; ++i)
if (V[i] != V[V.size() - 1 - i]) return false;
return true;
}
int main() {
// freopen("in.txt", "r", stdin);
int n, r;
scanf("%d%d", &n, &r);
vector<int> V = ten2n(n, r);
if (isP(V)) printf("Yes\n");
else printf("No\n");
for (int i = V.size() - 1; i >= 0; --i) {
printf("%d", V[i]);
if (i > 0) printf(" ");
}
return 0;
} 第一次排第一，留个纪念：）
发表于 2019-08-29 16:52:14
回复(0)
out = []
n,b = map(int,input().split())
while n>=b:
out.append(n%b)
n=n//b
out.append(n)
out1 = list(map(int,out))
out.reverse()
if out1==out:
print('Yes')
else:
print('No')
print(' '.join(map(str,out)))
发表于 2018-12-10 16:31:59
回复(0)
发表于 2018-08-04 11:03:24
回复(0)
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
using namespace std;
int main()
{
vector<int> tmp;
int N,base;
scanf("%d %d",&N,&base);
if(N==0)
{
cout<<"Yes"<<endl<<"0"<<endl;
return 0;
}
while(1)
{
int left = N%base;
//cout<<left<<endl;
tmp.push_back(left);
N =N/base;
if(N<base)
{
tmp.push_back(N);
break;
}
}
for(int i=0;i<tmp.size()/2;i++)
{
int k = tmp.size()-i-1;
if(tmp[i]!=tmp[k])
{
cout<<"No"<<endl;
for(int j=tmp.size()-1;j>=0;j--)
{
cout<<tmp[j];
if(j==0)
cout<<endl;
else
cout<<" ";
}
return 0;
}
}
cout<<"Yes"<<endl;
for(int i=tmp.size()-1;i>=0;i--)
{
cout<<tmp[i];
if(i==0)
cout<<endl;
else
cout<<" ";
}
return 0;
}
发表于 2018-02-27 19:41:28
回复(0)
#include <cstdio>
int main(void){
int N, b;
scanf("%d%d", &N, &b);
int n[32];
int i = 0;
do{
n[i++] = N % b;
N = N / b;
}while(N != 0);
bool flag = 1;
for(int j = 0; j < i / 2; j++){
if(n[j] != n[i - 1 - j]) {
flag = 0;
break;
}
}
if(flag == 0) printf("No\n");
else printf("Yes\n");
for(int p = i - 1; p >= 0; p--){
printf("%d", n[p]);
if(p != 0) printf(" ");
}
return 0;
}
发表于 2018-02-03 09:07:14
回复(0)
import java.util.ArrayList;
import java.util.Scanner;
//注意0
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int d=in.nextInt();
ArrayList<Integer> list=new ArrayList<Integer>();
if(n==0){
list.add(0);
}
while(n!=0){
list.add(n%d);
n/=d;
}
int size=list.size();
Boolean f=true;
for(int i=0;i<size/2;i++){
if(!list.get(i).equals(list.get(size-1-i))){
f= false;
break;
}
}
if(f){
System.out.println("Yes");
}else System.out.println("No");
String s="";
for(int i=size-1;i>=0;i--){
s+=(list.get(i)+" ");
}System.out.println(s.trim());
}
}
发表于 2016-10-29 10:12:47
回复(0)
#include<bits/stdc++.h>
using namespace std;
const int Max=500;
int main() {
int n,b,a[Max],i=0;
cin>>n>>b;
if(n==0) {
cout<<"Yes"<<endl<<0<<endl;
} else {
while(n!=0) {
a[i++]=n%b;
n/=b;
}
int j;
for(j=i-1; j>=i/2; --j) {
if(a[j]!=a[i-1-j]) {
break;
}
}
if(j==i/2-1) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
for(int k=i-1; k>=0; k--) {
cout<<a[k]<<" ";
}
}
return 0;
}
编辑于 2022-11-05 15:43:25
回复(1)
原版题目测试用例不包括N=0，这里输入N=0时要特判
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n,b;
cin>>n>>b;
if(n==0) {
cout<<"Yes"<<endl<<0;
return 0;
}
vector<int> ans,t;
if(!n){
cout<<"Yes"<<endl;
}
else{
while(n){
ans.push_back(n%b);
n/=b;
}
t=ans;
reverse(ans.begin(),ans.end());
bool flag=0;
for(int i=0;i<(int)ans.size()/2;i++){
if(ans[i]!=t[i]){
flag=1;
break;
}
}
if(flag==0) cout<<"Yes";
else cout<<"No";
cout<<endl;
for(int i=0;i<(int)ans.size();i++){
if(i==0) cout<<ans[i];
else cout<<" "<<ans[i];
}
}
}
发表于 2020-06-25 20:42:51
回复(0)
#include<iostream>
#include<vector>
using namespace std;
void palindromicnumber() {
long long a, b;
cin >> a >> b;
vector<long long >q, p;
if (a == 0) {
q.push_back(0);
}
while (a != 0) {
q.push_back(a % b);
a /= b;
}
p = q;
bool flag = true;
flag = q.front() == q.back();
while (q.size()!=1) {
flag = q.front() == q.back();
if (flag) {
q.erase(q.begin()); q.erase(q.end()-1);
}
else
{
break;
}
}
if (flag == true) {
cout << "Yes" << endl;
while (p.empty() != true) {
if (p.size() != 1) {
cout << p.front() << " ";
p.erase(p.begin());
}
else
{
cout << p.front(); p.erase(p.begin());
}
}
//cout << p.front();
}
else {
cout << "No" << endl;
while (p.empty() != true) {
if (p.size() != 1) {
cout << p.back() << " ";
p.erase(p.end()-1);
}
else
{
cout << p.back();
p.erase(p.end()-1);
}
}
}
}
//27 2 121 5
int main()
{
// helloworldforu();
palindromicnumber();
return 0;
}
发表于 2020-01-22 19:13:32
回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
//1019 General Palindromic Number
//Palindromic adj. 回文的
//特别规定0本身是一个回文数字，任何进制下
/**原来如此，系数并非固定1位，每个系数ai需要分开保存
测试用例:
609468183 236
对应输出应该为:
No
46 86 180 71
你的输出为:
No
6 4 6 8 0 8 1 1 7
*/
int main(){
int n,b; //0<n<=10^9, 2<=b<=10^9
cin>>n>>b;
//需要特别处理一下0
if(n==0) {cout<<"Yes"<<endl<<0; return 0;}
vector<string> v;
while(n>0){
v.push_back(to_string(n%b));
n/=b;
}
//得到的v是逆序的，不过本题求回文，所以正序逆序都没差
int len=v.size()-1;//已进行下标修正
int flag=0;
for(int i=0;i<=len/2;++i){
if(v[i]!=v[len-i]) flag=1;
}
if(flag==1) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
//逆序的v,从尾部开始输出
cout<<v[len];
for(int i=len-1;i>=0;--i){
cout<<" "<<v[i];
}
return 0;
}
#include <string>
#include <vector>
using namespace std;
//1019 General Palindromic Number
//Palindromic adj. 回文的
//特别规定0本身是一个回文数字，任何进制下
/**原来如此，系数并非固定1位，每个系数ai需要分开保存
测试用例:
609468183 236
对应输出应该为:
No
46 86 180 71
你的输出为:
No
6 4 6 8 0 8 1 1 7
*/
int main(){
int n,b; //0<n<=10^9, 2<=b<=10^9
cin>>n>>b;
//需要特别处理一下0
if(n==0) {cout<<"Yes"<<endl<<0; return 0;}
vector<string> v;
while(n>0){
v.push_back(to_string(n%b));
n/=b;
}
//得到的v是逆序的，不过本题求回文，所以正序逆序都没差
int len=v.size()-1;//已进行下标修正
int flag=0;
for(int i=0;i<=len/2;++i){
if(v[i]!=v[len-i]) flag=1;
}
if(flag==1) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
//逆序的v,从尾部开始输出
cout<<v[len];
for(int i=len-1;i>=0;--i){
cout<<" "<<v[i];
}
return 0;
}
发表于 2019-01-22 14:13:44
回复(0)
思路： 就是简单的判断和进制转换。
#include <iostream>
#include <vector>
using namespace std;
vector<long long> GenerNum(long long n, long long b)
{
vector<long long> v;
long long remainder;
if (n == 0)
{
v.push_back(0);
}
while (n)
{
remainder = n % b;
n = n / b;
v.insert(v.begin(), remainder);
}
return v;
}
bool JudgePalindromic(vector<long long>& v)
{
bool judge = true;
for (int i = 0; i < v.size(); i++)
{
if(v[i] != v[v.size() - 1 -i])
{
judge = false;
}
}
return judge;
}
int main()
{
long long n, b;
while (cin >> n >> b)
{
vector<long long> v;
v = GenerNum(n, b);
if (JudgePalindromic(v))
{
cout << "Yes" << endl;
for (int c = 0; c < v.size(); c++)
{
cout << v[c];
if (c != v.size() - 1)
cout << " ";
else
cout << endl;
}
}
else
{
cout << "No" << endl;
for (int c = 0; c < v.size(); c++)
{
cout << v[c];
if (c != v.size() - 1)
cout << " ";
else
cout << endl;
}
}
}
}
发表于 2018-08-22 10:41:43
回复(0)
#include <cstdio>
int main(){
int n, base, num = 0, after[100];
scanf("%d%d", &n, &base);
do{
after[num++] = n % base;
n = n / base;
}while(n != 0);
bool flag = true;
for(int i = 0;i < num / 2;i++){
if(after[i] != after[num - i - 1]){
flag = false;
break;
}
}
if(flag)
printf("Yes\n");
else
printf("No\n");
for(int i = num - 1;i >= 0;i--){
printf("%d", after[i]);
if(i != 0)
printf(" ");
}
}
int main(){
int n, base, num = 0, after[100];
scanf("%d%d", &n, &base);
do{
after[num++] = n % base;
n = n / base;
}while(n != 0);
bool flag = true;
for(int i = 0;i < num / 2;i++){
if(after[i] != after[num - i - 1]){
flag = false;
break;
}
}
if(flag)
printf("Yes\n");
else
printf("No\n");
for(int i = num - 1;i >= 0;i--){
printf("%d", after[i]);
if(i != 0)
printf(" ");
}
}
发表于 2018-02-28 19:08:38
回复(0)
进制转换，注意输出 #-*-coding:utf-8 -*- while True: try: N,b=map(int,raw_input().split()) s=[] if N==0:s=['0'] else: while N>0: a=N%b N=N//b s.append(str(a)) if s[::-1]==s: print 'Yes' else:print 'No' print ' '.join(s[::-1]) except:break
编辑于 2017-07-23 14:16:00
回复(0)
#include<cstdio>
#include<algorithm>
using namespace std;
int num[40],sz=0,n,b;
bool same(){
for(int i=0;i<sz/2;i++){
if(num[i]!=num[sz-1-i])
return false;
}
return true;
}
void solve(){
while(n){
num[sz++]=n%b;
n/=b;
}
}
int main(){
scanf("%d%d",&n,&b);
solve();
if(same()){
puts("Yes");
}
else{
puts("No");
}
for(int i=sz-1;i>0;i--){
printf("%d ",num[i]);
}
printf("%d\n",num[0]);
return 0;
}
发表于 2016-08-01 02:34:26
回复(0)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
int n,x;
cin>>n>>x;
int a[1000]={};
int k=0;
do{
a[k++]=n%x;
n=n/x;
}while(n);
int f=1;
for(int i=0;i<k;i++)
{
if(a[i]!=a[k-1-i])
{f=0;
break;
}
}
if(f)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
for(int j=k-1;j>=0;j--)
{
if(j)
cout<<a[j]<<" ";
else
cout<<a[j]<<endl;
}
return 0;
}
发表于 2016-02-19 13:54:26
回复(0)
def numSystem(num, base):
rlt = []
while num > 0:
rlt.append(num%base)
num /= base
return rlt
num, base = map(int, raw_input().strip().split())
if num:
rlt = numSystem(num, base)
rlt_reverse = rlt[:]; rlt_reverse.reverse()
if rlt == rlt_reverse:
print('Yes')
else:
print('No')
rlt_reverse = map(str, rlt_reverse)
print(' '.join(rlt_reverse))
else:
print('Yes')
print(0)
发表于 2016-01-28 15:13:43
回复(0)
问题信息
难度：
18条回答
2收藏
4490浏览
通过挑战的用户
-
2023-03-07 21:05:38 -
2023-02-23 01:12:18 -
2023-02-22 16:17:14 -
2023-01-16 14:57:02
-
2023-01-08 17:06:41
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
