选择题
1.C函数
题目:下列程序执行后,输出的结果为()
#include <stdio.h> int cnt = 0; int fib(int n) { cnt++; if (n == 0) return 1; else if (n == 1) return 2; else return fib(n - 1) + fib(n - 2); } void main() { fib(8); printf("%d", cnt); }
选项:
- A、41
- B、67
- C、109
- D、177
分析:该题考的是 斐波那契数列 相关知识:f(n) = f(n - 1) + f(n - 2)
(n > 0
,f(1) = 1
,f(2) = 2
),递归求某个斐波那契数值,累计创建了多少层栈帧,具体可以看下图
最终计算得出 67
在涉及递归相关的问题时,可以尝试画出递归展开图,并且涉及重复的递归部分不必画出来,比如本题中的右半部分,可以复用左半部分回归的结果
结果:
B
编程题
1.计算糖果
题目链接:计算糖果
题目分析:纯数学逻辑题了,可以根据条件可知:x1 = A - B
、x2 = B - C
、x3 = A+ B
、x4 = B+ C
,稍微运用一点等价计算,可以得出:A = x1 + B
,B = (x3 - x1) / 2
,C = x4 - B
接下来就很简单了,直接根据推导公式,编写程序即可
#include <iostream> using namespace std; //A = x1 + B //B = (x3 - x1) / 2 //C = x4 - B int main() { int x1, x2, x3, x4; cin >> x1 >> x2 >> x3 >> x4; int A, B, C; B = (x3 - x1) / 2; A = x1 + B; C = x4 - B; //需要进行合法性检测 if(x1 == A - B && x2 == B - C && x3 == A + B && x4 == B + C) cout << A << " " << B << " " << C << endl; else cout << "No" << endl; return 0; }
注意:因为存在不合法的情况,所以需要进行合法性检验,简单,对着题目要求判断一下所求值就好了
2.进制转换
题目链接:进制转换
题目分析:进制转换是程序员的必备技能,这题可以说是相当经典了。给定一个十进制数 M
,再给出一个进制数 N
,要求将 M
转为 N
进制数,比如十进制数 10
,转为 2
进制表示为 1010
,转为 8
进制为 12
,转为 16
进制为 a
,下面来看看具体代码实现
10 如何使用 2 进制表示?
- 假设十进制数为
val
,目标值为target
10 % 2 = 0
,此时val = 5 = (10 / 2)
,target = 0
5 % 2 = 1
,此时val = 2 = (5 / 2)
,target = 10 = 1 + 0
2 % 2 = 0
,此时val = 1 = (2 / 2)
,target = 010 = 0 + 10
1 % 2 = 1
,此时val = 0 = (1 / 2)
,target = 1010 = 1 + 010
当
val
等于0
时,进制转换就结束了
这里编写时用到了一个技巧:倒着转换,等转换完成后,再逆置,就是结果
这样做的好处是省去了很多麻烦,直接尾插即可
- 不然得头插,挺麻烦的,效率也比较低
class Solution { public: string solve(int M, int N) { //所求值数组 vector<int> solveVal = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'}; int val = M; int base = N; //进制数 //需要先判断是否为负数 bool flag = false; if(val < 0) { val *= -1; //转为正数计算 flag = true; } string target; //所求目标值 while(val) { target += solveVal[val % base]; val /= base; } if(flag) target += '-'; //需要注意负号 reverse(target.begin(), target.end()); //逆置 return target; } };
注意: 十六进制中,字母为大写,并且给出的十进制数 M
有可能为负数,假设为负数,需要标记一下,并在转换完成后,把 -
加上
选择题需要自己尝试画出递归展开图,这样才能领悟递归的真谛;两道编程题都是水题,但进制转换的思想值得学习,真正麻烦的进制转换是
M
进制数,转为N
进制数,此时不是常规的十进制,因此再计算时,还需要设计对应的进制转换算法
相关文章推荐
Day3 字符串中找出连续最长的数字串、数组中出现次数超过一半的数字
Day2 排序子序列、倒置字符串
Day1 组队竞赛、删除公共字符
C++题解 | 逆波兰表达式相关
C语言题解 | 去重数组&&合并数组
C语言题解 | 消失的数字&轮转数组