一、單詞翻轉
翻轉形式為：
輸入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()函數(shù)會一直運行，沒辦法回到main()函數(shù) - 并且這樣應該也不算遞歸吧。
改：用cin.getline()函數(shù)獲得整行后再處理。
#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上顯示W(wǎng)rong Answer。。
測試了很多種情況，沒發(fā)現(xiàn)不對的，暫時不知道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函數(shù)里j++用于走到下一個空格
j--; //j--再從這個空格往回輸出回去
cout << a[j]; //然后回到主函數(shù)，由i帶領到下一個空格繼續(xù)
}
int main()
{
cin.getline(a, 501);
for (int i=-1; i < 501; i++) //i==-1輸出第一個前面沒有空格的單詞，即使第一個字符
{ //就是空格，a[i] == ' '也能保證成功輸出它后面的單詞
if (a[i] == ' ' || i == -1) //在字符串里碰到空格時
{ //執(zhí)行convert輸出空格后的單詞
j = i; //i記錄著空格的位置
convert(); //然后把空格的位置傳遞給j
}
}
cout << '\b';
return 0;
}
二、角谷猜想
所謂角谷猜想，是指對于任意一個正整數(shù)，如果是奇數(shù)，則乘3加1，如果是偶數(shù)，則除以2，得到的結果再按照上述規(guī)則重復處理，最終總能夠得到1。如，假定初始整數(shù)為5，計算過程分別為16、8、4、2、1。
程序要求輸入一個整數(shù)，將經(jīng)過處理得到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
自己尚未編出來。。
網(wǎng)上看到一個超級厲害的。。不到十行就搞定了。。。關鍵程序只有三行。。
雖然已經(jīng)理清了程序的運行過程，自己在紙上一步一步的模擬，確實是很好的實現(xiàn)了題目的要求，但是還是感覺沒領會到這個解法到底是如何做到的。。好笨。。
#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為左括號的數(shù)量
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;
/*碰到左括號，左括號數(shù)n加一后在a[n]處標記目前最后一個左括號的位置i
碰到右括號，先輸出a[n]即目前最后一個左括號的位置。
因為此時是第一次碰到右括號，因此i即為再將n減1
*/
return 0;
}
四、括號匹配
在某個字符串（長度不超過100）中有左括號、右括號和大小寫字母；規(guī)定（與常見的算數(shù)式子一樣）任何一個左括號都從內到外與在它右邊且距離最近的右括號匹配。寫一個程序，找到無法匹配的左括號和右括號，輸出原來字符串，并在下一行標出不能匹配的括號。不能匹配的左括號用"$"標注,不能匹配的右括號用"?"標注.
樣例輸入
)(rttyy())sss)(```
樣例輸出
```((ABCD(x)
$$
)(rttyy())sss)(
? ?$```
**想了一天，和第三題一樣，還是做不來。。。四道遞歸題只做出來一個。。好笨。。**
### 五、遞歸搜索（八皇后）
**搜索問題：
1- 枚舉可能的動作（判斷）
2- 嘗試可能的動作
3- 遞歸計算
4- 撤銷這個動作（要嘗試下一種可能了）
5- 按要求返回值（位置或數(shù)量）**
> 在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
`int f(n)`解決從第n到7行放皇后的問題，返回可能性的數(shù)量
f(0) = (在(0,0)放皇后)f(1) + (在(0,1)放皇后)f(1) + ··· + (在(0,7)放皇后)*f(1)
f(8)=1 //搜索到了f(8)說明前面已經(jīng)放好了
### 六、遞歸搜索優(yōu)化（棋盤跳馬）
> 已知在一個n*m棋盤上馬走斜日字，棋盤上有用@字符標記的石頭，不能走到有石頭的格子里，也不能往石頭方向跳（蹩馬腿）。輸入起點終點的坐標，輸出最短幾步能從起點到達終點。
需用到列表。學習后再寫。