C语言刷题日记(附详解)(2)

一、有理数加法

输入格式：

输入在一行中按照a1/b1 a2/b2的格式给出两个分数形式的有理数，其中分子和分母全是整形范围内的正整数。

输出格式：

在一行中按照a/b的格式输出两个有理数的和。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

输入:1/6 1/4
输出:5/12
输入:4/9 5/9
输出:1

思路提示：此题算是较为常规的算法题，如果没有思路，不妨拿出笔和纸，在草纸上按照正常分数相加运算的过程编写代码~(需要注意如何判断分子分母相等时不需要输出‘/’)

答案：

#include<stdio.h>
int main()
{int a1 = 0, a2 = 0;int b1 = 0, b2 = 0;scanf("%d/%d %d/%d", &a1, &a2, &b1, &b2);int num1 = a1 * b2 + b1 * a2;int num2 = a2 * b2;int num = 0;int min = 0;int i = 0;min = (num1 < num2) ? num1 : num2;for (i = 2; i <= min; i++){if (num1 % i == 0 && num2 % i == 0){num = i;//最大公约数}}if (num != 0){num1 /= num;num2 /= num;}if (num2 == 1)printf("%d", num1);elseprintf("%d/%d", num1 , num2);return 0;
}

题解：主要的思路其实就是按照正常运算分数加法来一步步往下走，我们定义两个整形变量num1和num2，分别用来存放得到的分子和分母，然后我们寻找到分子和分母谁更小，用设定最小值为for循环的极限范围，只要num1和num2能同时被i整除，那么i就是两者的公约数。直到for循环完最后一次我们就能找到最大公约数，而后将分子分母同时除以最大公约数，便能得到两者约分后的的最终值。最后只需要判断一下，分别设置输出格式就好了~

二、龟兔赛跑

乌龟每分钟可以前进3米，兔子每分钟前进9米；兔子每跑10分钟回头看一下乌龟，若发现自己超过乌龟，就在路边休息，每次休息30分钟，否则继续跑10分钟；乌龟一直跑，不休息。假定乌龟与兔子在同一起点同一时刻开始起跑，请问T分钟后乌龟和兔子谁跑得快？

输入格式：

输入一个时间T（分钟）

输出格式：

乌龟赢输出@_@，兔子赢输出^_^，平局则输出-_-，后跟一空格，再输出胜利者跑完的距离。

输入:173
输出:@_@ 519

思路提示：最开始提交的版本，我当数学应用题来做了，我是分别按照不同时间分别判断兔子和乌龟谁领先，谁落后，然后发现是有规律的，竟然“误打误撞”的就做出来了~

大概思路可以看这个表格：

当时间从0流逝到90时刻时，正好两者又回到了同一起跑线，此为一次循环，当输入的时间比90大时，我们可以不断经历此循环，每次循环使时间减少90，并且乌龟和兔子运动的距离都增加270，直到时间小于90，停止循环，然后通过此表格按照时间计算两者的距离并比较。

答案1：

int main()
{int minute = 0;int rabrun = 0;int turrun = 0;scanf("%d", &minute);while (minute > 90){minute -= 90;rabrun += 270;turrun += 270;}if (minute % 30 == 0 || minute == 45)printf("-_- %d", turrun + minute * 3);else if (minute > 0 && minute < 30){if (minute < 10)printf("^_^ %d", rabrun + minute * 9);elseprintf("^_^ %d", rabrun + 90);}else if (minute > 30 && minute < 45)printf("@_@ %d", turrun + minute * 3);else if (minute > 45 && minute < 60){if (minute < 50)printf("^_^ %d", rabrun + minute * 9);elseprintf("^_^ %d", rabrun + 180);}else if (minute > 60 && minute < 90)printf("@_@ %d", turrun + minute * 3);return 0;
}

此种方法我感觉还是比较好理解的，但提交之后我觉得这个代码是否过于麻烦了？因为这好像只是我在算，而并不是计算机在算...于是我又尝试使用题目给的条件，编写一个较为简单的答案。

思路提示：使用循环的方式代表流逝的时间，创建整型变量time，time++代表时间流逝一分钟，而每流逝一分钟，乌龟的路程+3，兔子的路程+9，并且利用if语句中添加各种限制条件，使得函数实现兔子十分钟看一次乌龟，不休息的时候才能看，领先乌龟时休息的功能。最后时间time等于输入的时间时跳出循环，最后对比乌龟与兔子的路程并按照对应方式输出就好啦~

答案2：

int main()
{int T;//规定时间int time = 0;//记录过程时间int rabrun = 0;//兔子距离int turrun = 0;//乌龟距离int rabstill = 0;//兔子休息的时间scanf("%d", &T);while (time++ != T){if (rabstill == 0)rabrun += 9;turrun += 3;if (rabstill != 0)rabstill--;                                        //1.十分钟看一次乌龟if (time % 10 == 0 && rabstill == 0 && rabrun > turrun)//2.不休息时才看 {                                                      //3.领先乌龟                          rabstill += 30;                                //运行:兔子休息30分钟}}if (rabrun > turrun){printf("^_^ %d", rabrun);}else if (rabrun == turrun){printf("-_- %d", turrun);}else{printf("@_@ %d", turrun);}return 0;
}

题解：分别定义四个整型变量，代表流逝的时间time，兔子休息的时间rabstill，兔子奔跑的距离rabrun，乌龟奔跑的距离turrun。首先对兔子休息的时间是否为0，再决定兔子此时是否奔跑。而后使用if语句给上三个条件，分别实现十分钟看一次乌龟，不休息时才看，领先乌龟，的三种条件兔子才休息30分钟。而当休息时间>0时，时间每流逝1分钟，休息时间也减少1分钟，直到休息时间归零时，重新进行奔跑，回头的动作，时间结束后分别判断双方奔跑距离，并输出赢家~

三、说反话-加强版

输入一句英文，要求编写的程序实现将英文所有的单词逆序输出。

输入格式：

测试输入包含一个测试用例，在一行内给出总长度不超过500000的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用若干个空格分开。

输出格式：

每个测试用例的输出占一行，输出倒序后的句子，并且保证单词间只有1个空格。

输入:hello i     like  you
输出:you like i hello

思路提示：之前我们练习过将一段字符串逆序输出，对于字符串逆序输出我们采用的是定义两个整型变量left，right分别代表最左端和最右端，left向右移动，right向左移动，同时分别使str[left]和str[right]进行交换，最后得到逆序的字符串。那么这种逆序方法是否能够用到解决这道题当中呢???

答案1(比较繁琐,可以直接看后面的改进版)：

#include<stdio.h>
#include<string.h>
int main()
{char str[500100];fgets(str, 500100, stdin);int i = 0;int j = 0;int num = 0;int sz = strlen(str) - 1;int left = 0;int right = sz - 1;int danci = 0;while (left <= right){char tmp = str[left];str[left] = str[right];str[right] = tmp;left++;right--;}for (i = 0; i <= sz; i++){if (str[i] != ' '){num++; danci++;}if (str[i] == ' ' || i == sz){for (j = i - 1; j > i - num - 1; j--){printf("%c", str[j]);}if (str[i + 1] != ' ' && i != sz && danci > 0)printf(" ");else if (i == sz)printf("\n");num = 0;}}return 0;
}

主要的思路就是将字符串逆序，然后再从头到尾遍历，遇到一个非空格的字符就记作此单词的长度并num++，当遇到空格时利用num循环输出此单词，而后num清零。其中需要注意:每个测试用例的输出占一行，故最后需要输出一个换行\n。

答案2(简化版)：其实...当我用字符串逆序方法做完之后才发现，其实好像也并不一定需要逆序字符串，只需要将从前往后遍历改成从后向前遍历就好了，只不过理解起来可能稍微麻烦，但确实是一种非常简单的，代码量很少的方法。

#include<stdio.h>
#include<string.h>
int main()
{char str[500100];fgets(str, 500100, stdin);int i = 0, j = 0, num = 0;//用于记录每个单词的大小int sz = strlen(str) - 1;int danci = 0;//用于记录当前出现单词个数for (i = sz - 1; i >= 0; i--){if (str[i] != ' '){num++; danci++;}if (str[i] == ' ' || i == 0)//两种需要打印当前单词的情况{j = i + 1;//因为发现空格时,i处于此单词的下一位,所以输出需要前移一位if (i == 0)//因为i==0时,i处于此单词最后一位,故不需要前移,直接打印就好{j--;num--;}for (; j < i + num + 1; j++){if (str[j] != ' ')printf("%c", str[j]);}											 //str[i - 1]如果不是空格,则代表进入下一个单词.if (str[i - 1] != ' ' && i != 0 && danci > 0)//因为从后往前排查,为保证最后不输出多余空格,则i=0时(i!=0)不输出分割单词的空格printf(" ");							 //空格用于分割单词,若此时单词数为0,则不需要分割,则danci必须大于0else if (i == 0)printf("\n");//题中提到每个测试用例的输出占一行,故最后输出换行num = 0;//输出完一个单词,单词长度清零}}return 0;
}

同样的，我们还是需要定义一个num用于记录每个单词的长度，当此时str[i]不等于空格或者i此时等于0时打印该单词，打印完成后num清空，如此循环往复，直到遍历完字符串。

需要注意的几个点：

①：str[i] == ' ' 和 i == 0两种打印当前单词的情况，打印的方式略微有所差异。当发生前者时，因为发现空格时,i处于此单词的下一位,所以输出需要前移一位。而发生后者时，因为i==0时,i处于此单词最后一位,故不需要前移,直接打印就好。

②：为了避免第一个单词前有众多空格，导致遍历时多出一个空格。我们需要记录单词的数量，如果单词数量为0时则不打印分割单词的空格。

③：题中提到每个测试用例的输出占一行,故最后输出换行。

四、猴子选大王

一群猴子要选新猴王。新猴王的选择方法是：

让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：

在一行中给一个正整数N（≤1000）。

输出格式：

在一行中输出当选猴王的编号。

输入:11
输出:7

思路提示：此题不能硬解，需要先理清楚题目，明白选猴王的规则到底是什么，要清楚为什么输入的11，输出的是7，只要找到了方法便能轻松的解决此题~在这里给大家画一个图~便于大家理解这个选取猴王的规则。(实在是手残,但大概意思应该表达的差不太多,大家看了之后大概能明白吧...)

由此图我们能够知道，从第一个猴子开始往后一次进行1，2，3。1，2，3。1，2，3...的循环报数，而数到3的猴子就会淘汰，并且此后报数也不再算此猴子。但虽然我们能够通过画图的方法了解此题大意，想要真正的创建出一个闭合的数组使它进行循环并且淘汰，我能想到的办法就是在while循环里再嵌套一个for循环，while循环给定条件为淘汰到足够的猴子跳出while(比如11个猴子需要淘汰10个猴子，那么共有N个猴子，就要淘汰N-1个猴子)。

我们可以将数组中下标对应元素改成和下标一致的数字(比如arr[1]=1，arr[2]=2)这样就显得更加简单易懂，数组中对应的元素就是对应号码的猴子，我们从第一个猴子开始遍历，如果猴子数到3那么此猴子淘汰，同时数组下标的值也清零，并且记录猴子淘汰数的计数器也要+1。而再次遍历到这个被淘汰的猴子时，就不再让它报数(如果arr[i]=0，那么直接使用continue跳出该循环，开始数下一只猴子)。

最后以此往复，就能够做到找出最后一个猴子，也就是猴王啦~最后输出数组中剩下的唯一元素的值，也就是猴子的号码~

这个图片更加的简单易懂:

这样就成功的找出了最后一只猴王啦~

答案：

#include<stdio.h>
int main()
{int a;scanf("%d", &a);int arr[1000] = { 0 };int i = 0;int num = 0;//用于记录报数的1,2,3号数。int sum = 0;//用于记录被淘汰的猴子数。for (i = 1; i <= a; i++){arr[i] = i;//将所有的猴子给上对应的号码}i = 1;while (sum < a - 1){for (i = 1; i <= a; i++){if (arr[i] == 0)//值为0代表被淘汰的猴子,直接跳过,数下一个猴子continue;num++;if (num % 3 == 0){arr[i] = 0;sum++;//代表此猴子被淘汰了}}}for (i = 1; i <= a; i++)if (arr[i] != 0)printf("%d", arr[i]);return 0;
}

需要注意的是：如果让下标为1的元素对应猴子1，下标为2的元素对应猴子2，那么之后再使用for循环的时候i都要从1开始，用0的话就会出错。

五、删除字符串中的子串

输入2个字符串S1和S2，要求删除字符串S1中出现的所有子串S2，即结果字符串中不能包含S2。

输入格式：

输入在2行中分别给出不超过80个字符长度的、以回车结束的2个非空字符串，对应S1和S2。

输出格式：

在一行中输出删除字符串S1中出现的所有子串S2后的结果字符串。

输入：
Tomcat is a male ccatat
cat
输出：
Tom is a male 

思路提示：

① 在此题中，输入中会携带空格，而使用scanf("%s")遇到空格便会终止，或许我们应该尝试使用其他输入方法试试呢？

② 由输入输出样例中的ccatat全部被清空的情况，我们能够知道这不是一次性的排查能够做到的，如果用一次排查仅仅能够做到将中间的cat删除，此时或许我们可以在一次排查外套一个大循环，使其拥有每删除一次子串就判断字符串中是否还有子串，若还有则继续排查，若没有则结束排查~

③ 直接将字符删除或许会导致打印出现错误，也可能会影响后续的排查。或许我们可以为要删除的字符赋某值，使打印结果时不输出此类的字符。

答案1：

#include<stdio.h>
#include<string.h>
int main()
{char str1[200];char str2[200];gets(str1);gets(str2);int i = 0;int j = 0;int k = 0;int n = 0;int sz1 = strlen(str1);int sz2 = strlen(str2);int num = 0;int tmp = 0;char* p;while ((p = strstr(str1, str2)) != NULL)//检查字符串str1中是否含有str2子串,若没有,则退出循环{                         for (i = 0; i < sz1; i++){while (str1[i] == str2[j])//对每一个字符进行排查,相同字符才能进入{num++;//排查一个字符则num++j++;//i++的同时j++,使其比对对应的字符if (j == sz2)//此次字符串排查已完成{j = 0;//j清零,以备下次排查break;}}if (num == sz2){for (k = i - sz2 + 1; k <= i; k++)//将字符串置'0'{str1[k] = '0';}for(k = i;k >= i - sz2 + 1;k--){for (n = k; n < sz1; n++)//将置为'0'的字符串移到末尾,其余字符向前移动{tmp = str1[n];str1[n] = str1[n + 1];str1[n + 1] = tmp;}}num = 0;//num置0,便于下次排查}}}for (i = 0; i < sz1; i++){if (str1[i] != '0')//置'0'的字符排除不输出,其余字符正常输出printf("%c", str1[i]);}return 0;
}

此方法就是使用了比较常规的思想方法，先是用到了刚刚思路提示中的①，将scanf("%c")替换成了gets函数，这样就能够防止遇到空格终止输入。

由cplusplus.com - The C++ Resources Network网站的内容我们可以看到，在使用gets进行输入时，除非找到新行字符或文件结束，其他情况不会终止。

注：上一篇博客中提到的fgets函数要比gets函数更加安全，因为gets函数不包括结果字符串中的结尾换行符，并且不允许为str指定最大大小(可能导致缓冲区溢出)。

然后我们用到了思路提示②，我们使用了一个while循环，给定条件是(p = strstr(str1, str2)) != NULL，strstr函数的作用是能够在一个字符串中查找是否含有另一个子串，如果有则返回字符串str2在字符串str1中第一次出现的位置，字符串的比较匹配不包含 \0 字符，以 \0 作为结束标志。

(不太清楚的可以去我的这篇博客中看一看，里面讲解了大部分比较常用的字符串函数并且详解其模拟实现的函数：C语言常用的字符串函数（含模拟实现）-CSDN博客)

之后我们就创建好了大体的框架，接下来我们需要实现子串的排查并删除，我们先使用一个for循环从头到尾遍历一遍字符串str1，在遍历的途中，我们需要判断字符串中出现的与子串相同的字符，并统计其个数，直到从字符串str1中找到完整的一个子串str2 (因为只要能够进入while循环就说明含有字串，就一定能够找到)，将str1中的子串字符置'0'。

你以为这就结束啦？nonono，如果仅仅这样就草草结束，你会发现按照给定样例打印出来的结果中ccatat并没有被完全删除，而是仅仅删除了一个cat这是因为，如果只将子串置零就不去管它了，那么此时字符串其实变成了这个样子：

原来:Tom is a male ccatat
现在:Tom is a male c'0''0''0'at

这样会导致排查字符串时不连贯，导致strstr函数无法查出剩余的cat，并且在排查和删除中也难以做到在间隔'0'的前提下找到大小相同字符相同的子串。但如果我们将所有'0'都移到最后，将其余字符挪到前面，那么就会变成这样：

原来:Tom is a male ccatat
现在:Tom is a male cat'0''0''0'

这样就完美的解决了识别和删除错误，以及strstr函数无法查出cat的情况啦~

还有一个非常非常非常简单的方法，我也没想到竟然能这么简单...(这是我在网上查阅资料，看到别人使用的方法，真的是女少...)

此方法大概的思路是先利用strstr函数找到子串在字符串中的位置，然后使用strcpy函数将从此位置开始，跳过子串后的剩余字符拷贝到一个临时数组中，然后将原来指向子串的位置变成'\0'，使字符串正好到遇见子串前结束，这样下一步使用strcat函数将子串前和子串后的两段字符串链接到一起就ok了~

答案2：

#include<stdio.h>
#include<string.h>
int main()
{char str1[100],str2[100],t[100];gets(str1);gets(str2);char *p;while((p=strstr(str1,str2))!=NULL){strcpy(t,p+strlen(str2));*p='\0';strcat(str1,t);}puts(str1);
}

实现起来具体步骤是这样的，大概能帮助大家比较清晰的理解。

 第一次排查:s1 = Tomcat is a male ccatat     p -> cat is a male ccatatt -> is a male ccatat(is前有空格)*p = '\0's1 = Tom is a male ccatat第二次排查:s1 = Tom is a male ccatatp -> catatt -> at*p = '\0's1 = Tom is a male cat第三次排查:s1 = Tom is a male catp -> catt -> NULL*p = '\0's1 = Tom is a male

六、字符串的冒泡排序

输入格式：

输入在第1行中给出N和K（1≤K<N≤100），此后N行，每行包含一个长度不超过10的、仅由小写英文字母组成的非空字符串。

输出格式：

输出冒泡排序法扫描完第K遍后的中间结果序列，每行包含一个字符串。

输入：
6 2
best
cat
east
a
free
day

输出：
best
a
cat
day
east
free

思路提示：其实和之前学习过的将整数数组冒泡排序是一样的，只不过是在一些地方，将对整型数组的写法换成了对字符串的写法(比如字符串间的交换)。这题还是比较简单的啦~就当轻松的结个尾啦。

答案：

#include<stdio.h>
#include<string.h>
int main()
{int a;int b;int i = 0;int j = 0;scanf("%d %d", &a, &b);char str[a][81];char tmp[81];for (i = 0; i < a; i++){scanf("%s", str[i]);}while (b){for (i = 0; i < a - 1; i++){if (strcmp(str[i], str[i + 1]) > 0){strcpy(tmp, str[i]);strcpy(str[i], str[i + 1]);strcpy(str[i + 1], tmp);}}b--;}for (i = 0; i < a; i++){printf("%s\n", str[i]);}return 0;
}

题解：和正常的将整数数组进行冒泡排序是一个思路，我们定义两个整形变量a和b，分别代表字符串数组的长度，和进行冒泡排序的次数。需要注意的是这里我们不必再像上次一样使用fgets或gets函数来进行字符串的输入，因为使用scanf("%s")也正好每次换行就变成了输入下一个字符串。当输入字符串结束后，我们使用while(b)，在循环内b--，正好b是几就实现了几次冒泡排序。其余相较于整数冒泡排序都没有过多的变化，最值得注意的是此处对于字符串的比较大小使用了strcmp函数，并且字符串的交换使用了三个strcpy函数。那么对于C语言的刷题分享今天就到这里啦~如果有什么讲的不清楚的或者有错误，有麻烦的地方还请各位多多指出哦~我也会吸取教训，多多学习的！那么我们下期再见啦~