c++基础算法练习(1)

1、每个判断条件return 0返回：

        if (savings >= house_price) { // 检查是否够买房子
            cout << years + 1 << endl; // 输出年数，+1因为years从0开始
            return 0; // 成功找到结果，退出程序
        }

2、裴波那契数列

动态规划（Dynamic Programming，简称DP）是一种数学方法和算法设计思想，主要用于求解复杂问题。它的核心思路是将原问题分解为相对简单的子问题，通过逐步解决这些子问题来达到最终目标。这种方法在多个领域有广泛应用，包括计算机科学、经济学、运筹学、管理学和生物信息学等

1、重叠子问题：
动态规划适用于那些可以分解成重复的子问题的问题。例如，在计算 Fibonacci 数列时，F(n) 可以通过 F(n-1) 和 F(n-2) 来表示，这样就形成了重叠的子问题。
2、最优子结构：
若一个问题的最优解包含其子问题的最优解，则该问题具有最优子结构性质。动态规划将此性质作为设计迭代或递归算法的基础。
3、记忆化存储：
为了避免重复计算动态规划中已解决的子问题，将它们的结果存储在某种数据结构中（如数组或哈希表）。这样，当再次需要这些子问题的结果时，可以直接查找而无需重新计算，从而显著提高效率。

#include <iostream>
using namespace std;
/*
输入项数
终止是1，2
*/
int feibo(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    int a = 1, b = 1; // F(1) 和 F(2)
    for (int i = 3; i <= n; ++i) {
        int c = a + b; // F(n) = F(n-1) + F(n-2)
        a = b; // 更新 F(n-2)
        b = c; // 更新 F(n-1)
    }
    return b; // 返回 F(n)
}

int main() {
    int N;
    cin >> N ;
    //if()
    cout<<feibo(N);
    return 0;
}

3、鸡尾酒疗法

1、数组里面的变量用double

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N; // 输入组数

    vector<double> sequ(N, 0); // 存储各疗法的有效率
    for(int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y; // 输入总病例数和有效病例数
        double residue = 100.0 * y / x; // 计算有效率
        sequ[i] = residue; // 存储有效率
    }
    
    // 比较每个改进疗法与鸡尾酒疗法的效果
    for(int i = 1; i < N; ++i) {
        if (sequ[i] - sequ[0] > 5) {
            cout << "better" << endl; // 效果更好
        } else if (sequ[0] - sequ[i] > 5) {
            cout << "worse" << endl; // 效果更差
        } else {
            cout << "same" << endl; // 效果差不多
        }
    }

    return 0;
}

4、球弹跳高度的计算

1、这里的最后一次不要计算反弹的高度，要减去

1、printf("%g\n", totalDistance)
//自动选择格式：%g 会根据数值的大小自动选择使用 f（浮点数）或 e（科学记数法）格式来输出。

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    double h, totalDistance = 0;
    cin >> h; // 输入初始高度
    double reboundHeight;

    for (int i = 0; i < 10; ++i) {
        totalDistance += h;  // 落下的距离
        reboundHeight = h / 2; // 计算反弹高度
        if(i!=9)
        {
         totalDistance += reboundHeight; // 加上反弹的距离
        }

        h = reboundHeight; // 更新高度为反弹高度
    }
    

    // 输出结果
    printf("%g\n", totalDistance); // 总经过的米数
    printf("%g\n", reboundHeight); // 第10次反弹的高度

    return 0;
}

5、角谷猜想

1、这里面要用到的值都需要反复更新

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int n;
    cin >> n; // 输入正整数

    // 继续处理直到 n 等于 1
    while (n != 1) {
        if (n % 2 == 0) { // 偶数
            n = n / 2; // 更新 n
            printf("%d/%d=%d\n", n * 2, 2, n); // 显示除法过程
        } else { // 奇数
            n = n * 3 + 1; // 更新 n
            printf("%d*%d+%d=%d\n", (n - 1) / 3, 3, 1, n); // 显示乘法和加法过程
        }
    }
    cout << "End" << endl; // 输出结束标志
    return 0;
}

6、计分程序

1、按照题思路解题

#include <iostream>
using namespace std;

int calculateScore(int N) {
    int score = 0;
    
    if (N <= 10) {
        score = N * 6; // 前 10 道题，每道 6 分
    } else if (N <= 20) {
        score = 10 * 6 + (N - 10) * 2; // 前 10 道 6 分，后 N-10 道 2 分
    } else if (N <= 40) {
        score = 10 * 6 + 10 * 2 + (N - 20) * 1; // 前 20 道题按上述得分，后 N-20 道 1 分
    } else {
        score = 100; // 超过 40 道题，得 100 分
    }
    
    return score;
}

int main() {
    int N;
    while (cin >> N) { // 接收多组输入
        cout << calculateScore(N) << endl; // 输出每个学生的得分
    }
    return 0;
}

6、药房管理

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int m; // 药品总量
    int n; // 病人数
    
    // 输入药品总量
    cin >> m;
    // 输入病人数
    cin >> n;

    vector<int> requests(n); // 用于存储每个病人的取药请求

    // 输入每个病人的请求数量
    for (int i = 0; i < n; ++i) {
        cin >> requests[i];
    }

    int not_satisfied_count = 0; // 未能取药的病人数

    // 遍历每个病人的请求
    for (int i = 0; i < n; ++i) {
        if (requests[i] <= m) { // 库存足够
            m -= requests[i]; // 扣除库存
        } else { // 库存不足
            not_satisfied_count++; // 记录未满足请求的病人
        }
    }

    // 输出未能取药的人数
    cout << not_satisfied_count << endl;

    return 0;
}