比赛入门练习题
题目1
- 描述
把前n个数字排列在一起，统计一下0～9各出现多少次？ 编写C++程序 - 输入
整数n - 输出
0～9 各出现次数
#include <iostream>
#include <vector>
int main() {
int n;
std::cout << "请输入数字n: ";
std::cin >> n;
// 创建一个数组来存储0到9各数字的出现次数，初始化为0
int count[10] = {0};
// 将前n个数字排列在一起
for (int i = 1; i <= n; i++) {
int num = i;
while (num > 0) {
// 获取最后一位数字
int digit = num % 10;
// 增加相应数字的计数
count[digit]++;
// 去掉最后一位数字
num /= 10;
}
}
// 输出统计结果
std::cout << "0~9各数字出现的次数为：" << std::endl;
for (int i = 0; i < 10; i++) {
std::cout << i << ": " << count[i] << std::endl;
}
return 0;
}
题目2
- 描述
周期串，如果一个字符串可以由某个长度为k的字符串多次重复得到，则称该串以k为周期，输入一个长度不超过80的字符串，输出其最小周期，编写C++程序 - 输入
长度不超过80的字符串 - 输出
最小周期，一个整数，或者不存在
#include <iostream>
#include <string>
int findSmallestPeriod(const std::string& input) {
int n = input.length();
for (int k = 1; k <= n; k++) {
if (n % k == 0) {
bool isPeriod = true;
for (int i = k; i < n; i++) {
if (input[i] != input[i % k]) {
isPeriod = false;
break;
}
}
if (isPeriod) {
return k;
}
}
}
return n; // 如果没有找到周期，则返回字符串长度
}
int main() {
std::string input;
std::cout << "请输入一个字符串（长度不超过80）: ";
std::cin >> input;
int smallestPeriod = findSmallestPeriod(input);
std::cout << "最小周期为: " << smallestPeriod << std::endl;
return 0;
}解释说明
当我们说一个字符串具有周期性时，意味着该字符串可以由一个较短的子串重复多次组成。例如，字符串 "abcabcabc" 具有周期性，其周期为 "abc"，因为它可以重复三次来构建整个字符串。
这个C++程序的目标是找到给定字符串的最小周期。最小周期是能够将字符串重复多次以构建原始字符串的最短子串长度。下面我将逐步解释程序和算法的工作原理：
- 用户被要求输入一个字符串，该字符串的长度不超过80个字符。
- findSmallestPeriod 函数是用于查找最小周期的核心部分。它接受一个字符串作为参数，并返回最小周期的长度。
- 在 findSmallestPeriod 函数中，我们首先获取输入字符串的长度并将其存储在变量 n 中。
- 接下来，我们使用一个循环来尝试不同的周期长度 k，从1到字符串的长度 n。对于每个 k 值，我们检查是否可以通过重复长度为 k 的子串来构建原始字符串。
- 在循环中，我们首先检查 n 是否可以被 k 整除，因为只有在整除的情况下才可能存在周期性。
- 如果 n 可以被 k 整除，那么我们进一步检查是否可以通过重复 k 长度的子串来构建原始字符串。我们使用一个嵌套循环遍历字符串的每个字符，检查是否与其对应的周期位置上的字符相同。
- 如果所有的字符都匹配，那么我们就找到了一个周期，我们返回 k 作为最小周期的长度。
- 如果没有找到周期，我们继续尝试下一个 k 值，直到遍历所有可能的周期长度。
- 如果在整个循环中都没有找到周期，那么我们默认将字符串的长度 n 作为最小周期长度。
- 最后，程序输出找到的最小周期长度。
这个算法的时间复杂度是比较高的，因为它需要尝试多个周期长度。但是，对于较短的字符串，它仍然是一个合理的方法。如果字符串很长，可能需要考虑更高效的算法。这个程序提供了一个基本的示例，演示了如何找到字符串的最小周期。
时间复杂度：当我们谈论一个算法的时间复杂度时，实际上是在讨论这个算法需要多长时间来完成任务。可以将时间复杂度想象成一个度量标准，用来衡量不同算法在处理相同问题时，谁更快或更慢。
想象一下你和你的朋友在做同样的数学题，但你们使用了不同的方法。时间复杂度就像是一种方式，帮助你们比较谁的方法更快。
时间复杂度告诉我们，当输入的数据规模增加时，算法执行所需的时间会如何增加。一个具有较低时间复杂度的算法通常会更快，因为它可以在更短的时间内处理更多的数据。
举个例子，假设你和你的朋友都要计算从1加到100的和。你选择了直接相加的方法，而你的朋友选择了使用一个数学公式（如等差数列求和公式）。尽管两种方法都可以得到正确的答案，但使用公式的方法更快，因此它的时间复杂度更低。
所以，时间复杂度就是一种衡量算法执行速度的方式，它帮助我们选择最合适的算法来解决问题，特别是在处理大量数据时，能够帮助我们选择更高效的方法。
