Coursera C程序设计进阶 第三周 递归

1 . 单词翻转

来源:POJ ( Coursera 声明:在 POJ 上完成的习题将不会计入 Coursera 的最后成绩。)
注意:总时间限制;1000ms 内存限制;65536kB

  描述

      输入一个句子(一行),将句子中的每一个单词翻转后输出。

  输入

      只有一行,为一个字符串,不超过500个字符。单词之间以空格隔开。所谓单词指的是所有不包含空格的连续的字符。
      这道题请用cin.getline输入一行后再逐个单词递归处理。

  输出

      翻转每一个单词后的字符串,单词之间的空格需与原文一致。

  样例输入

hello    world.


  样例输出

olleh    .dlrow


  解答

#include <iostream>
using namespace std;

int main(){
    int i = 0, j, k;
    char sen[501], temp;
    cin.getline(sen, 501);
    while (sen[i]){
        while (sen[i] == ' ')
            i++;
        if (!sen[i])
            break;
        j = i;
        while (sen[j] != ' ' && sen[j])
            j++;
        for (k = i; k < (i + j) / 2; k++){
            temp = sen[k];
            sen[k] = sen[j - 1 + i -k];
            sen[j - 1 + i - k] = temp;
        }
        i = j;
    }
    cout << sen << endl;

    return 0;
}

2 . 角谷猜想

来源:POJ ( Coursera 声明:在 POJ 上完成的习题将不会计入 Coursera 的最后成绩。)
注意:总时间限制;1000ms 内存限制;65536kB

  描述

      所谓角谷猜想,是指对于任意一个正整数,如果是奇数,则乘3加1,如果是偶数,则除以2,得到的结果再按照上述规则重复处理,最终总能够得到1。如,假定初始整数为5,计算过程分别为16、8、4、2、1。
      程序要求输入一个整数,将经过处理得到1的过程输出来。

  输入

      一个正整数

  输出

      从输入整数到1的步骤,每一步为一行,每一部中描述计算过程,假定输入为7,则输出为:

7*3+1=22
22/2=11
11*3+1=34
34/2=17
17*3+1=52
52/2=26
26/2=13
13*3+1=40
40/2=20
20/2=10
10/2=5
5*3+1=16
16/2=8
8/2=4
4/2=2
2/2=1

      最后一行输出"End",如果输入为1,直接输出"End"

  样例输入

5


  样例输出

5*3+1=16
16/2=8
8/2=4
4/2=2
2/2=1
End


  解答

#include <iostream>
using namespace std;

int cal(int n){
    if (n == 1)
        cout << "End" <<endl;
    else if (n % 2 == 1){
        cout << n << "*3+1=" << n * 3 + 1 << endl;
        n = n * 3 + 1;
        return cal(n);
    }
    else {
        cout << n << "/2=" << n / 2 << endl;
        n = n / 2;
        return cal(n);
    }
}

int main(){
    int n;
    cin >> n;
    cal(n);
    return 0;
}

3 . 排队游戏

来源:POJ ( Coursera 声明:在 POJ 上完成的习题将不会计入 Coursera 的最后成绩。)
注意:总时间限制;1000ms 内存限制;65536kB

  描述

      在幼儿园中,老师安排小朋友做一个排队的游戏。首先老师精心的把数目相同的小男孩和小女孩编排在一个队列中,每个小孩按其在队列中的位置发给一个编号(编 号从0开始)。然后老师告诉小朋友们,站在前边的小男孩可以和他后边相邻的小女孩手拉手离开队列,剩余的小朋友重新站拢,再按前后相邻的小男孩小女孩手拉 手离开队列游戏,如此往复。由于教师精心的安排,恰好可以保证每两个小朋友都能手拉手离开队列,并且最后离开的两个小朋友是编号最小的和最大的两个小朋 友。(注:只有小男孩在前,小女孩在后,且他们两之间没有其他的小朋友,他们才能手拉手离开队列)。请根据老师的排队,按小女孩编号从小到大的顺序,给出 所有手拉手离开队列的小男孩和小女孩的编号对。

  输入

      用一个字符串代表小朋友队列。字符串中只会出现两个字符(样例输入里用的是 括号但实际数据则不一定),分别代表小男孩和小女孩,首先出现的字符代表小男孩,另一个字符代表小女孩。小孩总数不超过100

  输出

      按小女孩编号顺序,顺序输出手拉手离开队列的小男孩和小女孩的编号对,每行一对编号,编号之间用一个空格分隔。

  样例输入

((()(())())(()))


  样例输出

2 3
5 6
4 7
8 9
1 10
12 13
11 14
0 15ji


  解答

#include<iostream>
#include<stdio.h>
using namespace std;

int main()
{
    char boy, temp;
    int end = 0, num = 0;
    char a[55];
    scanf("%c", &boy);
    a[0] = 0;
    while (scanf("%c", &temp) != EOF)
    {
        if (temp == boy)
        {
            end++;
            num++;
            a[end] = num;
        }
        else
        {
            num++;
            printf("%d %d\n", a[end], num);
            end--;
            if (end < 0) return 0;
        }
    }
    return 0;
}

4 . 扩号匹配问题

来源:POJ ( Coursera 声明:在 POJ 上完成的习题将不会计入 Coursera 的最后成绩。)
注意:总时间限制;1000ms 内存限制;65536kB

  描述

      在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括号,输出原来字符串,并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

  输入

      输入包括多组数据,每组数据一行,包含一个字符串,只包含左右括号和大小写字母,字符串长度不超过100
      注意:cin.getline(str,100)最多只能输入99个字符!

  输出

      对每组输出数据,输出两行,第一行包含原始输入字符,第二行由"$","?"和空格组成,"$"和"?"表示与之对应的左括号和右括号不能匹配。

  样例输入

((ABCD(x)
)(rttyy())sss)(


  样例输出

((ABCD(x)
$$
)(rttyy())sss)(
?            ?$


  解答

#include<iostream>
#include<cstring>
using namespace std;

char c[200];
int match(int pos);

int main(){

    while (cin.getline (c, 101)) {
        int l = strlen(c);
        for (int i = 0; i < l; i++) {
            cout << c[i];
            if (c[i] != '(' && c[i] != ')'){
                c[i] = ' ';
            }
        }
        cout << endl;
        for (int i = 0; i < l; i++){
            if (c[i] == '('){
                int pos = i;
                match(pos);
            }
        }
        for (int i = 0; i < l; i++){
            if (c[i] == ')'){
                c[i] = '?';
            }
            cout << c[i];
        }
        cout << endl;
    }
}
int match(int pos){
    int r = pos + 1;
    while (1){
        if (c[r] == ')'){
            c[pos] = ' ';
            c[r] = ' ';
            return r;
        }
        else if (c[r] == '('){
            match(r);
        }
        else if (c[r] == 0){
            c[pos] = '$';
            return r;
        }
        else{
            r++;
        }

    }
}

tag(s): C++
show comments · back · home
Edit with markdown