算法竞赛--回文数

发表于 更新于 分类于 阅读次数：
本文字数： 4.4k 阅读时长 ≈ 4 分钟

1.回文数(一)

123321是一个非常特殊的数，它从左边读和从右边读是一样的。

输入一个正整数n， 编程求所有这样的五位和六位十进制数，满足各位数字之和等于n 。

输入格式:

输入一行，包含一个正整数n。

数据规模和约定:1<=n<=54。

输出格式:

按从小到大的顺序输出满足条件的整数，每个整数占一行。

样例输入:

1
52

样例输出:

1
2
3
899998
989989
998899

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
int change(int n,int i)				//将i进行高低位交换，并用sum记录i各位数字的和，如果sum和整数n完全相等，则返回这个数，否则返回0.
{
	int m=0,sum=0;
	while(i>0)
	{
		m=m*10+(i%10);
		sum+=i%10;
		i=i/10;
	}
	if(sum==n)
		return m;
	else
		return 0;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=10000;i<=999999;i++)	//在最小的五位数和最大的六位数之间循环
	{
		if(i==change(n,i))		//如果i是回文数并且满足各位数字之和等于n
			printf("%d\n",i);		
	}
	return 0;
}

2.回文数二)

若一个数（首位不为0）从左到右读与从右到左读都是一样，这个数就叫做回文数，例如12521就是一个回文数。

给定一个正整数，把它的每一个位上的数字倒过来排列组成一个新数，然后与原数相加，如果是回文数则停止，如果不是，则重复这个操作，直到和为回文数为止。给定的数本身不为回文数。

例如：87则有：

STEP1: 87+78=165

STEP2: 165+561=726

STEP3: 726+627=1353

STEP4: 1353+3531=4884

编写一个程序，输入M（12<=M<=100）,输出最少经过几步可以得到回文数。如果在8步以内（含8步）不可能得到回文数，则输出0。

输入格式:

第1行一个正整数L,代表测试数据的组数。

接下来L行每行一个整数M（12<=M<=100），M本身不为回文数

输出格式:

输出L行，第i行对应输入数据的第i+1行，输出最少需要的步数；如果步数大于8，则输出0。

样例输入:

1
2
3
4
3
12
87
89

样例输出:

1
2
3
1
4
0

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
int change(int n)     //将数的高低位进行交换
{
	int m=0;
	while(n>0)
	{
		m=m*10+(n%10);
		n=n/10;
	}
	return m;
}
int main()
{
	int n;
	scanf("%d",&n);     //记录测试数据的组数
	while(n--)
	{	
		int count=0,num;
		scanf("%d",&num);
		while(1)
		{	
			int m=change(num);
			if(num==m||count>8)	//该数为回文数并且变换次数大于8的话，跳出循环
				break;
			else
			{
				num=num+m;
				count++;
			}
		}
		if(count<=8)
			printf("%d\n",count);
		else
			printf("0\n");
	}
	return 0;
}

3.回文数(三)

一个正整数，如果交换高低位以后和原数相等,那么称这个数为回文数。比如121，2332都是文数，134567不是回文数。任意一个正整数，如果其不是回文数,将该数交换高低位以后和原数相加得到一个新的数,如果新数不是回文数，重复这个变换，直到得到回文数为止。例如，57变换后得到132(57+75)，132得到363(132 + 231), 363是一个回文数。

曾经有数学家猜想:对于任意正整数,经过有限次上述变换以后，一定能得出一个回文数。至至这个猜想还没有被证明是对的。现在请你通过编程来验证。

输入格式:

输入一行一个正整数n。

输出格式:

输出第一行一个正整数， 表示得到一个回文数的最少变换次数。

接下来一行，输出变换过程，相邻的数之间用—>”连接。输出格式可以参见样例。保证最后生成的数在int范围内。

样例输入:

1
349

样例输出:

1
2
3
349--->1292--->4213--->7337

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
int change(int n)		//将数的高低位进行交换
{
	int m=0;
	while(n>0)
	{
		m=m*10+n%10;
		n=n/10;
	}
	return m;	
}
int main()
{
	int n,count=0,a[50];
	scanf("%d",&n);
	while(1)
	{	
		a[count++]=n;		//将n的值进行存储
		int m=change(n);
		if(m==n)			//将n与高低位交换后的数比较，看是否相等(判断是否是回文数)是的话跳出循环
			break;
		else				//否则将n和m相加
			n=n+m;	
	}
	printf("%d\n",count-1);//输出变换的次数
	printf("%d",a[0]);	   //输出第一个n的值，即n的初值
	if(count==0)
		printf("\n");	  //如果输入为回文数,直接输出换行
	else
	{
		for(int i=1;i<count;i++)
		{
			if(i==count)
				printf("%d\n",a[i]);
			else
				printf("--->%d",a[i]);	
		}
	}
	printf("\n");	
	return 0;
}

4.回文数(四)

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。

又如：对于10进制数87：

STEP1：87+78 = 165

STEP2：165+561 = 726

STEP3：726+627 = 1353

STEP4：1353+3531 = 4884

在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2< =N< =10或N=16）进制数M（其中16进制数字为0-9与A-F），求最少经过几步可以得到回文数。

如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

输入格式:

两行，N与M 100位，两数的最高位都不是0。

输出格式:

如果能在30步以内得到回文数，输出“STEP=xx”（不含引号），其中xx是步数；否则输出一行”Impossible!”（不含引号）

样例输入:

1
2
9 
87

样例输出:

1
STEP=6

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
#include <string.h>
char c[100];
int a[100],b[100];
int main()
{
	int n,count=0;
	scanf("%d",&n);					//记录进制N
	scanf("%s",c);					//输入一个数，用字符数组c接收，可能包含A-F字符
	int len=strlen(c);
	for(int i=0;i<len;i++)
	{
		if(c[i]>='A')
			a[i]=c[i]-'7';
		else
			a[i]=c[i]-'0';
	}							   //将字符数组c[i]中每个字符转换为数字存储在a[i]整型数组中
    while(1)
    {
    	int flag=0,i;
		for(i=0;i<len;i++)
			b[i]=a[i]+a[len-i-1];	//将a[i]中数字进行高低位相加
		for(i=0;i<len;i++)      //该处进行相加时，和高精度加法相同，逐步求和，大于n,则高位进1.
		{
			int temp=b[i];
			b[i]=(temp+flag)%n;
			if((flag+temp)>=n)
				flag=1;
			else
				flag=0;
			a[i]=b[i];			//将经过处理的b[i]中数字赋值给a[i]
		}
		if(flag==1)
		{
			a[len]=b[len]=1;
			len++; 
		}						//如果相加最高位进1，则重新开辟空间，存储进位1
		count++;
		int fa=1;				//设置标志位,判断高低位是否相等，即判断是否是回文数，不是则跳出循环
		for(int i=0;i<len/2;i++)
			if(b[i]!=b[len-i-1])
			{
				fa=0;
				break;
			}
		if(fa&&count<30)		//如果是回文数,并且变换次数小于30则输出变换次数，跳出循环
		{
			printf("STEP=%d\n",count);
			break;
		}
		if(count>=30)			//如果变换次数大于30次，则跳出循环
		{
			printf("Impossible!");
			break;
		}
	}
    return 0;
}
小礼物走一个哟
0%