递推作业
一、单词翻转
翻转形式为：
输入hello world
输出olleh dlrow
输入只有一行，为一个字符串，不超过500个字符。单词之间以空格隔开。
开始的错误版本：
void reverse()
{
char a[20];
cin>>a;
int l = strlen(a);
int i = 0;
for(i = l - 1; i >= 0; i--)cout<<a[i];
cout<<" ";
reverse();
}
错误原因为：
- 最后一个单词后面多出一个空格。
-
reverse()函数会一直运行，没办法回到main()函数 - 并且这样应该也不算递归吧。
改：用cin.getline()函数获得整行后再处理。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
void reverse(char r[])
{
int l = strlen(r);
int i, j = l - 1, count = 0, positionOfLastSpace = 0;
int lengthOfTemp = 0;
char r2[1000];
for (i = 0;i < l;i++)
{
if (r[i] == ' ')
{
count++;
positionOfLastSpace = i;
}
}
lengthOfTemp = l - positionOfLastSpace - 1;
if (count == 0)
{
for (i = l - 1; i >= 0; i--)cout << r[i];
}
else
{
strncpy(r2, r, l - lengthOfTemp - 1);
reverse(r2);
cout << " ";
for (i = 1;i <= lengthOfTemp; i++)cout << r[l - i];
}
}
int main()
{
char a[1000];
cin.getline(a, 1000);
reverse(a);
return 0;
}
我的果然不是好方法。。。别处看来的，much better than mine
不过和我的一样，在POJ上显示Wrong Answer。。
测试了很多种情况，没发现不对的，暂时不知道WA的原因。
更新：WA可能是因为POJ把tab键也当作和空格一样的分隔单词的作用，我们都是把tab当普通字符放到单词里的
更新：POJ通过了，tab制表符键也当作普通字符处理的，但是Coursera仍然Wrong Answer
#include<iostream>
#include<string>
using namespace std;
char a[501] = { '\0' };
int j = 0;
void convert()
{
j++;
if (a[j] != ' '&&a[j]!='\0') convert(); //convert函数里j++用于走到下一个空格
j--; //j--再从这个空格往回输出回去
cout << a[j]; //然后回到主函数，由i带领到下一个空格继续
}
int main()
{
cin.getline(a, 501);
for (int i=-1; i < 501; i++) //i==-1输出第一个前面没有空格的单词，即使第一个字符
{ //就是空格，a[i] == ' '也能保证成功输出它后面的单词
if (a[i] == ' ' || i == -1) //在字符串里碰到空格时
{ //执行convert输出空格后的单词
j = i; //i记录着空格的位置
convert(); //然后把空格的位置传递给j
}
}
cout << '\b';
return 0;
}
二、角谷猜想
所谓角谷猜想，是指对于任意一个正整数，如果是奇数，则乘3加1，如果是偶数，则除以2，得到的结果再按照上述规则重复处理，最终总能够得到1。如，假定初始整数为5，计算过程分别为16、8、4、2、1。
程序要求输入一个整数，将经过处理得到1的过程输出来。
最后一行输出"End"，如果输入为1，直接输出"End"
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
bool isEven(int a)
{
if(a % 2 == 0)return true;
else return false;
}
void jiaogu(int a)
{
if(a == 1)cout<<"End";
else
{
if(!isEven(a))
{
cout<<a<<"*3+1="<<a * 3 + 1<<endl;
a = a * 3 + 1;
jiaogu(a);
}
else if(isEven(a))
{
cout<<a<<"/2="<<a / 2<<endl;
a = a / 2;
jiaogu(a);
}
}
}
int main()
{
int input;
cin>>input;
jiaogu(input);
return 0;
}
三、排队游戏（括号匹配化简版）
输出匹配的两种字符在字符串中的位置
范例输入：((()(())())(()))
范例输出：
2 3
5 6
4 7
8 9
1 10
12 13
11 14
0 15
自己尚未编出来。。
网上看到一个超级厉害的。。不到十行就搞定了。。。关键程序只有三行。。
虽然已经理清了程序的运行过程，自己在纸上一步一步的模拟，确实是很好的实现了题目的要求，但是还是感觉没领会到这个解法到底是如何做到的。。好笨。。
#include<iostream>
using namespace std;
//注释中假设第一种字符都是左括号，实际用了sex变量存储第一种字符的类型
int a[1111];
char s[1111];
/*
a里存放的是左括号的位置
例：若a[4]==5，指第4个左括号在s[5]处
a[1]==0指第1个左括号在s[0]处即第一个字符
*/
int i, n = 0; //n为左括号的数量
int main()
{
cin >> s;
char sex = s[0]; //sex存放第一种字符的类型
for (i = 0; s[i]; ++i)
if (s[i] == sex) a[++n] = i;
else cout << a[n--] << " " << i << endl;
/*碰到左括号，左括号数n加一后在a[n]处标记目前最后一个左括号的位置i
碰到右括号，先输出a[n]即目前最后一个左括号的位置。
因为此时是第一次碰到右括号，因此i即为再将n减1
*/
return 0;
}
此程序的运行流程
四、括号匹配
在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.
样例输入
)(rttyy())sss)(```
样例输出
```((ABCD(x)
$$
)(rttyy())sss)(
? ?$```
**想了一天，和第三题一样，还是做不来。。。四道递归题只做出来一个。。好笨。。**
### 五、递归搜索（八皇后）
**搜索问题：
1- 枚举可能的动作（判断）
2- 尝试可能的动作
3- 递归计算
4- 撤销这个动作（要尝试下一种可能了）
5- 按要求返回值（位置或数量）**
> 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
`int f(n)`解决从第n到7行放皇后的问题，返回可能性的数量
f(0) = (在(0,0)放皇后)f(1) + (在(0,1)放皇后)f(1) + ··· + (在(0,7)放皇后)*f(1)
f(8)=1 //搜索到了f(8)说明前面已经放好了
### 六、递归搜索优化（棋盘跳马）
> 已知在一个n*m棋盘上马走斜日字，棋盘上有用@字符标记的石头，不能走到有石头的格子里，也不能往石头方向跳（蹩马腿）。输入起点终点的坐标，输出最短几步能从起点到达终点。
需用到列表。学习后再写。
