高中信息技术教科版 (2019)选修1 数据与数据结构4.2 基数排序教案设计

课 题

4-2基数排列

课时安排

1

课型

素养目标

课程标准要求：1.理解队列的概念及其特征。

2. 理解基数排序的基本过程。
3. 了解排队取号模拟系统的基本功能。

信息意识：信息意识：能够根据解决问题的需要，自觉、主动地寻求恰当的方式获取与处理信息；在合作解决问题的过程中，愿意与团队成员共享信息，实现信息的更大价值。

计算思维：针对给定的任务进行需求分析，明确需要解决的关键问题。能提取问题的基本特征，进行抽象处理，并用形式化的方法表述问题。运用队列结构设计解决问题的方案，结合队列的相关操作，编程实现。

数字化学习与创新：1.理解队列结构及其现实。

 2.熟练运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。

信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的理论道德和法律法规。

教学重点

1.理解队列的概念及其特征。

2.理解基数排序的基本过程。

教学难点

了解排队取号模拟系统的基本功能。

教学方法

讲解法、互动法

学习方法

互动、讨论

教学过程

个别化教案

一、考勤。

二、课前测评。

三、引入

日常生活中，我们经常会遇到排队的情况，如在食堂排队买饭、在电影院排队买票、在超市排队结账等。排队的过程会形成一个队列，排在队列最前面的优先处理，后来的必须排在队尾。在计算机解决问题的过程中也经常会用到队列。本节主要学习队列的概念及其特征、队列抽象数据类型的定义、队列的实现方法。任务一：认识生活中的队列。 

队列：队列是一种操作受限的线性结构，数据元素只能在一端进，在另一端出，且具有“先进先出”的特征。队列出现在日常生活各类“排队”活动中，如影院排队入场、商店排队付款和餐厅排除就餐就时都会形成队列。另外，计算机科学中的很多功能，如打印队列、进程调度和键盘缓冲等也都是利用队列结构来实现的。

       1.本单元通过“排队买票”项目，理解队列结构的基本概念及特征，学习队列的两种实现方法。

队列(queue)是一种操作受限制的线性结构，只允许在表的前端(队首)进行数据元素删除操作，在表的后端(队尾)进行插入操作。在队列中插人一个数据元素称为人队，从队列中删除一个数据元素称为出队。因为队列只允许在队尾插人、在队首删除，所以先进入队列的元素先从队列中删除，故队列又称为先进先出(First In First Out，FIFO)线性表。

队列抽象数据类型：
为了在程序中使用队列结构来解决问题，我们需要定义队列抽象数据类型(ADT Queue)。根据问题解决需要，我们为队列抽象数据类型定义了如下接口。
·Queue()：创建一个空队列，返回值是一个空的队列。
·enQueue(item)：将数据元素 item添加到队尾，无返回值。
·deQueue()：从队首删除数据元素，返回队首数据元素。
·size()：返回队列中数据元素的个数。
·isEmptyO：判断是否为空队列，返回布尔值。

基数：

十进制记数是逢十进一，从零开始计数，数到十的时候，就要进一位，即变成10，个位数上是0，十位数上是1。一个十进制数的每个数位上可能的数字是0，1，2，…，9中的某一个。十进制的基数是10。二进制记数是逢二进一，从零开始计数，数到二的时候，就要进一位，即变成10(2)。一个二进制数的每个数位上可能的数字是0，1。二进制的基数是2。同理，一个N进制数是逢N 进一，它的基数是N，采用N个不同的数字符号来表示。例如，十六进制的基数是16，采用0~9和A~F这16个符号来记数。

基数排序的基本思路：
分发过程：
分发的过程是按照数据的某个数位上的数字依次把队列 mainQueue中的各个数据分发到相应的基数队列中，最先人队的数据处于队列的队首位置。
收集过程：
收集的过程是按照基数队列下标从小到大的顺序，将所有基数队列中的数据移出队列，放人队列 mainQueue，最先人队的数据处于队列的队首位置。

迭代次数：
因为要从低位到高位对数据的每一位进行一轮分发和收集，所以整个排序过程要进行k次分发和收集。k是需要排序的所有数据中最大值的位数，它可以通过以下表达式得到：

K=len(str(max(alist)))

排队取号模拟系统：
餐馆排队取号包括取号和叫号两个部分。取号就是根据所选餐桌类型生成排队号码等信息将顾客人队。叫号就是根据空闲餐桌类型，将排在该餐桌类型队列队首的顾客出队。

class Queue:

    def __init__(self):

        self.items = []

    def enQueue(self, item):

        self.items.append(item)

    def deQueue(self):

        return self.items.pop(0)

    def isEmpty(self):

        return self.size() == 0

    def size(self):

        return len(self.items)

class Guest:  # 客人

    def __init__(self, tableType):

        self.tableType = tableType                #顾客所选餐桌类型

        self.stayTime = random.randrange(20, 60)  #随机生成顾客用餐时间

    def takeTicket(self, number,order, timeTick):   #生成顾客取号信息

        self.ticket = '%s%03d 前面还有%d位' % (self.tableType,number,order) #生成排号单

        self.tableTypeNum='%s%03d' % (self.tableType,number)   #排队序号

        self.arriveTime = timeTick   #顾客取号时间

class Table:  # 餐桌

    def __init__(self, id, type):

        self.id = id  # 桌号

        self.type = type  # 类型'A','B','C'，容量分别是（2，4，8）

        self.status = 'free'  # 状态（free, busy)

        self.remain = 0       # 顾客占用时长

    def setBusy(self, remain):  # 设置餐桌状态

        self.status = 'busy'    #设置桌子为“在用”状态

        self.remain = remain    #设置占用时长

    def tickRemain(self):      # 餐桌用餐状态检测

        if self.remain > 0:    #判断是否还有占用时长

            self.remain -= 1   #占用时长减少1

        if self.remain == 0:   #判断占用时长是否为零

            self.status = 'free'  #设置桌子为“空闲”状态

class QueueSystem:  # 排号机

    def __init__(self):

        self.guestQueues = {'A': Queue(), 'B': Queue(), 'C': Queue()}  #顾客队列

        self.guestCount = {'A': 0, 'B': 0, 'C': 0}          #排队号码

        self.totalWaitTime = 0      #总等待时间

        self.totalGuest = 0         #总就餐人数

    def assignTicket(self, guest, timeTick):

        # 有顾客来，排队取号

        table = guest.tableType                   #顾客餐桌类型

        queue = self.guestQueues[table]           #顾客所排的餐桌队列

        self.guestCount[table] += 1               #生成排队号码

        guest.takeTicket(self.guestCount[table],queue.size(),timeTick)  #顾客取号

        queue.enQueue(guest)                       #顾客入队

        # 显示信息

        print('顾客取号：', guest.ticket,'取号时间：',timeTick)

    def arrangeTable(self, table, timeTick):   #叫号函数

        # 有空桌，看看是否有顾客等候

        if not self.guestQueues[table.type].isEmpty():

            guest = self.guestQueues[table.type].deQueue()    #顾客出队

            table.setBusy(guest.stayTime)                     #设置就餐状态为占用

            # 计入等待时间

            self.totalGuest += 1                              #累计用餐总人数

            self.totalWaitTime += timeTick - guest.arriveTime #累计总等待时间

            # 显示信息

            print('叫号：', guest.tableTypeNum, '到桌号：', table.id)

    def showResult(self, totalTime):

        print('*' * 40)

        print('本次模拟一共', totalTime, '分钟')

        print('共有', self.totalGuest, '桌顾客用餐')

        print('每桌顾客在用餐前平均等待时间为', round(self.totalWaitTime / self.totalGuest), '分钟')

        print('模拟结束时各队列情况如下：')

        for q in self.guestQueues:

           print('桌型：', q, '还有', self.guestQueues[q].size(), '桌顾客在排队')

        print('*' * 40)

import random

# 变量randomBox用于设定模拟来客的概率，20%概率2人桌，10%概率4人桌，5%概率8人桌

randomBox = [None] * 65 + ['A'] * 20 + ['B'] * 10 + ['C'] * 5

# 餐桌设置，5张2人桌，3张4人桌，2张8人桌

tableSetting = 'AAAAAAABBBBC'

# 生成餐桌对象列表

tableList = [Table(i + 1, tableSetting[i]) for i in range(len(tableSetting))]

qsys = QueueSystem()  # 生成一个排号机对象

totalTime = 4 * 60  # 模拟时间长度为4小时，最小单位分钟

for timeTick in range(totalTime):

    # 1，以设定概率随机模拟来客

    dice = random.choice(randomBox)

    if dice is not None:  # 有客人来

        guest = Guest(dice)

        qsys.assignTicket(guest, timeTick)  # 顾客取号

    # 2，让餐桌用餐时间减1，查看餐桌是否有空闲

    for table in tableList:

        table.tickRemain()

        if table.status == 'free':

            qsys.arrangeTable(table, timeTick)  # 叫号入桌

# 显示模拟统计信息

qsys.showResult(totalTime)

      四、总结

1.理解队列的概念及其特征。

2.理解基数排序的基本过程。

3.了解排队取号模拟系统的基本功能。

作 业

板

书

设

计

1.理解队列的概念及其特征。

2.理解基数排序的基本过程。

3.了解排队取号模拟系统的基本功能

教

学

反

思

教案查阅签字