Posted on 2010-08-17 13:48
Brian 閱讀(867)
評論(0) 編輯 收藏 引用 所屬分類:
一些好題
好幾個人問我校內OJ的回文數那道題，我去年沒做，現在看了，怪不錯的一道題：
Description
若一個數（首位不為零）從左向右讀與從右向左讀都一樣，我們就將其稱之為回文數。例如121就是一個回文數。
對于任意一個數，可以進行如下變換，可以得到一個回文數。
例如：
給定一個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，求最少經過幾步可以得到回文數。如果在30步以內（包含30步）不可能得到回文數，則輸出“Impossible！”
Input
第一行為N
第二行為M
Output
STEP=步數
或
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() //判斷是否是回文數
{
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); //將字符轉化為對應進制數字
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