1、走楼梯:
一次可以走一步,也可以一次走两步,那么走完20级台阶有多少种走法?
tips: 感觉有些类似于斐波纳契数, 走完20级台阶,可以是在走完18级台阶后再迈两步,或者是走完19级台阶后再迈一步,所以F(20)=F(19)+F(18)
走完一级台阶的走法有1种,即F(1)=1
走完两级台阶的走法有两种:走完一级台阶后再走一步,或者直接迈两步,所有F(2)=2
走完三级台阶的走法是:走完1级台阶后再迈两步或者走完两级台阶后再走一步,所以走法F(3)=F(1)+F(2)=3
依此类推
F(n)=F(n-1)+F(n-2)
python的递归写法:
def F(n):
if(n==0 or n==1):
return 1
else:
return F(n-1)+F(n-2)
非递归写法:
def F(n):
if(n==0 or n==1):
return 1
else:
a=1
b=1
c=0
for i in range(2,n+1):
c=a+b
a=b
b=c
return c
因此走完20级台阶总共有10946种走法
电影《少年班》中也有这个问题,不过神人王大发用铜钱算出来,也是极品了。
#求前20项的斐波那契数
a = 0
b = 1
for _ in range(20):
(a, b) = (b, a + b)
print(a, end=' ')
2、最大公约数 , 辗转相除法 / 求大分数(分子、分母为很大的整数)约分问题
ex:化简15563/19109
19109 / 15563 = 1 ... 3546
15563 / 3546 = 4 ... 1379
3546 / 1379 = 2 ... 788
1379 / 788 = 1 ... 591
788 / 591 = 1 ... 197
591 / 197 = 3 ... 0
def gcd(a,b):
if (a<b):
a,b=b,a
c=a%b
while(c!=0):
a=b
b=c
c=a%b
return b
gcd(15563,19109)
结果为:197
3、f(f(x))=x^2 - x + 1 ,求 f(0)的值
令x=0,f( f(0) ) = 0^2 - 0 + 1 = 1
则f( f( f(0) ) ) = f(1) -------------A
同时观察上式: f( f( f(0) ) ) ,将f(0) 看作x,放入给定的条件中,则:
f( f( f(0) ) ) = f(0)^2 - f(0) + 1 ---B
结合A和B两个式子,得到f(1) = f(0)^1 - f(0) + 1 -------E
令x=1,f( f(1) )=1^2 - 1 + 1 = 1
则f( f( f(1) ) )=f(1) --------------C
同样观察上式:f( f( f(1) ) ),将f(1)看作x,放入给定条件中,则:
f( f( f(1) ) ) = f(1)^2 - f(1) + 1 ----D
结合C和D两个式子,得到f(1) = f(1)^2 - f(1) + 1,最终得到f(1) = 1, 带入E式子
得到f(0)^2 - f(0) + 1 = f(1) = 1
所以f(0)=0 或 1
若f(0)=0,则f( f(0) ) = f( 0 ),同时f( f(0) ) = 0^2 - 0 + 1 =1,最终得到f(0) = 1,这个结果与f(0)=0相互矛盾,故f(0)=0应该舍去
若f(0)=1 , 则f( f(0) ) = f( 1) = 0^2 - 0 + 1 = 1
所以最终f(0)=1
4、复杂根式求解
用SL代替根号
SL(x+12) + SL(x+21) = 9 -----A
求x
构造根式,巧用(a+b)(a-b)=a^2-b^2
设SL(x+12)-SL(x+21)=t -----B
A*B ===》 x+12-(x+21)=9t
得到t = -1
A+B===》 2( SL(x+12)) =8
===》 SL(x+12) =4
===》 x+12 = 4^2
===》 x = 4
5、已知: a^3+a^2=36,
求:a^6
观察36,可以拆分为27和9,27是3的立方,9是3的平方,然后利用立方差和平方差求解
a^3+a^2 = 36=27+9
===》a^3 - 27 + a^2 - 9 =0
===》(a-3)*(a^2+3*a+9) + (a-3)*(a+3)=0
===》(a-3)(a^2+4*a+12)=0
===》a=3 或 a^2+4*a+12 = 0
a=3时 , a^6 = 729
a^2+4*a+12 = 0时,a=正负2SL(2)* i - 2