Palindromic Squares

2024-01-08 15:08
文章标签 squares palindromic

本文主要是介绍Palindromic Squares,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Palindromic Squares

Description

回文数就是顺着读和反着读都是一样的数字,数字12321就是一个典型的回文数。
给出一个表示进制的数字B(2<=B<=20 B是以十进制的数字呈现),如果整数N满足它的平方数在B进制下为回文数,则输出整数N(1<= N<=300 N也是以十进制的数字呈现), 同时也输出这个平方数。
输出满足条件的原数字在进制B下的数字以及它的平方在进制B下的数字

PROGRAM NAME: palsquare

INPUT FORMAT

输入一行表示B(B规定以十进制数表示)

SAMPLE INPUT (file palsquare.in)

10

OUTPUT FORMAT

每行包含两个整数,第一个整数是其平方为回文的数字,第二个是平方数本身,两个数之间用空格分开。注意两个数字都是以进制B表示。

SAMPLE OUTPUT (file palsquare.out)

1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696

设计算法

此处需要注意一个问题:题目并没有要求原数字在n进制下也要是回文数。
这道题其实很简单,需要写一个进制转换函数和一个判断一个数字是不是回文数的函数就基本上解决了,一个数如果是回文数其实那么把它当成一个字符串来看它也是回文的,而且用字符串来进行处理会方便快捷得多,所以我们只需要把数字转换为字符串来做,那么这个问题就没什么障碍了。

C++编写

/*
ID: your_id_here
TASK: palsquare
LANG: C++                 
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;const string t="0123456789ABCDEFGHIJ";
int B;string conv(int N)
{string num;while(N>0){int a = N%B;N/=B;num += t[a];}reverse(num.begin(),num.end());return num;
}bool check(string s)
{int len=s.size();for(int i=0;i<len/2;i++){if(s[i]!=s[len-1-i])return false;}return true;
}void solve(int n)
{int sq=n*n;if(check(conv(sq))){cout<<conv(n)<<" "<<conv(sq)<<endl;}
}int main()
{freopen("palsquare.in","r",stdin);freopen("palsquare.out","w",stdout);cin>>B;for(int i=1;i<=300;i++){solve(i);}return 0;
}

这篇关于Palindromic Squares的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/583865

相关文章

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

java常用算法之最长回文子串(Longest Palindromic Substring)

方法一:时间复杂度为O(n^3) public static String longestPalindrome1(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i

CodeForces 425D Sereja and Squares

题意: 平面上有n个点  问  最多能组成多少个边与坐标轴平行的正方形 思路: 这是一个通过不断二分查找乱搞的题… 首先枚举左下角  然后分别往上往右找左上角和右下角 这时如果发现边长不想等就通过长边长度在短边的方向二分查找最接近的值  不停往上往右延伸 如果发现边长想等了  那么要判断一下对应的左上角坐标出是不是有一个点 怎么判断呢  通过将所有点hash出一个值  然后二分

【二分查找】-POJ-2002-Squares

题目链接:http://poj.org/problem?id=2002 题目描述:给出平面上若干个点,问能最多构成几个不重复的正方形。 解题思路: 第一反应是标记数组直接搜,好吧,内存超限。然后想了BFS或者DFS,太没前途了。然后想了哈希,不失为一种方法,但是不会操作。好吧还是按照九野大神选题的初衷来做吧——二分查找,为了锻炼自己,嗯!手写!好吧,我写的只是二分找 x 坐标,y 坐标没二分

Palindromic Subsequence(最长回文字符串 输出路径)

初看好简单   一开始调试着一直re   后来也不知道怎么就对了  但是还有一些bug存在   , 这道题的打印路径和light oj An Easy LCS(ps:点击打开链接)一样 但是只改一下会Tle  因为(1000*1000*1000)好大 但是把存储的字符串改为string 定义的就过了 但是还是有一点有点难受(下面会说出) 我也是醉了 #include <stdio.

LeetCode | Longest Palindromic Substring

题目 Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 最长回文串问题,网上也有超

P2730 [USACO3.2] 魔板 Magic Squares

[USACO3.2] 魔板 Magic Squares 题目背景 在成功地发明了魔方之后,鲁比克先生发明了它的二维版本,称作魔板。这是一张有 8 8 8 个大小相同的格子的魔板: 1 2 3 4 1\quad2\quad3\quad4 1234 8 7 6 5 8\quad7\quad6\quad5 8765 题目描述 我们知道魔板的每一个方格都有一种颜色。这 8 8 8 种颜

第五题:最长回文子串(Longest Palindromic Substring)

题目描述: 给定一个字符串 s,找到 s 中最长的回文子串。 示例: 输入:s = "babad" 输出:"bab" 或 "aba" 输入:s = "cbbd" 输出:"bb" 要求: 你需要找出 s 中的最长回文子串。 解题思路 方法1:中心扩展法 回文字符串的特点是对称的,因此我们可以从每个字符(或字符间隙)作为中心,向两边扩展来找到回文子串。 遍历每个字符:对于字符串

POJ 2002 Squares hash求正方形个数

题意:给你n个点 坐标都小于20000 数一下可以组成多少个正方形 思路:借鉴了网上hash的思路 哈希链地址法 把x+y的绝对值相同的放人一个链表里 然后枚举2个点(1条边上的) 推算出另外2个点 另外2点分别是 x1 = a[i].x+(a[i].y-a[j].y);y1 = a[i].y-(a[i].x-a[j].x); x2 = a[j].x+(a[i].y-a[j].y);y2

Leet Code 5 Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 【算法思路】 1. 最简单的办法就是以