2023年贵州省中小学信息技术教师培训作业(5月16日）

1. 爬楼梯

树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级 也可以第一次走两级，第二次走一级，一共3种方法。输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30。输出不同的走法数，每一行输入对应一行输出。

样例输入

5

8

10

样例输出

8

34

89

#include <iostream>
using namespace std;
int zoufa(int n) {
    if (n <= 2) {
        return n;
    }
    
    int a = 1, b = 2, c;
    for (int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    
    return c;
}
int main() {
    int n;
    while (cin >> n) {
        int fangshi = zoufa(n);
        cout << fangshi << endl;
    }
    
    return 0;
}

2. 2的幂次方表示

任何一个正整数都可以用2的幂次方表示。例如：137=27+23+20

同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)

进一步：7=22+2+20（21用2表示）3=2+20

所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)

又如：1315=210+28+25+2+1

所以1315最后可表示为：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输入一个正整数n（n≤20000）。

输出一行，符合约定的n的0，2表示（在表示中不能有空格）。

样例输入

137

样例输出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

#include <iostream>
using namespace std;
void liupeng(int n) {
    if (n == 0) {
        cout << "0";
        return;
    }
    if (n == 1) {
        cout << "2(0)";
        return;
    }
    if (n == 2) {
        cout << "2";
        return;
    }
    
    int liup = 0;
    while ((1 << liup) <= n) {
        liup++;
    }
    liup--;
    
    if (liup == 0) {
        cout << "2(0)";
    } else if (liup == 1) {
        cout << "2";
    } else {
        cout << "2(";
        liupeng(liup);
        cout << ")";
    }
    
    n -= (1 << liup);
    if (n > 0) {
        cout << "+";
        liupeng(n);
    }
}
int main() {
    int n;
    cin >> n;
    
    liupeng(n);
    
    return 0;
}

3. 分数求和

输入n个分数并对他们求和，并用最简形式表示。所谓最简形式是指：分子分母的最大公约数为1；若最终结果的分母为1，则直接用整数表示。

如：5/6、10/3均是最简形式，而3/6需要化简为1/2, 3/1需要化简为3。分子和分母均不为0，也不为负数。输入第一行是一个整数n，表示分数个数，1 <= n <= 10；接下来n行，每行一个分数，用"p/q"的形式表示，不含空格，p，q均不超过10。

输出只有一行，即最终结果的最简形式。若为分数，用"p/q"的形式表示。

样例输入

2

1/2

1/3

样例输出

5/6

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
string jhfs(int fenzi, int fenmu) {
    int fenpei = gcd(fenzi, fenmu);
    fenzi /= fenpei;
    fenmu /= fenpei;
    
    if (fenmu == 1) {
        return to_string(fenzi);
    }
    
    return to_string(fenzi) + "/" + to_string(fenmu);
}
string tjxs(vector<string>& xsbf) {
    int resultfenzi = 0;
    int resultfenmu = 1;
    
    for (const auto& xiaoshu : xsbf) {
        stringstream ss(xiaoshu);
        int fenzi, fenmu;
        char slash;
        ss >> fenzi >> slash >> fenmu;
        
        int lcmValue = lcm(resultfenmu, fenmu);
        int chengshu1 = lcmValue / resultfenmu;
        int chengshu2 = lcmValue / fenmu;
        
        resultfenzi = (resultfenzi * chengshu1) + (fenzi * chengshu2);
        resultfenmu = lcmValue;
    }
    
    return jhfs(resultfenzi, resultfenmu);
}
int main() {
    int n;
    cin >> n;
    
    vector<string> xsbf(n);
    for (int i = 0; i < n; i++) {
        cin >> xsbf[i];
    }
    
    string result = tjxs(xsbf);
    cout << result << endl;
    
    return 0;
}