我的账户
觅峰编程

让孩子更有未来

亲爱的游客,欢迎!

已有账号,请

如尚未注册?

信息学奥赛赛题蛇形填数

[复制链接]
admin 发表于 2020-12-27 22:15:57 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
蛇形填数
     在n*n方阵里填入1,2,3,…,n*n,要求填成蛇形。例如n=4时方阵为:
    10 11 12  1
     9  16 13  2
     8  15 14  3
     7    6   5  4
    上面的方阵中,多余的空格只是为了便于观察规律,不必严格输出,n<=8。
【分析】:
    类比数学中的矩阵,我们可以用一个所谓的二维数组来储存题目中的方阵。只需声明一个int a[MAXN][MAXN],就可以获得一个大小为MAXN×MAXN的方阵。在声明时,两维的大小不必相同,因此也可以声明int a[30][50]这样的数组,第一维下标范围是0,1,2,…,29,第二维下标范围是0,1,2,…,49。
    让我们从1开始依次填写。设“笔”的坐标为(x,y),则一开始x=0,y=n-1,即第0行,第n-1列(别忘了行列的范围是0到n-1,没有第n列)。“笔”的移动轨迹是:下,下,下,左,左,左,上,上,上,右,右,下,下,左,上。总之,先是下,到不能填了为止,然后是左,接着是上,最后是右。“不能填”是指再走就出界(例如4→5),或者再走就要走到以前填过的格子(例如12→13)。如果我们把所有格子初始为0,就能很方便地加以判断。

回复

使用道具 举报

精彩评论1

 楼主| admin 发表于 2020-12-27 22:16:56 | 显示全部楼层
    这段程序充分利用了C++语言简洁的优势。首先,赋值x=0和y=n-1后马上要把它们作为a数组的下标,因此可以合并完成;tot和a[0][n-1]都要赋值1,也可以合并完成。这样,我们用一条语句完成了多件事情,而且并没有牺牲程序的可读性,这段代码的含义显而易见。
    那4条while语句有些难懂,不过十分相似,因此只需介绍其中的第一条:不断向下走,并且填数。我们的原则是:先判断,再移动,而不是走一步以后发现越界了再退回来。这样,我们需要进行“预判”,即是否越界,以及如果继续往下走会不会到达一个已经填过的格子。越界只需判断x+1<n,因为y值并没有修改;下一个格子是(x+1,y),因此只需a[x+1][y]==0,简写成!a[x+1][y](其中!是“逻辑非”运算符)。
    细心的孩子也许会发现这里的一个“潜在bug”;如果越界,x+1会等于n,a[x+1][y]将访问非法内存!幸运的是,这样的担心是不必要的。&&是短路运算符。如果x+1<n为假,将不会计算!a[x+1][y],也就不会越界了。
    至于为什么是++tot而不是tot++,留给孩子们去思考。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关注我们
觅峰编程关注孩子未来

客服电话:18834858459

客服邮箱1017951418@qq.com

周一至周日 9:00-20:00

觅峰教育(万科城店):太原小店万科城二期

觅峰编程 - 让孩子更懂编程!( 晋ICP备19002928号-1 )|网站地图

Powered by 觅峰教育 © 2001-2020