20250227-Rain

1. 嵌套循环

/*
1. 使用程序打印九九乘法表
样例输出: 
1 * 1 = 1
1 * 2 = 2    2 * 2 = 4
1 * 3 = 3    2 * 3 = 6    3 * 3 = 9
…
*/

#include <iostream>
#include <iomanip>

using namespace std;

int main(void)
{
    for(int i = 1; i <= 9; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            /*
            如果不设置输出宽度，在得到 10 以上的答案时，格式会混乱
            利用 cout 操纵算子 来进行 宽度输出设置（默认空格填充 补齐宽度）
                - setiosflags(ios::left)：设置左对齐，也可以在循环外设置（默认右对齐）
                - setw(5)：设置宽度为 5
            */
            cout <<  j << " * " << i << " = " << setiosflags(ios::left) << setw(5) << j * i;
        }
        cout << endl;
    }
    return 0;
}

2. 一维数组

/*
2. 合并有序数组
阿伟学长终于写好了游戏背包1和背包2的排序算法, 但他发现将两个背包同时带上时, 还得合并一下排序.
阿伟学长懒得再写排序了, 希望小伙伴能帮帮他完成背包的合并.
设计一个程序, 输入两个有序数组, 输出一个合并后的有序数组.

输入:
第一行: 整数n,m  表示数组1和数组2分别有n,m个数字
第二行: n个整数Ni, 表示数组1的每个元素
第三行: m个整数Mi, 表示数组2的每个元素
(n,m<=100. 0<=Ni,Mi<=1000)

输出: 
合并后的新数组
*/

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    // 获取输入
    int n, m;
    cout << "Please input 'n' 'm'(space to separate): ";
    cin >> n >> m;

    // 非法输入，报错退出
    if (n > 100 || m > 100) {
        cerr << "Error: n or m must be in the range (-inf, 100]" << endl;
        return 1;
    }

    vector<int> N(n, 0);
    cout << "Please input element of array 'N[]'(space to separate): ";
    for(int i = 0; i < n; i++)
    {
        cin >> N[i];
    }

    vector<int> M(m, 0);
    cout << "Please input element of array 'M[]'(space to separate): ";
    for(int i = 0; i < m; i++)
    {
        cin >> M[i];
    }

    /*
    利用一次归并排序
    时间复杂度 O(m+n)
    */
    vector<int> res(n + m, 0);  // 结果数组作为合并后的数组
    int pn = 0, pm = 0;
    while(pn < n && pm < m) // 直到一方数组遍历完毕
    {
        if(N[pn] > M[pm])
        {
            res[pn + pm] = M[pm];   // 结果数组的索引可以用 原始数组的索引和来表示
            pm++;
        }
        else
        {
            res[pn + pm] = N[pn];
            pn++;
        }
    }

    // 处理剩余元素
    while (pn < n)  // M 序列结束，将剩余的 N 序列补充在 res 数组中 
	{
		res[pn + pm] = N[pn];
        pn++;
	}
	while (pm < m) // N 序列结束，将剩余的 M 序列补充在 res 数组中 
	{
		res[pn + pm] = M[pm];
        pm++;
	}

    for(int i = 0; i < pn + pm; i++)
    {
        cout << res[i] << " ";
    }
    return 0;
}

3. 一维数组

/*
3. 排队枪毙
小约参与了犹余游戏, 在这个游戏中最后活下来的人才能获得胜利.
游戏规则是这样的, n个玩家们围成一个圈, 从第一个玩家开始报数
报到m的人被枪毙, 下一个人接着从1开始报数.
直到最后一个活下来的人获得胜利.

小约现在开始选编号了, 已知参与的玩家数量为n, 被枪毙的数是m. 小约要选到几号位置才会活下来.
(1<m<n<100)

设计一个程序, 输入n和m, 输出最后的胜利者

样例输入: 10 3
样例输出: 4
*/

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int n, m;
    cin >> n >> m;

    // 非法输入，报错退出
    if (n >= 100 || n <= 1 || m >= 100 || m <= 1 || m >= n) {
        cerr << "Error: n or m must be in the range (1, 100)" << endl;
        return 1;
    }

    // 创建玩家数组
    vector<int> array(n, 0);
    for(int i = 0; i < n; i++)
    {
        array[i] = i + 1;
    }

    // 下一个杀死元素 的 索引
    int kill = 0;
    while(array.size() != 1)
    {
        // 防止数组越界，与当前的数组大小 取余
        // - kill + m: 杀死的元素
        // - kill + m - 1: 由于数组下标从 0 开始，需要 - 1 再取模
        kill = (kill + m - 1) % array.size();
        array.erase(array.begin() + kill);
    }

    // 输出此时数组唯一的元素
    cout << array[0] << endl;
    return 0;
}