C/C++每日一练17

第一题小乐乐改数字题目描述小乐乐获得了一个数字 n他想把这个数字改成 m。每次操作可以将数字的某一位加 1 或减 1求最少操作次数。算法原理每个数位的修改是独立的比如个位、十位等修改某一位不会影响其他位。例如 n123m456个位 3 到 6 需 3十位 2 到 5 需 3百位 1 到 4 需 3总操作 3339 次。因此直接遍历两个数字的每一位用绝对值计算差值并累加结果即为最少操作次数。代码cpp运行#include iostream #include string #include cmath using namespace std; int main() { string n, m; cin n m; int res 0; for (int i 0; i n.size(); i) { res abs(n[i] - m[i]); } cout res endl; return 0; }第二题十字爆破题目描述在 n×n 的网格中每个格子有一个数字。选择一个格子进行 “十字爆破”会使该格子所在行和列的所有数字变为 0求爆破后网格中 0 的最大数量。算法原理对每个格子 (x,y)计算爆破后 0 的总数。首先统计爆破前该行和该列已有的 0 的数量注意 (x,y) 若本身是 0会被重复统计需减 1。爆破后新增的 0 数量为 “行长度 列长度 - 1”加上原有 0 的数量就是总 0 数。遍历所有格子取最大值且结果不能超过网格总格子数 n×n。代码cpp运行#include iostream #include vector using namespace std; int main() { int n; cin n; vectorvectorint grid(n, vectorint(n)); for (int i 0; i n; i) { for (int j 0; j n; j) { cin grid[i][j]; } } int max_zero 0; for (int x 0; x n; x) { for (int y 0; y n; y) { int cnt 0; for (int i 0; i n; i) { if (grid[i][y] 0) cnt; } for (int j 0; j n; j) { if (grid[x][j] 0) cnt; } if (grid[x][y] 0) cnt--; int total cnt (n n - 1); if (total max_zero) max_zero total; } } cout min(max_zero, n * n) endl; return 0; }第三题比那名居的桃子题目描述树上有 n 个桃子每次可以摘 1 个或 2 个求有多少种不同的摘法。算法原理这是斐波那契数列问题。设 f (n) 为摘 n 个桃子的方法数最后一次摘 1 个时前面 n-1 个有 f (n-1) 种方法最后一次摘 2 个时前面 n-2 个有 f (n-2) 种方法故递推公式 f (n)f (n-1)f (n-2)。边界条件n1 时 f (1)1n2 时 f (2)2。用迭代法计算 f (n)时间复杂度 O (n)空间复杂度 O (1)。代码cpp运行#include iostream using namespace std; int main() { int n; cin n; if (n 1) { cout 1 endl; return 0; } int a 1, b 2; for (int i 3; i n; i) { int c a b; a b; b c; } cout b endl; return 0; }谢谢