换座位、找 M 进制数、循环小数、数字方阵、单纯质因数 - C++ 代码实现 - 常规

五个算法题的 C++ 代码实现

这篇文章提供了五个算法题的 C++ 代码实现，包括换座位、找 M 进制数、循环小数、数字方阵、单纯质因数。每个题都包含详细的代码示例和测试用例，帮助你更好地理解和学习算法知识。

第一题换座位（seat）

问题描述：

期中考试结束了，班主任想给同学们重新安排座位，所以她让同学们按学号 1 至 n 的顺序依次在教室外排好队，然后在队伍中挑选一些同学来改变他们的位置。班主任想知道最终有多少个同学的位置发生了变化。

楠楠是个信息学高手，班主任把这个任务交给楠楠来完成。

输入格式：

第一行，输入一个整数 n(n<=100)，表示有 n 个同学。第二行，有 n 个整数，依次表示换位后的学号。

输出格式：

输出有多少个同学的位置发生了变化。

输入样例：

10 1 2 5 4 6 3 7 8 9 10

输出样例：

3 （样例说明：只有学号为 5，6，3 共 3 位同学的位置发生了变化。）

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

// 第一题 换座位（seat）
int seat(int n, vector<int> nums){
    int count = 0;
    for(int i=0; i<n; i++){
        if(nums[i] != i+1){
            count++;
        }
    }
    return count;
}

int main(){
    // 第一题 换座位（seat）
    int n1;
    cin >> n1;
    vector<int> nums1(n1);
    for(int i=0; i<n1; i++){
        cin >> nums1[i];
    }
    int res1 = seat(n1, nums1);
    cout << res1 << endl;

    return 0;
}

第二题找 M 进制数(num)

问题描述：

在信息学课上，楠楠学习了进制数。他知道了原来数不仅可以表示成十进制，还可以表示成二进制，八进制，十六进制，甚至是二十进制，三十进制都可以。而且它们都有一个相同的运算规则：逢 M 进一，例如：二进制逢二进一，八进制逢八进一。因此，M 进制数中每一位上的数可以用 0～M-1 来表示，即二进制数中只有 0 和 1 两种数字，八进制数中有 0，1，2…7 共八种数字。但是若 M 大于 10 时，大于等于 10 的数字用大写字母表示，例如十六进制数中有 0，1，2…9，A…F 共 16 种数字。现在老师给出 N 个任意进制数，要求统计出 N 个数中合法的 M 进数的个数。

输入格式：

输入数据有多行。第一行，有两个整数 N(1<=N<=100000)和 M(2<=M<=36)，分别表示任意进制数的个数和 M 进制。接下来有 N 行，每行一个由数字和大写字母构成的任意进制数,位数小于 50。

输出格式：

输出 N 个任意进制数中，合法的 M 进制数的个数。

输入样例：

5 16 102 AFF 5A 890 5S

输出样例：

**样例解释：**因为“5S”中“S”不是 16 进制数的合法数字，故只有 4 个合法的 16 进制数。

#include<iostream>
#include<vector>
#include<string>
using namespace std;

// 第二题 找 M 进制数(num)
int num(int n, int m, vector<string> nums){
    int count = 0;
    for(int i=0; i<n; i++){
        bool valid = true;
        for(int j=0; j<nums[i].length(); j++){
            if(nums[i][j] >= '0' && nums[i][j] <= '9'){
                if(nums[i][j]-'0' >= m){
                    valid = false;
                    break;
                }
            }
            else{
                if(nums[i][j]-'A'+10 >= m){
                    valid = false;
                    break;
                }
            }
        }
        if(valid){
            count++;
        }
    }
    return count;
}

int main(){
    // 第二题 找 M 进制数(num)
    int n2, m;
    cin >> n2 >> m;
    vector<string> nums2(n2);
    for(int i=0; i<n2; i++){
        cin >> nums2[i];
    }
    int res2 = num(n2, m, nums2);
    cout << res2 << endl;

    return 0;
}

第三题循环小数(decimal)

问题描述：

数学课上，楠楠学习了一个新的知识。两数相除，如果得不到整数商，会有两种情况：一种是得到有限小数，另一种是得到无限小数。从小数点后某一位开始依次不断地重复出现前一个或一节数字的十进制无限小数，叫做循环小数，如 2.9666..., (在数学中它读作“二点九六，六循环” ），定义循环小数的缩写法是将第一个循环节以后的数字全部略去，并将第一个循环节首末用括号括起来。

例如： 2.966666... 缩写为 2.9(6) 35.232323…缩写为 35.(23)

楠楠发现，根据循环小数的特征，很快能算出这个循环小数中小数点后第 n 位的数字，你能吗？

输入格式：

输入数据有两行。第一行，输入一个整数 n(n<=100000)，表示求小数点后的第 n 位。第二行，一个字符串，用缩写法表示的一个循环小数。

输出格式：

输出一个整数，求出循环小数中小数点后第 n 位的数字。

输入样例 1： 10 352.19(7)

输出样例 1： 7

输入样例 2： 5 7328.(192)

输出样例 2： 9

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

// 第三题 循环小数(decimal)
int decimal(int n, string num){
    int index = num.find('(');
    if(index != -1){
        int len = num.length();
        int count = stoi(num.substr(index+1, len-index-2));
        return count;
    }
    else{
        return num[n] - '0';
    }
}

int main(){
    // 第三题 循环小数(decimal)
    int n3;
    string num3;
    cin >> n3 >> num3;
    int res3 = decimal(n3, num3);
    cout << res3 << endl;

    return 0;
}

第四题数字方阵(matrix)

问题描述：

周末，爸爸妈妈带着楠楠去商场玩，正好碰上了商场在举办有奖竞答活动，而且根据问题的难度不同，奖品的价值也有不同。聪明爱动脑的楠楠挑了一个难度最大的问题来挑战自己。最后他赢得了丰厚的奖品和热烈的掌声。

这个问题是：在一个数字方阵中，随机放置了 0～9 的数字。我们把由数字 1～9 的组成的串称为非零串（不含 0 的数字串）。例如 02303230 ，这组数据中有 23 和 323 两种非零串。其中长度最长的非零串为 323。

已知一个 N*M（1<=N,M<=1000）的数字方阵，求方阵第 k 行的最长非零串的长度。

如下图：在这个 4*8 的方阵中，第 2 行的最长非零串长度为 3。

1 2 0 3 4 2 2 0 0 2 3 0 3 2 3 0 3 0 3 2 0 0 0 1 1 0 3 1 0 0 0 0

由于这个方阵太大了，很多人都不敢一试。这时候，楠楠拿出他的随身笔记本，编了一个程序，瞬间就秒杀了它！

如果是你，你能解决吗？

输入格式：

输入数据有若干行。第一行，有三个整数 N、M（1<=N、M<=1000）和 K（1<=K<=N），其中 N、M 分别表示这个数字方阵中行数和列数。K 表示求数字方阵第 K 行的最长数字串长度。接下来有 N 行，每行 M 个 0～9 的数字，每个数字间用一个空格隔开。

输出格式：

输出第 K 行的最长非零串的长度。

输入样例：

4 8 3 9 2 0 0 3 4 2 5 0 4 0 2 3 0 3 2 3 1 3 8 3 2 9 0 7 5 1 1 0 3 1 0 0 6 6 0

输出样例：

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

// 第四题 数字方阵(matrix)
int matrix(int n, int m, int k, vector<vector<int>> nums){
    int maxLen = 0;
    for(int j=0; j<m; j++){
        int len = 0;
        for(int i=0; i<n; i++){
            if(nums[i][j] != 0){
                len++;
            }
            else{
                len = 0;
            }
            if(i+1 == k && len > maxLen){
                maxLen = len;
            }
        }
    }
    return maxLen;
}

int main(){
    // 第四题 数字方阵(matrix)
    int n4, m4, k;
    cin >> n4 >> m4 >> k;
    vector<vector<int>> nums4(n4, vector<int>(m4));
    for(int i=0; i<n4; i++){
        for(int j=0; j<m4; j++){
            cin >> nums4[i][j];
        }
    }
    int res4 = matrix(n4, m4, k, nums4);
    cout << res4 << endl;

    return 0;
}

第五题单纯质因数(pprim)

问题描述

读五年级的楠楠刚学完了质数、合数、因数、质因数等概念。他还知道了每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，叫做这个合数的质因数．把一个合数用质因数相乘的形式表示出来，叫做分解质因数．

聪明爱动脑筋的楠楠突然对具有互不相同的质因数的合数产生了兴趣。例如： 30=235，它有互不相同的质因数；70=257，它也有互不相同的质因数。若一个合数中所有的质因数互不相同，则把它称之为具有单纯质因数的合数。他想知道还有哪些数是单纯质因数的合数。

你现在要帮楠楠解决的问题是：已知 N,依次输出 N 以内所有具有单纯质因数的合数。

输入格式：

输入数据只一个整数 N（10<=N<=100000）。

输出格式：

依次输出 N 以内所有具有单纯质因数的合数。

输入样例：

输出样例：

6 10

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

// 第五题 单纯质因数(pprim)
bool isPrime(int n){
    if(n <= 1){
        return false;
    }
    for(int i=2; i<=sqrt(n); i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

void pprim(int n){
    for(int i=4; i<=n; i++){
        bool flag = true;
        for(int j=2; j<=sqrt(i); j++){
            if(i % j == 0){
                if(isPrime(j)){
                    flag = false;
                    break;
                }
            }
        }
        if(flag){
            cout << i << ' ';
        }
    }
}

int main(){
    // 第五题 单纯质因数(pprim)
    int n5;
    cin >> n5;
    pprim(n5);

    return 0;
}

希望这些代码和解释能够帮助你更好地理解和学习算法知识。如果你有任何问题，请随时提出！