《妙趣横生的算法》（C语言实现）-第10章算法设计与数据结构面试题精粹

【10-1】输入一个字符串并将它输出，以ctrl+z组合键表示输入完毕，要求将输入的字符串中多于1个的连续空格符合并为1个。

//10-1 2023年12月30日17点11分-17点18分
# include <stdio.h>
int main()
{char c;c = getchar();//scanf("%c", &c);int space = 0;while (c != EOF) {if (c == ' ') {  //遇到空格符时统计空格数目 space++;if (space == 1) {putchar(c);}} else {  //遇到非空格符时清零空格数目 space = 0;putchar(c);  //显示非空格符 }
//        不要用scanf("%c", &c);c = getchar();}return 0;
} 

总结：这类输入流操作的问题可以直接对输入的字符进行判断和处理，无需将输入的字符先保存在数组或者其他数据结构中，这样会非常容易解决。
【10-2】从终端输入10个整数，输出其中最大的数和次大的数。要求输入的10个整数互不相等。

//10-2 2023年12月30日17点25分-17点42分 
# include <stdio.h>
void bubble_sort(int a[], int n)
{for (int i = n-1; i > 0; i--){for (int j = 0; j < i; ++j) {if (a[j] < a[j+1]) {int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;}}printf("第%d次循环排序后结果：", n-i);for (int k = 0; k < n; k++) {printf("%3d", a[k]);}printf("\n");}
}
int main()
{int arr[10];  //定义一个数组printf("Please input 10 integers:\n"); for (int i = 0; i < 10; i++) {  //输入数据 scanf("%d", &arr[i]);}bubble_sort(arr, 10);  //冒泡排序printf("After sorting:\n");for (int i = 0; i < 10; i++) {  //输出数据 printf("%d ", arr[i]);}printf("\nthe maxest number is %d, the other is %d\n", arr[0], arr[1]); return 0;
} 
//12 43 23 13 65 17 98 45 67 88

//书上的代码
# include <stdio.h>
int main()
{int a, maxVal = -1000, secondVal = -1000;for (int i = 0; i < 10; i++) {scanf("%d", &a);if (a > maxVal) {secondVal = maxVal;maxVal = a;} else {if (a > secondVal) {secondVal = a;}}}printf("The max value is    %d\n", maxVal);  //输出最大的数 printf("The second value is %d\n", secondVal);  //输出次大的数 return 0;
} 

总结：类似上一道题，可以不用保存这10个整数，直接在数据输入的过程中加以控制和比较。
【10-3】编写一个程序，求分数序列的前50项和。

//10-3 2023年12月30日17点50分-17点56分 
# include <stdio.h> 
int main()
{double s = 0.0;double a = 2, b = 1;  //用浮点类型，用int结果就不一样了s += a / b;for (int i = 1; i < 50; ++i) {double tmp = b;b = a;a += tmp;s += a / b;}printf("sum is %g\n", s);return 0;
}

总结：用好数据类型，可以写成函数哦！
【10-4】编写一个函数实现字符串内容逆置，要求不另外开辟字符串空间。

//10-4 2023年12月30日18点01分 
# include <stdio.h>
# include <string.h>
void reverse(char *s)
{for (int i = 0, j = strlen(s) - 1; i < j; i++, j--) {char tmp = s[i];s[i] = s[j];s[j] = tmp;}
}
int main()
{char s[200];printf("Please input a string:\n");gets(s);reverse(s);printf("After reversing:\n%s", s);return 0;
}

【10-5】编写一个程序，将两个字符串连接，要求不破坏原有字符串。

//10-5 2023年12月30日18点04分-18点10分 
# include <stdio.h>
char * cnnString(char *s1, char *s2)
{char s[400];int len = 0;for (int i = 0; s1[i]; i++) {s[len++] = s1[i];}for (int i = 0; s2[i]; i++) {s[len++] = s2[i];}s[len] = '\0';return s;
}
//书上代码
/*char * cnnString(char *s1, char *s2)
{int len, len1, len2;char *s3;len1 = strlen(s1);len2 = strlen(s2);len = len1 + len2 + 1;s3 = (char *)malloc(len);for (int i = 0; i < len1; i++)s3[i] = s1[i];for (int i = 0; i < len2; i++)s3[i+len1] = s2[i];s3[len-1] = '\0';return s3;
}*/
int main()
{char s1[200], s2[200];printf("Please input a string:\n");gets(s1);printf("Please input a string:\n");gets(s2);char *s;s = cnnString(s1, s2);printf("Connecting:\n%s", s);
//    printf("%s", cnnString(s1, s2));return 0;
} 

总结：我自己写的代码运行时警告：返回了局部变量的地址，要注意！！这是因为在函数里创建的字符串是在栈上创建的，用动态分配，书上的代码就不会有警告。
【10-6】编写一个递归函数，求和。

//10-6 2023年12月30日18点17分-18点20分 
# include <stdio.h>
int sum(int n)
{if (n == 1)return 1;elsereturn n+sum(n-1);
} 
int main()
{int n;printf("Please input a integer:\n");scanf("%d", &n);printf("The result is \n%d\n", sum(n));return 0;
} 

总结：递归函数解决问题哦。找到递归终止条件，递归函数。
【10-7】用递归方法编写一个程序，返回整型数组array中的最大值。数组array中的元素互不相等。

//10-7 2023年12月30日19点37分-19点51分 
# include <stdio.h>
int max(int a[], int n)  //递归方法哦！
{if (n == 1)return a[0];else //return a[n-1] >= max(a, n-1) ? a[n-1] : max(a, n-1);  //目前正确 return a[0] >= max(a+1, n-1) ? a[0] : max(a+1, n-1);
//        return a[0] >= max(a, n-1) ? a[0] : max(a, n-1);  //错误 
//        return max(a, n-1);  //错误 
}
int main()
{int n;printf("Please input a integer:\n");scanf("%d", &n);int arr[n];printf("Please %d numbers:\n", n);for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}printf("The maxValue is\n%d\n", max(arr, n));return 0;
} 

【10-8】用递归方法解决输出字符串。
看到这个题目时，我感觉不使用递归的话，应该很好输出。本题的输出结果其实就是这个小写字符串与它对应的大写字符串的逆序交叉输出。使用递归方法的话，终止条件应该是只包含一个小写字母，那么输出两个字母；如果是包含n个小写字母呢？
想法：n个小写字母其实就是一个小写字母循环，规律呢？

//10-7 2023年12月30日19点52分-20点16分 
# include <stdio.h>
# include <string.h>
char upper(char c)  //将小写字母转换为大写字母 
{return (c-'a'+'A');
}
//void func(char *s, int n)  //错误 
//{
//    if (n == 1) {
//        printf("%c%c", s[strlen(s)-n]-32, s[n-1]);
//    } else {
//        func(s, n-1);
//    }
//}
void func(char *str, int n, int i)  //递归法按要求格式输出字符串 
{if (i < n) {printf("%c%c", upper(str[n-i-1]), str[i]);func(str, n, i+1);}
}
int main()
{char s[200];printf("Please input a string:\n");  //输入字符串 scanf("%s", s);printf("The result is\n");func(s, strlen(s), 0);  //调用递归函数func() return 0;
} 

总结：这道题目还是有些难思考到。
【10-9】递归方法实现字符串内容就地逆置。

//10-9 2023年12月30日20点19分-20点27分 
# include <stdio.h>
# include <string.h>
void reverse(char *s, int n, int i)
{
//    if (n == 1) {  //错误 
//        printf("%c", s[n-1]);
//    } else {
//        reverse(s, n-1);
//    }if (i < n) {  //目前正确 printf("%c", s[n-1-i]);reverse(s, n, i+1);}
}
int main()
{char s[200];printf("Please input a string:\n");gets(s);printf("The result is\n");reverse(s, strlen(s), 0);return 0;
} 

//10-9 书上代码 
# include <stdio.h>
# include <string.h>
void reverser(char *s, int n, int i)
{if (i < n) {char tmp = s[n];  //字符的置换 s[n] = s[i];s[i] = tmp;reverser(s, n-1, i+1);  //递归调用函数reverser() }
}
void reverse(char *s)
{reverser(s, strlen(s)-1, 0);  //调用递归函数 
}int main()
{char s[200];printf("Please input a string:\n");gets(s);reverse(s);printf("The result is\n%s", s);return 0;
} 

总结：要与题目要求的接口一致哦！！
【10-10】编程计算可以制作出多少种水果拼盘。

//10-10 2023年12月30日20点34分-20点42分
# include <stdio.h> 
void func(int n)
{switch(n) {case 0: printf("apple "); break;case 1: printf("orange "); break;case 2: printf("banana "); break;case 3: printf("pineapple "); break;case 4: printf("pear "); break;}
}
int fruitPlate()
{int count = 0;for (int i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) {if (j == i) {continue;}for (int k = 0; k < 5; k++) {if (k == j || k == i) {continue;}count++;func(i);func(j);func(k);printf("\n");}}}return count;
}
int main()
{printf("There are %d kinds of methods for arranging plate.", fruitPlate());return 0;
}

总结：穷举法。写成函数然后调用哦！
【10-11】请在屏幕上输出一张乘法口诀表。

//10-11 2023年12月30日20点43分-20点46分 
# include <stdio.h>
void func()
{for (int i = 1; i < 10; i++) {for (int j = 1; j <= i; j++) {printf("%d*%d=%2d  ", j, i, j*i);}printf("\n");}
}
int main()
{func();return 0;
} 

【10-12】编程找出一个数字。

//10-12 2023年12月30日20点47分-20点50分 
# include <stdio.h>
# include <math.h>
int is_square(int n)  //判断完全平方数函数
{int r = sqrt(n);if (r * r == n) {return 1;} else {return 0;}
}
int func(void)
{for (int i = 1; ; i++) {  //穷举法找数字if (is_square(i+100) && is_square(i+168)) {return i;}}
}
int main()
{printf("The number is %d", func());return 0;
} 

【10-13】求和。

//10-13 2023年12月30日20点53分-20点57分 
# include <stdio.h>
int sum(int num, int t)
{int s = 0, r = 0;for (int i = 1; i <= num; i++) {r = r * 10 + t;s += r;}return s;
}
int main()
{printf("Please input n and a:\n");int n, a;scanf("%d %d", &n, &a);printf("The result is\n%d", sum(n, a));return 0;
} 

【10-14】设计一个递归算法将一个整数n转换成字符串。

//10-14 2023年12月30日20点58分-
# include <stdio.h>
# include <malloc.h>
/*char *func(int num)  //非递归做法 
{int tmp = num, k = 0;if (tmp == 0) {k = 1;}while (tmp) {k++;tmp /= 10;}char *ret = (char *)malloc(sizeof(char)*(k+1));
//    char ret[100];ret[k] = '\0';if (num == 0) {ret[0] = '0';}while (num) {ret[k-1] = num % 10 + '0';num /= 10;--k;}return ret;
}*/
//书上代码
void trans(int n)
{int i = n % 10;  //得到整数n的个位数字if (n/10 > 0)trans(n/10);  //递归调用trans，将高位数转换为字符串printf("%c", i + '0'); 
} 
int main()
{int n;printf("Please input a integer:\n");scanf("%d", &n);
//    printf("The result is\n%s", func(n));printf("The result is\n");trans(n);return 0;
} 

总结：用递归方法还是不熟练，写不出来。
【10-16】编程实现字符串复制。

//10-16 2023年12月30日21点11分-21点16分 
# include <stdio.h>
void mystrcpy(char *str, char *ret)
{/*int i;for (i = 0; str[i]; i++) {  //逐个字符复制 ret[i] = str[i];}ret[i] = '\0';*/int i = 0;while (str[i]) {*(ret+i) = *(str+i);  //复制字符串 i++;  //指针后移 }ret[i] = '\0';  //目的字符串的末尾要添加字符串结束标志'\0' 
}
int main()
{char s[200], t[200];printf("Please input a string:\n");//scanf("%s", s);gets(s);mystrcpy(s, t);printf("The result is\n%s", t);return 0;
} 

【10-17】编写一个函数loopMove(char *str, int n)实现字符串的循环右移功能。
自己有点想不出来诶！
书上分析，每次取字符串尾部一个字符保存到临时变量，然后将字符串前面的所有字符右移一位，然后将临时变量中存放的字符复制到字符串的首部，如此循环n次。

//10-17 2023年12月30日21点19分-21点27分 
# include <stdio.h>
# include <string.h>
void loopMove(char *str, int n)
{int strLength = strlen(str);for (int i = 0; i < n; i++) {char tmp = str[strLength - 1];  //取出字符串的最后一个元素 for (int j = 0; j < strLength - 1; j++) {str[strLength-j-1] = str[strLength-j-2];  //前面的元素后移 }str[0] = tmp;  //将原字符串尾部的元素放在字符串首部 }
}
int main()
{char s[200];printf("Please input a string:\n");gets(s); int n;printf("Please input a integer:\n");scanf("%d", & n);loopMove(s, n);printf("The result is\n%s", s);return 0;
} 

【10-18】找出01字符串中0和1连续出现的最大次数。

//10-18 2023年12月30日21点36分- 21点52分
# include <stdio.h>
void getMax(char *str, int *max0, int *max1)
{int cnt_0 = 0, cnt_1 = 0;if (str[0] == '0') {cnt_0++;} else {cnt_1++;}for (int i = 1; str[i]; i++) {if (str[i] == str[i-1]) {if (str[i] == '0') {cnt_0++;} else {cnt_1++;}} else {if (str[i] == '0') {if (cnt_1 > *max1) {*max1 = cnt_1;cnt_1 = 0;}cnt_0++;} else {if (cnt_0 > *max0) {*max0 = cnt_0;cnt_0 = 0;}cnt_1++;}}}if (cnt_1 > *max1) {*max1 = cnt_1;}if (cnt_0 > *max0) {*max0 = cnt_0;}
}
int main()
{char s[200];printf("Please input a string:\n");scanf("%s", s);int max0 = 0, max1 = 0;getMax(s, &max0, &max1);printf("max0 = %d, max1 = %d", max0, max1);return 0;
}

总结：函数中返回两个变量的值，用指针传递。
【10-19】编程计算该数列第20项的值。

//10-19 2023年12月30日21点55分-22点00分 
# include <stdio.h>
/*int func(int num)
{int tmp = 1;for (int i = 2; i <= num; i++) {if (i % 2 == 0) {tmp = tmp * 2 + 1;} else {tmp *= 2;}}return tmp;
}*/
//书上代码
unsigned long func(int num)
{if (num == 1)return 1;if (num % 2 == 0)return 2*func(num-1)+1;elsereturn 2*func(num-1);
} 
int main()
{printf("Please input n:\n");int n;scanf("%d", &n);
//    printf("The result is\n%d", func(n));printf("The result is\n%ld", func(n));return 0;
} 

总结：递归函数。还有注意数据的范围。
【10-20】计算这位集邮爱好者集邮总数是多少？以及每册中各有多少邮票？

//10-20 2023年12月30日22点04分-22点07分 
# include <stdio.h>
int main()
{int x;for (int y = 1; y < 7; y++) {if (303*7*10 % (56-10*y) == 0) {x = 303*7*10 / (56-10*y);break;}}printf("x = %d, A = %d, B = %d, C = 303", x, x/5, x-x/5-303);return 0;
} 

【10-21】编写递归算法，计算出每个人的年龄。

//10-21 2023年12月30日22点09分-22点14分 
# include <stdio.h>
int func(int num)
{if (num == 1) {  //第一个人10岁 return 10;} else {return 2+func(num-1);  //第n个人的年龄比第n-1人的年龄大2岁 }
}
int main()
{for (int i = 1; i <= 5; i++) {printf("Age %d: %d\n", i, func(i));} return 0;
} 

【10-22】