程序设计思维与实践实验1总结

博主： grinrain
发布时间：2022 年 02 月 24 日
2120次浏览
12 条评论
2365字数
分类：程序设计思维与实践

# **F** : Remove It

## 问题描述

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

## 输入格式

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

## 输出格式

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

## 样例输入1

```
6 4
1 2 3 4 3 4
```

## 样例输出1

```
1 2 3 3
```

## 样例输入2

```
3 6
6 6 6
```

## 样例输出2

```

<br/>

## 做题中遇到的问题

一开始的思路比较复杂：接收数组之后想把数组中的目标数（也就是x）删掉，再输出整个数组。在与竞赛党交流之后发现可以直接在原数组中判断这个数字是否与x相等，相等则不输出，这样大大简化了思路。
<br/>
完整代码如下

```c++
#include <cstdio>

int a[100100];

int main()
{
	int n, x;
	scanf("%d%d", &n, &x);
	for(int i=0; i<n; i++)
	{
		scanf("%d", a+i);
	}
	
	for(int i=0; i<n; i++)
	{
		if(a[i] != x)
		{
			printf("%d ", a[i]);
		}
	}
	
	return 0;
}
```

在程序的第11行犯过一个小错误，误把`a[i]`当作地址，实际上应该写作`&a[i]`或者`a+i`
一开始时在本地测试正常，但是oj全部报RE，经过检查是数组开太小了

全局变量可以开到1e7,局部变量1e4
</div>

# **G** : Rally

Description

## 问题描述

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

## 输入格式

第一行一个整数 **n**，接下来一行有 **n** 个整数，表示每个人的位置。**1**≤****n****≤****100****,****1****≤****x****i********≤****100****

## 输出格式

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

## 样例输入

```
6
5 2 4 2 8 8
```

## 样例输出

```
37
```

<br/>

## 思路

由于本题的规模较小，所以可以用穷举法解题
代码如下

```C++
#include <cstdio>
#define MAX 0x3f3f3f3f

int a[120];

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		scanf("%d", a+i);
	}
	
	int minCost = MAX;
	for(int p=1; p<=100; p++)
	{
		//p是当前判断的位置
		int cost = 0;
		for(int i=0; i<n; i++)
		{
			//i是第i个人的位置 
			cost += (a[i]-p) * (a[i]-p);
		}
		if( cost < minCost )
		{
			minCost = cost;
		}
	}
	
	printf("%d", minCost);
	
	return 0;
}
```

# **I** : Kaprekar Number

## 思路：

如果将K视为一个整数输入的话，那么对它进行升降序排序操作将会比较困难；如果转换思路，把它视作一个字符串，那么就可以用STL函数`sort`对这个字符串进行排序。并且，程序输出的内容不收变量类型的影响（即同样的整数“123”， 将它作为`int`类型或者作为`string`类型输出的效果是相同的，因此最后不必将结果转换回`int`.

完整代码如下:

```C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string f(string s)
{
	string ans = "", g1, g2;
	//将g1和g2排好序 
	sort(s.begin(), s.end());	//升序 
	g2 = s;
	g1 = g2;
	reverse(g1.begin(), g1.end());	//降序

//将g1, g2转换为整数运算
	int gg1 = 0, gg2 = 0;
	int temp = 1;
	for (int i = 0; i < s.length(); i++)
	{
		// 这种算法会使得结果数字逆序
		gg2 += (g1[i] - '0') * temp;
		gg1 += (g2[i] - '0') * temp;
		temp *= 10;
	}

// 将结果转回字符串
	int diff = gg1 - gg2;
	while (diff > 0)
	{
		ans += char('0' + diff % 10);
		diff /= 10;
	}
	reverse(ans.begin(), ans.end());

return ans;
}

int main()
{
	string n;	//可以将输入视为字符串，接下来用字符串处理较为方便 
	int k;
	cin >> n >> k;

for (int i = 0; i < k; i++)
	{
		n = f(n);
	}

cout << n;

return 0;
}
```

# 实验报告

# 一、时间复杂度

**1.请使用 O() 表示以下函数的渐进时间复杂度，并按照时间复杂度从高到低的顺序，排序以下函数：**

$O(f_1) = O(log(log(n)))$

$O(f_2) = O(n)$

$O(f_3) = O(n^8)$

$O(f_4) = O(n!)$

$O(f_5) = O(n^{16})$

$O(f_6) = O(e^{n})$

$f_4 > f_6 > f_5 > f_3 > f_2 > f_1$

**2. 请给出并说明如下代码的时间复杂度（使用 O() 与 n 表示）**

$O(n)$

**3.请给出并说明如下代码的时间复杂度（使用 O() 与 n 表示）**

$O(log(n^2))$

**4.请给出并说明如下代码的时间复杂度（使用 O() 与 n 表示）**

$O(log_3(n))$

# ⼆、Online Judge 系统与调试

**1.** 答：张三的代码只能满足样例中的情况，对于其他其他情况没有考虑周到，所以可能在其他数据上出现错误答案。

**2.**  答：C 库函数 `FILE *freopen(const char *filename, const char *mode, FILE *stream)` 把一个新的文件名 `filename` 与给定的打开的流 `stream` 关联，同时关闭流中的旧文件。

```C++
//重定向标准输入到文件
freopen("a.in", "r", stdin);

//重定向标准输出到文件
freopen("a.out", "w", stdout);
```

# 三、实验E1

## 1.G(Rally)

### 题目大意

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

### 解法

由于本题的规模较小（最多100个人，100个位置），所以可以用穷举法解题。穷举所有位置并计算出对应的代价，求出最小代价即可。

### 时间复杂度

$O(n^2)$

#### 分析

外层循环是穷举n个位置*（题目说了位置是数轴上的整数位置，那为什么不是无穷个位置呢？原因是当位置`p<1`或`p>100`时，其成本肯定比`1<=p<=100`要大)*，内层循环是对n个人计算总成本。因此循环总次数是`n*n`。

### 代码

```C++
#include <cstdio>
#define MAX 0x3f3f3f3f
 
int a[120];
 
int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		scanf("%d", a+i);
	}
	
	int minCost = MAX;
	for(int p=1; p<=100; p++)
	{
		//p是当前判断的位置
		int cost = 0;
		for(int i=0; i<n; i++)
		{
			//i是第i个人的位置 
			cost += (a[i]-p) * (a[i]-p);
		}
		if( cost < minCost )
		{
			minCost = cost;
		}
	}
	
	printf("%d", minCost);
	
	return 0;
}
```

## 2.Kaprekar Number

### 题目大意

定义函数 g1(x), g2(x), f(x), x>0

g1(x), g2(x), f(x),x>0 如下:

g1(x)=g1(x)= 将 x 的各位数字按照降序排序

g2(x)=g2(x)= 将 x 的各位数字按照升序排序，忽略前导零

f(x)=g1(x) − g2(x)

例如，g1(318)=831 g1(318)=831, g(1024)=124

g2(1024)=124, f(271)=721−127=594 *f*(271)=721−127=594

给出整数 N,KN,K, 定义数列 a0=N, $a_{i+1}=f(a_i) (i≥0)a0=N,ai+1=f(ai)(i≥0)$，求 aK.

### 解法

如果将K视为一个整数输入的话，那么对它进行升降序排序操作将会比较困难；如果转换思路，把它视作一个字符串，那么就可以用STL函数`sort`对这个字符串进行排序。并且，程序输出的内容不受变量类型的影响（即同样的整数“123”， 将它作为`int`类型或者作为`string`类型输出的效果是相同的，因此最后不必将结果转换回`int`.

### 时间复杂度

$O(nlog(n))$

#### 分析

主函数中for循环的执行次数是n, 每次循环中都执行函数f.

函数f中使用`sort`和`reverse`函数，上网查阅它们的时间复杂度如下

> `std :: sort() `具有平均情况线性 $nlog(n)$时间复杂度
> 
> `reverse()`函数无返回值，时间复杂度$O(n)$

函数f中使用1个sort函数，两个reverse函数，一个for循环和一个while循环

因此函数f的时间复杂度为$O(nlog(n) + 2n + n + n)$

### 代码

```C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string f(string s)
{
	string ans = "", g1, g2;
	//将g1和g2排好序 
	sort(s.begin(), s.end());	//升序 
	g2 = s;
	g1 = g2;
	reverse(g1.begin(), g1.end());	//降序 
 
	//将g1, g2转换为整数运算
	int gg1 = 0, gg2 = 0;
	int temp = 1;
	for (int i = 0; i < s.length(); i++)
	{
		// 这种算法会使得结果数字逆序
		gg2 += (g1[i] - '0') * temp;
		gg1 += (g2[i] - '0') * temp;
		temp *= 10;
	}
 
	// 将结果转回字符串
	int diff = gg1 - gg2;
	while (diff > 0)
	{
		ans += char('0' + diff % 10);
		diff /= 10;
	}
	reverse(ans.begin(), ans.end());
 
	return ans;
}
 
int main()
{
	string n;	//可以将输入视为字符串，接下来用字符串处理较为方便 
	int k;
	cin >> n >> k;
 
	for (int i = 0; i < k; i++)
	{
		n = f(n);
	}
 
	cout << n;
 
	return 0;
}
```

最后修改：2022 年 02 月 26 日 05 : 18 PM

如果觉得我的文章对你有用，请随意赞赏

12 条评论

yixfrfzmvc
March 4th, 2025 at 06:46 pm

作者以简洁明了的语言，传达了深刻的思想和情感。

回复
ykansduiio
March 2nd, 2025 at 11:35 am

韵律感强烈，朗读时如音乐流淌。

回复
rxjiyoybeq
January 6th, 2025 at 02:35 pm

哈哈哈，写的太好了https://www.lawjida.com/

回复
hzzzeihgay
December 15th, 2024 at 04:53 am

你的文章让我学到了很多技能，非常实用。 https://www.yonboz.com/video/92748.html

回复
tadppnyksf
December 15th, 2024 at 03:45 am

每次看到你的文章，我都觉得时间过得好快。 https://www.4006400989.com/qyvideo/71055.html

回复
jppngydihm
December 6th, 2024 at 06:14 am

《一路北上》欧美综艺高清在线免费观看：https://www.jgz518.com/xingkong/124756.html

回复
vddconlwvu
November 25th, 2024 at 08:23 pm

你的文章让我感受到了艺术的魅力，谢谢！ https://www.4006400989.com/qyvideo/14255.html

回复
piohjuckja
November 22nd, 2024 at 12:47 am

《妖妃真假总裁夫人》短片剧高清在线免费观看：https://www.jgz518.com/xingkong/13972.html

回复
lwkxxkvjuh
November 19th, 2024 at 07:09 pm

你的文章让我感受到了不一样的风景，谢谢分享。 https://www.yonboz.com/video/2952.html

回复
iugfedbalx
November 18th, 2024 at 05:12 am

你的才华让人惊叹，你是我的榜样。 https://www.4006400989.com/qyvideo/92003.html

回复
irwreqdrpg
October 4th, 2024 at 09:55 pm

想想你的文章写的特别好https://www.ea55.com/

回复
fbiuykooav
October 1st, 2024 at 09:24 pm

不错不错，我喜欢看 https://www.237fa.com/

回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

xzhlikbvdt
立意高远，以小见大，引发读者对社会/人性的深层共鸣。
ahfwbqnzmy
文章结构紧凑，层次分明，逻辑严密，让人一读即懂。
hufixjveix
作者的情感表达细腻入微，让人在阅读中找到了心灵的慰藉。
yixfrfzmvc
作者以简洁明了的语言，传达了深刻的思想和情感。
jhwrxkjwyt
案例丰富且贴合主题，论证逻辑环环相扣。

程序设计思维与实践实验1总结

grinrain • 2022 年 02 月 24 日

# **F** : Remove It

## 问题描述

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

## 输入格式

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

## 输出格式

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

## 样例输入1

```
6 4
1 2 3 4 3 4
```

## 样例输出1

```
1 2 3 3
```

## 样例输入2

```
3 6
6 6 6
```

## 样例输出2

```

<br/>

## 做题中遇到的问题

```c++
#include <cstdio>

int a[100100];

int main()
{
	int n, x;
	scanf("%d%d", &n, &x);
	for(int i=0; i<n; i++)
	{
		scanf("%d", a+i);
	}
	
	for(int i=0; i<n; i++)
	{
		if(a[i] != x)
		{
			printf("%d ", a[i]);
		}
	}
	
	return 0;
}
```

全局变量可以开到1e7,局部变量1e4
</div>

# **G** : Rally

Description

## 问题描述

## 输入格式

第一行一个整数 **n**，接下来一行有 **n** 个整数，表示每个人的位置。**1**≤****n****≤****100****,****1****≤****x****i********≤****100****

## 输出格式

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

## 样例输入

```
6
5 2 4 2 8 8
```

## 样例输出

```
37
```

<br/>

## 思路

由于本题的规模较小，所以可以用穷举法解题
代码如下

```C++
#include <cstdio>
#define MAX 0x3f3f3f3f

int a[120];

# **I** : Kaprekar Number

## 思路：

完整代码如下:

```C++
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string f(string s)
{
	string ans = "", g1, g2;
	//将g1和g2排好序 
	sort(s.begin(), s.end());	//升序 
	g2 = s;
	g1 = g2;
	reverse(g1.begin(), g1.end());	//降序

// 将结果转回字符串
	int diff = gg1 - gg2;
	while (diff > 0)
	{
		ans += char('0' + diff % 10);
		diff /= 10;
	}
	reverse(ans.begin(), ans.end());

return ans;
}

int main()
{
	string n;	//可以将输入视为字符串，接下来用字符串处理较为方便 
	int k;
	cin >> n >> k;

for (int i = 0; i < k; i++)
	{
		n = f(n);
	}

cout << n;

return 0;
}
```

# 实验报告

# 一、时间复杂度

**1.请使用 O() 表示以下函数的渐进时间复杂度，并按照时间复杂度从高到低的顺序，排序以下函数：**

$O(f_1) = O(log(log(n)))$

$O(f_2) = O(n)$

$O(f_3) = O(n^8)$

$O(f_4) = O(n!)$

$O(f_5) = O(n^{16})$

$O(f_6) = O(e^{n})$

$f_4 > f_6 > f_5 > f_3 > f_2 > f_1$

**2. 请给出并说明如下代码的时间复杂度（使用 O() 与 n 表示）**

$O(n)$

**3.请给出并说明如下代码的时间复杂度（使用 O() 与 n 表示）**

$O(log(n^2))$

**4.请给出并说明如下代码的时间复杂度（使用 O() 与 n 表示）**

$O(log_3(n))$

# ⼆、Online Judge 系统与调试

**1.** 答：张三的代码只能满足样例中的情况，对于其他其他情况没有考虑周到，所以可能在其他数据上出现错误答案。

```C++
//重定向标准输入到文件
freopen("a.in", "r", stdin);

//重定向标准输出到文件
freopen("a.out", "w", stdout);
```

# 三、实验E1

## 1.G(Rally)

### 题目大意

### 解法

由于本题的规模较小（最多100个人，100个位置），所以可以用穷举法解题。穷举所有位置并计算出对应的代价，求出最小代价即可。

### 时间复杂度

$O(n^2)$

#### 分析

### 代码

## 2.Kaprekar Number

### 题目大意

定义函数 g1(x), g2(x), f(x), x>0

g1(x), g2(x), f(x),x>0 如下:

g1(x)=g1(x)= 将 x 的各位数字按照降序排序

g2(x)=g2(x)= 将 x 的各位数字按照升序排序，忽略前导零

f(x)=g1(x) − g2(x)

例如，g1(318)=831 g1(318)=831, g(1024)=124

g2(1024)=124, f(271)=721−127=594 *f*(271)=721−127=594

给出整数 N,KN,K, 定义数列 a0=N, $a_{i+1}=f(a_i) (i≥0)a0=N,ai+1=f(ai)(i≥0)$，求 aK.

### 解法

### 时间复杂度

$O(nlog(n))$

#### 分析

主函数中for循环的执行次数是n, 每次循环中都执行函数f.

函数f中使用`sort`和`reverse`函数，上网查阅它们的时间复杂度如下

> `std :: sort() `具有平均情况线性 $nlog(n)$时间复杂度
> 
> `reverse()`函数无返回值，时间复杂度$O(n)$

函数f中使用1个sort函数，两个reverse函数，一个for循环和一个while循环

因此函数f的时间复杂度为$O(nlog(n) + 2n + n + n)$

### 代码

程序设计思维与实践实验1总结

12 条评论

发表评论取消回复

程序设计思维一些技巧

山东大学（青岛）学生Dream-seeker器乐社团2022级部长团名单公示

shell编写中readline库的使用

程序设计思维与实践实验1总结

【转载】山青双创攻略-by刘冲

程序设计思维一些技巧

关于开展山东大学（青岛）学生Dream-seeker器乐社团2022-2023学年部长团换届的通知

最长公共子串

windows下使用批处理脚本比较两个文件的内容

C++关于星期、日期问题的一般性写法

程序设计思维与实践实验1总结

12 条评论

发表评论 取消回复

程序设计思维与实践 实验1总结

发表评论取消回复

程序设计思维与实践实验1总结