上海交通大学2017年复试题:FibonacciRepresentation
second commit
今天看了看复试群里其他同学的解答,我的算法相对来说繁琐了很多。其实完全可以不用计较n=2的边界条件,也无需推导出之前所叙述的第二类数的规则。只需利用
向下递归判断,便可轻松地写出代码。
第二次的代码:
int dfs2(int n,int lev){
if (n==0) return 1;
if (fib[lev+2]-2<n) return 0;
int i;
for (i=lev; fib[i]>n; i--);
return dfs2(n, i-1)+dfs2(n-fib[i], i-1);
}
这种做法完全靠上述公式剪枝,无需手动判断需不需要减去第二个数,边界条件直接解决了这个问题。比自己第一次做的要简单很多,而且可读性也强得多。
最后时间效率对比,小数据两种方法差不多,大的数据(例如)的运行时间,后者是前一个方法的一半,省去了大量没必要的递归操作。
之前的算法主要误区就是编程的时候太注重分类讨论,因此数字比较小的时候,分类情况不好界定,于是把(n>2)当作边界条件。同时也是受此影响写公式的时候也出了点小问题,公式中的下标其实是1,因此范围是(n>0)而不是(n>2)。
自己的递归意识和编程能力还是有些薄弱,得出了数学公式,却写出了相比于别人又复杂又慢的算法。
first commit
今天把交大考研复试题目全部刷完了,整体难度比pat要高一个档次。
交大复试难题往往考的不是编程,而是蕴含在代码中数学和算法思想。
有一道题是披着最短路径外皮的最小生成树。给出路径,每走一步的代价为2的k次方,给出的数据还特别大。落入陷阱的人会思考如何用高精度表示路径和,我就是其中一员。不得正解后看别人的解才知道,做这道题实际上要经过简单的数学推导,经过等比数列求和或者是二进制求和,可以得到前n步的和永远小于第n+1步,于是后面出现的重复路径可以忽略不计。
今天做了这一道题
这一道题是2017年上海交大考研复试的最后一题。乍一看并不难,用动态规划或者DFS就能解决。但实际上给出了的变态数据,使用动态规划必然内存超限(),关键就在于DFS和剪枝的处理了。
这道题的难点同样在于数学思想(我尚未知道是否有其他解法),在10^8的数据下,DFS特别容易超过时间限制,关键在于找规律。
有了前一道题的经验,我试着把这些fibonacci数前n项加起来,发现前n项和始终等于第n+2项-2。知道了这个规律,编程就好办多了。
这道题的难点在于这个规则,
每当一个数的范围在 因此必然包含第n+1项fibonacci数Fib(n+1)。编程的过程需要将两项值相隔超过2,方便处理,可将n=2算作递归边界。
因此在DFS编写代码的过程中,由大往小,按照一定规则列举fibonacci数,可以将数分为两类,一类是
另一类是
第一类数:减去必有的n+1项fibonacci数,递归统计即可。
第二类数:可以被前n项表示出来,因此需要切成两部分递归统计,
第一部分减去n+1项fibonacci数;
第二部分需要减去第n项的fibonacci数再向前n项递归统计。
第二类数第二部分的原理推导:
N必然大于后n-1项和,不能以Fib(n-1)作为开头。
因此,设置好递归出口,就可以按照上述规则进行递归运算了。
仔细思索了一下,这种做法应该尽最大可能剪枝了。剩下能强化其时间效率的做法,大概只能使用我尚未了解的空间换时间算法来解决了。
具体的实现代码如下。
#include <iostream>
#include <ctime>
int fib[80];
using namespace std;
int cnt=0;
void fb(int n){ //预处理
fib[0]=1; // 第0项和第1项是相同的,DFS处理的时候小心。
fib[1]=1;
int i=2;
while (fib[i-1]<n) {
fib[i]=fib[i-1]+fib[i-2];
i++;
}
}
void dfs(int n,int lev){ //设置层数限制,从大往小一一列举,防止后层的无效元素,取到前层的fib数,令cnt增加发生错误。
if(n<=0) return;
int i=1;
for (;fib[i]<n&&i<lev; i++);
if (i<lev&&fib[i]==n) {
cnt++;
}
if(i>lev||n==2) return; //将n为2化为边界条件。当n为2时,递归会把循环引导进fib[0],fib[1]的情况,计算出一个错误值。
if(fib[i]-n>=2)
dfs(n-fib[i-2],i-2);
dfs(n-fib[i-1],i-1);
}
int main(int argc, const char * argv[]) {
freopen("in.txt", "r", stdin);
freopen("out.txt","w",stdout);
clock_t start,end;
start=clock();
fb((int)1e9);
int n;
while(cin>>n){
cnt=0;
dfs(n,50); //提前了解一下范围内的fibonacci数有多少,随便填写一个范围内的fibonacci系数。
printf("%d\n",cnt);
}
end=clock();
printf("The running time is %lf s.\n ------ %.2lf ms.\n",double(end-start) /1000,double(end-start));
return 0;
}
————————————————————————————————————————
渣机测试,输入数据,从 到一一枚举,超过其要求的的数据大小的时间
最终得到的结果
即使是的数据,单点测试的条件下也能够通过。
用语言表达出数学思想,可能相对比较晦涩难懂。还是亲手计算、写写代码,才能更深刻地理解算法。
当然。。这道题如果真的到考场上,大概想不出这样的思路,暴力DFS能混多少分是多少分。