当前位置：首页 > web >正文

【笔试训练4】Fibonacci数列|单词搜索|杨辉三角

web 2025/7/21 20:43:31

文章目录

Fibonacci数列
单词搜索
杨辉三角

Fibonacci数列

Fibonacci数列
在这里插入图片描述

算法思想：在求斐波那契数列的过程中，判断输入的数n离那个斐波那契数列最近，求出来即可。
求斐波那契数列：

a = 0;
b = 1;
c = 1;
while(...)
{a = b;b = c;c = a + b
}

具体代码：

#include <iostream>
using namespace std;//判断这个数在斐波那契数列中离哪个数最近呗
//求斐波那契数列的过程中判断这个数离哪个斐波那契数列最近int main() 
{int n;cin >> n;int a = 0,b = 1,c = 1; //前三个斐波那契数while(n > c){a = b;b = c;c = a + b;}cout << min(n - b,c - n) << endl;
}

单词搜索

在这里插入图片描述
算法思想：使用深度优先搜索算法（dfs）

大模块：

1.在二维数组中，判断每个字符是否跟word的第一个字符匹配。（如果匹配了，就对该字符进行深度优先搜索，传递几个参数给dfs函数（board，i，j，word，pos）也就是从[i,j]位置开始进行上下左右遍历，找到与pos位置匹配的字符，找到之后，继续从成功匹配的位置再次调用dfs，传入pos+1。
2.搜索如果返回true，则在二维数组中成功匹配了word的所有字符）直接返回即可。
3、如果找的所有路口都不符合条件，则返回false。（可能会有多个入口）

深度优先搜索模块（dfs）：

在这里插入图片描述

这样看来，需要写4个相似的函数，上下左右都遍历一遍。
但是有更简单的方法：

//使用向量来表示左右上下四个方向
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

使用时只需要循环遍历：int x = i + dx[k], y = j + dy[k] 即可。

但是还有一个问题：在进行回溯时，可能会出现这个位置遍历过的情况，比如：
word = “XXXX”;
在进入入口字符X时，往右递归，为X，符合条件，在右边这个X开始，又往左递归，发现又符合条件，又是X，这样当XXXX符合条件时，就成功返回了。但实际上是不对的。

所以要想办法标记已经遍历过的位置。
在这里插入图片描述
办法如下：

.设置一个bool数组，数组大小与字符数组大小相同，每个位置标记为true，表示已经遍历过，false表示没遍历过。

注意这几个细节问题，就能解决这道题。

代码如下：

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param board string字符串vector * @param word string字符串 * @return bool布尔型*/int m ,n;bool vis[101][101] = {0};//深度优先搜索bool exist(vector<string>& board, string word) {m = board.size(),n = board[0].size();for(int i = 0;i < m;++i)for(int j = 0;j < n;++j){if(board[i][j] == word[0]) //找入口{vis[i][j] = true; //标记当前位置已经遍历过if(dfs(board,i,j,word,1)) return true;vis[i][j] = false; //还原现场,因为ij位置行不通} }return false;}//使用向量来表示左右上下四个方向int dx[4] = {0,0,-1,1};int dy[4] = {-1,1,0,0};bool dfs(vector<string>& board,int i,int j,const string& word,int pos){if(pos >= word.size())return true;//遍历i,j位置的四个方向for(int k = 0;k < 4;++k){int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board,x,y,word,pos+1))return true;vis[x][y] = false;}}return false;}
};