E - 猜想滞销，帮帮小明

约定不等于承诺〃 2022-03-21 07:11 128阅读 0赞

### 题目描述： ###

一个正整数，如果从左向右读和从右向左读是一样的，这样的数就叫回文数。  
任取一个正整数，如果不是回文数，将该数与他的倒序数相加，若其和不是回文数，则重复上述步骤，一直到获得回文数为止。  
小明在某次考试中突然想到一个问题：是不是不论由什么正整数开始，在经过有限次正序数和倒序数相加的步骤后，都会得到一个回文数。  
小明是那么执着于他的猜想，以致于没有做完试卷（惨案现场）。 现在，小明决定化悲痛为力量，并将这个猜想命名为小明猜想。  
他悄悄地塞给了你几个数，你能帮他计算吗。  
Input  
每行一个正整数。  
特别说明：输入的数据保证中间结果小于2^31。  
Output  
对应每个输入，输出两行，一行是变换的次数，一行是变换的过程。  
保证题中的每个数经过变换后都能变成回文数  
Sample Input  
27228  
37649  
Sample Output  
3  
27228—>109500—>115401—>219912  
2  
37649—>132322—>355553

##### 分析： #####

在本题中，我一开始以为有可能还会加正序数的样例，但是后来发现。如果有加正序数的样例，就要要到dfs。但在本题中没有，所以直接模拟就好。  
这份代码是将dfs的方法去掉了加正序数的。

#include"stdio.h"
    #include"string.h"
    int k;
    int transfer(int N)
    {
        int i,j;
        char word[1000];
        j=0;i=0;
        while(N)
        {
            word[j++]=N%10+'0';
            N=N/10;
        }
        for(i=0;i<j;i++)
        {
            N=N*10+word[i]-'0';
        }
      return N;
    }
    int isprime(int N)
    {
        int i,j;
        char word[1000];
        j=0;i=0;
        while(N)
        {
            word[j++]=N%10+'0';
            N=N/10;
        }
        j--;
        while(i<j)
        {
            if(word[i]!=word[j])
                break;
            i++;j--;
        }
        if(i<j)
            return 0;
        return 1;
    }
    void dfs(int step[],int N,int k)
    {
        int i=0;
        if(isprime(N))
        {
            printf("%d\n",k);
            step[k+1]=N+i;
            for(i=0;i<k;i++)
                printf("%d--->",step[i]);
            printf("%d\n",step[i]);
            return ;
        }
        i=transfer(N);
        step[k+1]=N+i;
        dfs(step,N+i,k+1);
        
    
    }
    int main()
    {
        int step[1000];
        int N;
        int i;
        int mark;
        while(~scanf("%d",&N))
        {
           step[0]=N;
           k=0;
           mark=isprime(N);
           if(mark==1)
           {
               printf("%d\n",0);
               printf("%d\n",N);
           }
           else
           {
               dfs(step,N,k);
           }
        }
    }