简单的小题集（七）

一、斐波那契数列

大学学 C 语言的时候，老师都少不了讲斐波那契数列，什么递归、递推、还有
矩阵幂，反正方法多的是，不过今天这道题咱们稍微改变一下，毕竟直接写斐波那契数列
是小学生做的事，太 LOW 了，想证明你 tql，那就把我改编的这道 AC 吧：
斐波那契数列：1,1,2,3,5,8,13,21,34…，现在给你一个 n，让你求出 f(n)/f(n+1)的值，注意
啦，要求输出的值保留小数点后 8 位

#include <stdio.h>
#include <stdlib.h>
#include <bigint.h>
BigInteger f[10000];
BigInteger fibo(int n){
 if(n<=1) return BigInteger("1");
 if(f[n].isInitialized()) return f[n];
 f[n] = fibo(n-1) + fibo(n-2);
 return f[n]; 
}
int main(){
 int n;
 scanf("%d", &n);
 
 BigInteger a = fibo(n);
 BigInteger b = fibo(n+1);
 
 BigInteger result = a/b;
 printf("%.8f", result.toDouble());
 return 0;
}

二、皮皮小南遭不住

皮皮的小南又出现了，估计大家对他仍记忆犹存，上次确实给大家坑的够呛，
哈哈，对不起，这家伙就是不肯走，他又来了，最近小南压力还真不小，这不放学了，一
个人边走还边在嘴里唠叨着：“这什么玄学复杂度的题，一个人压根顶不住好吧！”，“顶不
住？不是还有我吗？”，这时小浪从小南身后出现了，小南：“矣，怎么今天就你一个？浪 G
天涯不成功？要不要一起堕落？”。小浪：“算了吧，什么题把你愁成这样呀，来来，分享一
下”。小南从书包拿出一张纸，题目是这样的：
小 C 是一位可爱并且很爱学习的小女孩。但是数学不太好，并且对数字十分不敏感，可是
她又很想学好数学，这天她碰到一道这样的题：有一个 N * N 的格子， 每个格子中都有一
个小于 10 的非负整数。聪明的你可以在这 NN 的格子中移动。 如果它当前在（x，y）格
子中，它可以移动到（x + 1，y），（x，y + 1），（x-1，y），（x，y-1）格子中。但你的一切
操作都必须在这 NN 的格子内操作。
你可以从 N*N 方格中的任何格子开始，采取上下左右方式任意移动，并且它可以停在方格
中的任何位置。我们按顺序连接这些走过格子中的数字以获得幸运数。例如，你经过了 3
个格子，这 3 个格子的数字依次是 5,2 和 0，则幸运数为 520.所有幸运数都是非负整数，并
且生成的幸运数是不包含前导 0 的。
通过小 C 的一波操作，得到了很多的幸运数。现在她想知道她无法获得的最小幸运数是多
少？

#include <stdio.h>
int matrix[N][N]; // N*N 矩阵
int visited[N][N]; 
int minlucky = 0; // 最小幸运数
int n; // 矩阵大小
void dfs(int x, int y, int curNum){
if(visited[x][y]) return;
 visited[x][y] = 1;
 
 curNum = curNum * 10 + matrix[x][y];
 
 if(curNum >= minlucky)
 minlucky = curNum + 1;
 
 dfs(x+1,y,curNum);
 dfs(x,y+1,curNum); 
 dfs(x-1,y,curNum);
 dfs(x,y-1,curNum); 
}
int main(){
 scanf("%d", &n);
 
 for(int i=0; i<n; i++)
 for(int j=0; j<n; j++)
 scanf("%d", &matrix[i][j]);
 
 dfs(0,0,0);
 
 printf("%d", minlucky);
 return 0;
}