Skip to content

第0课 算法基础课程简介与上学期回顾

课程简介

终于迎来了本学期的《算法基础》课程,在本学期的课程中,你将真正接触到程序设计的两个重要部分:数据结构与算法。在上学期的《算法初步》中,小伙伴实际上是学习了基础的Python语言的语法,为本学期的算法基础课程做好了铺垫。有了上个学期的基础,我们终于可以开心地、正式地学习算法内容了。

本学期的课程将不再是小打小闹,而会非常烧脑,而且《数据结构与算法》这门课程是出了名的枯躁与乏味!请大家要做好心理准备,当然老师也会尽量引入一些例子让课程生动一些,另外也会安排一些活动和环节缓解大家的不适感,不过你们要做好补脑和养精蓄锐的准备(老师的经验:多吃核桃和睡眠非常重要)。

另外要提及的是,除去非常少的天才外,要学好算法唯一有效的途径就是大量的练习,所以请大家一定要重视作业,最好把每道题练习得非常熟练,理解得非常透彻。

课程大纲

  • 课程简介与上学期回顾(1 Block)
  • Python程序设计 - 抽象数据类型与Python类 (1 Block)
  • 数据结构基础 (3 Blocks)
    • 数据结构基本概念
    • 栈与队列
    • 数组与链表
  • 排序算法 (4 Blocks)
  • 散列表 (2 Blocks)
  • 二叉树与图 ( 4 Blocks )
    • 二叉树与图
    • 广度优先算法
    • 深度优先算法

评价方式

习题(30道) 考勤与课堂表现 大作业(or 期末考试) 自评
50% 10% 30% 10%

本学期涉及素养

学会学习

课程需要的相关工具与网站

  1. Python 3.6+以上版本
  2. Visual Studio Code
  3. 课程材料网站:http://course.naxiro.cn
  4. OJ系统: http://oj.naxiro.cn

课堂任务

跟随老师完成OJ系统的注册,了解OJ系统,并且完成B001题!

OJ系统使用方法

这里需要详细讲解一下OJ系统。OJ系统即在线评测系统(Online Judge System)。采用黑盒测试的方法,用户在网络上提交源程序,系统会输入测试数据去运行你提交的代码,将代码产生的结果与正确的结果相比较,以验证你提交的程序是否符合题目要求。

请大家访问Theia Online Judge System, 按照下列步骤完成注册。

  1. 点击右上角“Register”按钮

  2. 在弹出的对话框中填写对应信息

  3. 在弹出登录框中填写刚刚注册的用户名和密码,登录系统!

  4. 登录后界面是这样子的:

  5. 点击“Problems"后进入习题列表:

  6. 点击一道习题,可看到下面的界面:

  7. 点击“Submit”就能提交你的代码,最后你会在左下角得到题目当前的状态:

    • Pending & Judging : You solution will be judged soon, please wait for result.
    • Compile Error : Failed to compile your source code. Click on the link to see compiler's output.
    • Accepted : Congratulations. Your solution is correct.
    • Wrong Answer : Your program's output doesn't match judger's answer.
    • Runtime Error : Your program terminated abnormally. Possible reasons are: segment fault, divided by zero or exited with code other than 0.
    • Time Limit Exceeded : The CPU time your program used has exceeded limit.
    • Memory Limit Exceeded : The memory your program actually used has exceeded limit.
    • System Error : Oops, something has gone wrong with the judger. Please report this to administrator.

OJ注意事项

  • 本学期的习题作业都会使用这个系统完成,所以大家必须要熟练掌握。
  • 实际上,现在绝大多数的算法练习和比赛都会使用OJ系统,所以要记住题目状态的代码及其含义。
  • 一般情况下,你可以在Visual Studio Code中编辑好代码,调试成功,再把正确的程序复制粘贴到系统的编辑框中进行提交。这种方法在大部分的系统和比赛中是可接受的,但是有极少部分的比赛会将这种行为视为违规。
  • 不要妄图直接返回答案以通过测试。因为测试用例是非常多的以至于你基本不可能完全覆盖。并且在比赛中,这种行为是违规的(当然作业中也不允许)。

Python程序设计回顾

一起完成小程序

  1. 定义6个变量,用于分别用于表示player的姓名,职业,魔法值,血量值,武器装备,是否死亡。变量名和默认值由你自己拟定(比如:姓名:"Toggor",职业:"Warrior" ……, 武器装备中请装备至少2种武器)。你可以说出每个变量的数据类型是什么?用typeof(变量名)看看?

  2. 现在需要给武器装备的列表中添加一把匕首,请使用append方法完成这个操作,并使用print打印出player当前的姓名、职业和武器装备列表。

  3. 完成一个函数attack(), 这个函数会消耗player的魔法值10个点,产生的攻击力由公式10 + 血量值 * 0.3决定。 请通过print打印出player当前的姓名、魔法值,以及此次攻击力值的大小(注意:如果魔法值为零,则攻击力为零)。

    def attack():
        # Write your code here
    
  4. 调用函数attack, 最后输出你定义6个变量的值。

  5. player在当前的环境中,会受到一种毒素的影响,会掉10次血: 第1次掉1点血,第2次掉2点血,以此类推。。。请使用while循环完成这个操作。(要注意,如果血量掉到0下后,就不再继续掉血,并且是否死亡标记为True。)

小球的运动

  1. 首先使用pip或者pip3安装turtlefreegames
  2. 下载bounce.py文件到你的算法文件夹中
  3. 打开并运行程序;
  4. 尝试修改代码,加快或者降低球速;
  5. 你能改变球在撞墙后的反射角度吗?
  6. 你能画出球的轨迹吗?
  7. 你能根据球的位置,改变颜色吗?(提示:colormode(255);color(0, 100, 200))