Palindromic Squares（枚举）

Palindromic Squares
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进制后的数再来判断是否为回文串了。

    这些细节和技巧的东西也要慢慢积累才行，不然代码会写得多又繁杂，当然也要保持清醒的头脑，才会想到那么多，有时候只会想着说要怎么解决一个题，然后就会忽略了很多可以运用技巧的地方。

评论

3 楼 Simone_chou 2013-08-01  

RChee 写道

char k[20]="0123456789ABCDEFGHIJ"

OH!我懂了！原来是这样！之前有个错误原来是因为这个！你早说嘛……哈哈

2 楼 RChee 2013-08-01  

使用"0123456789ABCDEFGHIJ"描述字符串时，程序会自动在最后加上一个转义字符0，即'\0'。

因此，char k[20]="0123456789ABCDEFGHIJ"通过不了编译的原因是这个字符串一共有20个字符，但是为了保存字符串结束标记'\0'一共需要21个字符。如果要使用这种方式初始化，应该把字符数组开大一位，否则会造成越界访问，程序会把越界的字符'\0'存到内存里面未知区域，不过此时，因为程序处于初始化阶段，即使是访问到了未知区域，未知的区域可能还没有被初始化，所以带来的风险不会很大。

而使用strcpy(k,"0123456789ABCDEFGHIJ")的时候同样有越界的风险。这个时候，由于程序已经完成了初始化，可能会把越界'\0'字符保存到一个有数据的未知区域，造成有用数据的改变或者丢失。

如果不需要保存字符串末尾的'\0'，可以用char k[20]={'0','1','2',……}这样的方式初始化字符数组，或者干脆在初始化时先不保存最后一个字符'J'，在程序开始运行的时候再把'J'加上：

//初始化阶段
char k[20]="0123456789ABCDEFGHI";
//此时 k[20]中保存的实际上是"0123456789ABCDEFGHI\0"
/*
其它初始化……
*/
//程序开始
k[19]='J';

1 楼 RChee 2013-08-01  

char k[20]="0123456789ABCDEFGHIJ"