[iHooya]1月17日寒假班作业解析

多余的数
小A同学在完成一个数学题求给定的10个整数的和。小A同学在求完之后发现和参考答案对不上检查后发现在求和过程中多计算了一个数其他过程没有问题。现给出小A计算用的11个数以及正确的参考答案请算出小A同学多计算的那一个数。

输入第一行11个正整数每个数小于等于1000000 第二行一个整数表示参考答案
输出一个整数表示多计算的那一个数。

样例输入
2 4 6 8 1 3 5 7 9 5 11
54

样例输出7

提示
样例中原有的10个数为2 4 6 8 1 3 5 9 5 11和为54多余的数为7。

//这道题就是把数组中11个累加起来然后把参考答案减掉就是多余的那个数了
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int arr[11]={0};
	int right=0,sum=0;
	for(int a=0;a<11;a++)
		cin>>arr[a];
	cin>>right;
	for(int b=0;b<11;b++)
		sum=sum+arr[b];
	cout<<sum-right;
	return 0;
}

---

数组指定部分逆序重放
将一个数组中的前k项按逆序重新存放。例如将数组8,6,5,4,1前3项逆序重放得到5,6,8,4,1。

输入
输入为两行 第一行两个整数以空格分隔分别为数组元素的个数n（1 < n < 100)以及指定的k(1 <= k <= n)。 第二行是n个整数每两个整数之间用空格分隔。

输出
输出为一行输出按题目要求逆序后数组的整数每两个整数之间用空格分隔。

样例输入
5 3
8 6 5 4 1

样例输出
5 6 8 4 1

#include <bits/stdc++.h>
using namespace std;

//方法1,复制一个数组然后再对原数组进行操作。
int main()
{
	int n, k; //数组长度,前k项
	cin >> n >> k;
	int arr1[n], arr2[n]; //原来数组修改后的数组

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

	for (int b = 0; b < k; b++)
		arr1[b] = arr2[k - b - 1];
	for (int c = 0; c < n; c++)
		cout << arr1[c] << " ";
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

//方法2利用头和尾进行交换注意不能越过中间下标不然等于没交换。
int main()
{
	int n = 0, k = 0;
	cin >> n >> k;
	int arr[n];
	for (int a = 0; a < n; a++)
		cin >> arr[a];
	for (int b = k - 1; b > (k - 1) / 2; b--)
		swap(arr[b], arr[k - 1 - b]);
	for (int c = 0; c < n; c++)
		cout << arr[c] << " ";

	return 0;
}

---

数组逆序存放
将一个数组中的值按逆序重新存放。例如原来的顺序为8,6,5,4,1。要求改为1,4,5,6,8。

输入
输入为两行第一行数组中元素的个数n（1<n<100)第二行是n个整数每两个整数之间用空格分隔。

输出
输出为一行输出逆序后数组的整数每两个整数之间用空格分隔。

样例输入
5
8 6 5 4 1

样例输出
1 4 5 6 8

#include <bits/stdc++.h>
using namespace std;
//和前面的题做法无区别也可以复制一个数组倒序遍历赋值给原数组。
int main()
{
	int n = 0;
	cin >> n;
	int arr[n];
	for (int a = 0; a < n; a++)
		cin >> arr[a];
	for (int b = 0; b < n / 2; b++)
		swap(arr[b], arr[n - 1 - b]);
	for (int c = 0; c < n; c++)
		cout << arr[c] << " ";

	return 0;
}

---

汉诺塔问题
约19世纪末在欧州的商店中出售一种智力玩具在一块铜板上有三根杆最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上条件是一次只能移动一个盘且不允许大盘放在小盘的上面。
这是一个著名的问题几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘且不允许大盘放在小盘上面所以64个盘的移动次数是18,446,744,073,709,551,615
这是一个天文数字若每一微秒可能计算(并不输出)一次移动那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔但很难用计算机解决64层的汉诺塔。假定圆盘从小到大编号为1, 2, …

输入输入为一个整数后面跟三个单字符字符串。 整数为盘子的数目后三个字符表示三个杆子的编号。

输出输出每一步移动盘子的记录。一次移动一行。 每次移动的记录为例如 a->3->b 的形式即把编号为3的盘子从a杆移至b杆。

样例输入2 a b c
样例输出
a->1->c
a->2->b
c->1->b

#include<bits/stdc++.h>
using namespace std;
void Hanoi(int n,char a,char b,char c)
{
	if(n>1){
		Hanoi(n-1,a,c,b);
		cout<<a<<"->"<<n<<"->"<<b<<endl;
		Hanoi(n-1,c,b,c);
	}	
	else if(n==1)
		cout<<a<<"->"<<1<<"->"<<b<<endl;	
}
int main()
{
	int n=0;
	char a=0,b=0,c=0;
	cin>>n>>a>>b>>c;
	Hanoi(n,a,b,c);
	return 0;
}

注意题目要求是左边移到中间而给大家的示意图是从最左边移到最右边不要搞混但他俩本质上是一样的。
1.从一层、两层、三层甚至四层的尝试中我们应该发现的问题也是汉诺塔问题的2个症结点是首先是三根柱子（起始、目标、辅助的身份是不断改变的所以才不容易发现规律。其次是能够直接解决的问题是——当n-1个圆盘在我们的辅助柱子上最大的第n个圆盘在起始柱子上——这种情况我们是能够直接解决的——直接把第n个圆盘从起始柱子上挪到目标柱子上。
2.然后通过这两个发现我们要得到第三个症结点——在哪递归？实际上问题你的答案已经藏在第二个症结点之中。就是用递归来操作实现“n-1个圆盘在我们的辅助柱子上”也就是让“n-1个圆盘从我们的起始柱子上到我们的辅助柱子上”。
3.在第三个症结点的描述中其实又涉及到第一个症结点——柱子身份的转化。
n-1个圆盘是要从起始点（也是n个圆盘一起的起始点移动到他们的目标点（也就是整个问题的辅助点。这里就变成了一个小的n-1层汉诺塔问题。只不过目标柱子发生了转化。然后对于这个n-1的问题又可以变成n-2个盘子的汉诺塔加1个盘子的移动（目标柱又发生转化。
当然这个问题还没有结束现在这个问题已经被我们对半劈开——对于n个盘子的汉诺塔我们首先要把n-1个盘子移到辅助柱子上（这里是一个需要递归的n-1个规模的汉诺塔问题然后把第n个盘子从起点挪到目标——这前一半问题已经解决后一半其实就是把n-1个盘子挪回来（这里又是一个需要递归的n-1个规模的汉诺塔问题从辅助柱移到目标柱（这里的辅助柱变成了子问题的起始柱。
综上汉诺塔问题的处理如下
——如何把n个盘子从起始通过起始柱通过辅助柱移到目标柱
（1把n-1盘子从“起始”（n个盘子中的起始。通过“辅助”（原来的目标移到“目标”（n个盘子中的辅助。
（2把第n个盘子直接从起始到目标
（3要把n-1盘子从“起始”（n个盘子中的辅助。通过“辅助”（n个盘子中的起始移到“目标”（n个盘子中的目标。