A - 大菲波数
取石子问题 – 1堆
问 题 描 述
有N粒石子,甲乙两人轮流从中拿取,一次至少拿一粒,至多拿先前对方一次所取石子数目的两倍。甲先拿,开始甲可以拿任意数目的石子(但不得拿完)。最先没有石子可拿的一方为败方。 请问,甲能否获胜?(1 < N < 100)
题解:
设{F}为Fibonacci数列(F1=2,F2=3,FK=FK-1+FK-2) 初始时有N粒石子,若N∈{F}则先手必败,否则先手必胜。
如果数是Fibonacci数列,则甲必败.
常用数列一栏表<1>Fibonacci数列
{ 0 n=0
Fib(n)={ 1 n=1
{ Fib(n-1)+Fib(n-2) 其他情况
Fib(n)的前十项
Fib(0)=0, Fib(1)=1, Fib(2)=1, Fib(3)=2, Fib(4)=3, Fib(5)=5, Fib(6)=8, Fib(7)=13 Fib(8)=21, Fib(9)=34, Fib(10)=55.
当n>45 int已经超出范围了, long long int 也只能到91.大于这个数就必须用高精度了.
1.取石子游戏,
有N粒石子,甲乙两人轮流从中拿取,一次至少拿一粒,至多拿先前对方一次所取石子数目的两倍。甲先拿,开始甲可以拿任意数目的石子(但不得拿完)。最先没有石子可拿的一方为败方
如果数是Fibonacci数列,则甲必败.
2. 楼梯上有n阶台阶,上楼时可以一步上一阶,也可以一步上两阶,问一共有多少种不同的上楼梯的方法.
3.杨辉三角对角线上各数之和构成斐波拉契数列 .
4.多米诺牌(可以看作一个2×1大小的方格)完全覆盖一个n×2的棋盘,覆盖的方案数等于斐波拉契数列。
5. 从蜜蜂的繁殖来看,雄峰只有母亲,没有父亲,因为蜂后产的卵,受精的孵化为雌蜂,未受精的孵化为雄峰。人们在追溯雄峰的祖先时,发现一只雄峰的第n代祖先的数目刚好就是斐波拉契数列的第n项Fn。
6.钢琴的13个半音阶的排列完全与雄峰第六代的排列情况类似,说明音调也与斐波拉契数列有关。
7.自然界中一些花朵的花瓣数目符合于斐波拉契数列,也就是说在大多数情况下,一朵花花瓣的数目都是3,5,8,13,21,34,……(有6枚是两套3枚;有4枚可能是基因突变)。
8.如果一根树枝每年长出一根新枝,而长出的新枝两年以后,每年也长出一根新枝,那么历年的树枝数,也构成一个斐波拉契数列
以上的问题都能应用到Fibonacci数列.