Rob Kolstad
Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.
Given a number base B (2 <= B <= 20 base 10), print all the integers N (1 <= N <= 300 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on.
Print both the number and its square in base B.
PROGRAM NAME: palsquare
INPUT FORMAT
A single line with B, the base (specified in base 10).
SAMPLE INPUT (file palsquare.in)
10
OUTPUT FORMAT
Lines with two integers represented in base B. The first integer is the number whose square is palindromic; the second integer is the square itself.
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
题意:
输入M表示M进制,找出N在范围1到300(十进制)中所有N*N为回文串的数,输出N与N*N。比如当M=2时找出N在1~300(十进制)中,N*N为回文串的数,输出N和N*N,其中的N和N*N都用二进制来表示。
思路:
i从1循环到300,转换为N进制的操作封装在一个函数中,另外作为判断是否为回文串的操作封装在另一个函数中,最后在主函数的循环中直接调用两个函数即可判断出是否为回文串。M进制的M为1到20,说明最多用20进制来表示,则用一个数组来装M进制个位数的表示方式。
总体思路就是:将a和a平方转化为M进制(倒着存)后判断a平方是否为回文串(余数判断),是则输出,不是则判断下一个数。
AC:
/* TASK:palsquare LANG:C ID:sum-g1 */ #include<stdio.h> #include<string.h> int N,alength,blength; int a[20],b[20]; //a数组为还没平方时的数(已经转化为M进制)(倒序) //b数组为a数平方后的数(已经转化为M进制)(倒序) int change(int c) { int cs=c*c,i=1; while(c) {a[i++]=c%N;c/=N;} alength=i-1; i=1; while(cs) {b[i++]=cs%N;cs/=N;} blength=i-1; } //change为改变成M进制的数,存的方式为倒序 int judge() { int i,j; for(i=1,j=blength;i<=blength;i++,j--) if(b[i]!=b[j]) return 0; return 1; } //judge判断这个数是否为回文串,变量i从头开始向后遍历,变量j从尾开始向前遍历 //发现有一项不同就返回0,说明不同 int main() { FILE *fin =fopen("palsquare.in","r"); FILE *fout=fopen("palsquare.out","w"); int i,p; char k[20]="0123456789ABCDEFGHIJ"; //k数组为M进制的表示方式 fscanf(fin,"%d",&N); for(i=1;i<=300;i++) { change(i); if(judge()) { for(p=alength;p>=1;p--) fprintf(fout,"%c",k[a[p]]); //满足条件则输出a,记得从尾开始输出,因为前面是倒序存储的 fprintf(fout," "); for(p=blength;p>=1;p--) fprintf(fout,"%c",k[b[p]]); //满足条件输出a平方,同样的也是从尾部开始输出(也可以不倒序,因为是回文串) fprintf(fout,"\n"); } } exit(0); }
总结:
字符数组的初始化为char k[20]="0123456789ABCDEFGHIJ"时编译器会通过不了,所以改用strcpy(k,"0123456789ABCDEFGHIJ")。但是,提交上去的时候strcpy(k,"0123456789ABCDEFGHIJ")则不能通过,所以改回用char k[20]="0123456789ABCDEFGHIJ",然后就AC了这道题了。
考虑这题的时候思维真的很混乱,用数组存的话存进去的顺序是倒序的,后来想着想着,回文串既然是对称的,倒不倒序好像没关系……但是对于还没平方的数要倒序输出才行。现在想问题很容易将问题复杂化,其实细心想想,很多地方还是可以简化的。
1.不需要开一个数组存倒序的,另外再开个数组存顺序的,输出的时候倒着输出就行了,判断的时候一个从前向后遍历,一个从后向前遍历,倒不倒序也没什么影响的;
2.还有在比较是否对称的时候,只要有一个不满足相等的条件就返回False,不需要等全部都比较完才判断是Ture还是False;
3.用几进制来表示可用开个数组来表示对应关系(M进制里面没有M数字表示,比如2进制中表示的数字中没2);
4.判断是否对称不需要一定先转化为M进制表示的数才开始对称的,对这个数不断对M取余(当然每取完一次要/M)保存在数组后,就可以直接对这个数组进行判断是否对称了。如果用20进制表示的话,比如数63的平方3696(10进制),然后对3696不断取余变成一个20进制的数(变成9I9),用一个数组a[5](这个数组应该是int类型的)存着,那么就是a[1]=9,a[2]=19(I就是第19个表示数),a[3]=9(9跟9对称,19在中间)。这样的话,把20进制表示数对称转化为余数对称,这样一来就不用想那么多了,不需要另外找一个数组来存他们转换成M进制后的数再来判断是否为回文串了。
这些细节和技巧的东西也要慢慢积累才行,不然代码会写得多又繁杂,当然也要保持清醒的头脑,才会想到那么多,有时候只会想着说要怎么解决一个题,然后就会忽略了很多可以运用技巧的地方。
相关推荐
USACO题目Palindromic Squares(回文平方数)及代码解析
8 [1.2] 回文平方数 Palindromic Squares 9 [1.2] 双重回文数 Dual Palindromes 10 [1.3] 混合牛奶 Mixing Milk 11 [1.3] 修理牛棚 Barn Repair 12 [1.3] 牛式 Prime Cryptarithm 13 [1.3] 虫洞 wormhole 14 [1.3] ...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
zoj 3661 Palindromic Substring.md
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. ...
PAT甲级 1024 Palindromic Number 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...
原创:PAT 1019 General Palindromic Number (20 分)A number that will be the same when
回文数要确定是否需要取消费用,必须先确定是否需要取消费用。 Elnúmerodebe ser市长de 2dígitos。 Desarrollar unaaplicaciónque ingrese dosnúmerosy se cambien las posiciones pares del底漆númerocon el ...
最长回文子序列 动态规划 | 第 12 组(最长回文子序列)( )
回文数发生器当给出正数时,返回回文数以及达到该数需要执行多少步骤。眼镜创建一个名为palindromeNumberGenerator的函数,该函数采用一个Number值。 检查数字是否为回文数,如果不是,则将值和取反的值相加,并检查...
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
最长回文子串最长回文子串 | 设置 1 ( )
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also ...substri
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 示例 1: Input: "babad" Output: "bab" Note: "aba" is also a valid ...re
虫和农作物等细胞内的基因进行精确编辑的热门技术之精髓: 细菌和古细菌已经根据CRISPR(规律成簇的间隔短回文重复,Clustered regularly interspaced short palindromic repeats)位点和多样化CRISPR相关(CRISPR- ...
细菌和古细菌已经根据CRISPR(规律成簇的间隔短回文重复,Clustered regularly interspaced short palindromic repeats)位点和多样化CRISPR相关(CRISPR-associated,Cas)基因,进化出了复杂的CRISPR适应性免疫...
主要介绍了Python实现常见的回文字符串算法,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
Palindromic Substrings * Problem URL : https://leetcode.com/problems/palindromic-substrings/ * Date : Oct 17 2017 * Complexity : O(n^3) Time, O(n) space * Author : Atiq Rahman * Status : Accepted * ...
leetcode 516 8/13 - 8/18 周:leetcode#: 409. longestPalindrome 125. Valid Palindrome ...Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:
leetcode 分类leetcode ...Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先队列 #23:Merge k Sorted Lists