首页 > 试题广场 >

General Palindromic Number (20

[编程题]General Palindromic Number (20

热度指数：2404 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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 the sum of (a_i bⁱ ) for i from 0 to k. 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 non-negative 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 non-negative numbers N and b, where 0 <= N <= 10⁹ is the decimal number and 2 <= b <= 10⁹  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₀".  Notice that there must be no extra space at the end of output.

示例1

输入

27 2

输出

Yes<br/>1 1 0 1 1

算法知识视频讲解

JacobGo！

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)

good1uck

我的代码莫名其妙通不过 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)

C/C++

Backtraxe

#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)

Disconnect

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)

不想取名啊

本题题解 https://blog.csdn.net/S_zhicheng27/article/details/81408616

发表于 2018-08-04 11:03:24 回复(0)

LiuTaw

#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)

hustsun

#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)

C/C++

猫猫猫1

#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)

MniQ

#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;
}

发表于 2019-01-22 14:13:44 回复(0)

C/C++

Caffeine

思路： 就是简单的判断和进制转换。
#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)

C/C++

尼米茨的风

#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(" ");
    }

}

发表于 2018-02-28 19:08:38 回复(0)

carson0408


进制转换，注意输出
#-*-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)

Russell

#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)