吉林大学超星MOOC学习通高级语言程序设计 C++ 实验04 数组及其在程序设计中的应用(2021级)(2)

这几道题的技巧性比较强,需要大家静下心来思考和理解

6. 转移0元素

题目编号:Exp04-Basic05,GJBook3-06-06

题目名称:转移0元素

题目描述:编写程序,不使用其他辅助数组,把给定整型数组中所有0元素全部移到后面,且所有非0元素的顺序不变。
 

输入:第一行输入数组长度n(≤100),第二行依次从键盘随机输入n个整数作为数组元素值。

输出:已将所有0元素串到后面的整数数组,各元素间以一个西文空格间隔,最后一个元素后无字符。
 

样例1:

输入:
10
0 3 1 0 0 0 1 2 3 0
输出:
3 1 1 2 3 0 0 0 0 0

样例2:

输入:
10
0 0 0 0 0 0 1 2 3 4
输出:
1 2 3 4 0 0 0 0 0 0
#include <iostream>

using namespace std;

int main()
{
	int n = 0;
	int arr[100];
	cin >> n;
	for (int i = 0;i < n;i++)
	{
		cin >> arr[i];
	}
	int cnt = 0;
	for (int i = 0;i < n;i++)
	{
		if (arr[i] != 0)
		{
			cout << arr[i] << " ";
			cnt++;
		}

	}
	for (int i = cnt;i < n;i++)
	{
		cout << "0 ";
	}

	return 0;
}

如果题目没什么特别要求的话,改变数组中元素的输出顺序比改变数组简单,下一题也是如此

7. 循环右移

题目编号 :Exp04-Basic06,GJBook3-06-04

题目名称:循环右移

题目描述:编写程序,不使用其它辅助数组,把一维整型数组中的各个元素循环右移j位。

输入:

第一行输入两个整数,n表示数组长度(0<n<=100),j表示循环右移的位数(j>=0);

第二行依次从键盘随机输入n个整数作为数组元素值。

输出:

循环右移后的整数数组,各元素间以一个西文空格间隔,最后一个元素后无字符。

样例1:

输入:
10 2
1 2 3 4 5 6 7 8 9 0
输出:
9 0 1 2 3 4 5 6 7 8

样例2:

输入:
10 23
1 2 3 4 5 6 7 8 9 0
输出:
8 9 0 1 2 3 4 5 6 7

 第一种比较简单的方法,同上一题改变输出

#include <iostream>

using namespace std;

int main()
{
	int n, m, * a;
	cin >> n >> m;
	a = new int[n];
	for (int i = 0;i < n;i++)
	{
		cin >> a[i];
	}
	if (m > n)
	{
		m = m % n;
	}
	for (int i = n - m;i < n;i++)
	{
		cout << a[i] << " ";
	}
	for (int i = 0;i < n - m;i++)
	{
		cout << a[i] << " ";
	}

	return 0;
}

 第二种方法是改变数组,把代码放在下面供大家参考

#include <iostream>
#include <vector>

using namespace std;

vector<int> a;

int main()
{
	int n, m, x;
	cin >> n >> m;
	if (m > n)
		m = m % n;
	int cnt = n;
	while (n > 0)//输入数组
	{
		cin >> x;
		a.push_back(x);
		n--;
	}
	for (int i = 0;i < m;i++)
	{
		int tmp = a[cnt - 1];//暂时储存vector中的最后一个元素
		a.erase(a.end()-1);//将其删除
		a.insert(a.begin(),tmp);//把原来vector中的最后一个元素插入到vector的开头

	}
	for (vector<int>::iterator it = a.begin();it != a.end();it++)//打印排序后的数组
	{
		cout << *it << " ";
	}
	return 0;
}

 

8. 括号匹配

题目编号:Exp04-Basic01,GJBook3例-06-13

题目名称:括号匹配

题目描述:编写程序,从终端读入以‘@’为结束符的字符序列,检查该字符序列中的 ( 与 )、 [ 与 ] 、{ 与 } 是否匹配(个数相等且位置不相交)。

输入:包含一串以‘@’为结束符的字符串,其间可能包含空白或其它非括号字符。

输出:如果字符串中三类括号匹配,则输出YES;否则输出NO。
 

样例1:

输入:

{a,a}b{c[cc]c}  {a(bb[cc]dd)a}@
输出:
YES

样例2:

输入:
{a,a}b{c[cc]c] {a(bb[cc]dd)a}@
输出:
NO

#include <iostream>
#include <vector>

using namespace std;

vector<char> a;


int main()
{
	char ch;
	cin >> ch;
	int cnt = 0;
	while (ch != '@')
	{
		switch (ch)
		{
		case '(':a.push_back('(');break;
		case '[':a.push_back('[');break;
		case '{':a.push_back('{');break;

		case ')':
		{
			if (a.back() == '(')
			a.pop_back();//删除vector的最后一个元素
			break;
		}
		case ']':
		{
			if (a.back() == '[')
			a.pop_back();
			break;
		}
		case '}':
		{
			if (a.back() == '{')
			a.pop_back();
			break;
		}

		}
		cin >> ch;
	}
	cnt = a.size();
	if (cnt == 0)
	{
		cout << "YES" << endl;

	}
	else
	{
		cout << "NO" << endl;
	}

	return 0;
}

熟悉的while循环和vector又来了,为我们提供了非常好的解题思路

此题的难点就是检查括号相等且不相交

输入一段以'@'结尾的字符串,遇到左括号时压入vector ,遇到右括号时判断是否与前面的左括号匹配,若匹配,则将对应的左括号删掉,随后继续读下一个字符

最后,若a.size()==0,则说明括号匹配,否则不匹配

9. 检验矩阵重复元素

题目编号:Exp04-Basic07,GJBook3-06-01

题目名称:检验矩阵重复元素

题目描述:编写程序判断任意给定n*n的两维整型数组中是否有相同元素。
 

输入:第一行输入数组行数n(≤10),第二行随机输入n*n个整数作为数组元素值。

输出:如果数组中有相同元素,则输出YES;否则,输出NO。
 

样例1:

输入:
3
1 2 3 4 5 6 7 8 9
输出:
NO

样例2:

输入:
3
1 1 2 3 4 5 6 7 8
输出:
YES

#include <iostream>

using namespace std;

int main()
{
	int n, * a;
	cin >> n;
	a = new int[n * n];

	for (int i = 0;i < n * n;i++)
	{
		cin >> a[i];
	}

	int flag = 0;
	for (int i = 0;i < n * n - 1;i++)
	{
		for (int j = i + 1;j < n * n;j++)
		{
			if (a[i] == a[j])
				flag = 1;
		}
	}
	if (flag == 1)cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

 判断重复的核心就在于中间的两个for循环嵌套,这种排序方式能保证在比较元素中不重不漏,不能只写一个for循环,否则容易漏掉某些元素之间的比较

10. 螺旋矩阵

题目编号:Exp04-Enhance05,freshman-1050,GJBook3-0622

题目名称:螺旋矩阵

题目描述:

螺旋矩阵指一个呈螺旋状的数字矩阵,它的数字由第一行开始到右边不断变大,向下变大,向左变大,向上变大,如此循环。如下所示为3阶螺旋矩阵。

吉林大学超星MOOC学习通高级语言程序设计 C++ 实验04 数组及其在程序设计中的应用(2021级)(2)

输入:输入一个正整数 N (N<=30),标明矩阵阶数。

输出:按螺旋矩阵形式输出整数 1~N^2, 共 N 行N 列,每个数字输出占4个西文字符宽度,右对齐,最后一个数字后无多余字符。

样例:

输入:
15
输出:

    

吉林大学超星MOOC学习通高级语言程序设计 C++ 实验04 数组及其在程序设计中的应用(2021级)(2)

 终于见到了终极大Boss,螺旋矩阵,据说很多大厂都爱考这个题,

主要解题思路有两个,

一是数组法:寻找每个递增元素的下标关系,利用循环输出

二是递归法:本题给出的是N*N阶方阵,所以用递归法也比较容易思考到

最终要归结到合理判断a[i][j]的元素

鉴于学校现在可能还没讲到递归算法,在此主要讲解数组法

1.首先要考虑到N为奇数或者N为偶数时候的情况

N=5
a00 a01 a03 a04 a05

a10

a11 a12 a13 a14
a20 a21 a22 a23 a24
a30 a31 a32 a33 a34
a40 a41 a42 a43 a44

 输出思路是,先输出外面的 N/2 层,再把中间的a[N/2][N/2]输出

N=4
a00 a01 a03 a04

a10

a11 a12 a13
a20 a21 a22 a23
a30 a31 a32 a33

当N为偶数时就比较简单了,直接输出 N/2 层循环

2.观察两个表格上面颜色相同的元素,来确定每一个元素的输出顺序

每一层输出应写成四个循环,每一个循环输出N-1个元素,由外向内,依次输出

int k = 1;
	for (i = 0;i < n / 2;i++)//判断循环层数
	{
		for (j = i;j < n - i - 1;j++)//上
			a[i][j] = k++;
		for (j = i;j < n - i - 1;j++)//右
			a[j][n - i - 1] = k++;
		for (j = n - i - 1;j > i;j--)//下
			a[n - i - 1][j] = k++;
		for (j = n - i - 1;j > i;j--)//左
			a[j][i] = k++;
	}
	if (n % 2 == 1)//N为奇数时单独给中间剩下的元素赋值
		a[n / 2][n / 2] = k;

最终的代码放在下边

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
	//n阶螺旋矩阵
	int n, m;
	int i, k, j;
	cin >> n;
	int** a = new int* [n];
	for (int i = 0;i < n;i++)
		a[i] = new int[n];
	k = 1;
	for (i = 0;i < n / 2;i++)
	{
		for (j = i;j < n - i - 1;j++)
			a[i][j] = k++;
		for (j = i;j < n - i - 1;j++)
			a[j][n - i - 1] = k++;
		for (j = n - i - 1;j > i;j--)
			a[n - i - 1][j] = k++;
		for (j = n - i - 1;j > i;j--)
			a[j][i] = k++;
	}
	if (n % 2 == 1)
		a[n / 2][n / 2] = k;
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n;j++)
		{
			cout << setfill(' ') << setw(4) << a[i][j];
			
		}
		cout << endl;
	}
	

	return 0;
}

最后别忘了用iomanip头文件来完成题目要求的输出格式

cout << setfill(' ') << setw(4) << a[i][j];//设置宽度为4,用空格补齐

上一篇:算法-Mooc-浙江大学


下一篇:吉林大学超星MOOC学习通高级语言程序设计 C++ 实验04 数组及其在程序设计中的应用(2021级)(1)