院校机试刷题第二天：1479 01字符串、1701非素数个数

一、1479 01字符串

1.题目描述

2.解题思路

方法一：暴力法

模拟过程，列出几个数据来a[1]=1, a[2]=2, a[3]=3, a[4]=5以此类推，这就是斐波那契数列，每一项都等于前两项之和，确定好a[1], a[2]即可。

方法二：动态规划法

首先，我们考虑基本情况：

• 当 n=1 时，只有一个0，无法进行压缩，所以 f(1)=1。

• 当 n=2 时，可以压缩成1，或者保持00，所以 f(2)=2。

对于 n≥3，我们可以考虑两种情况：

1. 第一个0不与第二个0压缩，那么剩下的 n−1 个0可以有 f(n−1) 种组合。

2. 第一个0与第二个0压缩成1，那么剩下的 n−2 个0可以有 f(n−2) 种组合。

因此，我们可以得到递推关系： f(n)=f(n−1)+f(n−2)

3.代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[10005];
    a[1] = 1;
    a[2] = 2;
    for(int i = 3; i <= n; i++) {
        a[i] = (a[i - 1] + a[i - 2]) % 2333333;
    }

    cout << a[n];

    return 0;
}

二、1701非素数个数

1.题目描述

2.解题思路

模拟题，没有涉及到任何算法，关键在于如何判断素数。

要判断一个数 n 是否为素数，可以尝试用从2到 根号n​ 的所有整数去除 n。如果 n 能被这些数中的任何一个整除，那么 n 就不是素数；否则， n 是素数。

常见的素数判断函数isPrime

bool isPrime(int n) {
    // 小于2的数不是素数
    if (n < 2) {
        return false;
    }
    
    // 检查从2到sqrt(n)的整数是否能整除n
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false; // 如果能整除，n不是素数
        }
    }
    
    return true; // 如果不能被任何数整除，n是素数
}

这里将1看作非素数，有的题目中1是素数，看不同题目的定义。

3.代码

直接版

#include <iostream>
using namespace std;

bool isPrime(int a) {
    if(a == 1) {
        return true;
    }
    for(int j = 2; j * j <= a; j++) {
        if(a % j == 0) return false;
    }
    return true;
}

int number(int a, int b) {
    int result = 0;
    for(int i = a; i <= b; i++) {
        if(!isPrime(i)) result++;
    }
    return result;
}

int main() {
    int a, b;
    while(cin >> a >> b) {
        int count1 = number(a, b);
        cout << count1 << endl;
    }
    return 0;
}

省时间版：有的题目有时间限制，用上面的代码会超时。

本质和上面是相同的，但是这里用一个数组存起来该数字是否是素数，避免之后重复求，省时间

#include <iostream>
using namespace std;

int A[10000005];

bool isPrime(int a) {
    if(a == 1) {
        return true;
    }
    for(int j = 2; j * j <= a; j++) {
        if(a % j == 0) return false;
    }
    return true;
}

void getA(){
    for(int i = 0; i <= 10000005; i++) {
        if(isPrime(i)){
            A[i] = 1; // 是素数标记为1
        }
        else {
            A[i] = 0;
        }
    }
}

int number(int a, int b) {
    int result = 0;
    for(int i = a; i <= b; i++) {
        if(A[i] == 0) result++;
    }
    return result;
}

int main() {
    getA();

    int a, b;
    while(cin >> a >> b) {
        int count1 = number(a, b);
        cout << count1 << endl;
    }
    return 0;
}

OS：N诺的编译器真的不行，看数据要钱，提交总是过不了