【35天从0开始备战蓝桥杯 -- Day5】

🫧个人主页：小年糕是糕手

💫个人专栏：《C++》《Linux》《数据结构》《C语言》

🎨你不能左右天气，但你可以改变心情；你不能改变过去，但你可以决定未来！

目录

一、输入输出

1.1、单组测试用例

1°计算 (a+b)/c 的值

2°与 7 无关的数

1.2、多组测试用例

情况一

1°多组输入a+b II

2°斐波那契数列

3°制糊串

情况二

1°多组输入a+b

2°数字三角形

3°定位查找

情况三

1°字符统计

拓展函数

2°多组数据a+b III

1.3、输入时的特殊技巧

1°含空格字符串的输入技巧 -- 统计数字字符个数

2°数字的特殊处理方式 -- 小乐乐改数字

1.4、scanf / printf与cin / cout的对比

1°格式控制差异

2°性能差异

数字游戏

求第 k 小的数

3°优化方案

二、函数

2.1、概述

1°普通参数

2°数组

3°字符串

4°全局变量

2.2、返回值

2.3、声明和定义

2.4、函数调用

1°传值调用

2°引用

3°效率比较

2.5、函数重载

练习

1°最大数 max(x,y,z)

拓展函数

max

min

2°求正整数 2 和 n 之间的完全数

3°素数个数

4°素数对

5°素数回文数的个数

6°区间内的真素数

三、递归

3.1、概述

3.2、典型案例解析

1°计算阶乘

迭代

递归

2°斐波那契数列

迭代

递归

练习

一、输入输出

前面我们学过了很多种输入输出，cin / cout、scanf / printf、getline、fgets等等，但是实际上的oj编程题中情况一般都是比较常见的几种，下面为大家做个小结并结合一些习题帮助大家更好理解

1.1、单组测试用例

**1°**计算 (a+b)/c 的值

计算 (a+b)/c 的值

1#include<iostream>
2using namespace std;
3int main()
4{
5    int a,b,c;
6    cin>>a>>b>>c;
7    int ret=(a+b)/c;
8    cout<<ret<<endl;
9    return 0;
10}

2°与 7 无关的数

与 7 无关的数

1#include<iostream>
2#include<cmath>
3using namespace std;
4int main()
5{
6	int n;
7	cin >> n;
8	int sum = 0;
9	int i = 1;
10	while (i <= n)
11	{
12		//判断i是否是和7无关
13		if ((i % 7 != 0) && (i % 10 != 7) && (i / 10 != 7))
14		{
15			sum += i * i;
16		}
17		i++;
18	}
19	cout << sum << endl;
20	return 0;
21}

相信通过前面的学习这两题的代码大家已经是信手拈来了，也没啥好解释的这两道题，只是让大家体会一下什么是单组测试用例，我们重点来看下面的内容：

1.2、多组测试用例

情况一

这部分我们来看测试数据组数已知的情况

1°多组输入a+b II

多组输入a+b II

1#include<iostream>
2using namespace std;
3int main()
4{
5    int n;
6    cin >> n;
7    int a, b;
8    int ret;
9    while (n--)
10    {
11        ret = 0;
12        cin >> a >> b;
13        ret = a + b;
14        cout << ret << endl;
15    }
16    return 0;
17}

2°斐波那契数列

斐波那契数列

这里我们提供两种思路，其实还有一种递归的思路，下面章节我们会学习，这里留个悬念，思路一我们是循环读取多组输入的数字a，对每个a用迭代法计算第a个斐波那契数并输出。

1#include<iostream>
2using namespace std;
3int main()
4{
5    int n;
6    cin>>n;
7    int a;
8    while(n--)//n次访问
9    {
10        cin>>a;
11        //计算第n个斐波那契数
12        int x = 1;
13        int y = 1;
14        int z = 1;
15        while (a > 2)
16        {
17        	z = x + y;
18        	x = y;
19        	y = z;
20        	a--;
21        }
22        cout << z << endl;
23    }
24   return 0; 
25}

思路二我们采用计算好前30个斐波那契数，存储到ret数组中，需要第几个就从下标几的位置去取

1#include <iostream>
2using namespace std;
3int main()
4{
5	int n = 0;
6	int a = 0;
7	int i = 0;
8	//计算好前30个斐波那契数，存储到ret数组中 
9	//需要第⼏个就从下标⼏的位置去取 
10	int ret[40] = { 0, 1, 1 };
11	for (i = 3; i < 30; i++)
12	{
13		ret[i] = ret[i - 1] + ret[i - 2];
14	}
15	cin >> n;
16	int z = 0;
17	while (n--)
18	{
19		cin >> a;
20		cout << ret[a] << endl;
21	}
22	return 0;
23}

**3°**制糊串

制糊串

1#include<iostream>
2#include<string>
3using namespace std;
4int main()
5{
6	string s, t;
7	cin >> s >> t;
8	string s1, t1;
9	int q, l1, r1, l2, r2;
10	cin >> q;
11	while (q--)
12	{
13		cin >> l1 >> r1 >> l2 >> r2;
14		s1 = s.substr(l1 - 1, r1 - l1 + 1);
15		t1 = t.substr(l2 - 1, r2 - l2 + 1);
16		//比较
17		if (s1 < t1)
18			cout << "yifusuyi" << endl;
19		else if (s1 > t1)
20			cout << "erfusuer" << endl;
21		else
22			cout << "ovo" << endl;
23	}
24	return 0;
25}

编程小技巧：

题目中说 “有 q 次询问”，意思是程序要处理 q 组测试数据，（也就是对应 q 次循环），我们要针对每次询问，给出一个结果。

其实就是之前的单组测试变成了 q 组测试，在之前的代码上套一层 while 循环即可。当有 q 次询问的时候，while (q--) 是非常方便的方式。然后就按照单组输入的方式处理每组输入的数据就好了

情况二

这部分我们来看测试数据组数未知的情况

1°多组输入a+b

多组输入a+b

1#include<iostream>
2using namespace std;
3int main()
4{
5    int a,b;
6    while(cin >> a >> b)
7    {
8        cout << a + b <<endl;
9    }
10    return 0;
11}

cin >> a; 会返回一个流对象的引用，即 cin 本身。在 C++ 中，流对象 cin 可以被用作布尔值来检查流的状态。如果流的状态良好（即没有发生错误），流对象的布尔值为 true。如果发生错误（如遇到输入结束符或类型不匹配），布尔值为 false。

---

在 while (cin >> a >> b) 语句中，循环的条件部分检查 cin 流的状态。如果流成功读取到 2 个值，cin >> a >> b 返回的流对象 cin 将被转换为 true，循环将继续。如果读取失败（例如遇到输入结束符或无法读取到 2 个值），cin >> a >> b 返回的流对象 cin 将被转换为 false，循环将停止。

2°数字三角形

数字三角形

1#include<iostream>
2using namespace std;
3int main()
4{
5    int n;
6    while(cin >> n)
7    {
8        for(int i = 1;i <= n;i++)
9        {
10            for(int j = 1;j <= i;j++)
11            {
12                cout << j << ' ';
13            }
14            cout<<endl;
15        }
16        
17    }
18    return 0;
19}

这个题目其实很类似我们前面写过的，判断质数，乘法口诀表这类

3°定位查找

定位查找

这里为大家展示两种最常见的写法：

1#include<iostream>
2#include<cstring>
3using namespace std;
4int main()
5{
6    int n;
7    int arr[20] = {0};
8    while(cin >> n)
9    {
10        for(int i = 0;i < n;i++)
11        {
12            cin >> arr[i];
13        }
14        int m;
15        cin >> m;
16          
17        int pos = -1; // 标记位置
18        for(int j = 0; j < n; j++) // 从0开始遍历
19        {
20            if(arr[j] == m)
21            {
22                pos = j;
23                break; // 第一次出现就停止
24            }
25        }
26        
27        if(pos != -1)
28            cout << pos << endl;
29        else
30            cout << "No" << endl;
31        
32        memset(arr, 0, sizeof(arr));
33    }
34    return 0;
35}

我们来解释这第一段代码：我们定义了一个整型n，代表n组数据，然后定义了一个数组暂且全部初始化为0，下面我们进入while循环，定义了一个for循环来给这个数组赋值，下面定义并且输入一个m作为我们的要查找的值，下面定义了一个pos用来标记位置，然后我们遍历数组并且与m进行比较，如果找到了就跳出循环并且给pos位置赋值标记下标，如果没找到pos还是一开始的值，我们打印no即可，最后使用我们之前学过的memset给数组置为0即可

这个思路很简单，但是其实代码的水平不是很高，有点冗余，下面给出优化之后的解法：

1#include <iostream>
2using namespace std;
3const int N = 25;
4int arr[N];
5int main()
6{
7	int n = 0;
8	int m = 0;
9	while (cin >> n)
10	{
11		//输入n个数字，存放在arr中
12		for (int i = 0; i < n; i++)
13		{
14			cin >> arr[i];
15		}
16		//输入m
17		cin >> m;
18		int i = 0;
19		//在arr数组中查找m
20		for (i = 0; i < n; i++)
21		{
22		if (m == arr[i])
23		{
24			cout << i << endl;
25			break;
26		}
27	}
28	if (i == n)
29		cout << "No" << endl;
30}
31	return 0;
32}

这里我们舍弃了memset，因为这里其实根本不需要去清空数组，上一次的结果会被我们下一次直接覆盖，我们查找的范围也是根据元素个数来的，所以根本不需要重置数组。

情况三

这部分我们来看特殊值结束测试数据的情况

1°字符统计

字符统计

这题我们依旧有两种思路，我们可以逐个字符的读取，然后统计，这里可以使用getchar()，我们也可以一次性读取整个字符串然后统计

1#include<iostream>
2using namespace std;
3int Letters, Digits, Others;
4int main()
5{
6    int ch = 0;
7    while ((ch = getchar()) != '?')
8    {
9        if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z'))
10            Letters++;
11        else if (ch >= '0' && ch <= '9')
12            Digits++;
13        else
14            Others++;
15    }
16    cout << "Letters=" << Letters << endl;
17    cout << "Digits=" << Digits << endl;
18    cout << "Others=" << Others << endl;
19    return 0;
20}

这里将那几个参数定义为全局变量是因为：全局变量 / 静态变量 → 系统自动帮你赋值为 0

拓展函数

下面为大家介绍几个函数帮助大家简化代码：

1//头文件
2#include <cctype>

返回值规则 完全一模一样

所有这 5 个函数的返回值规则：

• 如果【是】 → 返回一个 非 0 的整数（真）
• 如果【不是】 → 返回 0（假）

下面我们对代码进行优化：

1#include<iostream>
2#include<cctype>
3using namespace std;
4int Letters, Digits, Others;
5int main()
6{
7    int ch = 0;
8    while ((ch = getchar()) != '?')
9    {
10        if ((islower(ch)) || (isupper(ch)))
11            Letters++;
12        else if (isdigit(ch))
13            Digits++;
14        else
15            Others++;
16    }
17    cout << "Letters=" << Letters << endl;
18    cout << "Digits=" << Digits << endl;
19    cout << "Others=" << Others << endl;
20    return 0;
21}

1#include<iostream>
2#include<cctype>
3using namespace std;
4int Letters, Digits, Others;
5int main()
6{
7    int ch = 0;
8    while ((ch = getchar()) != '?')
9    {
10        if (isalpha(ch))
11            Letters++;
12        else if (isdigit(ch))
13            Digits++;
14        else
15            Others++;
16    }
17    cout << "Letters=" << Letters << endl;
18    cout << "Digits=" << Digits << endl;
19    cout << "Others=" << Others << endl;
20    return 0;
21}

下面我们来看方法二：

1#include<iostream>
2#include<string>
3using namespace std;
4int Letters, Digits, Others;
5int main()
6{
7	string s;
8	getline(cin, s, '?');
9	for (auto e : s)
10	{
11		if (isalpha(e))
12			Letters++;
13		else if (isdigit(e))
14			Digits++;
15		else
16			Others++;
17	}
18	cout << "Letters=" << Letters << endl;
19    cout << "Digits=" << Digits << endl;
20    cout << "Others=" << Others << endl;
21	return 0;
22}

这里需要注意我们之前介绍过的getline的第二种用法，其实还有一种方法就是使用getline的第一种写法，然后写个pop_back，也可以满足需求

2°多组数据a+b III

多组数据a+b III

1#include<iostream>
2using namespace std;
3int main()
4{
5    int a, b;
6    while (cin >> a >> b)
7    {
8        if (a == 0 && b == 0)
9            break;
10        cout << a + b << endl;
11    }
12    return 0;
13}

这里其实还有一种写法，利用到了逗号表达式：逗号隔开的一串表达式的特点：从左向右依次计算，整个表达式的结果是最后一个表达式的结果

1#include<iostream>
2using namespace std;
3int main()
4{
5    int a, b;
6    while (cin >> a >> b, a || b)
7    {
8        cout << a + b << endl;
9    }
10    return 0;
11}

1.3、输入时的特殊技巧

根据我们现在掌握的知识，含空格的字符串，如要读取有 fgets、scanf、getchar、getline 四种方式解决，但是有时候，根据题目的情况，不一定非要完整的读取这个带空格的字符串，而是将字符串中空格隔开的每一个字符串，当做一个单词处理更方便，也避免了读取带空格字符串的各种问题。

1°含空格字符串的输入技巧 -- 统计数字字符个数

统计数字字符个数

这个题目其实与字符统计那个题目非常类似，我们依旧可以采取整个字符串一次性读取，然后处理字符串，也可以采取逐个单词的方式处理，下面给出两种方案的代码：

1#include<iostream>
2#include<string>
3using namespace std;
4int main()
5{
6    string s;
7    getline(cin, s);
8    int count = 0;
9    for (auto e : s)
10    {
11        if (isdigit(e))
12            count++;
13    }
14    cout << count << endl;
15    return 0;
16}

1#include<iostream>
2#include<string>
3using namespace std;
4int main()
5{
6    string s;
7    int count = 0;
8    while (cin >> s)
9    {
10        for (auto e : s)
11        {
12            if (isdigit(e))
13                count++;
14        }
15    }
16    cout << count << endl;
17    return 0;
18}

2°数字的特殊处理方式 -- 小乐乐改数字

小乐乐改数字

1#include<iostream>
2#include<cmath>
3#include<string>
4using namespace std;
5
6int main() {
7    int n;
8    cin >> n;
9    int i = 0; //标记⼀下此时处理到多少位
10    int ret = 0;
11    while (n) {
12        if (n % 10 % 2) //如果这⼀位是奇数
13            ret += 1 * pow(10, i);
14        else
15            ret += 0 * pow(10, i);
16        n /= 10; //把最后⼀位干掉
17        i++;
18    }
19    cout << ret << endl;
20    return 0;
21}

其实我们还有一种思路就是将输入的内容当做字符串处理：

1#include<iostream>
2#include<cmath>
3#include<string>
4using namespace std;
5
6int main() {
7    string s;
8    cin >> s;
9    for (int i = 0; i < s.size();i++)
10    { // 数字字符与对应的数的奇偶⼀致
11        if (s[i] % 2) 
12        {
13            s[i] = '1';
14        } 
15        else 
16        {
17            s[i] = '0';
18        }
19    }
20    cout << stoi(s) << endl; // 转换成数字输出
21    return 0;
22}

1.4、scanf / printf与cin / cout的对比

1°格式控制差异

• scanf 和 printf 不能自动识别输入数据的类型，需要手动指定格式字符串，容易出现格式错误。开发者需要确保格式字符串与变量类型匹配，否则会导致未定义行为。
• cin 和 cout 会根据变量类型自动处理输入输出，避免格式化错误。相对 scanf 和 printf 而且，C++ 的 cin 和 cout 更加易用。
• scanf 和 printf：格式化输出更精确直观，特别适合复杂格式的输入输出，比如：在要求指定格式输出的时候，printf 函数就比 cout 更加方便和灵活。

---

区别

1. cout 默认不会输出六位小数，自动忽略小数点后多余的 0，printf 函数打印浮点数的时候，小数点默认打印 6 位。
2. cout 在输出的时候不需要指定格式，printf 则需要明确的格式。

2°性能差异

结论：scanf 和 printf 通常比 cin 和 cout 快。

---

原因：cin 和 cout 由于要考虑兼容 C 语言的输入和输出，封装实现的更加复杂，通常比 scanf 和 printf 稍慢，但这种差异在大多数应用场景中可以忽略不计。

但是在竞赛的题目中，尤其是当输入、输出数据量较大时，使用 cin 和 cout 完成输入输出，经常会出现 Time Limit Exceeded 的情况。而 scanf 和 printf 就不存在类似的问题。下面给大家准备了两个案例。

数字游戏

数字游戏

我们从这个题目的输入描述应该就不难看出这个题目的数据量是非常大的，题目也提示我们请选择较快的读入方式，下面给出两种输入方式所展现的代码，大家不用看懂代码只需要去对比一下性能差异即可：

1#include <iostream>
2using namespace std;
3int t, x;
4int main()
5{
6	cin >> t;
7	while (t--)
8	{
9		cin >> x;
10		int ret = 0;
11		while (x)
12		{
13			int count = 0, high = 0;
14			int tmp = x;
15			while (tmp)
16			{
17				//计算最右边的1代表的值
18				int low = tmp & -tmp;
19				//如果low中剩余的1就是最后⼀个1就是最左边的1 
20				if (tmp == low)
21				{
22					high = low;
23				}
24				//去掉最右边的1 
25				tmp -= low;
26				count++;
27			}
28			if (count % 2 == 0)
29			{
30				x -= high;
31			}
32			else
33			{
34				x ^= 1;
35			}
36			ret++;
37		}
38		cout << ret << endl;
39	}
40	return 0;
41}
42

1#include <iostream>
2using namespace std;
3int t, x;
4int main()
5{
6	scanf("%d", &t);
7	while (t--)
8	{
9		scanf("%d", &x);
10		int ret = 0;
11		while (x)
12		{
13			int count = 0, high = 0;
14			int tmp = x;
15			while (tmp)
16			{
17				//计算最右边的1代表的值
18				int low = tmp & -tmp;
19				//如果low中剩余的1就是最后⼀个1就是最左边的1 
20				if (tmp == low)
21				{
22					high = low;
23				}
24				//去掉最右边的1 
25				tmp -= low;
26				count++;
27			}
28			if (count % 2 == 0)
29			{
30				x -= high;
31			}
32			else
33			{
34				x ^= 1;
35			}
36			ret++;
37		}
38		printf("%d\n", ret);
39	}
40	return 0;
41}
42