华为od机试真题 taska 和 taskb

Task A：斐波那契数列

对于Task A，需要实现一个函数 fib(m, n)，它接受两个参数 m 和 n，返回第 m 到 n 项斐波那契数列的和（包含第 m 和第 n 项）。需要注意的是，m 和 n 的范围为 [1, 50]，斐波那契数列的第一项为 1，第二项为 1。

解题思路：

利用斐波那契数列的递推公式，计算出第 m 到 n 项的值并求和即可。在实现过程中需要注意变量类型的选择，避免溢出和精度误差。

Task B：字典序列

对于Task B，需要实现一个函数 dict_seq(n)，它接受一个正整数 n，返回字典序列中第 n 小的数。字典序列指的是从小到大排列的所有由 0 和 1 组成的数，例如：

1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
10000
……

解题思路：

我们可以采用递归的方式求解。具体地，考虑递归求解以 0 和 1 为首位的字典序列的数量 cnt（假设首位为 0），以及当前需要求解的字典序列的排名 n。若 n 大于 cnt，则当前字典序列必然以 1 开头，而其排名也可以通过递归求解 n-cnt 得到；否则，当前字典序列以 0 开头，而其排名可以直接通过递归求解 n 得到。最终递归结束的条件为 n 等于 1 或 2。