第一天

今天学习内容是高精度计算。这里记录一下今天的作业题。

【问题描述】
     若一个数(首位不为零)从左向右读与从右向左读都是一样,我们就将其称之为回文数。例如:给定一个 10进制数 56,将 56加 65(即把56从右向左读),得到 121是一个回文数。又如,对于10进制数87, 
STEPl: 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” 
【输入样例】
       9 87
【输出样例】
       6

【思路】输入->循环30次,每次判断得到的数是否为回文数?跳出:继续->提前跳出?输出次数:“Impossible”。判断过程分为两个函数:第一步高精度计算得出每次结果;第二步判断结果是否为回文数。

【代码】

#include<bits/stdc++.h>

using namespace std;

string add(int n,string a)
{
  char a1[201]={0},b1[201]={0},s[201]={0};

  int i,l;

  l=a.size();

  for(i=0;i<l;i++) a1[i]=a[l-i-1]-‘0’;

  for(i=0;i<l;i++) b1[i]=a[i]-‘0’;

  for(i=0;i<l;i++)

  {

    a1[i]+=b1[i];

    if(a1[i]>=n)

    {

      a1[i+1]++;

      a1[i]-=n;

    }

  for(i=l;!a1[i] && i;i–);

  l=i;

  for(i=0;i<=l;i++) s[i]=a1[l-i]+’0′;

  s[i]=’\0′;

  return s;

  }
bool check(int n,string a)

{

  int i,l=a.size();

  for(i=0;i<l;i++)

    if(a[i]!=a[l-1-i])

      return 0;

  return 1;
}

int main()

{

  int n,t;

  string a,b;

  scanf(“%d%d”,&n,&a);

  for(t=1;t<=30;t++)

  {

    if(t==1) b=add(n,a);

    else b=add(n,b);

    if(check(n,b))

      break;

  }

  if(t<=30)

    printf(“%d”,t);

  else

    printf(“Impossible”);

return 0;
}