欢迎回到:遇见蓝桥遇见你,不负代码不负卿!
目录
一、简单模拟
栗子:换酒问题
栗子:按奇偶排序数组
栗子:害死人不偿命的(3n+1)猜想
栗子:挖掘机技术哪家强
二、查找元素
栗子:找 x
三、图形输出
栗子:跟奥巴马一起编程
四、日期处理
栗子:日期差值
五、进制转换
栗子:D 进制的 A+B
六、字符串处理
栗子:回文串
栗子:说反话
七、蓝桥结语:遇见蓝桥遇见你,不负代码不负卿!
【前言】
之前有铁汁要求将入门部分也更新一下,比如简单模拟,简单数学部分,这两块在蓝桥杯中考的都不难,但是特别重要,就像我们高考的时候数学试题那前五道选择题,前两道填空题一样,属于送分题,但是对于马虎的同学是致命的,所以要上心哦,这部分内容没有涉及算法,完全只是根据题目描述来进行代码的编写,侧重考查的是代码能力,我们在做这种类型题目的时候一定要认真读题!读题!!题!!!对于模拟题,“题目怎么说,你就怎么做” 。这块内容最好别失分,将这部分的分拿到了,后面的题目就算不会用算法解决,暴力求解也能省三起步!毕竟蓝桥杯的别名就是“暴力杯”嘛!不过要想拿高分还是得把算法学好,求解问题时能事半功倍!!
【声明】
简单模拟、简单数学这周就会更新结束,下周更新BFS部分,对于DFS、BFS要大量练习哦,蓝桥中涉及的比较多,后面我将贪心、动态规划等更新结束,会开启一个蓝桥冲刺专栏,系统性的刷题,包括历年的真题!笔者已经将路线安排好咯,只不过正在挤时间更新,一起加油鸭!
这部分内容比较简单,但是请铁汁们不要眼高手低哦,希望大家可以动动小手把例题全部自己实现一遍,这对基础代码能力的提升是很重要的!
题型:
- 简单模拟
- 查找元素
- 图形输出
- 日期处理
- 进制转换
- 字符串处理
一、简单模拟
模拟题是一类“题目怎么说,你就怎么做” 的题目,如果实现起来不太麻烦,就可以称之为“简单模拟”这种题目不涉及算法,完全只是根据题目描述来进行代码的编写,所以考查的是代码能力,下面先举三个例子:
栗子:换酒问题
题目描述:
小区便利店正在促销,用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
如果喝掉了酒瓶中的酒,那么酒瓶就会变成空的。
请你计算 最多 能喝到多少瓶酒。
示例1:
输入:numBottles = 9, numExchange = 3
输出:13
解释:你可以用 3 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
示例2:
输入:numBottles = 15, numExchange = 4
输出:19
解释:你可以用 4 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 15 + 3 + 1 = 19 瓶酒。
思路:
如果有b 瓶酒,并且规定e 个空瓶换一瓶酒,首先我们一定可以喝到 b 瓶酒,剩下 b 个空瓶。接下来我们可以拿瓶子换酒,每次拿出 e 个瓶子换一瓶酒,然后再喝完这瓶酒,得到一个空瓶。以此类推,我们可以统计得到答案。
代码执行:
int numWaterBottles(int numBottles, int numExchange){
int bottle = numBottles;//空瓶子的数量
int ans = numBottles;//总共喝的酒
while(bottle >= numExchange)//空瓶子只要大于numExchange,循环就要继续
{
bottle -= numExchange;
ans++;
bottle++;
}
return ans;
}
栗子:按奇偶排序数组
题目描述:
输入一个长度为 n 整数数组,数组里面不含有相同的元素,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前面部分,所有的偶数位于数组的后面部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
示例1:
输入:[1,2,3,4]
返回值:[1,3,2,4]
示例2:
输入:[2,4,6,5,7]
返回值:[5,7,2,4,6]
思路:
题目比较简单,只需要遍历两遍数组即可
代码执行:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @param arrayLen int array数组长度
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*
* C语言声明定义全局变量请加上static,防止重复定义
*/
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
// write code here
int* ans = (int*)malloc(sizeof(int) * arrayLen);
*returnSize = arrayLen;
int i = 0;
int j = 0;
for(i = 0; i < arrayLen; i++)
{
if(array[i] % 2)
{
ans[j++] = array[i];
}
}
for(i = 0; i < arrayLen; i++)
{
if(!(array[i] % 2))
{
ans[j++] = array[i];
}
}
return ans;
}
栗子:害死人不偿命的(3n+1)猜想
题目描述:
卡拉兹猜想:
对任意一个自然数n ,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。这样一直反复砍下去,最后一定在某一步得到n = 1 。卡拉兹在1950年的世界数学家大会上公布了这个猜想,传说当时耶鲁大学师生齐动员,平明想证明这个貌似很荒唐......
此处并非要证明卡拉兹猜想,而是对给定的任一不超过1000的正整数n, 简单的数一下需要多少步才能得到 n = 1?这里就拿n = 1000举例。
思路:
用while循环语句反复判断n 是否为1:
- 如果 n == 1,则退出循环;
- 如果 n != 1,则判断n 是否为偶数,如果是偶数,则令n 除以2;否则令n 为(3*n+1)/2, 之后令计数器step++;
这样退出循环后,step的值就是需要的答案。
代码执行:
#include<stdio.h>
int main()
{
int n = 1000;
int step = 0;
while (n != 1)
{
if (!(n % 2))//偶数
{
n /= 2;
}
else//奇数
{
n = (3 * n + 1) / 2;
}
step++;
}
printf("%d\n", step);//输出72
return 0;
}
栗子:挖掘机技术哪家强
题目描述:
为了用事实说明挖掘机技术到底哪家强,组织了一场挖掘机技能大赛。请根据比赛结果统计出技能最强的哪个学校。
输入格式:
在第一行给出不超过10^5 的正整数N ,即参赛人数。随后N 行,每行给出一位参赛者的信息和成绩,包括其所代表的学校的编号及其比赛成绩,中间以空格分隔(注意,学校从1开始连续编号,比赛成绩百分制)
输出格式:
在一行中给出总得分最高的学校的编号及其总分,中间以空格分隔。题目保证答案唯一,没有并列。
输入样例:
6
3 65
2 80
1 100
2 70
3 40
3 0
输出样例:
2 150
思路:
- 令数组school[MAXN]记录每个学校的总分,初值为0,对每一个读入的学校schID与其对应的分数score,令school[schID] += score;
- 令变量k 纪录最高总分的学校编号,变量max纪录最高总分,初值为-1,由于学校是连续编号的,因此枚举编号1~N,不断更新k 和max 即可。
代码执行:
#include<stdio.h>
#define MAXN 100010
int school[MAXN] = { 0 };//记录每个学校的总分
int main()
{
int n = 0;
int schID = 0;//学校编号
int score = 0;//分数
scanf("%d", &n);//参赛人数
for (int i = 0; i < n; i++)//读入每一位参赛人员信息
{
scanf("%d %d", &schID, &score);
school[schID] += score;//学校schID的总分增加score
}
int k = 0;//用于记录最高总分的学校编号
int max = -1;//用于记录最高总分
for (int i = 1; i <= n; i++)//由于学校是从1开始连续编号的,所以范围是1~N,其中包括N
{
if (school[i] > max)
{
max = school[i];
k = i;
}
}
printf("%d %d\n", k, max);
return 0;
}
二、查找元素
有时候我们会遇到这样一种情况:给定一些元素,然后查找某个满足条件的元素。这就是查找操作需要做的事情。查找是学习写代码的一项基本功,是肯定需要掌握的。一般来说,如果需要在一个比较小范围的数据集里进行查找,那么直接遍历每一个数据即可;如果需要查找的范围比较大,那么可以用二分查找等算法进行更加快速的查找。这里就讲一下在小范围的数据集里查找指定元素。
二分查找算法之前已经更新咯,还没康的铁汁快点去康康吧。
蓝桥杯算法竞赛系列第四章——二分算法_安然无虞的博客-CSDN博客
栗子:找 x
题目描述:
输入一个数n (n >> 1 && n << 200),然后输入n 个数值各不相同的数,再输入一个值x,输出这个值在这个数组中的下标(下标从0开始,若不在数组中则输出-1)
输入格式:
测试数据有多组,输入n(n>=1 && n<=200),接着输入n 个数,然后输入x
【敲黑板】:对于这种输入格式中说明或者要求测试数据有多组时,要写成循环,直到读取到EOF停止。
输出格式:
对于每组输入,请输出结果。
样例输入:
4
1 2 3 4
3
样例输出:
2
思路:
题目给定了n 个互不相同的数,然后需要从中寻找值为x 的数的下标,因此可以设定一个数组a ,用来存放这n 个数。然后遍历数组a ,寻找某个下标k ,使得a[k] == x 成立,如果找到,则输出k ,并退出查询;如果当遍历完数组之后还没有找到x ,那么输出-1。
代码执行:
#include<stdio.h>
#define MAXN 210
int a[MAXN] = { 0 };
int main()
{
int n = 0;
int x = 0;
while (scanf("%d", &n) != EOF)//考虑到多组输入,所以写成循环的形式
{
for (int i = 0; i < n; i++)
{
scanf("%d", &a[i]);//输入n 个数
}
scanf("%d", &x);//输入欲查询的数
int k = 0;//下标
for (k = 0; k < n; k++)
{
if (a[k] == x)//如果找到了x,输出对应的下标
{
printf("%d\n", k);
break;//找到了之后记得退出查询
}
}
if (k == n)//如果没有找到,输出-1
{
printf("-1\n");
}
}
return 0;
}
三、图形输出
在有些题目中,题目会给定一些规则,需要考生根据规则来进行画图。所谓图形,其实是由若干字符组成的,因此只需要弄清楚规则就能编写代码。这种题目一般有两种做法:
- 通过规律,直接进行输出;
- 定义一个二维字符数组,通过规律填充之,然后输出整个二维数组
栗子:跟奥巴马一起编程
题目描述:
美国总统奥巴马不仅呼吁所有人都学习编程,甚至亲自编写代码,成为美国历史上首位编写计算机代码的总统。2014年底,为庆祝“计算机科学教育周” 正式启动,奥巴马编写了一个简单的计算机程序——在屏幕上画一个正方形。
输入格式:
在一行中给出正方形边长N(N >= 3 && N <= 20)和组成正方形边的某种字符C,间隔一个空格。
输出格式:
由给定的字符C画出的正方形。当时注意到行间距比列间距大,所以为了让结果看上去更像正方形,所输出的行数实际上是列数的50%(四舍五入取整)
样例输入:
10 7
样例输出:
7777777777
7 7
7 7
7 7
7777777777
思路:
由于行数是列数的一半(四舍五入取整),因此当列数col 是奇数时,行数row 就是col / 2 + 1;当列数col 是偶数时,row 就是col / 2。
代码执行:
#include<stdio.h>
int main()
{
int row = 0;//行
int col = 0;//列
char ch = 0;//符号
//输入列数、字符
scanf("%d %c", &col, &ch);//注意哦,输入空格时%c也会读取的,所以中间要自动加上空格
//判断col奇偶性,并且是奇数时要向上取整
if (col % 2)
{
row = col / 2 + 1;
}
else
{
row = col / 2;
}
int i = 0;
int j = 0;
//第一行,col个字符
for (i = 0; i < col; i++)
{
printf("%c", ch);
}
printf("\n");
//第2~row-1行(注意这一层循环的思想)
for (i = 2; i < row; i++)
{
printf("%c", ch);//每行的第一个指定的字符
for (j = 0; j < col - 2; j++)//每行的第2~col-1列
{
printf(" ");//col-2个空格
}
printf("%c", ch);
printf("\n");
}
//最后一行,col个字符
for (i = 0; i < col; i++)
{
printf("%c", ch);
}
return 0;
}
四、日期处理
日期处理的问题总是会让很多人感到头疼,因为在这种问题中,总是需要处理平年和闰年时的情况(由此产生二月的天数区别)、大约和小月的问题,因此细节比较繁杂。但是只要细心处理细节,一般都能很好的解决这类问题。
栗子:日期差值
题目描述:
有两个日期,求这两个日期之间的天数,如果两个日期是连续的,则规定它们之间的天数为两天。
输入格式:
有多组数据,每组数据有两行,分别表示两个日期,形式为YYYYMMDD。
输出格式:
每组数据输出一行,即日期差值
样例输入:
20130101
20130105
样例输出:
5
思路:
不妨假设第一个日期早于第二个日期(否则进行交换)。
这种求日期之间相差天数的题目有一个很直接的思路,即令日期不断加一天,直到第一个日期等于第二个日期为止,即可统计出答案。
具体处理时,如果当加上一天之后天数d 等于当前月份m 所拥有的的天数加1,那么就令月份m 加1、同时置天数d 为1号(即把日期变为下个月的1号);如果此时月份m 变成了13,那么就令年份y 加1、同时置月份m 为1月(即把日期变成下一年的1月)
为了方便直接取出每个月的天数不妨给定一个二维数组 int month[13][2],用来存放每个月的天数,其中第二维用0表示平年,1表示闰年,然后,再想想为什么把一维赋为13?
其实还有一种比较快的方法,在这里笔者就不给出咯,有兴趣的铁汁可以了解一下,欢迎留言交流哦,有时间笔者都会回的。
代码执行:
#include<stdio.h>
//#include<stdbool.h>
//平年和闰年每个月的天数
//之所以将一维写成13,是因为保证二维数组的下标与我们生活中的月份相对应,方便处理
int month[13][2] = { {0,0},{31,31},{28,29},{31,31},{30,30},{31,31},{30,30},{31,31},{31,31},{30,30},{31,31},{30,30},{31,31} };
bool isLeap(int year)
{
return ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0));
}
int main()
{
int time1, y1, m1, d1;
int time2, y2, m2, d2;
scanf("%d %d", &time1, &time2);
if (time1 > time2)//设定time1早于time2,也就是说数字也它小,否则交换它们的值
{
int temp = time1;
time1 = time2;
time2 = temp;
}
y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;
int ans = 1;//记录结果,之所以初始值为1,为了满足“当两个日期是连续的,规定它们之间的天数是2天”这个条件
//第一个日期没有达到第二个日期时进行循环
//即!((y1 == y2)&&(m1 == m2)&&(d1 == d2))
while (y1 < y2 || m1 < m2 || d1 < d2)
{
d1++;//天数加1
if (d1 == month[m1][isLeap(y1)] + 1)//满当月天数
{
m1++;//日期变成下个月的1号
d1 = 1;
}
if (m1 == 13)//月份满12个月
{
y1++;//日期变成下一年的1月
m1 = 1;
}
ans++;//累计
}
printf("%d\n", ans);//输出结果
}
其实逻辑很简单,现在看看去年蓝桥杯看的一道分值五分的真题:
纪念日(5分)
题目描述:
2020 年 7 月 1 日是中国 共 产 党 成立 99 周年纪念日。
中国 共 产 党 成立于 1921 年 7 月 23 日。
请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包含多少分钟?
其实历年来这样的题目比比皆是,所以说,送分题,铁汁们一定要好好拿下!
五、进制转换
日常生活中人们使用的数字一般都是十进制,而计算机使用的进制是二进制,另外还有八进制、十六进制以及各种数字的进制,那么这就会产生一个问题:对两个不同进制,应该如何进行相互转换呢?下面请听笔者慢慢道来...
对于一个P进制的数,如果要转换成Q进制,需要分为两步:
- 将P进制数x 转换为十进制数y
- 将十进制数y 转换为Q进制数z
第一步:将P进制数x 转换为十进制数y
对一个十进制数 a = d1d2...dn,它可以写成这个形式:
a = d1 * 10^(n-1) + d2 * 10^(n-2) + ... + dn * 10^0
同样的,如果P进制数x 为a1a2...an,用下面这种方法即可转换为十进制数 y:
y = a1 * P^(n-1) + a2 * P^(n-2) + ... an * P^0
上面的公式用循环实现:
int y = 0;
int pro = 1;//pro在循环中会不断乘以P,得到P^0(1),P^1,P^2,...
while (x != 0)
{
y = y + (x % 10) * pro;//x % 10 是为了每次获取x 的个位数
x = x / 10;//去掉x 的个位
pro = pro * P;
}
第二步:将十进制数y 转换为Q进制数 z
采用“除基取余法”。所谓“基”,是指将要转换成的进制Q,因此除基取余法的意思就是每次将待转换数除以Q,然后将得到的余数作为低位存储,而商则继续除以Q并进行上面的操作,最后当商为0时,将所有位从高到低输出就可以得到z 。
举一个例子,现在将十进制数11转换为二进制数:
11 除以2,得商为5,余数为1;
5 除以2,得商为2,余数为1;
2 除以2,得商为1,余数为0;
1 除以2,得商为0,余数为1,算法终止;
将余数从后往前输出,得1011即为11 的二进制数。
由此可以得到实现的代码(将十进制数y 转换为Q进制,结果存放于数组中),想想为什么存放在数组中?
int z[40] = { 0 };//数组z 存放Q进制数y 的每一位,num 为位数
int num = 0;
do
{
z[num] = y % Q;//除基取余
num++;
y = y / Q;
} while (y != 0);//当商不为0进行循环
这样z 数组从高位z[num - 1]到低位 z[0]即为Q进制z,进制转换完成。值得注意的是,代码中使用do...while()语句而不是while语句的原因是:如果十进制数y 恰好等于0,那么使用while语句将使循环直接跳出,导致结果出错(正确结果应该是数组z 中存放了z[0] = 0)
栗子:D 进制的 A+B
题目描述:
输入两个非负十进制整数A和B(<= 2^30 - 1)以及D(进制数),输出A+B的D(2~10)进制数
输入格式:
在一行中依次给出三个整数A、B和D(进制数)
输出格式:
A+B的D进制数
输入样例:
123 456 8
输出样例:
1103
思路:
先计算A+B(此时为十进制),然后把结果转化为D进制,而十进制转化为D进制的过程可以直接进行“除基取余法”
代码执行:
#include<stdio.h>
int main()
{
int A = 0;
int B = 0;
int D = 0;
int z[40] = { 0 };//存放D进制的每一位
scanf("%d %d %d", &A, &B, &D);
int y = A + B;
int n = 0;
do
{
z[n++] = y % D;
y /= D;
} while (y != 0);
for (int i = n - 1; i >= 0; i--)//从高位到低位进行输出
{
printf("%d", z[i]);
}
return 0;
}
六、字符串处理
字符串处理题在考试中十分常见,也是能很好体现代码能力的一种题型。本来笔者想把它专门弄成一章的,但是考虑到进度的问题就没有这么做,等到后面再看看能不能挤出时间来全面总结一下字符串相关问题。对于这种题型,一般需要仔细分析清楚题目中的输入和输出格式才能顺利解决题目。在有些题目中,可能实现逻辑会非常麻烦,而且可能会有许多细节和边界情况,因此对代码能力较弱的考生是很不利的。此类题目需要多做多想,积累经验。
栗子:回文串
题目描述:
读入一串字符,判断是否是“回文串”。“回文串” 是一个正读和反读都一样的字符串,比如“level” 或者 “noon” 就是回文串。
输入格式:
一行字符串,长度不超过255
输出格式:
如果是回文串,输出“YES”,否则输出“NO”
样例输入:
12321
样例输出:
YES
思路:
假设字符串str 的下标是从0 开始的,由于“回文串” 是正读和反读都一样的字符串,因此只需要遍历字符串的前一半(注意:不需要取到 i == len / 2),如果出现字符str[i]不等于其对称位置str[len - 1 - i],就说明这个字符串不是回文串;如果前一半的所有字符str[i] 都等于对称位置的str[len - 1 - i],那么就说明这个字符串是“回文串”
代码执行:
#include<stdio.h>
#include<string.h>
#define MAXN 256
//判断字符串str是否是回文串
bool judge(char* str)
{
int len = strlen(str);
int i = 0;
for (i = 0; i < len / 2; i++)
{
if (str[i] != str[len - 1 - i])
{
return false;
}
}
return true;
}
int main()
{
char str[MAXN] = { 0 };
while (gets(str))//读入字符串
{
bool flag = judge(str);
if (flag == true)
printf("YES\n");
else
printf("NO\n")
}
return 0;
}
栗子:说反话
题目描述:
给定英文一个句子,要求编写程序,将句中所有单词按颠倒顺序输出
输入格式:
测试输入包含一个测试用例,在一行给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由英文字母(大小写有区分)组成的字符串,单词之间用一个空格分开
输出格式:
每个测试用例的输出占一行,输出倒序后的句子
样例输入:
Hello World Here I Come
样例输出:
Come I Here World Hello
思路:
使用gets函数读入一整行,(想想为什么不用scanf()?),从左至右枚举每一个字符,以空格为分隔符对单词进行划分,并按照顺序存放到二维字符数组中,最后按单词输入顺序的逆序来输出所有单词。
【注意点】:
- 最后一个单词之后输出空格会导致“格式错误”;
- 由于PAT是单点测试,因此产生了下面这种更简洁的方法,即使用EOF来判断单词是否已经输入完毕。
#include<stdio.h>
int main()
{
int num = 0;
char ans[90][90] = { 0 };
while (scanf("%s", ans[num]) != EOF)//想想为什么不要&
{
num++;
}
for (int i = num - 1; i >= 0; i--)//倒着输出单词
{
printf("%s\n", ans[i]);
if (i > 0)//注意这个条件
{
printf(" ");
}
}
return 0;
}
要注意的是,在黑框中手动输入时,系统并不知道什么时候到达了所谓的“文件末尾”,因此需要用<ctr + Z>组合键然后按<Enter>键的方式来告诉系统已经到了EOF,这样系统才会结束while。
#include<stdio.h>
#include<string.h>
int main()
{
char str[90] = { 0 };
gets_s(str);
int len = strlen(str);
int r = 0;//行
int h = 0;//列
char ans[90][90] = { 0 };//ans[0]~ans[r]存放单词
for (int i = 0; i < len; i++)
{
if (str[i] != ' ')//如果不是空格,则存放至ans[r][h],并令h++
{
ans[r][h] = str[i];
h++;
}
else//如果是空格,说明一个单词结束,行r++,列h 恢复至0
{
ans[r][h] = '\0';//末尾是结束标志\0
r++;
h = 0;
}
}
for (int i = r; i >= 0; i--)//倒着输出单词即可
{
printf("%s", ans[i]);
if (i > 0)
printf(" ");
}
return 0;
}
七、蓝桥结语:遇见蓝桥遇见你,不负代码不负卿!
上面的题目都很简单,所以铁汁们都自己实现一遍哈,不能懒惰哦,这部分的分数是必须要拿到的,冲冲冲鸭!文章来源:https://www.toymoban.com/news/detail-421665.html
最后的最后,请求老铁给笔者来个三连吧,万字博文,码字不易,求求啦。文章来源地址https://www.toymoban.com/news/detail-421665.html
到了这里,关于蓝桥杯算法竞赛系列第六章——蓝桥必备篇之模拟、思维的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!