您的位置是:少儿编程网>少儿C/C++编程少儿C/C++编程

信息学奥赛2019年CSP-J初赛真题分析(一)

少儿编程网2020-11-13 22:05:23少儿C/C++编程 人已围观 来源:少儿编程 -用户投稿

简介各位小伙伴,大家好:好久没更新,这次我们来聊聊C++。今天分享到的是去年(2019)年CSP第一次考试(J)入门级第一轮的一道完善程序题。之所以选择“信奥”的题,是因为信息学奥赛毕竟是“清、北”大学的敲门砖。其难度是不言而喻的,所出题目的专业性自然也就不用多说。

各位小伙伴,大家好:E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

好久没更新,这次我们来聊聊C++。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

今天分享到的是去年(2019)年CSP第一次考试(J)入门级第一轮的一道完善程序题。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

之所以选择“信奥”的题,是因为信息学奥赛毕竟是“清、北”大学的敲门砖。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

其难度是不言而喻的,所出题目的专业性自然也就不用多说。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

非常值得我们去好好的研究和参考。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

题干如下:E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

信息学奥赛2019年CSP-J初赛真题分析(一)信息学奥赛2019年CSP-J初赛真题分析(一)信息学奥赛2019年CSP-J初赛真题分析(一)信息学奥赛2019年CSP-J初赛真题分析(一)E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

题目很长,我们直接上代码,E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

完整的答案和代码如下:E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

信息学奥赛2019年CSP-J初赛真题分析(一)E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

比较难以理解的是递归算法中step变量的巧妙设置和使用。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

这里的step依次等于1,2,4,8……E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

我们以n = 3为例,这里step从里到外,依次是1,2,4,E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

而变化3次会产生一个8*8的矩阵。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

在进入第一层递归的时候,step = 3E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

所以此时的(x,y),(x,y+step),(x+step,y),(x+step,y+step)E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

分别是(0,0)(0,4)(4,0)(4,4)E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

如图所示:E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

信息学奥赛2019年CSP-J初赛真题分析(一)E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

在进入n= 2这层时上面每一个坐标会产生一个4*4的矩阵。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

以(0,0)为例,这时step=2对应的各个角的坐标如下:E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

信息学奥赛2019年CSP-J初赛真题分析(一)E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

这就是为什么在递归中step会等于1 << (n-1),左移n-1位的原因。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

因为这样正好使得(x+step,y+step)在顶点上。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

答案已经奉上(C,D,B,B,B)E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

关于答案的讲解,这里就不啰嗦了。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

 E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

因为,算法这东西用文字很难说的明白,就留给大家自己去学习、领会吧。E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台
E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台
E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台
来源   高维创客E0G少儿编程网-Scratch_Python_教程_免费儿童编程学习平台


相关文章:

支持一下 ( )

信息学奥赛2019年CSP-J初赛真题分析(一)

      匿名评论
    • 评论
    人参与,条评论
    少儿编程网

微信公众号

免费视频教程

先知道