学习,思考,分享,创造

月份:2019年8月

美国计算机科学联赛 简介

See the source image

ACSL,美国计算机科学联赛 您让孩子参加吗?

国内少儿编程培训逐渐升温,相关的比赛竞赛也是发展迅速。

你可知道美国有个计算机科学联赛-ACSL,从举办到现在已经41年了。

在国内上学的学生,尤其是国际学校的学生,如果对于计算机编程感兴趣,参加这样的比赛应该更加合适。 今天就要介绍一下这个计算机科学联赛ACSL。

背景知识

美国计算机科学联赛起源于美国硅谷,是美国历史悠久的中小学生计算机编程赛事之一。该比赛同时获得了美国国家中学校长联盟NASSP 与美国计算机科学教师协会的官方认证和推荐,同时获得了如谷歌、Adobe、No Starch Press、O’Reilly Media、Pearson、Pragmatic Bookshelf和 Wolfram 等著名高科技企业和教育企业的支持。随着各国日益重视编程教育,每年来自美国、加拿大、欧洲、非洲和亚洲的众多中小学生都踊跃参加到该竞赛中。

比赛规则

该项比赛采用的比赛语言是英文,其中在中国参赛, 小学,初级和中级提供中文翻译

赛事组成

分为两种,一种是积分赛,每年四轮,另外一种是全明星总决赛(积分赛获奖选手受邀参加)

比赛时间

积分赛

  • 第一轮: 2019 年12 月20 日 周五,
  • 第二轮: 2020 年2 月7 日, 周五
  • 第三轮: 2020 年3 月13 日,周五
  • 第四轮: 2020 年4 月17 日,周五

完成题目,提交的最后截止日期如上。

其中第一轮属于选拔赛。

全明星赛:

  • 全明星赛:2020 年5月23日

比赛地点

国外是每个学校可以注册,由本校的老师来管理。 目前国内有不少国际学校作为考点。

华北赛区:

组队方式

3 人/ 组

小学组不需要组队,因为小学组只有简答题,没有团队编程题目。

难度级别

  • 高级 Senior Division:适合高中同学,并且具备较强计算机编程能力同学,尤其是选择学习AP 课程中计算机科学课程的同学
  • 中级 Intermediate Division:面向编程基础较浅的初中和高中生
  • 初级 Junior Division:适合没有编程基础的初中同学参加

这是三个级别的比赛分两部分, 书面简答(30分钟)  和上机团队编程 (2小时)

  • 小学Elementary Division:适合小学3-6年级同学参加,不需要具备丰富的编程语言基础,没有编程经验的同学也可以参加, 只有书面简答题,考试时间40分钟
  • classroom division: 面向任何年级的学生,只有简答题,需要在50分钟内完成

其中, 小学、初级、中级是提供中文翻译的。高级是英文的题目。

另外,编程经验丰富的低年级参赛者可以选择高年级的赛事,例如编程能力强的小学生可以选择高级或中级、初级赛事,编程能力强的初中生可以选择高级赛事。但是高中生不能选择小学和初级赛事,初中生不能选择小学赛事。

也就是说可以超前比赛,但是不能降级比赛。

高级、中级、初级比赛内容

  • 第一部分:个人笔试:30 分钟,5 道编程数理题。每题1 分,满分为5 分
  • 第二部分:团队编程:2 小时编程挑战赛,团队共同完成。仅1 道编程题,满分为5 分

注:小学难度竞赛仅个人笔试40 分钟,没有团队编程赛,不需要三人组队

积分规则

  • 个人得分:个人简答题总得分
  • 团队得分:(个人简答题总得分+ 编程挑战赛得分* 团队总人数)/ 团队总人数
  • 简答题 答对一题记1分, 最多5分
  • 编程题: ACSL发给指导老师5组测试数据, 指导老师在输入官方给出的input之后,如果程序能跑出正确答案, 则每一个正确答案记1分, 最多5分。 如果程序出现死循环则不得分。  一个参赛者最高个人得分是10分。 简答题5+编程题5
  • 最后一个队伍选出最高的3个分数交给ACSL,作为这一次比赛的团体总分, 团队最高分是30分( 10+10+10)

奖项设置

每个难度级别单独评奖

个人奖项:

  • 个人卓越奖:四轮比赛全部获得满分
  • 个人高分奖:个人赛积分排名前20% 的个人

团队综合奖:

  • 金牌:团队积分排名前5% 的团队
  • 银牌:团队积分排名前5-15% 的团队
  • 铜牌:团队积分排名前15-30% 的团队
  • 优秀奖:团队积分排名前30-50% 的团队

获奖团队可获邀参加全明星总决赛(北京),角逐全球奖项

邀请每个组别4次比赛中累计得分最高的几个学校参赛。 ACSL同时会给每个地区累计得分最高的几个学校和该学校得分最高的几位学生颁发奖状

全明星赛总决赛 All Star Contest

积分赛获奖团队受邀参与全明星总决赛,比赛于8 月16 日在北京举办。同样分为三个难度级别:初级、中级和高级,参赛团队只能选择与积分赛同样的难度参加,不能跨级。每支团队将获得4 道编程题,每道题根据难度分别值5-10 分,比赛时间为3.5 小时。笔试环节也需团队进行,在规定时间内,完成相应的题目

全明星赛承办学校:北京市第八十中学(北京市朝阳区望京北路甲16 号)

考点

ACSL考试的内容分为两部分, 一部分是重要的计算机科学概念,比如

  • 分析程序流程
  • 分析变量的值
  • 布尔代数
  • 简单的数字电路分析
  • 二进制,16进制 转换

另外一部分是问题的算法解决能力,这就是团体编程部分了。

例题解析

针对小学组的题目,我们可以举几个例子来介绍:

不同进制的转换:

这个题目考了三个知识点, 一个是颜色在计算机中的表示方式, 另外一个就是16进制的表示, 最后一个就是16进制的减法计算。

下面这个题目考察的知识点是后缀表达的解析。 其中用到了计算机可续中堆栈的知识点。

结论

美国计算机科学联赛(ACSL)考察的是计算机科学中的基本的且重要的知识点。 对于小学生来讲,不涉及到真正的编程,关键知识点虽然不是很多,但是涉及的面还是挺广的。需要老师专门的教授,学生需要系统地学习。

另外, 这个考试虽然有中文的翻译,但是如果英文能力可以,最好借此机会把计算机科学相关的英语知识同时强化一下,这对于国际学校的学生未来出国留学,继续学科的学习非常有帮助。

ACSL得到美国计算机科学教师协会的认可,所以把其成绩用于国外学校的申请,作为学术方面的成就,能够起到一定的助力。

如果想要咨询更多的信息,请联系微信: techradio

解数独,学编程 -python 3

数独中每个格子地址的表示

上次我们已经学会了用列表来表示一个数独的值。 当某个空格的值我们不能决定时,可以用一个字符串来表示多个值, 比如下面,就表示A1处1到9都有可能,不能确定。
line1 = [‘123456789′,’7′,’8′,’123456789′,’123456789′,’123456789′,’123456789′,’123456789′,’123456789’]
这个是上次的作业。


本篇的目标是介绍如何用Python代码来实现一些最基本的数独的概念。
我们知道,每个数独的格子都是编号了, 比如 ’A1‘, ’B2‘ 等等。这些编号可以当做地址,所以快速生成这些地址也非常重要。

DIGITS意思是数字, 这里是一个字符串, 还有从1到9这些字符。

ROWS意思是行,含有’A‘ 到 ’I‘ 这些字符。 那么COLS就表示列, 行是字母, 列是数字。 上面是Python里面的三个字符串变量。


我们要写一个函数, 输入是行和列的表示,输出是一个数独格子的地址表示。

函数的定义和使用

函数在编程语言里可以根据一个功能,把一些语句组合起来。这样可以实现代码的重复使用,而且也容易阅读代码。

在代码中,函数涉及到定义和调用。

比如,下面就是一个函数的定义: 它始于用def 定义的函数名字。

def add(a,b):    
    return a+b 

这个函数输入两个值 a 和b,输出一个值, a与b的和。 return的意思是返回。

把a与b的和返回到函数的调用的地方。 这个函数的使用方法如下:

c = add(100, 200)

在函数执行的时候, a=100, b=200, 返回的就是 (a+b) = (100 + 200 ) = 300

函数定义中一遇到return , 函数就退出了, 返回到调用的地方。 在这里返回了300, 然后c这个变量的值是300 。


我们要写一个输入是行和列的值,输出可以表示每个格子的位置。

def cross(A, B):    
     # "Cross product of elements in A and elements in B."    
     return [a+b for a in A for b in B]


这个函数严格来讲只有两行, 里面要理解的概念倒不少。

首先就是列表的生成。


[a+b for a in A for b in B]


我们已经知道,用[]可以生成列表。 可是,这里的列表生成语句好奇怪啊。
我们先看 “for a in A”, 这部分的意思是说,对于每一个在A中的元素a 。

后面紧跟着 “for b in B”, 意思是 对于每一个在B中的元素b。
a+b 表示两个元素相加。我们知道 1+3 = 4而’1‘+’3‘ 就变成了 ’13‘而’A‘ + ’4‘ 就变成了 ’A4‘ 了。


如果我们不用列表生成语句,而是用普通的编程语句来实现,程序可能需要这样:

假如A = ‘abcd’, B= ’1234‘ 那么 程序执行的顺序就是:

先从A中取第一个元素’a‘,然后顺序从B中取各个元素’1234’,做加法,形成

      'a' + '1'  = 'a1'        
      'a' + '2'  = 'a2'  
      'a' + '3' =  'a3' 
      'a' + '4' =  'a4'         

然后从A中取第二个元素’b‘, 接着从B中取各个元素’1234′, 做加法,形成

'b' + '1' = 'b1'

'b' + '2' = 'b2'

'b' + '3' = 'b3'

'b' + '4' = 'b4'


以此类推。最后形成了一个列表, 结果是这样的

[‘a1′,’a2′,’a3′,’a4′,’b1′,’b2′,’b3′,’b4’, …. ‘d4’] 所以, 下面的列表生成语句就是先从A中取元素,然后再在B中取元素,做加法,最后形成一个列表。

[a+b for a in A for b in B]

由此,我们可以得出结论 函数 cross(A,B) 就是生成了一个新的列表,这个列表中每个元素都是来自于A和B的组合。

如果我们调用下面的语句:

CELLS = cross(ROWS, COLS)

CELLS变量的值就是一个列表, 其中包含了 [‘A1′,’A2′,’A3′,’A4’ …. ]

CELLS的意思是单元。 我们用它来保存数独中每个格子的地址。

作业

1. 已经知道一个列表A,其中都是数值, 请构造一个新的列表,其中每个元素都是列表A中元素的3倍。


2. 一个字符串A,内容是’this is good’, 请构造一个新的列表, 其中每个元素都是字符串A中字符的大写, 比如 [‘T’,’H’,’I’, ‘S’, ‘I’, ‘S’, ‘G’, ‘O’, ‘O’, ‘D’]


3. 理解CELLS中的元素值, 看它是怎么形成的。

解数独,学编程-Python篇-2

python

问题解决是学习编程、学习计算机科学的核心。

很多少儿编程班都是带孩子一步一步地做一个游戏。学生做出来了,觉得很高兴,也挺有成就感。可是后来一想,除了做这样一个游戏之外,似乎再做别的游戏就不太会了,摸不着头脑。

这种现象出现的主要原因是老师没有教到问题的分析和思维过程。依样画葫芦很容易,但是学生要学到知识的迁移,举一反三,就不那么容易了。

解决数独问题就是一个具体的问题。 我们这一系列文章要通过解决数独问题,教会你怎么分析问题,怎么把问题在程序中表达出来,怎么设计算法,最后怎么编程来解决问题。

有些情况需要学生先理解人力是怎么解决问题的,然后把人解决问题的方法(算法)转换成计算机操作的步骤,然后用编程语言来实现。有些情况计算机解决问题跟人力解决问题的方法是截然不同的,因为计算机和人相比,有自己显著的优点和缺点。设计算法的时候需要充分利用这些优点。

编程解决问题,首先需要知道如何在计算机上表示那些描述问题的数据,然后设计算法,把这些表示转换成其它形式,直到问题解决。

上一篇介绍了解决简单数独问题时,人们常用的办法。 本次我们会介绍数独在Python中的表示方法。

数独在计算机程序中的表示

计算机其实是非常笨的。因为它只懂一些简单的事情,比如数字, 字符, 列表等等这些原生的数据结构。 而其它所有的信息都必须由多种简单的数据结构组合近似地来表示。把事实信息用这些数据来表示可以看做是一个”编码”的过程。

我们要看一下如何对数独编码,在计算机中表示出来。

从上一次的文章中,我们已经给数独中的每个格子都编了号,

  1. 每一列用数字1到9来表示,
  2. 每一行用字母A到I来表示,

那么,第一行第一列就是A1, 第一行第二列就是A2. 最后一行最后一列是I9。


在Python编程语言中,有一种原生的数据结构,叫做列表。 把一些元素放到[] 中,互相之间用,隔开就会创建列表,比如[1,2,3,4,5] 就是一个有5个数字元素的列表。 [’a’,’b’,’c’,’d’,’e’]  是一个含有5个字符元素的列表。   其实列表中的元素类型可以不一样的, [1,2,3,’a’,’b’,’c’] 也是合法的。

有读者可能会问, 数独既有行,也有列,怎么用列表表示呢?  这个问题好解决, 只要列表中套列表就可以了。

数独第一行可以用 [‘A1’, ‘B1’, ‘C1’, ‘D1’, ‘E1’, ‘F1’, ‘G1’, ‘H1’, ‘I1’] 来表示, 第二行可以用 [‘A2’, ‘B2’, ‘C2’, ‘D2’, ‘E2’, ‘F2’, ‘G2’, ‘H2’, ‘I2’]

那么前面两行可以放到同一个列表中,

[ [‘A1’, ‘B1’, ‘C1’, ‘D1’, ‘E1’, ‘F1’, ‘G1’, ‘H1’, ‘I1’],

  [‘A2’, ‘B2’, ‘C2’, ‘D2’, ‘E2’, ‘F2’, ‘G2’, ‘H2’, ‘I2’] ]

我们介绍过单元的概念,就是包含某个格子的行,列和3×3方格。

下面就是包含了一个数独所有单元的列表的例子, 你可以分析一下,是不是这样的。

作业

语法知识:

我们这次讲了列表,列表的生成在Python中的语法是 []。比如下面的语句就生成了一个名字为aList的列表,其中还有三个数字元素。

aList = [1,2,3,4]

如果数独中一个格子中有不确定的值,我们可以把所有的可能的值放进去。 比如下面数独的例子, 我们单看第一行, 用列表可以这样表示:

line1 = [‘123456789′,’7′,’8′,’123456789′,’123456789′,’123456789′,’123456789′,’123456789′,’123456789’]

1. 请用这样的方法, 表示第二行, 第三行

line2= [] ?

line3 = [] ?

2. 我们根据第一行已经给定的数字 7 和8 ,可以判断出第一行其它数字不可能是7或者8, 所以,第一行的表示可以修正为:

line1 = [‘1234569′,’7′,’8′,’1234569′,’1234569′,’1234569′,’1234569′,’1234569′,’1234569’]

请问, 如果我们根据第一列给出的数字信息, 我们可以如何修正第一行?

同样的,我们可以根据第二列给出的数字信息,如何修正第一行?

如何根据左上角3×3的信息,修正第一行?

3. 你能用同样的方法,表示一下别的行,然后修正吗?

如果你遇到了问题,或者想讨论一下,请在下面留言哦。

python

解数独,学编程-Python篇

数独就是一种数字猜谜游戏了,相信不少人都玩过。 为了方便从来没有玩过的同学继续阅读这一系列的文字,这里会简单介绍一下这个游戏的规则和玩法。 懂得了游戏怎么玩,接下来就是要学习怎么用Python来玩数独游戏。 用编程来解决实际问题,涉及到几个方面的内容,一个是Python语言的基本知识,另一个是用语言来解决问题的思维方式,就是计算思维,再一个就是动手实操和练习,把问题实实在在的通过写代码来解决。

这些内容如果挤到一篇文字里面 ,内容显得会有点多,阅读起来也不方便。所以,我们会分几个个部分。


面向的读者

这一系列文章面向的读者是4年级以上,有兴趣学习Python编程的小朋友。希望你喜欢阅读,喜欢尝试, 愿意动脑筋思考问题。 另外, 没有编程基础的成人也会从中受益。

如果您的孩子自学能力欠佳,可以考虑联系报我们的线下编程课。 另外,除了线下Python编程课,我们有计划推出线上直播课,详细信息,请联系鲸小小 王老师 微信 techradio

鲸小小科技创客教育作为线下线上K12高端精品科技教育品牌,以有料、有趣,有爱,并且融合国际标准的课程为核心,赋予孩子充满热情地探索和实践的机会,培养孩子不断地学习包括编程在内的科技知识,在项目导向的教学活动中培养未来需要的关键技能,逐步提高孩子的综合素质。通过线下游戏化的运营方式,高水平的国际合作项目,让学生学以致用,展现创造力。
http://kids.abakus.cn
今天是第一部分: 你喜欢玩数独吗?

你喜欢玩数独吗?

数独是一种智力游戏。有时候外出旅行的时候, 我会看到有旅客左手握一本厚厚的布满格子的书,右手捏着一支秃了头的铅笔,一有机会就皱着眉头往书上划几个数字,填满了空格就高兴地咧咧嘴笑笑。他们在做什么呢? 一般来说,他们在玩数独游戏。
数独是一种风靡全球的智力游戏,也称为Sudoku,Number Place。我们来看一下数独游戏的规则。


数独游戏的规则

数独游戏需要9×9的81个格子,9行9列的方阵。 出题目的时候,有的格子里面会有数字,有的格子是空的,像下面这个图。 玩家需要按照规则,把空格子中缺失的数字填上。 其规则主要有三条

空格中需要填写1到9这样的数字 ,并且需要满足下面的条件

  • 每一行都包含1,2,3,4,5,6,7,8,9
  • 每一列都包含1,2,3,4,5,6,7,8,9
  • 每3×3的方阵(如果所示) 都包含1,2,3,4,5,6,7,8,9

我们把上面所述的每一行,每一列,以及每一个3×3的方阵都统称为一个单元

一个单元中的格子互相之间称为同伴。 如下图, 由第一行第一列的4所决定的单元就包含了 第一行,第一列,和左上角的3×3的方阵。 考虑,考虑一个格子的单元,要考虑三个地方, 行,列和3×3方阵。

为了描述方便, 数独上每一个格子都有个编号, 从上到下,每一行分别用A,B,C,D,E,F,G,H,I l来表示, 从左到右,每一列分别用1,2,3,4,5,6,7,8,9来表示。 那么, 4所在的格子就是A1, 第一行5所在的格子就是A9. 最右下角的8所在的格子就是I8.

用这样的方法表示, A1 所有的同伴就是:

  • 1) A2, A3, A4, A5, A6, A7, A8, A9
  • 2) B1, C1, D1,E1,F1, G1,H1,I1
  • 3) B2, B3,C2, C3

那么数独的规则就可以简化成一句话: 1到9中任何一个数字都不能在同一个单元中出现两次,也就是说一个格子中的数字与其同伴中的数字是不同的。


单元和同伴的概念在解决数独的时候挺重要的,需要仔细理解了。

一个设计好的数独游戏只有唯一解。

为了加深理解,我们再举几个例子:
1 在上面的数独游戏中,第一行第三列的空格就不能填写7, 因为7 已经在该行中出现了,同时也在该列中出现了。 2. E4 只可能填 6,7,9,因为其它数字已经出现在了E4所在的单元中(行,列,3×3方阵)

手工解决数独的策略

解决一个数独问题,有很多种策略。一种策略是从数字开始找,比如先找所有给定的数字1,然后推断哪些空格处必须要填1. 另外的策略就是首先根据给定的数字,看一下某个空格中可能填的数字, 做一下标记,然后再根据其它信息,逐步地从这些候选数字中去除不可能的数字,最后剩下的唯一的数字就是答案。
其它信息从哪里来呢,就从数独的规则和单元信息。 空格子中需要填写1到9这样的数字 ,并且需要满足下面的条件

  • 每一行都包含1,2,3,4,5,6,7,8,9
  • 每一列都包含1,2,3,4,5,6,7,8,9
  • 每3×3的方阵(如果所示) 都包含1,2,3,4,5,6,7,8,9

扫描数字

根据1在一行一列中只能出现一次,上图中只要出现了1的行,或者列,其它空格处就不能放1了。 画红线标记一下, 我们发现X所在的3×3方阵中,除了X所在的空格,其它空格都不可能是1. 所以,X处必填1.

用同样的方法, 我们可以找到在X格所处的3X3方阵中,除了X所在的空格,其它处都不可能是1, 所以这个地方的X处必须填4.

在上图中, 中间一行只剩一个空格,只剩9这个数字没有在该行中出现,所以,该处就一定填9了。
解决了上面这些空格, 此数独游戏形成了下面的样子。

可以用同样的方式寻找其它的数字。


标记空格可选数字


每个空格的可选数字根据数独的规则是可以缩小范围的。 我们可以在空格处标记一下这些可选数字。这些标记可以帮助我们很快地定位一些唯一的数字,比如I7出只能填1, 那么I3处就只能填3了。 进而H1就必然是6, H3必然是1了。

通过上面扫描数字和标记空格可选数字这两种策略,我们可以解决一部分简单的数独游戏。 请大家登陆 http://cn.sudokupuzzle.org 选择一些数独游戏来试一下吧。

作业


从 http://cn.sudokupuzzle.org 选择三个简单的数独游戏,尝试用上面所学内容解决该游戏。

总结

在今天的文章中,我们介绍了

  1. 数独这个游戏和它的规则。 我们用字母和数字给每个格子做了标记。
  2. 一个格子同时处于三个单元中,行,列和3×3方阵。
  3. 单元中其它格子称为该格子的同伴, 一个格子的值不能和同伴的值一样
  4. 解决数独游戏,可以扫描数字,也可以标记格子的可能值,把可能值尽可能地减少,最终变成唯一。

用手工可以解决数独游戏,很多人热衷于此。那么怎么用Python来解数独呢? 接下来我们会先介绍一个数独在Python中的表示,然后介绍Python的基本语法,进而一步一步地写程序解决数独。
有的读者可能会担心有难度。 不用担心, 这一系列文章会从零开始介绍Python编程语言,真正地带你体会用程序解决实际问题的步骤,其中会涉及到基本的语法,算法的思路,面向对象的知识点。


感谢

本文参考了 http://www.sudokuessentials.com/how_to_play_sudoku.html 中的图片和内容。 有些图片是直接借用的,有的是修改了一下,向作者致谢。

世间爱书之人有此一物,岂不美哉

懂得自然懂啦。

MIT best seller books

  1. https://mitpress.mit.edu/best-sellers

Powered by WordPress & Theme by Anders Norén