CodeVS刷题日记·1842·白银

CodeVS刷题日记（二）

1842 递归第一次

http://codevs.cn/problem/1842/

数学高能预警！！！

数学高能预警！！！

数学高能预警！！！

同学们在做题时常遇到这种函数 f(x)=5 (x>=0) f(x)=f(x+1)+f(x+2)+1 (x<0) 下面就以这个函数为题做一个递归程序吧

话说这种函数我一点都没碰到过啊！！！

这道题目不应该叫函数第一次吗！！

其实这道题蛮简单的，只要发现一件事情：

f(x)=f([x])（[]为高斯函数(下取整)）

[证]: 设x=[x]+{x}(0≤{x}<1) 若{x}=0，x=[x],得证。 若{x}≠0 f(x)=f(x+1)+f(x+2)+1 (1) f(x)=f(x+2)+f(x+3)+1+f(x+2)+1=2*f(x-2)+f(x+3)+1 f(x)=2*(f(x+3)+f(x+4)+1)+f(x+3)=…… ∵由此种迭代可设f(x)=pf(x+k)+qf(x+k+1)+r(p,q,r,k∈Z,x+k<0) 取k使-1≤x+k<0变形得-1-k≤x<-k ∵[x]∈Z,-k∈Z ∴-1-k≤[x]+{x}<-k ∵0<{x}<1 ∴-1-k-{x}∉Z ∴-1-k-{x}≠[x] ∴-1-k< x <-k 假设[x]≠-1-k 若[x]>-1-k即[x]≥-k 则-k>x=[x]+{x}>[x]≥-k 矛盾! 若[x]<-1-k即[x]≤-2-k 则∵-1-k-[x]≥1,[x]+{x}-(-1-k)>0 ∴{x}>1 矛盾! 综上[x]=-1-k ∵(x+k+1)>0 ∴由上得([x]+k+1)≥-1-k+k+1=0 ∴f(x)=pf(x+k)+qf(x+k+1)+r=p(f(x+k+1)+f(x+k+2)+1)+qf(x+k+1)+r =p(5+5+1)+5q+r =p(f([x]+k+1)+f([x]+k+2)+1)+qf([x]+k+1)+r =pf([x]+k)+qf([x]+k+1)+r =f([x]) 得证

其实信息竞赛里不一定要你会证，只要有猜想并且猜对了（自己找不出反例），写上去就基本对了，证明是数学竞赛的事。

利用这个结论可以直接取整加入（后来发现数据好像只有整数。。。）

AC代码：

#include< bits/stdc++.h> using namespace std; int m,fn[101]; double l; int f(int n)//递归 { if(n>=0) return 5; else return f(n+1)+f(n+2)+1; } int main() { int n; scanf(“%d”,&n); printf(“%d”,f(n)); }

(关于为什么不用数组储存一下值以便重复利用，我是开了一个的，但是忘了储存……）

后记： 其实当初我是以为要读入小数，然后自己写取整。 一气之下求出了这个玩意的通项公式：（以x∈Z举例,其余利用上方结论）

取m=-x f(m)= +f(m-2)+1 f(m-1)=f(m-2)+f(m-3)+1 消去常数 f(x)=2f(x-1)-f(x-3 利用特征方程 x^3-2x^2+1=0 x1=1 x2=(-1+sqrt(5))/2 x3=(-1-sqrt(5))/2 代入计算得:(我已经不知道算的对不对了…脑袋已经昏了) f(m)=19-7*((-1+sqrt(5))/2)^m+((-1-sqrt(5))/2)^m)

(此时正在思考为什么要算这个) 没错你们可以用快速幂了 但首先你得把(-1±sqrt(5))/2)写进去….