洛谷p1015

题目描述

若一个数(首位不为零)从左向右读与从右向左读都一样,我们就将其称之为回文数。
例如:给定一个十进制数56,将56加65(即把5656从右向左读),得到121是一个回文数.
又如:对于十进制数87:
STEP1:87+78 = 16
STEP2:165+561 = 726
STEP3:726+627 = 1353
STEP4:1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法,上例最少用了4步得到回文数4884.

写一个程序,给定一个N(2 <= N <= 10,N =16 )进制数M(100位之内),求最少经过几步可以得到回文数。如果在30步以内(包含30步)不可能得到回文数,则输出Impossible!

输入输出格式

输入格式
两行,分别是N,M.
输出格式
STEP=ans

题目分析

  1. 首先此类题目设计数字的反转,不妨想到用字符串进行操作更方便。同时,C++的reverse()函数,方便了字符串的反转
  2. 其次,我们应学会高效率的进制转换
  3. 通过计数器进行STEP计数,我们便可求解

    代码示例

    #include <iostream>
    #include <cstdio>
    #include <string>
    using namespace std;
    unsigned long long n=0,k,len,nex;
    string nn;
    bool wow(unsigned long long a)
    {
    unsigned long long s=0;
    for (unsigned long long i=a;i;i/=k) //第三个for循环
    s=s*k+i%k;
    nex=s+a;
    return s==a;
    }
    unsigned long long ch(char a)
    {
    if (a>='0' && a<='9') return a-'0';
    return a-'A'+10;
    }
    int main()
    {
    cin>>k>>nn;len=nn.size();
    for (int i=0;i<len;i++) //第一个for循环
    n=n*k+ch(nn[i]);
    unsigned long long step;
    for (step=0;!wow(n) && step<=30;step++) //第二个for循环
    n=nex;
    if (step<=30) cout<<"STEP="<<step<<endl;
    else cout<<"Impossible!";
    return 0;
    }

代码分析

  1. 首先,数字以字符串输入,通过第一个for循环,可直接将任意进制转换为十进制(大大降低了用栈求进制的麻烦).这里涉及到一个数学知识,即秦久韶公式,大家可以搜索了解下
  2. 第三个for循环更加精巧.通过一个for循环,将一个十进制数变成相应的反转后k进制数,再转换为十进制数。
  3. wow函数内部通过比较反转前后的k进制数的十进制进行比较,如果相等,则返回true,若不相等,则再次调用wow函数,直到为true或STEP > 30
  4. 数字字符串转化为数字.ch函数巧妙地运用ASDII码的特性,将单个字符转化为单个数字

追加学习

字符串反转
  1. 使用string.h中的strrev函数。

    char s[20] = "hello";
    strrev(s);
    cout<<s<<endl; //输出为 olleh
  2. 使用algorithm中的reverse函数

    string s[20] = "hello";
    reverse(s.begin(),s.end()); //也可写成reverse(s)
    cout<<s<<endl; //输出为 olleh
字符数字转数字

利用ASDII码特性,字符数字 - ‘0’ 即为对应数字,字母 - ‘A’ + 10 即为9以上对应数字

  unsigned long long ch(char a)
{
if (a>='0' && a<='9') return a-'0';
return a-'A'+10;
}

进制转换
  1. 利用C++栈转换

     #include <iostream>
    #include <stack>
    using namespace std;
    int main()
    {
    int b,n,e;
    cout << "请输入数制转换的进制及数值:"<<endl;
    cin >> b >> n;
    cout << "数值" << n << "的" << b << "进制为:" << endl;
    stack<int>stk; //重点
    while (n)
    {
    stk.push(n%b);
    n /= b;
    }
    while (!stk.empty())
    {
    cout << stk.top();
    stk.pop();
    }
    return 0;
    }
  2. 利用秦九韶公式转换(仅仅适用于K进制转十进制)

    for (int i=0;i<len;i++)      //第一个for循环
    n=n*k+ch(nn[i]);
C++栈的使用说明
  1. 使用栈,要先包含头文件:

    #include <stack>
  2. 定义栈,以如下形式实现:

    stack<Type> s;    //其中Type为数据类型(如 int,float,char等)。
  3. 栈的主要操作

    s.push(S);		        //将S压入栈顶  
    s.pop(); //删除栈顶的元素,但不会返回
    s.top(); //返回栈顶的元素,但不会删除
    s.size(); //返回栈中元素的个数
    s.empty(); //检查栈是否为空,如果为空返回true,否则返回false

谢谢访问