课后作业：过程的封装：函数（下）& 指针（上）
最大三角形
任务描述
给出平面内n个点，求以这n个点中的三个点为顶点的三角形的最大面积。三点共线时认为三角形的面积为0。 范围： 3 <= n <= 100 所有的点的坐标为整数，且其绝对值不超过127
相关知识
假设三角形三个顶点为 $(x_1,y_1)$ , $(x_2,y_2)$, $(x_3,y_3)$, 那么面积为 $\frac{1}{2}|(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)|$ 。(证明可用向量积得到）
编程要求
实现 getMaxTriangle() 函数。
测试说明
平台会对你编写的代码进行测试：
测试输入：
5
0 0
1 1
1 -1
-1 -1
-1 1
预期输出：
max area = 2
参考代码
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
//n points are (x[0],y[0]), (x[1],y[1]), ... ,(x[n-1],y[n-1])
double getMaxTriangle(int n, int x[], int y[])
{
// write your code here
int ans = 0;
for (int i=0;i<n;i++) {
for (int j=i+1;j<n;j++) {
for (int k=j+1;k<n;k++) {
int tmp = abs((x[j]-x[i])*(y[k]-y[i])-(x[k]-x[i])*(y[j]-y[i]));
if (tmp > ans) ans = tmp;
}
}
}
return ans/2.0;
}
int main(void)
{
int n, x[101], y[101];
cin >> n;
assert(3 <= n && n <= 100);
for (int i=0;i<n;i++)
cin >> x[i] >> y[i];
cout << "max area = " << getMaxTriangle(n, x, y) << endl;
return 0;
}
孔融分梨
任务描述
孔融没有兄弟姐妹，到了周末，就找堂兄孔明、堂姐孔茹、堂弟孔伟等7个堂兄妹来到家里玩。孔融妈妈买了8个梨给孩子们吃，结果小黄狗桐桐淘气叼走了一个，大花猫鑫鑫偷偷藏了一个。孔融抢过剩下的6个梨，妈妈止住他，说他要和大家平分吃。孔融不高兴，说8个人怎么分6个梨？妈妈说可以用分数解决这个问题。孔融学过分数，说把每个梨切8个相等的块，每个人拿6块就行了。妈妈说不用切那么多块，每个梨切4个相等的块，每个人拿3块正好。孔融糊涂了。孔明说，我来教你。于是孔明给孔融讲起了分数的化简。
分数化简是指，对于正整数m,n,q,p，如果分数 m/n = p/q 且p与q互质，则称p/q是m/n的最简形式，比如12/20的最简形式是3/5；100/8的最简形式是25/2。
请编程帮助孔融将任意一个分数化简成最简形式。先从键盘输入两个整数m和n(1<=m,n<=10000) ，其中m表示分子，n表示分母。然后输出分数化简后的最简形式。
函数原型：int Gcd(int a, int b); 函数功能：计算a和b的最大公约数
编程要求
根据提示，在右侧编辑器补充代码，编写函数使之符合要求。
测试说明
平台会对你编写的代码进行测试：
测试1:
测试输入：
8 14
测试输出：
4/7
测试2:
测试输入：
210 35
测试输出：
6/1
参考代码
#include <iostream>
#include <cassert>
using namespace std;
int Gcd(int m, int n)
{
// write your code here
for (int i=m;i>=1;i--)
if (n%i==0 && m%i==0) return i;
assert(0);
}
int main()
{
int m, n, ans;
cin >> m >> n;
// write your code here
int g = Gcd(m, n);
cout << m/g << '/' << n/g << endl;
return 0;
}
递归法计算游戏人员的年龄
任务描述
本关任务：编写一个使用递归法计算游戏人员年龄的小程序。
有n个人围坐在一起，问第n个人多大年纪，他说比第n-1个人大2岁；问第n-1个人，他说比第n-2个人大2岁,…..,问第3个人，他说比第2个人大2岁；问第2个人，他说比第1个人大2岁。第1个人说自己10岁，问第n个人多大年纪。（范围 n <= 50）
编程要求
根据提示，在右侧编辑器补充代码，使用递归法计算游戏人员年龄并输出。
测试说明
平台会对你编写的代码进行测试：
测试输入：5
预期输出：
18
测试输入：10；
预期输出：
28
参考代码
#include<iostream>
using namespace std;
int f(int n)
{
// write your code here
// make sure that the implementation is by **recursion**
return n==1?10:(f(n-1)+2);
}
int main()
{
// write your code here
int n; cin >> n;
cout << f(n) << endl;
return 0;
}
数组对调
任务描述
设计一个程序，让用户输入两个数组，然后将它们中下标相同的非空元素对调，再输出这两个新的数组。用户输入的两个数组元素数量都小于20个。
限制条件
- 除了
<iostream>之外不可包含其它库； - 只能使用已定义的三个int变量、四个int指针，不能定义别的变量、数组或其它对象 （包括 for (int i;…;…) 也算定义了新的变量 i）。
输入输出示例
第一行 n m 第二行 $a_0$ $a_1$ … $a_{n-1}$ (第一个数组) 第三行 $b_0$ $b_1$ … $b_{m-1}$ (第二个数组)
样例输入:
5 6
1 2 3 4 5
6 5 4 3 2 1
样例输出：
6 5 4 3 2
1 2 3 4 5 1
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int * a = new int [n];
int * b = new int [m];
int tmp, * p1, * p2;
/*Start your code here*/
for (tmp=0; tmp<n; tmp++) cin >> a[tmp];
for (tmp=0; tmp<m; tmp++) cin >> b[tmp];
for (p1=a, p2=b; p1-a<n && p2-b<m; p1++, p2++)
tmp = *p1, *p1 = *p2, *p2 = tmp;
for (tmp=0; tmp<n; tmp++) cout << a[tmp] << " \n"[tmp==n-1];
for (tmp=0; tmp<m; tmp++) cout << b[tmp] << " \n"[tmp==m-1];
/*end your code*/
return 0;
}
加密字符
任务描述
编写程序，将输入的一个字符串进行加密和解密。加密时，每个字符依次反复加上[8,7,3,4,9,6,2]中的数字，如果范围超过ASCII码的032（空格）- 122（'z'），则进行模运算。解密与加密的顺序相反。请编写加密和解密的过程，并打印出结果。注：要加密的字符串长度不会超过30。
说明
- 字符的范围。无论时输入的字符还是加密后的字符，字符的ASCII值都需要控制在032（空格）- 122（’z’）之间，即[32,122]
- 加密。把待加密字符串7个字符分为一组，每组对应位依次加上[8,7,3,4,9,6,2] 中的数字。如果执行加法后得到的数值 N 超过[32,122]，则需要调整。加密公式为32+(N-32)%(122-32+1)，当N>122时在本题目中加密公式可简化为 N-91。
- 解密。解密的过程与加密的过程顺序正好相反。如果执行减法后得到的数值不在[32,122]，则需要调整。解密公式为32+[N-32+(122-32+1)]%(122-32+1)；当N＜32时在本题目中可简化为 N+91.
输入输出示例
input:
wherewithal
output:
$ohvn"k!odp
wherewithal
| 待加密字符 | 加法运算 | 加密后字符的ASCII码 | 加密后字符 | 减法运算 | 解密后字符的ASCII码 | 解密后字符 |
|---|---|---|---|---|---|---|
| w | 119+8=127 | 127-91=36 | $ | 36-8=28 | 28+91=119 | w |
| h | 104+7=111 | 111 | o | 111-7=104 | 104 | h |
| e | 101+3=104 | 104 | h | 104-3=101 | 101 | e |
| r | 114+4=118 | 118 | v | 118-4=114 | 114 | r |
| e | 101+9=110 | 110 | n | 110-9=101 | 101 | e |
| w | 119+6=125 | 125-91=34 | ” | 34-6=28 | 28+91=119 | w |
| i | 105+2=107 | 107 | k | 107-2=105 | 105 | i |
| t | 116+8=124 | 124-91=33 | ! | 33-8=25 | 25+91=116 | t |
| h | 104+7=111 | 111 | o | 111-7=104 | 104 | h |
| a | 97+3=100 | 100 | d | 100-3=97 | 97 | a |
| l | 108+4=112 | 112 | p | 112-4=108 | 108 | l |
参考代码
#include <iostream>
using namespace std;
void encrypt(char * s)
{
// write your code here
int t[7] = {8,7,3,4,9,6,2};
for (int i=0;s[i];i++) {
s[i] += t[i%7];
if (s[i] > 122) s[i] -= 91;
}
}
void decrypt(char * s)
{
// write your code here
int t[7] = {8,7,3,4,9,6,2};
for (int i=0;s[i];i++) {
s[i] -= t[i%7];
if (s[i] < 32) s[i] += 91;
}
}
// do not change main function
int main(void)
{
char s[35];
cin.getline(s, 31);
encrypt(s);
cout << s << endl;
decrypt(s);
cout << s << endl;
return 0;
}
机器人的路线数量（附加题，选做）
任务描述
如图所示，有一个m行n列的网格。起点坐标为(m,n),终点坐标为(1,1)。有一个机器人从起点出发，每次移动只能 移动到当前方格的下方方格或右方方格。请设计函数计算，给定方格的行m列n，机器人可以有几种路线到达终点。
例如，当m = n = 2时，共有两种可能的路线。
编程要求
程序输入两个整数m,n，输出 路线数量。
测试说明
平台会对你编写的代码进行测试：
测试输入：
1 1
预期输出：
1
测试输入：
2 2
预期输出：
2
测试输入：
5 5
预期输出：
70
提示：
可以将原问题转化为两个子问题： 如果在(m, n)向右走，则变成了求解输入为(m,n-1)的子问题，即列数变少1单位。如果向下走，则变成了求解输入为(m-1,n)的子问题，即行数变少1单位。而原问题的答案就是两个子问题答案之和。
上述将原问题分解为子问题的递归思路尽管正确，但是会造成许多重复计算。例如 $f(5,5) = f(5,4) + f(4,5);f(4,5) = f(3,5) + f(4,4);f(5,4) = f(4,4) + f(5,3)$ 可以注意到f(4,4)被重复计算。实际上当mn很大时，重复计算现象会很严重。而事实上对于一个(i,j),f(i,j)只需要计算一次。我们可以用一个二维数组$dp[][]$记录每个计算结果，即$dp[i][j] = f(i,j)$.首先我们将$dp[i][1],dp[1][j]$都初始化为1，对于其他的$i,j$,按照一定的顺序计算$dp[i][j] = dp[i-1][j] + dp[i][j-1]$。
注意：此题目测试集可以保证使用递归函数不会超时或栈溢出。
不要说我们一无所有，我们要做全天下的主人 ——《国际歌》
参考代码
#include <iostream>
using namespace std;
int cal_routines(int m ,int n){
// write your code here
return (m==1||n==1)?1:(cal_routines(m,n-1) + cal_routines(m-1,n));
}
// NEVER EDIT THE MAIN FUNCTION
int main()
{
int m, n;
cin >> m >> n;
cout << cal_routines(m, n) << endl;
}
二进制小数（附加题，选做）
任务描述
给定一个十进制下的非负小数（包括整数），输出它在二进制下的表示，如果有循环节，在循环节两边加上小括号表示。如 $3.6{(10)} = 11.(1001){(2)}$
编程要求
根据提示，在右侧编辑器补充代码。 不限制具体实现形式，请综合的使用所学知识。
测试说明
输入
一个非负小数n（包括整数） (0<=n<65536)，如果存在小数点，n的小数点后不超过2位。 保证n无前导0，但小数点末尾可能有0。
输出
输出n的二进制表示。 请保证输出的整数部分无前导0。 小数部分如果是0，不输出小数点及小数部分。 小数部分如果非0且是有限的，不输出末尾的0。 小数部分如果非0且是无限的，则必有循环节，循环节用小括号括起来。且所有表示中输出长度最短的表示。
样例输入1：10.00
样例输出1：1010
样例解释1：小数部分为0，直接输出整数部分。
样例输入2：5.25
样例输出2：101.01
样例解释2：小数部分非0且有限。
样例输入3：0.1
样例输出3：0.0(0011)
样例解释3：小数部分非0且无限，这时候可以表示为0.0(0011),0.00(0110),0.0(00110011)等，其中长度最短的是0.0(0011)。
参考代码
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
const double eps = 1e-8;
int vis[100];
int s[111], tot;
int main(void) {
double n;
cin >> n;
int x = (int)(n+eps);
int y = (n - (int)x)*100+eps;
int ff=0;
for (int i=20;i>=0;i--) if (ff || (x>>i)&1) {
cout << ((x>>i)&1);
ff=1;
}
if (ff == 0) cout << 0 << '\n';
if (y == 0) return 0;
cout << '.';
memset(vis,-1,sizeof(vis));
int f=0, v;
vis[y] = 0;
for (int i=0;i<1000;i++) {
y = 2*y;
if (y >= 100) s[tot++]=1, y -= 100;
else s[tot++]=0;
if (vis[y] >= 0) {f=1; v=vis[y]; break;}
vis[y] = tot;
if (y == 0) break;
}
if (f == 0) {
for (int i=0;i<tot;i++) cout << s[i];
cout << '\n';
} else {
for (int i=0;i<v;i++) cout << s[i];
cout << "(";
for (int i=v;i<tot;i++) cout << s[i];
cout << ")\n";
}
return 0;
}
游戏（附加题，选做）
任务描述
X和Y正在玩一个游戏。 这个游戏初始时有n个小于10的非负整数排成一排，X和Y轮流进行自己的回合，由X先开始。 在自己的回合里， 1）玩家可以选择一个非负整数$a_i$，并把这个数字变成比$a_i$小的非负整数； 2）也可以选择一个0，并且把这个0和它后面的数都去掉。
如果某个玩家在自己回合内去掉了所有数字，那么他将获得胜利。 X和Y都非常聪明，所以他们都会使用最佳的策略。请问X和Y谁会是最终的赢家？
范围：$1\leq n\leq 5, 0 \leq a_i \leq 3$.
提示
使用递归来计算某个局面下X或Y的最佳决策。 假设当前处于某个局面，最佳决策是： 1）如果这个局面中某个决策演化到下一个局面，下一个局面对于先行者是必败的状态，那么当前的决策者必然选择这一决策，从而获胜。 2）如果这个局面下的所有决策演化到下一个局面，下一个局面对于先行者都是必胜的状态，那么决策者无论怎么选择，都是必败。 3）对于这个游戏，“剩下0个数”的局面是一个对于先行者的必败的状态。
使用伪代码表示这一过程就是：
bool f(局面 A)
{
for each (从局面 A 可到达的) 局面 B {
// 如果局面 B 是必败局面
// 则玩家就会选择这个 局面 B（使对手必败）
// 从而在局面 A 是必胜局面
if (f(B) == false)
return true;
}
// 如果不存在局面 A 可到达的局面 或
// 局面 A 可到达的都是必胜局面
// 则局面 A 是必败局面
return false;
}
可以使用一个数组以及一个整数（表示该数组的长度）来表示一个局面，可以遍历数组来找到局面 A 可到达的所有局面 B。
最后，如果初始局面是必胜局面，则X赢，否则Y赢。
编程要求
根据提示，在右侧编辑器补充代码。
测试说明
输入
第一行一个正整数n $(1\leq n\leq 5)$，第二行n个非负整数$a_1,a_2,…,a_n (0\leq a_i\leq 3)$, 两个相邻的数以1个空格相间。
输出
输出赢家，‘X’ 或 ‘Y’。
样例输入：
4
0 3 2 1
样例输出：X
样例解释：X在第一回合选择第1个0，局面变成空。因此X必胜。
样例输入：
3
1 3 2
样例输出：Y
参考代码
#include <iostream>
#include <cstring>
using namespace std;
int f[7][1000000];
bool dfs(int s, int n) {
if (f[n][s]!=-1) return (bool)f[n][s];
if (n == 0) return false;
bool ok=false;
int o = 1;
for (int i=0;i<n;i++) {
int k = (s / o % 10);
if (k > 0) {
for (int j=0;j<k;j++) {
if (!dfs(s-k*o+j*o, n)) {ok = true; break;}
}
} else {
if (!dfs(s/(10*o), n-i-1)) ok = true;
}
o *= 10;
}
f[n][s]=ok;
return ok;
}
int main(void) {
int n, t[10];
cin >> n;
for (int i=0;i<n;i++) cin >> t[i];
memset(f, -1, sizeof(f));
int s=0;
for (int i=0;i<n;i++) s=(s*10)+t[i];
bool f = dfs(s, n);
cout << (f?"X\n":"Y\n");
return 0;
}