1309：【例1.6】回文数(Noip1999)

Dear 丶 2023-06-18 13:54 17阅读 0赞

今天写代码的时候遇到大整数回文数，本来就有点难，再加上不细心，搞了半天才搞好

//
    // Created by L on 2019-12-01.
    //
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    
    using namespace std;
    
    int a[100],b[100],n,count;
    //初始化数组a--使用数组进行判断
    void init(int a[]){
        int i;
        string s;//将需要验证的数以字符串的形式输入
        memset(a, 0, sizeof(a));//将数组a清零
        cin>>n>>s;
        //将字符数组转换成整数数组
        a[0]=s.length();//用a[0]存储输入数字的大小
        for (i = 1; i <=a[0];i++) {//将字符数组转换成整数数组
            if(s[a[0]-i]>='0'&&s[a[0]-i]<='9'){
                a[i]=s[a[0]-i]-'0';
            }else{
                a[i]=s[a[0]-i]-'A'+10;
            }
        }
    
    }
    
    //判断一个数是否是回文数
    int palindrom(int a[]){
        int i;
        for (i = 1; i <= a[0]; i++) {//此处使用i <= a[0]判断，效率比较低
            if(a[i]!=a[a[0]+1-i]){//这地方是加1，不是减1，就是因为这个错误，搞了好长时间，气死我了
                return 0;
            }
        }
        return 1;
    }
    
    //将非回文数进行加法运算
    void addition(int a[]){
        int i;
        for(i=1;i<=a[0];i++)//将数组a中的数字逆序存入到b中
            b[i]=a[a[0]-i+1];
        for (i = 1; i <=a[0]; i++) {//将两个数字进行加法运算，注意条件中的等号
            a[i]+=b[i];
        }
        for (i = 1; i <=a[0] ; i++) {//将加法得到的数进行n进制合理化
            a[i+1]+=a[i]/n;//注意加号，注意这里除的是n不是10
            a[i]=a[i]%n;
        }
        if(a[a[0]+1]>0) a[0]++;//修正新的a位数
    }
    
    //主函数
    int main(){
        //初始化a
        init(a);
        //判断是否回文数
        if(palindrom(a)){cout<<0<<endl;return 0;}
        //判断M是否是n进制的回文数字--使用数组的方式
        count=0;
        while (count<=30){
            count++;
            addition(a);
            if(palindrom(a)){cout<<count<<endl;return 0;}//这个地方要打印count
        }
        cout<<"impossible";
        return 0;
    }

总结：

对于大整数的运算比较好的方法是使用字符数组进行运算，所以这个题目选择用字符数组比较好是实现，同时记住使用数组的第一个来存储数组长度，这一个就类似简单排序里面的“哨兵 ”原理