一、求最小公倍数
题目描述
正整数A和正整数B的最小公倍数是指能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的的最小公倍数。
输入描述
输入两个正整数A和B。
输出描述
输出A和B的最小公倍数。
示例
输入:5 7输出:35
第一种解法
#include <stdio.h> int main() { int a, b = 0; scanf("%d %d", &a, &b); int n = a > b ? a : b; while (1) { if ((n % a) == 0 && (n % b) == 0) break; n++; } printf("%d\n", n); return 0; }
这种算法耗时较长,效率较低。但是思路是最简单和基础的,其思路是先找出A和B中的最大值,然后以这个最大值为基础,一个一个去试除A和B,当同时能够整除A和B时即为A和B的最大公倍数。
运行时间1001ms 占用内存476KB
第二种解法
#include <stdio.h> int main() { int a, b, i = 1; scanf("%d %d", &a, &b); while (1) { if ((a * i) % b == 0) break; i++; } printf("%d\n", a * i); return 0; }
第二种算法相比第一种会快很多,用乘法的方式使得循环的次数少了很多
运行时间3ms 占用内存400KB
第三种解法
#include <stdio.h> int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } int main() { int a, b; scanf("%d %d", &a, &b); printf("%d\n", a / gcd(a, b) * b); return 0; }
这种算法利用了辗转相除法,先求出最大公约数,再求出最小公倍数。
最小公倍数=两个数的乘积/最大公约数
为防止溢出,(a*b)/m改为(a/m)*b --m为最大公约数
运行时间4ms 占用内存348KB
二、倒置字符串
题目描述
将一句话的单词进行倒置,标点不倒置。比如 I like beijing. 经过函数后变为:beijing. like I
输入描述
每个测试输入包含1个测试用例: I like beijing. 输入用例长度不超过100
输出描述
依次输出倒置之后的字符串,以空格分割
示例
输入:I like beijing.
输出:beijing. like I
解法
#include <stdio.h> #include <string.h> void reverse(char* left, char* right) { while (left < right) { char tmp = 0; tmp = *left; *left = *right; *right = tmp; left++; right--; } } int main() { char arr[100] = { 0 }; gets(arr); int len = strlen(arr); reverse(arr, arr + len - 1);//将整个字符串翻转,即全部倒序排放 char* start = arr;//再将每个单词翻转为正序 while (*start) { char* end = start; while (*end != ' ' && *end != '\0') end++; reverse(start, end - 1); if (*end == ' ') start = end + 1; else start = end; } printf("%s\n", arr); return 0; }
一道很经典的题目,定义字符串倒置函数,先翻转整个字符串一次,再逐个将单词翻转一次。
运行时间2ms
占用内存308KB