Posted on 2010-08-17 13:48
Brian 閱讀(887)
評論(0) 編輯 收藏 引用 所屬分類:
一些好題
好幾個人問我校內(nèi)OJ的回文數(shù)那道題，我去年沒做，現(xiàn)在看了，怪不錯的一道題：
Description
若一個數(shù)（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數(shù)。例如121就是一個回文數(shù)。
對于任意一個數(shù)，可以進行如下變換，可以得到一個回文數(shù)。
例如：
給定一個10進制數(shù)56，將56加65（即把56從右向左讀），得到121是一個回文數(shù)。
又如：
對于10進制數(shù)87：
STEP1：87+78 = 165
STEP2：165+561 = 726
STEP3：726+627 = 1353
STEP4：1353+3531 = 4884
在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數(shù)4884。
寫一個程序，給定一個N（2<=N<=10，N=16）進制數(shù)M，求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible！”
Input
第一行為N
第二行為M
Output
STEP=步數(shù)
或
Impossible!
Sample Input
9
87
Sample Output
STEP=6
#include<stdio.h>
#include<string.h>
char M[20];
int N,len;// 進制、字符串長度
int a[20]={0},b[20]={0};
void Format(char a[],int b[])
{
int i=0;
for (; i<len; i++)
if(N>10 && a[i]>='A')
b[i]=a[i]-'A'+10;
else b[i]=a[i]-'0';
}
void Step()
{
int i=0;
a[len]=0;
for (; i<len; i++)
b[i]=a[len-i-1];
for (i=0; i<len; i++) //核心代碼
{
a[i]+=b[i];
if (a[i]>N-1)
{
a[i+1]+=a[i]/N;
a[i]=a[i]%N;
}
}
if(a[len]) len++;
}
int IsPalindrome() //判斷是否是回文數(shù)
{
int i=0;
for (; i<=len/2; i++)
if (a[i]!=a[len-1-i])
return 0;
return 1;
}
int main()
{
int STEPS=0;
scanf("%d",&N);
scanf("%s",M);
len=strlen(M);
Format(M,a); //將字符轉(zhuǎn)化為對應進制數(shù)字
while(1)
{
if(STEPS>30)
{
printf("Impossible!\n");
return 0;
}
if(STEPS && IsPalindrome())
break;
Step();
STEPS++;
}
printf("STEP=%d\n",STEPS);
return 0;
}
我的是任意進制都可以的， 192MS 0K