【day04】Fibonacci数列 | 单词搜索 | 杨辉三角

1.Fibonacci数列

题目链接： Fibonacci数列_牛客题霸_牛客网

解题思路：

求斐波那契数列的过程中，判断⼀下：何时n会在两个fib数之间。

#include <bits/stdc++.h>using namespace std;#define int long longsigned main()
{int n;cin >> n;int a = 0 , b = 1 , c = 1;while(n > c){a = b;b = c;c = a + b;}cout << min(c - n , n - b) << endl;return 0;
}

2.单词搜索

题目链接： 单词搜索_牛客题霸_牛客网

解题思路：简单的深度搜索题（dfs）

class Solution
{int n, m;bool vis[101][101] = {0};int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};public: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]){if (dfs(board, i, j, word, 0))return true;}}}return false;}bool dfs(vector<string> &board, int i, int j, string &word, int pos){if (pos == word.size() - 1)return true;vis[i][j] = true;for (int k = 0; k < 4; k++){int a = i + dx[k], b = dy[k] + j;if (a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && board[a][b] == word[pos + 1]){if (dfs(board, a, b, word, pos + 1))return true;}}vis[i][j] = false;return false;}
};

3.杨辉三角

题目链接：

杨辉三角_牛客题霸_牛客网

解题思路：最基础的dp模型，按照规律模拟出来杨辉三⻆即可。

#include <bits/stdc++.h>using namespace std;#define int long longint dp[31][31];
signed main()
{int n;cin >> n;dp[1][1] = 1;for(int i = 2;i <= n;i ++){for(int j = 1;j <= n;j ++){dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++){printf("%5d", dp[i][j]);}printf("\n");}return 0;
}