一、兔子繁殖问题：一对兔子满4个月后,可以生育一对兔子,那么第n个月后,有多少对兔子。（n=5时，输出2）
n1=1;n2=1;n3=1;n4=1;n5=n4+n1.
用f(n)=f(n-4)+f(n-1)去求。
（我笔试竟然没有想到，哎。。。好久没做这种题了）
二、1000枚硬币中有10枚金币，现取n枚硬币，求含有金币的概率。要求保留小数点后6位。
测试用例：输入n=1,输出0.010000;输入n=999,输出1.000000
（n990,则输出1.000000）
作者：sunandstarws
【奇安信笔试题解析】
在奇安信的笔试中，我们遇到了两个经典的数学问题，它们不仅考验逻辑思维，还涉及到计算机编程中的递归和概率计算。下面将详细讲解这两个问题及其解题方法。
**一、兔子繁殖问题**
这是一个典型的斐波那契数列（Fibonacci Sequence）变种问题。在斐波那契数列中，每个数字是前两个数字的和。在兔子繁殖问题中，每对兔子4个月后才能生育新的兔子对，我们可以根据这个规则来构建数列。
假设f(n)表示第n个月后的兔子对数：
- f(1) = 1 对（初始的一对兔子）
- f(2) = 1 对（因为不足4个月，无法生育）
- f(3) = 1 对（同样不足4个月，无法生育）
- f(4) = 1 对（这对兔子达到4个月，可以生育，但新的兔子对还没出生）
- f(n) = f(n-4) + f(n-1) 对（n大于4时）
这里的关键在于理解每对兔子在第n个月的贡献是它在第n-4个月的贡献加上它自己。因此，我们可以编写如下的递归函数来计算f(n)：
```python
def fibonacci_rabbits(n):
if n <= 4:
return 1
else:
return fibonacci_rabbits(n - 4) + fibonacci_rabbits(n - 1)
```
然而，由于递归可能导致大量的重复计算，我们可以使用动态规划来优化算法，存储已计算过的值，避免重复计算：
```python
def optimized_fibonacci_rabbits(n, memo={}):
if n in memo:
return memo[n]
elif n <= 4:
return 1
else:
memo[n] = optimized_fibonacci_rabbits(n - 4, memo) + optimized_fibonacci_rabbits(n - 1, memo)
return memo[n]
```
对于题目中给出的例子n=5，调用`optimized_fibonacci_rabbits(5)`会得到结果2。
**二、含金币的概率问题**
这是一个组合概率问题。在1000枚硬币中，有10枚是金币，其余990枚是银币。我们要求的是随机选取n枚硬币中含有至少一枚金币的概率。
不包含金币的所有组合数量为C(990, n)。而总共有C(1000, n)种不同的组合方式。所以，包含至少一枚金币的概率P为1减去没有金币的概率：
P = 1 - C(990, n) / C(1000, n)
为了保留小数点后6位，我们需要使用浮点数运算，并且注意C(n, k)的计算可以用阶乘的方式简化：
C(n, k) = n! / (k!(n-k)!)，其中"!"表示阶乘。
我们可以编写一个函数来计算这个概率：
```python
import math
def coin_probability(n):
total_combinations = math.comb(1000, n)
no_gold_combinations = math.comb(990, n)
p = 1 - (no_gold_combinations / total_combinations)
return round(p, 6)
```
对于题目中的测试用例：
- 当n=1时，P = 1 - C(990, 1) / C(1000, 1) = 0.010000
- 当n=999时，P = 1 - C(990, 999) / C(1000, 999) ≈ 1.000000
这两个问题在IT笔试中出现，既展示了基础数学知识的重要性，也强调了解决问题的策略和算法设计。在实际的编程面试或工作中，这样的能力同样关键。
