C/C++每日一练4

1.最小步数变成 Fib 数给定数字 x每次操作可以 \(x\pm1\)求最少操作步数使得数字变为斐波那契数。 等价于找到离 x 最近的斐波那契数输出差值绝对值。举例子 \(x4\) Fib 序列0,1,1,2,3,5,8… 离 4 最近是 3、5差值都是 1答案 1C AC 完整代码cpp运行#include iostream #include vector #include climits #include cmath using namespace std; typedef long long ll; int main() { vectorll fib; fib.push_back(0); fib.push_back(1); // 预先生成足够多斐波那契数 while (true) { ll nxt fib.back() fib[fib.size() - 2]; if (nxt 2e18) break; fib.push_back(nxt); } ll x; cin x; ll ans LLONG_MAX; for (ll v : fib) { ll d abs(v - x); if (d ans) ans d; } cout ans endl; return 0; }思路说明预先生成全部不超过 \(2\times10^{18}\) 的斐波那契数列数量很少不到 90 项遍历每一个 fib 数计算与输入 x 的距离记录最小距离直接输出2.单词搜索题目描述给定一个m x n二维字符网格board和一个字符串单词word。 在网格中按上下左右四个方向搜索是否存在该单词每个位置字符只能使用一次不能重复走可以从任意格子起点出发输入样例plaintextA B C E S F C S A D E E word ABCCED 输出true思路DFS 回溯遍历网格每一个点作为起点深度优先搜索向上下左右走使用标记原地修改 /vis 数组防止重复访问匹配完所有字符直接返回 true剪枝C AC 代码牛客可直接提交cpp运行#include iostream #include vector #include string using namespace std; // 四个方向上、下、左、右 int dir[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; bool dfs(vectorvectorchar board, string word, int x, int y, int idx) { // 当前字符不匹配 if(board[x][y] ! word[idx]) return false; // 全部匹配完成 if(idx word.size() - 1) return true; char tmp board[x][y]; board[x][y] #; // 原地标记已访问 for(int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; // 边界判断 if(nx 0 nx board.size() ny 0 ny board[0].size()) { if(dfs(board, word, nx, ny, idx 1)) return true; } } board[x][y] tmp; // 回溯恢复 return false; } bool exist(vectorvectorchar board, string word) { int m board.size(); int n board[0].size(); for(int i 0; i m; i) { for(int j 0; j n; j) { if(dfs(board, word, i, j, 0)) return true; } } return false; } int main() { int m,n; cin m n; vectorvectorchar board(m,vectorchar(n)); for(int i0;im;i) for(int j0;jn;j) cin board[i][j]; string word; cin word; if(exist(board,word)) cout true; else cout false; return 0; }关键要点笔试易错回溯必须恢复现场否则多条路径互相干扰优先判断idx word.size()-1找到直接 return大量剪枝原地修改#节省空间不允许修改原数组就开vis[][]只允许上下左右不能对角线3.BC40 杨辉三角题目描述输入 n输出 n 行杨辉三角。第一行一个数字 1每行首尾数字为 1中间数字 上一行相邻两个数字之和每个数字输出占 5 个宽度域宽 5右对齐输入描述输入一个整数 n1 ≤ n ≤ 20输出描述输出 n 行杨辉三角每个数值占 5 字符宽度。样例输入plaintext4样例输出plaintext1 1 1 1 2 1 1 3 3 1#include iostream #include vector using namespace std; int main() { int n; cin n; vectorint arr; for (int i 0; i n; i) { arr.push_back(1); for (int j i - 1; j 0; --j) { arr[j] arr[j] arr[j - 1]; } for (int x : arr) { printf(%5d, x); } printf(\n); } return 0; }谢谢