算法实战(四)

题目来源(PAT题目)

7-22 龟兔赛跑

题目

乌龟与兔子进行赛跑，跑场是一个矩型跑道，跑道边可以随地进行休息。乌龟每分钟可以前进3米，兔子每分钟前进9米；兔子嫌乌龟跑得慢，觉得肯定能跑赢乌龟，于是，每跑10分钟回头看一下乌龟，若发现自己超过乌龟，就在路边休息，每次休息30分钟，否则继续跑10分钟；而乌龟非常努力，一直跑，不休息。假定乌龟与兔子在同一起点同一时刻开始起跑，请问T分钟后乌龟和兔子谁跑得快？

输入格式：
输入在一行中给出比赛时间T（分钟）。

输出格式：
在一行中输出比赛的结果：乌龟赢输出@@，兔子赢输出^_，平局则输出--；后跟1空格，再输出胜利者跑完的距离。

题解

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int main() {
    int i,T, time= 0, sTortoise = 0, sRabbit = 0;
    scanf("%d", &T);
    while (time < T) {  // 退出循环之后也就是time>=T,由于time每次+1,所以退出循环之后，time=T 符合题意
        time++;
        sTortoise += 3; // 跑了1分钟，距离+3
        sRabbit += 9; // 兔子跑了1分钟，距离+9

        if (time % 10 == 0) {
            if (sRabbit - sTortoise > 0) { 
                 // 通过for循环进行控制兔子休息，乌龟跑
                 // 控制条件里面要加上time < T,必须满足这个条件,有可能兔子在休息的时候，乌龟已经到达终点
                for (i = 1; i <= 30 && time < T; i++) {
                    time ++;        // 休息1分钟
                    sTortoise += 3; // 乌龟跑了1分钟，距离+3
                }
            }
            else { // 继续跑10分钟
                for (i = 1; i <= 10 && time < T; i++) {
                    time++;
                    sRabbit += 9;   // 兔子跑了1分钟，距离+9
                    sTortoise += 3; // 乌龟跑了1分钟，距离+3
                }
            }
        }
    }
    // 循环完之后，通过他们两个的距离进行判断谁赢
    if (sRabbit > sTortoise)
        printf("^_^ %d", sRabbit);
    else if (sRabbit < sTortoise)
        printf("@_@ %d", sTortoise);
    else
        printf("-_- %d",sRabbit);
    return 0;
}

7-24 约分最简分式

题目

分数可以表示为分子/分母的形式。编写一个程序，要求用户输入一个分数，然后将其约分为最简分式。最简分式是指分子和分母不具有可以约分的成分了。如6/12可以被约分为1/2。当分子大于分母时，不需要表达为整数又分数的形式，即11/8还是11/8；而当分子分母相等时，仍然表达为1/1的分数形式。

输入格式：
输入在一行中给出一个分数，分子和分母中间以斜杠/分隔，如：12/34表示34分之12。分子和分母都是正整数（不包含0，如果不清楚正整数的定义的话）。

提示：

对于C语言，在scanf的格式字符串中加入/，让scanf来处理这个斜杠。
对于Python语言，用a,b=map(int, input().split(‘/’))这样的代码来处理这个斜杠。
输出格式：
在一行中输出这个分数对应的最简分式，格式与输入的相同，即采用分子/分母的形式表示分数。如
5/6表示6分之5。

题解

#include<stdio.h>

// 寻找最大公约数
int gcd(int a,int b){
    if(b == 0)
        return a;
    return gcd(b,a%b);
}

int main(){
    int numerator,denominator,common; // 分子 分母
    scanf("%d/%d",&numerator,&denominator);
    common=gcd(numerator,denominator);
    if(common!=1){ // 有最大公约数
        numerator/=common;
        denominator/=common;
    }else if(numerator==denominator){
        numerator=denominator=1;
    }
    printf("%d/%d",numerator,denominator);
    return 0;
}

求最大公约数方法：三种方法

7-25 念数字

题目

输入一个整数，输出每个数字对应的拼音。当整数为负数时，先输出fu字。十个数字对应的拼音如下：

0: ling
1: yi
2: er
3: san
4: si
5: wu
6: liu
7: qi
8: ba
9: jiu
输入格式：
输入在一行中给出一个整数，如：1234。

提示：整数包括负数、零和正数。

输出格式：
在一行中输出这个整数对应的拼音，每个数字的拼音之间用空格分开，行末没有最后的空格。如
yi er san si。

原理

通过scanf获得数字之后,如果是0的话，通过0在maps集合里面进行索引，结束程序即可；如果为负数的话，如果是取为相反数，并且把标志位设为true; 然后把每一位逆序保存在数组当中去，然后如果flag为true, 说明就是负数，所以要打印出来“fu”,然后的话，通过从后往前遍历数组，然后在maps集合进行索引，输出字符即可。

题解

#define _CRT_SECURE_NO_WARNINGS
#include<map>
#include<stdio.h>
#include<string>
#include <iostream>
using namespace std;

void initializeMap(std::map<int, std::string>& maps) {
    maps = {
        {0, "ling"},{1, "yi"},{2, "er"},{3, "san"},{4, "si"},{5, "wu"},{6, "liu"},{7, "qi"},{8, "ba"},{9, "jiu"} };
}

int main() {
    map<int,string> maps;
    initializeMap(maps);
    int number, count = 0, array[10] = { 0 };
    bool flag=false;   // 通过flag位来标志是不是负数
    scanf("%d", &number);
    if (number == 0) { // 为0
        cout << maps[number];
        return 0;
    }
    else {
        if (number < 0) {
            flag = true;
            number = -number;
        }
        while (number) {  // 把数字的每一位保存在数组中
            array[count++] = number % 10;
            number /= 10;
        }
        if (flag == true)
            printf("fu ");
        
        for (int i = count - 1; i >= 0; i--) { // 从后往前遍历数组，然后通过数组里面存放的值在maps集合里面进行索引，把结果打印出来。
            if (i == count - 1)
                cout << maps[array[i]];
            else
                cout << " " << maps[array[i]];
        }
    }
    return 0;
}