题目2529：A+B in Hogwarts
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1535
题目描述：哈利波特去的魔法学院使用一种特殊进制法表示数字：第i位用第i个素数为进制（radix），例如“个位”的进制为第一个素数2，“十位”的进制为第二个素数3，“百位”的进制为第三个素数5，...依此类推。例如，十进制数2表示为10，十进制数6被表示为100。现在要求你为哈利波特写一个简单的计算器用于计算a+b的结果，每一行输入魔法学院的数字a和b，两个数字用空格分割，数字的每一位用逗号分割，要求计算出a+b的结果，并用魔法学院的表示法表示（注意，输入数字最多不超过25位）。
示范输入：
1,0 2,1
4,2,0 1,2,0
1 10,6,4,2,1
示范输出：
1,0,1
1,1,1,0
1,0,0,0,0,0
该题目的难度不大，但对输入的解析和正确输出上有一定的技巧性，因此不能算特别简单的题。看到该题目的第一印象，我想把输入的数字a和b都转换为常规的int整数，然后再把a+b的结果转换为该特殊进制，但是这个转换过程会比常规的进制转换复杂一些，例如把1,0,0转换为10进制的过程是1*(2*3)+0*(2)+0=6;
因此我们马上改变思路，采用类似大数算法的方法，即使用一个数组来表示数字，然后把每一位使用的进制存储到一个数组r中，即r中存储前25个素数。然后计算a+b的过程和大数加法完全一致，唯一不同的是，大数加法的每一位都使用10进制，而这里每一位使用的进制都不同。
我们首先写出前25个素数，并存储到一个固定的数组中，我们可以用下面的代码来获取（请注意下面的代码完全是辅助性质，和最终题目的解并无关系）：
Code_求出前25个素数
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/* 判断一个数字n是否是素数 */
int isPrime(int n)
{
int i;
for( i=2; i < min( sqrt(n)+1, n-1) ; i++ )
{
if(n%i==0)
return 0;
}
return 1;
}
void main()
{
int n=1, count=0;
printf("\n");
for( ; count <= 30; n++)
{
if(isPrime(n))
{
printf("%3d,",n);
count++;
if(count%10==0)
printf("\n");
}
}
}
下面我们给出ZOJ 2529题目的完整代码：
Code_ZOJ_2529_Solution
/* ZOJ 2529 - A+B in Hogwarts */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* 前25个质数，也是第i位的radix */
int r[]={2,3,5,7,11, 13,17,19,23,29, 31,37,41,43,47, 53,59,61,67,71, 73,79,83,89,97, 101,103,107,109,113};
/* 记a+b=c */
int a[30], b[30], c[30];
/*用于读入两个加数的缓冲区*/
char buf1[512], buf2[512];
/*根据输入的用逗号间隔的字符串，转化为魔法世界进制的数组表示*/
void ParseInput(char* buffer, int dest[])
{
int i=0;/*第i位*/
char *s;/*逗号所在的位置，从字符串的尾部向前查找*/
while( (s=strrchr(buffer,','))!=NULL )
{
*s=0;/*在逗号处截断字符串！*/
dest[i++] = atoi(s+1);
}
/*已经没有逗号了，还剩下最高位的数字*/
dest[i++] = atoi(buffer);
}
/*计算出c=a+b*/
void Add()
{
int i;
for(i=0;i<30;i++)
c[i]=a[i]+b[i];
/*进位*/
for(i=0;i<29;i++)
{
c[i+1]+=c[i]/r[i];
c[i]=c[i]%r[i];
}
}
/*把结果打印出来，包含换行符，注意特殊情况，比如结果为1和0时*/
void PrintResult()
{
int i=29;
while(c[i]==0) i--;
for(;i>0;i--) printf("%d,", c[i]);
/*打印最后一位*/
printf("%d\n", c[0]);
}
int main()
{
while(scanf("%s %s",buf1,buf2)!=EOF && strcmp(buf1,"end")!=0)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
ParseInput(buf1, a);
ParseInput(buf2, b);
Add();
PrintResult();
}
return 0;
}
最后值得一提的是，解析输入的代码：ParseInput方法，用于把形如"10,6,4,2,0"这样的字符串解释到一个int数组（dest）内，是dest数组成为{0,2,4,6,10,0,...}。
用于把结果输入的方法，PrintResult，要注意当计算结果为0和1这样的比较特殊的情况，必须也应该能正确输出。这些比较临界的细节是尤其需要注意的地方。