[C++知识库]程设思维实践-实验E1

本次实验线上进行，推荐大家使用 CSP(ubuntu) 环境进行实验（Windows 也可以进行实验）。

A : 签到题【请在实验开始5分钟内完成签到】

???????请在比赛开始 5分钟 以内提交以下代码进行签到。

#include <cstdio>
int main(){puts("qiandao");}

B : Slot

???????给出一个长度为3的字符串，所有字母均为大写英文字母，请判断该字符串是否由同一个字母构成。

输入格式

???????输入一行表示字符串。

输出格式

???????若该字符串是否由同一个字母构成，输出Won，否则输出Lost。

样例输入

TTT

样例输出

Won

思路

???????说实话我这道题做的有一段时间（很多大佬都四十分钟把这些都在做完了，我不能比，我需要一步一步来，因为我基础很薄弱。）
???????判断是否为同一个字母，直接判断他们所对应的ASCII码是否一样即可（虽然有的IDE可以自动进行数据类型转化）。那么如何遍历得到每一个位置的字符呢？
???????我这里采用string的方式。因为string可以当成数组来使用，而且拥有 length() 函数方便我们遍历。同时，一定要注意，我遍历的方式中出现了 input[i + 1]，这意味着什么？对于i而言，在循环条件下可以取得 string 或者说是字符数组的最后一位，即i取得 input.length() - 1，那么现在 i + 1 = input.length()，数组越界。
???????因此在循环内添加 if(input[i+1] != ‘\0’) 的判定条件，进行对数组越界情况的排除。

代码

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

int main(){
	string input;
	cin >> input;
	char tmp = input[0];
	for(int i = 0; i < input.length(); i++){
		if(input[i+1] != '\0'){
			if(tmp == input[i+1]){
		}
		else{
			printf("Lost\n");
			return 0;
		}
		i++;
		}
		else{
			break;
		}
	} 
	printf("Won\n");
	return 0;
} 

C : Discount

???????给出商品的原价和现价，求该商品的优惠力度

输入格式

???????输入两个数A，B(1 ≤ B < A ≤ $10^5$) 分别表示原价和现价。

输出格式

???????输出一个实数，表示降价的百分比，保留三位小数输出。

样例输入

7 5

样例输出

28.571

思路

???????这道题仅仅需要注意给的样例之中，答案是28.571，这显然是百分比乘以了100。还有就是保留小数的方法：
???????1.引用#include<iomanip>，然后cout << setprecision(3) << fixed << variable << endl;（讲variable改为需要输出的变量）;
???????2.使用%的方法：
???????比如 : %2f是把float的所有位数输出2位，包括小数点，如果不足2位，补0，如果超过2位，按照实际输出；%.2f是float后的小数只输出两位。

代码

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

int main(){
	float A, B;
	cin >> A >> B;
	float downper = (A - B) / A * 100;
	cout << setprecision(3) << fixed << downper << endl;
	return 0;
}

D : Orthogonality

???????给出两个 N 维向量，判断他们的内积是否等于0。

输入格式

???????第一行一个整数N，接下来两行分别有N个整数，分别表示向量 A, B
1 ≤ N ≤ $10^5$, -100 ≤ $A_i$, $B_i$ ≤ 100

输出格式

???????若两个向量的内积等于0，输出Yes，否则输出No。

样例输入

3
1 0 5
-5 0 1

样例输出

Yes

思路

???????这里直接开了定长数组进行存储。虽然特别特别占空间

代码

#include<iostream>
using namespace std;

int main(){
	int num, sum = 0;
	int a[1000005], b[1000005];
	cin >> num;
	for(int i = 0; i < num; i++){
		cin >> a[i];
	}
	for(int i = 0; i < num; i++){
		cin >> b[i];
	}
	for(int i = 0; i < num; i++){
		sum = sum + a[i] * b[i];
	}
	if(sum == 0)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

E : uNrEaDaBlE sTrInG

???????我们称一个字符串是“难读的”，当且仅当它的奇数位置的字母都是小写字母，偶数位置的字母都是大写字母。请你判断一个字符串是否为“难读的”字符串。

输入格式

???????输入一行包含一个字符串。

输出格式

???????如果输入的字符串是“难读的”，输出Yes，否则输出No。

输入样例

tImElImItExCeEdEd

输出样例

Yes

思路

???????使用 while 循环，在这里需要判断“下一个”是奇数还是偶数，是不是很熟悉？正如我们在B题中犯的错，我这里采用了另外一种方式：使用两个变量 i和j 来进行遍历（有一种后续我们将要说到的双指针的感觉）。判定奇数偶数，使用 j 。判定 words 数组是否越界，使用指向当前元素的 i （常数指针）。

代码

#include<iostream>
#include<string>

using namespace std;
int main(){
	string words;
	int i = 0;
	int j = 1;
	cin >> words;
	while(words[i] != '\0'){
		if(j % 2 == 0){
			if(int(words[i]) >= 65 && int(words[i]) <= 90){
			}
			else{
				printf("No\n");
				return 0;
			}
		}
		if(j % 2 == 1){
			if(int(words[i]) >= 97 && int(words[i]) <= 122){ 
			}
			else{
				printf("No\n");
				return 0;
			}
		}
		j++;
		i++;
	}
	printf("Yes\n");
	return 0;
}

F : Remove It

???????给出一个长度为n的数列和一个数x，请从数列中删除数值等于x的项，输出剩余的数列。

输入格式

???????输入第一行包含两个整数n,x，第二行包含n个整数，表示数列。

输出格式

???????输出一行，表示删除后的数列。输出数字的相对顺序应与原数列相同。

输入样例

6 4
1 2 3 4 3 4

输出样例

1 2 3 3

思路

???????碰到一样的不输出即可。

代码

#include<iostream>
using namespace std;
int main(){
	int a[100005];
	int n, x;
	cin >> n >> x;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	for(int i = 0; i < n; i++){
		if(a[i] == x){
		}
		else{
			printf("%d ",a[i]);
		}
	}
	return 0;
}

G : Rally

???????有$n$个人居住在数轴的整数位置上，第$i$个人的位置是$x_i$。现需要选定一个整数位置$p$，使所有人移动到$p$使得所有人的代价之和最小，第$i$个人移动的代价为$(x_i?p{)}^2$，求最小代价。

输入格式

???????第一行一个整数$n$，接下来一行有$n$个整数，表示每个人的位置。
???????$1\le n\le 100$，$1\le x_i\le 100$

输出格式

???????输出一个整数，表示最小代价。

输入样例

6
5 2 4 2 8 8

输出样例

37

思路1

???????这道题因为数据范围较小，我直接采用了：对于$p$而言，只有从 1 到 100 一百个数字，完全可以遍历。见代码1。
???????同时可以看到我的代码中存在 smaller和bigger 的变量，我是想通过求得最大最小值，来缩小遍历范围来缩短时间。
???????这里需要注意的是，我代码中之前没有if(tmp == 0)这一部分，这意味着，这种情况下我没有考虑到最终值为0的情况。当时我百思不得其解，最终我选择了编写如下程序来试错：

#include<iostream>
using namespace std;
int main(){
	printf("0\n");
}

???????结果不出意料，只有我第一次错的那个值是正确的。最终发现错误并修正。

思路2

???????这道题还有一个巧妙的方法，直接求其均值，然后求代价即可。（这里感谢一下李同学）
???????见代码2。

代码1

#include<iostream>
using namespace std;
int main(){
	int a[105] = { 0 };
	int n = 0;
	int res = 0, tmp = 0;
	//int bigger, smaller;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		/*if(bigger < a[i])
			bigger = a[i];
		if(smaller == 0){
			smaller = a[i];
		}
		else{
			if(smaller > a[i])
				smaller = a[i];
		}*/
	}
	//printf("smaller = %d\n",smaller);
	//printf("bigger = %d\n",bigger);
	for(int i = 1; i <= 100; i++){
	//for(int i = smaller; i <= bigger; i++){
		for(int j = 0; j < n; j++){
			tmp = tmp + (a[j] - i) * (a[j] - i);
			//printf("sum1 = %d\n",tmp); 
		}
		if(res == 0 && tmp != 0){
			res = tmp;
		}
		else{
			if(res > tmp)
				res = tmp;
		}
		if(tmp == 0){
			printf("0\n");
			return 0;
		}
		tmp = 0;
	}
	printf("%d\n",res);
	return 0;
}

代码2

#include<bitsdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	int a[n];
	double sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	int p = round(sum/n);
	int f = 0;
	for (int i = 0; i < n; i++) {
		f += (a[i]-p)*(a[i]-p);
	}
	cout << f << endl;
  	return 0;
}

H : : (Colon)

???????钟表的时针和分针长度分别为a,b，当前的时间为H时M分，求时针端点与分针端点的距离。

输入格式

???????输入一行包含4个整数a,b,H,M

输出格式

???????输出一个实数，表示端点之间的距离。你的输出与实际值的误差应小于$10^{?9}$。

输入样例

3 4 10 40

输出样例

4.56425719433005567605

思路

???????这里采用 %.12lf 的方式进行最终的格式变化。这里一定要注意分针对时针也是存在影响的。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
   double a, b, h, m;
   cin >> a >> b >> h >> m;
   double ans = a * a + b * b - 2 * a * b * cos(2 * M_PI * ((h + m/60)/12 - m/60));
   printf("%.12lf\n",sqrt(ans));
   return 0;
}

I : Kaprekar Number

???????定义函数$f(x)$ $g_1(x)$ $g_2(x)$如下：
$f(x)$：$g_1(x)?g_2(x)$
$g_1(x)$：将$x$的各位数字按照降序排序
$g_2(x)$：将$x$的各位数字按照升序排序，忽略前导零
???????给出整数$N,K$,定义数列$a_0=N,a_{i+1}=f(a_i)(i\ge 0)$，求$a_k$

输入格式

???????输入一行包含两个整数，包含$N,K$,$N\le 10^9,K\le 10^5$

输出格式

???????输出一个整数表示$a_k$

输入样例

1024 2

输出样例

8172

思路

???????注意题目中的函数到底是怎么运作的，是怎么操作的。
???????注意a1 += a[i] * pow(10, i); a2 += a[i] * pow(10, l - i- 1);

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1005;
int a[N];
int l;
void eval(int n)
{
	l = 0;
	while(n / 10 != 0)
	{
		a[l] = n % 10;
		n = n / 10;
		l++;
	}
	a[l++] = n;
}

int main()
{
	int n, k;
	cin >> n >> k;
	while(k--)
	{
		if(n == 0)
		{
			cout << 0 << endl;
			return 0;
		}
		else
		{
			eval(n);
			sort(a, a + l); 	//排序
			int a1 = 0, a2 = 0;
			for(int i = 0; i < l; i++)
			{
				a1 += a[i] * pow(10, i);
				a2 += a[i] * pow(10, l - i- 1);
			}
			n = a1 - a2;
		}
	}
	cout << n << endl;
	return 0;
}

IO操作 ：计算a+b

J：IO1（输入N = 行数 = 每行的样例组数）

输入格式

???????输入第一行是一个整数N，代表接下来N行会有N组样例输入。

输出格式

???????每组输出占一行。

输入样例

2
1 5
10 20

输出样例

6
30

思路

???????我采用开定长数组的方法进行计算、存储、输出。

代码

#include<iostream>
using namespace std;
int main(){
	int a[1005], b[1005], c[1005];
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		c[i] = a[i ]+ b[i];
		printf("%d\n", c[i]);
	}
	return 0;
}

K：IO2（以0 0代表输入结束）

输入格式

???????有多组样例输入，以0 0代表输入结束。

输出格式

???????每组输出占一行

输入样例

1 5
10 20
0 0

输出样例

6
30

思路

???????这里直接进行一个无限循环，再根据题目中的要求：输入两个 0 即停止，作为终止条件。

代码

#include<iostream>
using namespace std;
int main(){
	while(1){ 
		int m, n;
		cin >> m >> n;
		if(m == 0 && n == 0){
			return 0;
		}
		printf("%d\n", m + n);
	}
}

L : IO3 （“无”终止条件）

输入格式

???????有多组样例输入

输出格式

???????每组输出占一行

输入样例

1 5
10 20

输出样例

6
30

思路

???????这里面没有一个输入的停止，我认为OJ平台在测试时会给停止符号Ctrl Z 或者 Ctrl C。对此的判断条件是：while(scanf("%d %d",&m, &n) != EOF)

代码

#include<iostream>
using namespace std;
int main(){
	int m, n;
	int sum;
	while(scanf("%d %d",&m, &n) != EOF){
		cout << (m + n) << endl;
	}
	return 0;
}

M : IO4 （输入到某一组数的数字个数为 0 ）

输入格式

???????输入包含多组样例。
???????每组样例包含一个整数N，然后在同行有N个整数。
???????若N = 0，则表示输入结束，这个样例不需要被处理。

输出格式

???????对于每组用例，你应当输出这组样例N个数字的和，每个输出占一行。

输入样例

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

输出样例

10
15

思路

???????这里要求输入到某一组数的数字个数为 0 的时候停止循环。因此采用： while(scanf("%d",&tmp) && tmp != 0)

代码

#include<iostream>
using namespace std;
int main(){
	int tmp;
	int sum;
	while(scanf("%d",&tmp) && tmp != 0){
		for(int i = 0; i < tmp; i++){
			int input; 
			cin >> input;
			sum = sum + input;
		}
		cout << sum << endl;
		sum = 0;
		tmp = 0;
	}
	return 0;
}

N : IO5 （输入N组数据且每组数据个数可不同）

输入格式

???????第一行有一个整数N，表示有N行数。接下来N行，每行第一个为整数M，表示本行后面有M个整数。

输出格式

???????对于输入的每一行数，请分别对应输出每一行数的和。

输入样例

2
4 1 2 3 4
5 1 2 3 4 5

输出样例

10
15

思路

???????需要注意定义变量的时候可以再函数之中定义，重复循环。（虽然很不提倡）代码’ 是修正之后的代码。

代码

#include<iostream>
using namespace std;
int main(){
	int n;
	int sum;
	cin >> n;
	for(int i = 0; i < n; i++){
		int m;
		cin >> m;
		for(int j = 0; j < m; j++){
			int tmp;
			cin >> tmp;
			sum = sum + tmp;
		}
		cout << sum << endl;
		sum = 0; 
	}
	return 0;
}

代码’

#include<iostream>
using namespace std;
int main(){
	int n;
	int sum, m, tmp;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> m;
		for(int j = 0; j < m; j++){
			cin >> tmp;
			sum = sum + tmp;
       		tmp = 0;
		}
    	m = 0;
		cout << sum << endl;
		sum = 0; 
	}
	return 0;
}

O : IO6 （“无”停止的NNN即IO3）

输入格式

???????输入包含多组数据，每组数据占一行。每行第一个数为整数N，后面有N个整数

输出格式

???????对于输入的每一行数，请分别对应输出每一行数的和。

输入样例

4 1 2 3 4
5 1 2 3 4 5

输出样例

10
15

思路

???????没有直接的终止标志，就用EOF。然后这里需要判定的是一开始输入的数字个数。因此判定代码为：

while(scanf("%d", &n) != EOF)

代码

#include<iostream>
using namespace std;
int main(){
	int n;
	int sum;
	while(scanf("%d", &n) != EOF){
		for(int j = 0; j < n; j++){
			int tmp;
			cin >> tmp;
			sum = sum + tmp;
		}
		cout << sum << endl;
		sum = 0; 
	}
	return 0;
}

P : IO7 （无组数，无组中数据个数）

输入格式

???????输入包含多组数据，每组数据占一行。每行有若干个整数

输出格式

???????对于输入的每一行数，请分别对应输出每一行数的和。

输入样例

1 2 3 4
1 2 3 4 5

输出样例

10
15

思路

???????本题中助教给了一个Hint：本题相关知识：读取一行的处理和格式化读取字符串，也可使用getline和stringstream。

扩展知识

???????下面的引用自该链接，且更多详细知识请点击该链接

???????getline()函数可以让我们很方便的输入一串字符串。getline()不仅简单,而且安全,因为全局函数 getline() 会帮你处理缓冲区用完之类的麻烦。常见的getline()函数语法有两条：

istream &getline( char *buffer, streamsize num, char delim );
istream &getline( char *buffer, streamsize num );

???????其中的buffer、num、delim的意思分别为：
???????buffer 进行读入操作的输入流
???????num 存储读入的内容
???????delim 终结符

getline()函数功能：

???????将输入流num中读到的字符存入buffer中，直到遇到终结符delim才结束。对于第一个函数delim是可以由用户自己定义的终结符；对于第二个函数delim默认为 ‘\n’（换行符）。
???????函数在输入流num中遇到文件结束符（EOF）或者在读入字符的过程中遇到错误都会结束。
???????在遇到终结符delim后，delim会被丢弃，不存入line中。在下次读入操作时，将在delim的下个字符开始读入。

eg1:输入get?line() 输出get

#include<iostream>
#include<string>
using namespace std;
 
int main(){
	string line;
	getline(cin,line,'?');
	cout<<line;
	return 0;
}

???????这里输入流实际上只读入了get，？后面的line()并没有存放到line中（仍停留在输入缓冲区里）。
???????而且这里把终止符设为?，你输入的时候就算输入几个回车换行也没关系，输入流照样会读入。

getline也可以作为成员函数使用：
???????向cha中输入num个字符，输入过程中达到num-1个数或者提前遇到f字符，输入结束。

cin.getline(char *cha,int num,char f);

eg2:输入hello wo?rld 输出hello wo,或者输入hello world 输出hello wor

#include<iostream>
#include<string>
using namespace std;
 
int main(){
	char line[100];
	cin.getline(line,10,'?');
	cout<<line;
	return 0;
}

???????下面的引用自该链接，且更多详细知识请点击该链接

输入原理简述：

???????程序的输入都建有一个缓冲区，即输入缓冲区。每次输入过程是这样的，当一次键盘输入结束时会将输入的数据存入输入缓冲区，而cin函数直接从输入缓冲区中取数据（cin读取数据是从第一个非空白字符开始到下一个空白字符结束）。正因为cin函数是直接从缓冲区取数据的，所以有时候当缓冲区中有残留数据时，cin函数会直接取得这些残留数据而不会请求键盘输入。
???????由于cin在遇到空格/tab时，就会停止读取，所以如果我在第一次输入时，利用空格隔开两个字符串，那么cin在第一次取的时候，只会读取前一个字符串，到空格结束，此时缓冲区还保留着前面输入的第二个字符串，那么第二次cin就会直接从缓冲区取残留数据，而不会请求输入。
???????当然对于以上的情况，也有解决的方案，那就是在第二次调用cin>>str之前通过cin.sync()来清空输入缓冲区。

???????下面的引用自该链接，且更多详细知识请点击该链接

stringstream总结：

???????1.stringstream实际是在其底层维护了一个string类型的对象用来保存结果。
???????2.多次数据类型转化时，一定要用clear()来清空，才能正确转化，但clear()不会将
??????? 3.stringstream底层的string对象清空。
???????4.可以使用s. str("")方法将底层string对象设置为""空字符串。
???????5.可以使用s.str()将让stringstream返回其底层的string对象。
???????6.stringstream使用string类对象代替字符数组，可以避免缓冲区溢出的危险，而且其会对参数类型进行推演，不需要格式化控制，也不会出现格式化失败的风险，因此使用更方便，更安全。

代码

#include<iostream>
#include<string>
#include<sstream>
using namespace std;
 
int main() {
    string line;
    int k = 1;
    while(getline(cin, line)) {
    int sum = 0, x;
    stringstream ss(line);
    while(ss >> x) sum += x;
        cout << sum << endl;
        ++k;
    }
	return 0;
}

Q : IO8 （“无”终止16进制加法）

???????给定两个十六进制整数a和b，输出他们的和

输入格式

???????输入多组数据，以EOF作为数据的结束。每组数据在一行中包含了两个十六进制整数a和b。

输出格式

???????对于每一组数据，以十进制输出a+b的和。每组输出占用一行。

输入样例

1 9
A B
a b

输出样例

10
21
21

思路

???????依然使用 EOF ，输入用 %x ，输出用 %d。简单粗暴。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main()	
{
	int a,b;
	while(scanf("%x %x",&a,&b)!=EOF)
	{
		printf("%d\n",a+b);
	}
	return 0;
}

总结

???????第一周题目确实不少，但是这些题目给我了我许多警醒。一些BUG让我学会了很多。而且最后几个IO的题目，真的有很多学问。首先要看是否“明显”的终止标志，如果没有就是用EOF。如果有看是否有类似“组数”或者“组内成员个数”类的数据，像这样的，我们使用while(scanf("%d",&tmp) && tmp != 0)类似的代码来进行判断。
???????文末，虽然我不能和大佬比，但是我能够做自己。希望大佬不要对我拙劣的代码能力和书写博客能力嘲笑，我会继续努力。

???????最后，感谢本文中被我引用的两个博主。希望这篇文章对你有所帮助！感谢观看！