《程序设计语言综合设计》第三周上机练习

4 回文数

对于一个自然数n，若将n的各位数字反向排列所得的数n1与n相等，则称n为回文数，例如2332。
若给定一个N( 2<=N<=16)进制数M（M的长度在一百位以内），如果M不是回文数，可以对其进行N进制加法，最终得到回文数。
例如对于十进制数79 STEP1 : 79 + 97 = 176 STEP2 : 176 + 671 = 847 STEP3 : 847 + 748 = 1595 STEP4 : 1595 +5951 = 7546 STEP5 : 7546 + 6457 = 14003 STEP6 : 14003 + 30041 = 44044
那么对于给定的N进制数M，请判断其能否在30步以内（包括30步）得到回文数。

输入格式

第一行包括一个正整数 N（2<=N<=16）。
第二行包括一个正整数M（一百位以内）。

输出格式

如果可以在n步内得到回文数，输出“STEP=n”，否则输出“NO”。

输入样例1

10
79

输出样例1

STEP=6

输入样例2

8
665556

输出样例2

NO

Accepted

#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
using namespace std;
void rever(string a){ //可用 reverse(a.begin(), a.end());代替
    int i,j;
    char temp;
    int len=(int)a.size()-1;
    if(len%2){
    for(i=0,j=len-1;i!=j;i++,j--){
        temp=a[i];
        a[i]=a[j];
       a[j]=temp;
      }
    }
    if(len%2==0){
    for(i=0,j=len-1;i!=j-1;i++,j--){
        temp=a[i];
        a[i]=a[j];
       a[j]=temp;
      }
    }
}
string sum_str(string m,int n){
    int temp = 0,i;
    int flag=0;
    string a;
    int j=(int)m.size()-1;
    for(i=0;i<m.size()&&j>=0;i++,j--){
        temp=0;
       if(m[i]>='0'&&m[i]<='9') temp+=(m[i]-'0');
        if(m[j]>='0'&&m[j]<='9') temp+=(m[j]-'0');
        if(m[i]>='A'&&m[i]<='Z')temp+=(m[i]-'A')+10;
        if(m[j]>='A'&&m[j]<='Z')temp+=(m[j]-'A')+10;
        if(flag==1){//进位1
            temp++;
             flag=0;
        }
        if(temp>=n){//大于n要进位
            flag=1;
            temp-=n;}
        if(temp<10) temp+='0';
        else temp=temp-10+'A';
          a+=temp;
    }
    if(flag==1){
        a=a+"1";
    }
      rever(a);
    return a;
}
int judge(string m){
    int i,j;
    for(i=0,j=(int)m.size()-1;i<m.size()&&j>=0;i++,j--){
        if(m[i]!=m[j]) return 0;
    }
    return 1;
}
int main() {
    int n;
    int step=0;
    string m;
    cin >> n;
    cin >> m;
    if(judge(m)) cout << "STEP=" <<step << endl;
    else{
        while(step<=30){
            m=sum_str(m,n);
            step++;
            
            if(judge(m)){
                cout << "STEP=" <<step << endl;
                break;
            }
        }
    }
    if(step>30) {cout << "NO" << endl; }
    return 0;
}

高精度计算加减乘除

5 数楼梯

楼梯有N阶，上楼可以一步上一阶，也可以一步上两阶。那么走到第N阶楼梯共有多少种不同的走法呢？

输入格式

一个正整数 N（1<=N<=5000），表示楼梯阶数。

输出格式

输出一个数，表示走到第N阶楼梯有多少种走法。
注意，数据范围很大，即使是64位也可能不够存。

输入样例1

4

输出样例1

5

输入样例2

400

输出样例2

28481229810848961175798893768146099561538008878230489098647719564596927140403

Accepted
(来源：洛谷)

#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string.h>
using namespace std;
int len=1,fl[5005][5005]={0};//fl[k][i]--第k阶台阶所对应的走法数
void floor(int k){
    int i;
    for(i=1;i<=len;i++)
        fl[k][i]=fl[k-1][i]+fl[k-2][i];
    for(i=1;i<=len;i++){
        if(fl[k][i]>=10){
            fl[k][i+1]+=fl[k][i]/10;
            fl[k][i]=fl[k][i]%10;
            if(fl[k][len+1]) len++;
        }
    }
}
int main() {
    int n;
    cin >> n;
    fl[1][1]=1;
    fl[2][1]=2;
    for(int i=3;i<=n;i++){
        floor(i);
    }
    for(int i=len;i>=1;i--){
        printf("%d",fl[n][i]);
    }
    return 0;
}

这道题我们可以论述一下递推与递归的方法与区别

递推一般用循环来解决,从已知条件到未知逐渐接近结果:
（1）将复杂运算分解为若干重复的简单运算
（2）后一步骤建立在前一步骤之上
（3）计算每一步骤的方法相同
（4）从开始向后计算出结果
（5）使用循环结构，通过多次循环逐渐逼近结果
递归一般自己调用自己,从未知到已知,把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题,并且小到一定程度可以直接得出它的解,从而得到原来问题的解。
（1）每一次递归都缩小问题规模，直到问题足够小
（2）使用选择分支语句
（3）从后往开始逐步逼近
（4）达到最开始，再把初始值带入往后逐一求解

《程序设计语言综合设计》第三周上机练习

原文：https://www.cnblogs.com/lvhang/p/12441090.html