1. 索引数组排序

题目编号：Exp04-Enhance04,GJBook3-06-21

题目名称：索引数组排序

题目描述：已知n（n≤100）个元素的整型数组 A 未排序，一个索引数组 B 保存 A 的下标。编写程序，在不改变数组A的情况下，只改变数组 B完成对A的递增排序，如下所示：排序后索引数组B的第一个元素值是A数组中最小元素的下标。

排序前
数组A：9 7 5 8 0 4 1 3 2 6 
数组B：0 1 2 3 4 5 6 7 8 9
排序后
数组A：9 7 5 8 0 4 1 3 2 6
数组B：4 6 8 7 5 2 9 1 3 0

输入：第一行输入一个正整数n，第二行随机输入n个互不相同的整数作为数组A的元素。

输出：第一行输出数组A的n个元素，元素间以一个西文空格间隔；第二行输出数组B的n个元素，元素间以一个西文空格间隔；每行最后一个元素后无字符。
 

样例1：

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

输出：
9 7 5 8 0 4 1 3 2 6
4 6 8 7 5 2 9 1 3 0

样例2：

输入：
5
9 8 7 6 5

输出：
9 8 7 6 5
4 3 2 1 0

#include <iostream>

using namespace std;

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

	for (int i = 0;i < n - 1;i++)
	{
		for (int j = 0;j < n - i - 1;j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp1 = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp1;
				int tmp2 = b[j];
				b[j] = b[j + 1];
				b[j + 1] = tmp2;

			}
		}
	}
	for (int i = 0;i < n - 1;i++)
		cout << b[i] << " ";
	cout << b[n - 1];


	return 0;
}

动态数组根据输入的n开辟适当的空间 ，合理利用内存

a[n] 保存输入的数据，b[n] 保存数组下标

既然要在不改变数组A的情况下，只改变数组 B完成对A的递增排序，那就先将A输出，

还是两层for循环，for循环内部一定要将a[n]，b[n]的相应元素同时交换，而不要只交换b中的对应元素，这样做是确保a中的元素与下标一一对应

还有一点特别重要，就是对行末空格的处理，必须要处理，不然程序过不去

2. 约瑟夫问题(Josephus)

题目编号 ：Exp04-Enhance02，GJBook3-06-26

题目名称：约瑟夫问题(Josephus)

题目描述：

古代某法官要判决 n 个犯人死刑, 他有一条荒唐的逻辑, 将犯人首尾相接排成圆圈，所有计数从1开始； 然后从第 s 个人开始数, 每数到第 m 个犯人，则拉出来处决; 然后再数 m 个，数到的犯人再处决；... ; 但剩下的最后一个犯人可以赦免。编程序，给出处决顺序，并告知哪一个人活下来。

输入：三个正整数 n（≤1000），s和m，都可以使用int类型变量表示。

输出：依次输出被处决人员的编号，每个编号之间用一个西文空格间隔，最后一个编号后无字符。
 

样例：

输入：6 1 5

输出：5 4 6 2 3 1

#include <iostream>

using namespace std;

int main()
{
	int n, m, i, x = 1, y = 0;
	cin >> n >> x >> m;
	int* arr;
	arr = new int[n + 1];
	for (i = 1; i <= n; i++)
		arr[i] = i;
	for (y = 0; y < n; y++)//死的人数（全死）
	{
		for (i = 1; i <= m; i++)
		{
			while (arr[x] == 0)
			{
				x++;
				if (x > n)
					x = 1;
			}//死人没意义
			if (arr[x] != 0)
			{
				x++;
				if (x > n)
					x = 1;
			}//继续数一个人
		}
		if (x == 1)
		{
			arr[n] = 0;
			cout << n;
		}
		else
		{
			arr[x - 1] = 0;
			cout << (x - 1);
		}
		if (y != n - 1)
			cout << " ";
	}


	return 0;
}

代码先放到这里，希望能帮助大家理解。

另外。约瑟夫问题是一个比较经典的算法题，以后我会单独出一期来讲解约瑟夫问题 

3. n倍数关系

题目编号：Exp04-Basic02

题目名称：n倍数关系

题目描述：

给定若干不完全相同的正整数（<10000）和n（n<5)，计算这些正整数里面有多少数对满足：其中一个是另一个的n倍。例如：1 4 3 2 9 7 18 22，n=3时得到的答案是2；因为3是1的3倍，9是3的3倍。

输入：输入第一行给出正整数n的值，接下来包括多组测试数据。每组数据最多100个整数占用一行，以数字0结束(不计入100个整数里)。测试数据不超过20组，最后一行只包括-1，表示输入数据结束。

输出：对每组输入数据，输出一行，给出有多少数对满足其中一个是另一个n倍。（注：最后一行末尾无换行符等多余字符。）
 

样例：

输入：
2
1 4 3 2 9 7 18 22 0
2 4 8 10 0
7 5 11 13 1 3 0
-1

输出：
3
2
0

#include <iostream>
#include <vector>

using namespace std;

vector<int> v1;
vector<int> v2;

int main()
{
	int n, m, x;
	int cnt = 0;
	cin >> n;
	while (1)
	{
		v1.clear();
		cin >> x;
		if (x == -1)
			break;
		while (x != 0)
		{
			v1.push_back(x);
			cin >> x;
		}
		cnt++;
		int res = 0;
		for (int i = 0;i < v1.size();i++)
		{
			for (int j = i + 1;j < v1.size();j++)
			{
				if (v1[i] == v1[j] * n || v1[j] == v1[i] * n)
					res++;
			}			
		}
		v2.push_back(res);
	}
	for (int i = 0;i < v2.size();i++)
	{
		cout << v2[i];
		if (i != v2.size() - 1)
			cout << endl;

	}

	return 0;
}

加了vector的头文件就可以使用十分方便的动态数组vector了 

如何按照题目的要求读入输入的格式是本题的关键

4. 矩阵转置

题目编号: Exp04-Basic08,GJBook3-06-03

题目名称: 矩阵转置

问题描述: 编写程序，将任意给定n*n的两维整型数组转置。

输入：第一行输入数组行数n（≤10），第二行随机输入n*n个整数作为数组元素值。

输出：按先行后列、从左至右的顺序输出转置后数组内的所有元素，每行n个元素，同一行内的各元素间以一个西文空格间隔；每行最后一个元素除必要的回车换行符外无其它字符。

样例1：

输入：
3
1 2 3
1 2 3
1 2 3

输出：
1 1 1
2 2 2
3 3 3

样例2：

输入：
3
1 1 1
2 2 2
3 3 3

输出：
1 2 3
1 2 3
1 2 3

#include <iostream>

using namespace std;

int main()
{
	int n;
	cin >> n;
	int** a = new int* [n];
	for (int i = 0;i < n;i++)
		a[i] = new int[n];
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n;j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n - 1;j++)
		{
			cout << a[j][i] << " ";
		}
		cout << a[n - 1][i] << endl;
	}

	return 0;
}

注意开头动态二维数组的创建

int **a=new int*[n];

 for(int i=0;i<n;i++)

a[i]=new int[n];

5. 检验矩阵主对角线对称

题目编号：Exp04-Basic09，GJBook3-06-02

题目名称：检验矩阵主对角线对称

题目描述：编写程序，判断任意给定n*n的两维整型数组是否关于主对角线对称。
 

输入：第一行输入数组行数n（≤10），第二行随机输入n*n个整数作为数组元素值。

输出：如果数组关于主对角线对称，则输出YES；否则输出NO。

样例1：

输入：

3
1 2 3
2 1 2
3 2 1

输出：
YES

样例2：

输入：

3
0 0 1
2 1 2
3 2 1

输出：
NO

#include <iostream>

using namespace std;

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

	for (int i = 0;i < n;i++)
	{
		for (int j = 0;j < n;j++)
		{
			cin >> a[i][j];
		}
	}
	int flag = 1;
	for (int i = 1;i < n;i++)
	{
		for (int j = i + 1;j < n;j++)
		{
			if (a[i][j] != a[j][i])
				flag = 0;

		}
	}
	if (flag == 1)
		cout << "YES" << endl;
	else if (flag == 0)
		cout << "NO" << endl;

	return 0;
}