院校机试刷题第二天：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)的整数是否能整除nfor (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诺的编译器真的不行，看数据要钱，提交总是过不了