网站开发数据库课程设计,学院网站建设管理办法,商标图案设计创意,制造企业网站建设目录 一.[蓝桥杯 2013 省 AB] 错误票据
代码如下#xff1a;
二.[蓝桥杯 2024 省 Java B] 报数游戏
代码如下#xff1a;
讲解#xff1a;
三.[蓝桥杯 2014 国 C] 拼接平方数
代码如下#xff1a;
四.三步问题#xff08;递归#xff0c;上台阶#xff09;
代码…目录 一.[蓝桥杯 2013 省 AB] 错误票据
代码如下
二.[蓝桥杯 2024 省 Java B] 报数游戏
代码如下
讲解
三.[蓝桥杯 2014 国 C] 拼接平方数
代码如下
四.三步问题递归上台阶
代码1不用递归
代码2使用递归
该代码特色
往期回顾 一.[蓝桥杯 2013 省 AB] 错误票据 代码如下
代码如下
#include stdio.h
int main()
{int n 0, i 0, j 0;int g[10005];scanf(%d, n);while (scanf(%d, g[i]) ! EOF){i;}int len i;
//冒泡排序for (i 0; i len - 1; i){for (j i 1; j len; j){if (g[i] g[j]){int t g[i];g[i] g[j];g[j] t;}}}int ans1 0, ans2 0;for (i 0; i len; i){if (g[i 1] - g[i] 2)ans1 g[i] 1;if (g[i] g[i 1])ans2 g[i];}printf(%d %d, ans1, ans2);return 0;
}虽然是二维数组但是可以看成一维
题解中冒泡排序是解答关键
二.[蓝桥杯 2024 省 Java B] 报数游戏 代码如下
int gcd(int a, int b)
{long long temp;long long temp1;long long n ;while (b ! 0){n a % b;temp a;a b;b temp;temp1 b;b n;n temp1;}return a;
}
int main()
{long long n 0;n 20*24/gcd(20, 24);long long m 202420242024 / 10*n;long long i 0;while (i5){if (m % 20 0 || m % 24 0){i;}m ;}m--;printf(%lld, m);return 0;
}讲解
先通过gcd函数辗转相除法求出最大公约数再利用公式a * b / gcd(a, b)求出最小公倍数20 和 24 的最小公倍数是 120。
这意味着每 120 个数里是 20 或 24 倍数的数有一定规律且数量是固定的。在区间[1, 120]内是 20 倍数的数有120 / 20 6个分别是 20、40、60、80、100、120是 24 倍数的数有120 / 24 5个分别是 24、48、72、96、120但其中 120 重复计算了一次所以在每 120 个数里满足条件的数共有6 5 - 1 10个。
批量计算利用这个规律可以批量跳过一些区间来快速逼近第 202420242024 个符合要求的数。比如已经知道每 120 个数里有 10 个符合要求的数那么可以先计算出完整的 “120 个数区间” 的个数即202420242024 / 10 20242024202这里只取整数部分个这样的区间。
这意味着前面已经处理了20242024202 * 120 2429042904240个数此时还剩下一定数量的数要继续找可以通过202420242024 % 10算出还需要在后续区间里找几个符合要求的数余数为 4表示还需要找 4 个。
然后从2429042904240 1开始继续按顺序找剩下的数直到找到 4 个符合要求的数为止这样相比逐个数字去判断是否符合要求可以大大减少循环次数节省时间。
细节问题
循环结束m--当i符合条件的时候m会又自增一下。
虽然要再找4个但是要i5因为开始进入一定符合但是不能算起始那个因此要循环五次
三.[蓝桥杯 2014 国 C] 拼接平方数 代码如下
#include stdio.h
#include math.h
#include stdlib.h// 计算数字的位数
int slen(int n)
{int len 0;while (n 0){n n / 10;len;}return len;
}// 判断一个数是否为拼接平方数
int is_spliced_square(int num)
{int len slen(num);for (int split_pos 1; split_pos len; split_pos){// 分割数字为两部分int part1 num / (int)pow(10, split_pos);int part2 num % (int)pow(10, split_pos);// 排除 0、00 等无效数字情况if (part1 0 || part2 0){continue;}int part1_sqrt (int)sqrt((double)part1);int part2_sqrt (int)sqrt((double)part2);if (part1_sqrt * part1_sqrt part1 part2_sqrt * part2_sqrt part2){return 1;}}return 0;
}int main()
{int a 0;int b 0;int i1 0;int i2 0;if (scanf(%d%d, a, b) ! 2){printf(输入格式有误请重新输入两个整数\n);return 1;}// 遍历区间内的所有数字进行判断并输出for (int i a; i b; i){i1 (int)sqrt(i);if (i1 * i1 ! i){continue;}else{if (is_spliced_square(i)){printf(%d\n, i);}}}return 0;
}
注意拼接平方数首先自己得是平方数
四.三步问题递归上台阶
三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。
示例1: 输入n 3 输出4 说明: 有四种走法
示例2: 输入n 5 输出13
提示:
n范围在[1, 1000000]之间
核心思想
当 n 3 时进入这个 for 循环从 i 4 开始逐步计算上 i 阶楼梯的走法数量。 递推关系的核心在于 a (s1 s2 s3) % 1000000007; 这一行。对于上 i 阶楼梯i 3最后一步可能是走了 1 阶那么前面 i - 1 阶的走法数量就是 s1、走了 2 阶前面 i - 2 阶的走法数量是 s2或者走了 3 阶前面 i - 3 阶的走法数量是 s3根据加法原理上 i 阶楼梯的总走法数量就是上 i - 1 阶、i - 2 阶、i - 3 阶楼梯走法数量之和即 s1 s2 s3。同时为了满足题目对结果取模的要求这里直接对相加的结果取模 1000000007 后赋值给 aa 就代表上 i 阶楼梯的走法数量取模后。
代码1不用递归
int waysToStep(int n){long long int s11,s22,s34,a0,b,c;if(n3){switch(n){case 1:as1;break;case 2:as2;break;case 3:a s3;break;}}else{for(int i4;in;i){a (s1s2s3)%1000000007;b s3;s3 a;c s2;s2 b;s1 c;}}return a;}
代码2使用递归
#include stdio.h
#include stdlib.h// 定义一个足够大的数组用于存储已经计算过的结果避免重复计算初始化为 -1 表示未计算过
long long int memo[1000001];// 递归函数结合记忆化来计算上n阶楼梯的走法数量取模操作按照题目要求进行
long long int waysToStep(int n) {if (n 1) return 1;if (n 2) return 2;if (n 3) return 4;// 如果已经计算过该值直接返回存储的结果避免重复计算if (memo[n]! -1) return memo[n];long long int result (waysToStep(n - 1) waysToStep(n - 2) waysToStep(n - 3)) % 1000000007;// 将计算结果存储到备忘录数组中memo[n] result;return result;
}
int main() {// 初始化memo数组为 -1表示都未计算过for (int i 0; i 1000001; i) {memo[i] -1;}int n 61;long long int ways waysToStep(n);printf(上 %d 阶楼梯的走法数量取模后为%lld\n, n, ways);return 0;
}该代码特色
数组的记忆使用避免了代码重复运算
1. 为什么会出现重复计算以纯递归情况分析
在不使用数组进行优化的纯递归解决 “三步问题” 的过程中存在大量重复的子问题计算。例如当我们要计算 waysToStep(5) 时按照递归关系
隐藏过程
long long int result (waysToStep(4) waysToStep(3) waysToStep(2)) % 1000000007;
需要先去计算 waysToStep(4)而计算 waysToStep(4) 时又会按照它的递归关系
隐藏过程
long long int result (waysToStep(3) waysToStep(2) waysToStep(1)) % 1000000007;
再次去计算 waysToStep(3) 和 waysToStep(2) 以及 waysToStep(1)。注意这里的 waysToStep(3) 和 waysToStep(2) 在计算 waysToStep(5) 时已经计算过一次了但是纯递归的方式没办法记住这个结果所以就会重复地去调用函数计算它们。
同样地在后续计算更大的 n 值时像 waysToStep(2) 和 waysToStep(3) 这样的基础子问题会被反复地计算很多很多次随着 n 的增大这种重复计算的次数会急剧增加导致效率变得极低白白浪费了很多计算资源。
1memo 数组的定义和初始化
首先定义了一个数组 memo 来存储已经计算过的结果代码如下
展开过程
这里把 memo 数组的每个元素初始化为 -1是为了表示对应位置也就是对应 n 值的上楼梯走法数量还没有被计算过后续通过判断元素的值是否为 -1 就能知道是否需要重新计算。
2在递归计算过程中的使用
在 waysToStep 函数内部每次要进行递归计算之前会先检查 memo 数组中对应位置的值代码如下
隐藏过程
if (memo[n]! -1) return memo[n];
这行代码的意思是如果 memo[n] 的值不等于 -1那就说明之前已经计算过了上 n 阶楼梯的走法数量并且已经把结果存储在了 memo[n] 这个位置此时就不需要再去重复地通过递归调用计算了直接返回 memo[n] 存储的结果就行这样就避免了重复计算已经算过的子问题。
而当发现 memo[n] 是 -1也就是还没有计算过时才会按照正常的递归关系去计算上 n 阶楼梯的走法数量计算完之后会把结果存储到 memo[n] 中方便下次再遇到同样的 n 值时直接获取代码如下
隐藏过程
long long int result (waysToStep(n - 1) waysToStep(n - 2) waysToStep(n - 3)) % 1000000007;
memo[n] result;
return result;
通过这样的方式在整个递归调用的过程中对于每个 n 值最多只需要计算一次其对应的上楼梯走法数量后续再次需要这个值时直接从 memo 数组中获取大大减少了不必要的计算提高了代码的执行效率尤其是当 n 的值比较大或者频繁调用 waysToStep 函数时这种优化效果会更加明显。
往期回顾
C语言——结构体超详解-CSDN博客
C语言——判断输入字符串是否合法代码分享-CSDN博客
C语言——字符串指针变量与字符数组易错分析-CSDN博客
C语言——习题练习一-CSDN博客
C语言——海龟作图对之前所有内容复习_海龟图c语言-CSDN博客
C语言函数递归经典题型——汉诺塔问题_汉诺(hanoi)塔问题-CSDN博客
C语言算法经典基础题型——求一个数的回文数两种方法_c语言编程题回文数-CSDN博客
