下载文档原格式
本栏目责任编辑：王力计算机教学与教育信息化小学信息技术教材中的计算思维挖掘与教学案例浅析——以南方版“算法与程序设计初体验”一课为例蔡荣华，万梦思（湖南师范大学教育科学学院，湖南长沙410006）摘要：计算思维是当前教育领域和计算机科学领域重点关注的一个话题，在中小学阶段如何将计算思维更好地融入课堂教学，一直是一线教师比较关注的内容。
通过深度挖掘小学信息技术教材南方版六年级下册第一单元中的计算思维内容和对案例进行分析，以期为一线教师在用教材进行教学设计和课堂教学中融入计算思维提供新的视角。
关键词：中小学信息技术教材；计算思维；教学案例中图分类号：G642文献标识码：A文章编号：1009-3044(2021)14-0080-02开放科学（资源服务）标识码（OSID ）：1引言计算思维这一概念的公开提出是周以真教授在2006年通过美国的权威刊物发表的，同时周教授还强调了计算思维的重要性，它应该跟读、写、算一样成为每个人都应该掌握的一种基本能力。
周教授认为，计算思维是运用计算机科学的基础概念进行问题求解、系统设计、以及人类行为理解等涵盖计算机科学之广度的一系列思维活动[1]。
根据周教授的观点，计算思维是通过仿真、递归、抽象、自动化、冗余、分解等一系列核心的方法将复杂的问题转化成计算机能够识别的基本的解决问题步骤，并且将问题解决。
美国国际教育技术协会（简称ISTE ）对基础教育阶段的计算思维培养给出了操作层面的定义，包括六个要素[2]。
目前针对计算思维国内外还没有统一的定义，国内外许多学者都对计算思维的定义和操作提出了自己的理解，南安普敦大学的CynthiaSelby 博士和John Woollard 博士提出的计算思维包括算法思维、抽象、分解、概括和评估这五个要素[3]，如图1所示。
图1计算思维五要素Selby 博士和Woollard 博士关于对计算思维的定义比较适合中小学信息技术教育，本次文章里也是借用这个定义认为计算思维是由抽象思维、算法思维、分解思维、概括思维以及评估思维这五个思维要素组成的。
第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。
为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。
二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。
1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。
（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。
- 对每种算法进行时间复杂度和空间复杂度的分析。
- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。
（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。
- 编写三种排序算法的代码。
- 分析代码的时间复杂度和空间复杂度。
- 编写测试程序，生成随机测试数据，测试三种算法的性能。
- 比较三种算法的运行时间和内存占用。
2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。
（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。
- 分析贪心算法的正确性，并证明其最优性。
（3）实验步骤：- 分析活动选择问题的贪心策略。
- 编写贪心算法的代码。
- 分析贪心算法的正确性，并证明其最优性。
- 编写测试程序，验证贪心算法的正确性。
3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。
（2）实验内容：- 实现一个动态规划算法问题，如背包问题。
- 分析动态规划算法的正确性，并证明其最优性。
（3）实验步骤：- 分析背包问题的动态规划策略。
- 编写动态规划算法的代码。
- 分析动态规划算法的正确性，并证明其最优性。
- 编写测试程序，验证动态规划算法的正确性。
三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。
一、实训背景随着计算机技术的飞速发展，算法作为计算机科学的核心，在各个领域都发挥着至关重要的作用。
为了提高自身在算法设计与应用方面的能力，我们选择了“程序算法实训”作为课程实践项目。
本次实训旨在通过实际编程，加深对算法理论知识的理解，提高编程能力，并培养团队协作精神。
二、实训目标1. 理解并掌握常见算法的基本原理和设计方法；2. 能够根据实际问题选择合适的算法进行编程实现；3. 提高编程能力，提高代码质量和可读性；4. 培养团队协作精神，提高团队沟通和协作能力。
三、实训内容本次实训主要围绕以下内容展开：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序等；2. 查找算法：顺序查找、二分查找等；3. 数据结构：栈、队列、链表、树、图等；4. 动态规划；5. 贪心算法；6. 分治算法。
四、实训过程1. 阶段一：理论学习首先，我们对上述算法的基本原理和设计方法进行了深入学习，通过查阅相关资料、观看教学视频等方式，掌握了算法的基本概念和实现方法。
2. 阶段二：编程实现在理论学习的基础上，我们开始编写代码实现各种算法。
在编写过程中，我们遵循以下原则：（1）代码规范：遵循代码规范，提高代码可读性和可维护性；（2）注释清晰：对关键代码段进行注释，说明其功能；（3）调试优化：在编写过程中，不断调试和优化代码，提高代码性能。
3. 阶段三：团队协作在实训过程中，我们分成小组进行合作。
每个小组负责一个或多个算法的编程实现。
在小组内，我们分工明确，共同讨论和解决问题。
通过团队协作，我们不仅提高了编程能力，还培养了团队协作精神。
4. 阶段四：成果展示与总结在实训结束后，我们对成果进行展示和总结。
每个小组展示自己负责的算法实现，包括代码、运行结果和性能分析。
同时，我们对实训过程中的收获和不足进行总结，为今后的学习和工作提供借鉴。
五、实训成果1. 成功实现了各种常见算法的编程；2. 提高了编程能力，掌握了代码规范和调试技巧；3. 培养了团队协作精神，提高了团队沟通和协作能力；4. 对算法理论知识的理解更加深入。
基于信息技术新课标的单元教学设计案例研究—以《算法与程序实现》单元为例摘要：核心素养教育是当前教育变革的核心主题，基于学科核心素养的单元教学是推动核心素养落地的要点，因此，笔者以“单元教学设计”为出发点，以《算法与程序实现》为例阐述了单元教学设计的关键，希望为广大一线教师同行提供一定的参考。
关键字：信息技术教学;大单元设计;实践研究；一单元教学设计单元教学设计源于国外，有关研究经历了“单元教学理念—单元教学法—单元教学设计”的路径。
[1]目前关于单元教学设计还没有统一的界定，综合各位专家的说法可以将其认为是从一章或者一单元的角度出发，根据章节或单元中不同知识点的需要，综合利用各种教学形式和教学策略，通过一个阶段的学习让学习者完成对一个相对完整的知识单元的学习。
可以将单元教学设计流程细分为单元规划、学情和教法分析、单元教学目标设计等六个步骤[2]。
二单元教学设计设计案例—以《算法与程序实现》单元为例计算机就是一个大的计算器，纵观目前计算机解决的问题，其中有很一大类是“数值计算问题”，在研读了新课标之后，我联系生活实际设计了《多功能计算器的设计与实现》这一大单元项目。
希望学生从底层更好地理解计算机解决问题的思路和方法。
项目分四个模块实施（如图1所示），按照算法的三种控制结构——顺序、选择、循环结构来组织内容，整个项目层层推荐、难度逐渐加大，在项目活动中学习相应知识、掌握相关技能，提高使用计算机解决问题的能力，发展计算思维。
图1 《多功能计算器的设计与实现》单元项目设计下面我以单元项目第二节《选择结构程序设计》一课为例，阐述教学设计的各个环节，具体设计如下：1 教材分析本节课选自中国地图出版社，高一年级信息技术新教材必修一《数据与计算》第二章《算法与程序实现》第三节内容，本章学生将走进计算机科学领域，认识算法和程序这两个非常重要的概念，并通过python变成语言，实现简单的算法，体验程序设计的基本流程，提升计算思维。
第1篇一、背景随着信息技术的飞速发展，算法在各个领域的应用越来越广泛。
为了培养学生的算法思维和编程能力，提高学生的综合素质，我国高校纷纷开设了算法课程。
然而，传统的算法教学方式往往过于理论化，学生难以将理论知识与实践相结合。
为了解决这一问题，本文提出一种基于项目驱动的算法实践教学设计案例。
二、教学目标1. 让学生掌握基本的算法设计方法，包括分治法、贪心法、动态规划法等。
2. 培养学生的编程能力，使学生能够熟练运用编程语言实现算法。
3. 提高学生的团队合作能力，使学生能够与团队成员有效沟通，共同解决问题。
4. 增强学生的创新意识，使学生能够针对实际问题提出新的解决方案。
三、教学内容1. 基本算法设计方法：分治法、贪心法、动态规划法等。
2. 编程语言：Python、Java、C++等。
3. 项目驱动：设计并实现一个具有实际应用背景的算法项目。
四、教学过程1. 项目选题与需求分析教师根据学生的专业背景和兴趣，选取一个具有实际应用背景的算法项目。
例如，设计一个在线图书馆系统，实现图书借阅、归还、查询等功能。
教师引导学生分析项目需求，明确项目目标。
2. 算法设计与实现（1）分治法：以图书借阅功能为例，将图书按照类别进行划分，然后对每个类别分别进行借阅操作。
（2）贪心法：以图书归还功能为例，根据图书归还时间排序，优先归还最早归还的图书。
（3）动态规划法：以图书查询功能为例，采用动态规划法实现关键词搜索，提高查询效率。
（4）编程实现：教师引导学生使用Python、Java、C++等编程语言实现算法，并进行调试和优化。
3. 团队合作与沟通教师将学生分成若干小组，每组负责项目的一个模块。
小组成员之间进行沟通，明确各自的任务和责任。
教师定期组织小组会议，了解项目进展，解决团队协作中的问题。
4. 项目测试与评价教师组织学生进行项目测试，确保项目功能的完整性和稳定性。
同时，对学生进行评价，包括编程能力、算法设计能力、团队合作能力等方面。
一、实验目的1. 熟悉基本算法操作，包括排序、查找等。
2. 掌握常用算法的原理和实现方法。
3. 培养编程实践能力，提高算法设计水平。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.73. 开发工具：PyCharm三、实验内容1. 排序算法2. 查找算法3. 算法分析四、实验步骤1. 排序算法（1）选择插入排序算法进行实现。
（2）编写代码，实现插入排序算法。
（3）编写测试用例，验证插入排序算法的正确性。
2. 查找算法（1）选择二分查找算法进行实现。
（2）编写代码，实现二分查找算法。
（3）编写测试用例，验证二分查找算法的正确性。
3. 算法分析（1）分析插入排序算法的时间复杂度和空间复杂度。
（2）分析二分查找算法的时间复杂度和空间复杂度。
五、实验结果与分析1. 排序算法（1）插入排序算法实现如下：```pythondef insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = keyreturn arr```（2）测试用例：```pythontest_arr = [5, 2, 9, 1, 5, 6]sorted_arr = insertion_sort(test_arr)print("Sorted array:", sorted_arr)```输出结果：```Sorted array: [1, 2, 5, 5, 6, 9]```2. 查找算法（1）二分查找算法实现如下：```pythondef binary_search(arr, x):low = 0high = len(arr) - 1mid = 0while low <= high:mid = (high + low) // 2if arr[mid] < x:low = mid + 1elif arr[mid] > x:high = mid - 1else:return midreturn -1```（2）测试用例：```pythontest_arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] x = 5result = binary_search(test_arr, x)if result != -1:print("Element is present at index", result)else:print("Element is not present in array")```输出结果：```Element is present at index 4```3. 算法分析（1）插入排序算法的时间复杂度为O(n^2)，空间复杂度为O(1)。
第1篇一、实验目的1. 理解快速排序算法的基本原理和实现方法。
2. 掌握快速排序算法的时间复杂度和空间复杂度分析。
3. 通过实验验证快速排序算法的效率。
4. 提高编程能力和算法设计能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理快速排序算法是一种分而治之的排序算法，其基本思想是：选取一个基准元素，将待排序序列分为两个子序列，其中一个子序列的所有元素均小于基准元素，另一个子序列的所有元素均大于基准元素，然后递归地对这两个子序列进行快速排序。
快速排序算法的时间复杂度主要取决于基准元素的选取和划分过程。
在平均情况下，快速排序的时间复杂度为O(nlogn)，但在最坏情况下，时间复杂度会退化到O(n^2)。
四、实验内容1. 快速排序算法的代码实现2. 快速排序算法的时间复杂度分析3. 快速排序算法的效率验证五、实验步骤1. 设计快速排序算法的C++代码实现，包括以下功能：- 选取基准元素- 划分序列- 递归排序2. 编写主函数，用于生成随机数组和测试快速排序算法。
3. 分析快速排序算法的时间复杂度。
4. 对不同规模的数据集进行测试，验证快速排序算法的效率。
六、实验结果与分析1. 快速排序算法的代码实现```cppinclude <iostream>include <vector>include <cstdlib>include <ctime>using namespace std;// 生成随机数组void generateRandomArray(vector<int>& arr, int n) {srand((unsigned)time(0));for (int i = 0; i < n; ++i) {arr.push_back(rand() % 1000);}}// 快速排序void quickSort(vector<int>& arr, int left, int right) { if (left >= right) {return;}int i = left;int j = right;int pivot = arr[(left + right) / 2]; // 选取中间元素作为基准 while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr[i], arr[j]);i++;j--;}}quickSort(arr, left, j);quickSort(arr, i, right);}int main() {int n = 10000; // 测试数据规模vector<int> arr;generateRandomArray(arr, n);clock_t start = clock();quickSort(arr, 0, n - 1);clock_t end = clock();cout << "排序用时：" << double(end - start) / CLOCKS_PER_SEC << "秒" << endl;return 0;}```2. 快速排序算法的时间复杂度分析根据实验结果，快速排序算法在平均情况下的时间复杂度为O(nlogn)，在最坏情况下的时间复杂度为O(n^2)。
目录CS1：斐波那契数列 (1)CS2：正整数解 (6)CS3：鸡兔同笼 (7)CS4：棋盘上的距离 (10)CS5：校门外的树木 (12)CS6：填词 (14)CS7：装箱问题 (17)CS8：求平均年龄 (19)CS9：数字求和 (20)CS10：两倍 (21)CS11：肿瘤面积 (22)CS12：肿瘤检测 (23)CS13：垂直直方图 (24)CS14：谁拿了最多的奖学金 (25)CS15：简单密码 (27)CS16：化验诊断 (29)CS17：密码 (31)CS18：数字阶梯 (32)CS19：假票 (34)CS20：纸牌（Deck） (35)《算法与程序实践》习题解答1——简单计算这一章的主要目的是通过编写一些简单的计算题，熟悉C/C++语言的基本语法。
基本思想：解决简单的计算问题的基本过程包括将一个用自然语言描述的实际问题抽象成一个计算问题，给出计算过程，继而编程实现计算过程，并将计算结果还原成对原来问题的解答。
这里首要的是读懂问题，搞清输入和输出的数据的含义及给出的格式，并且通过输入输出样例验证自己的理解是否正确。
课堂练习：CS1、CS2、CS3课堂讲解：CS4（CS5）A类（满分80）课堂练习：CS8、CS9、CS10B类（满分100）课堂上机：CS11、CS20CS1：斐波那契数列问题描述：已知斐波那契数列第n项的计算公式如下。
在计算时有两种算法：递归和非递归，请分别给出这两种算法。
当n=0时，Fib(n)=0，当n=1时，Fib(n)=1，当n>1时，Fib(n)= Fib(n-1)+ Fib(n-2)输入：第一行是测试数据的组数m，后面跟着m行输入。
每行包括一个项数n和一个正整数a。
（m，n，a均大于0，且均小于10000000）输出：输出包含m行，每行对应一个输入，若a不大于Fib(n)，则输出Yes，否则输出No输入样例：33 310 5024 20000输出样例：NoYesYes参考程序1（zzg）：循环版#include<stdio.h>int main(){int fn2,fn1,fn,m,n,a,i,j;fn2=0;fn1=1;//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&m);for(i=1;i<=m;i++){scanf("%d %d",&n,&a);if(n==1){if(a<=fn1)printf("Yes\n");elseprintf("No\n");}else{for(j=2;j<=n;j++){fn=fn2+fn1;fn2=fn1;fn1=fn;if(a<=fn){printf("Yes\n");break;}}if(j>n)printf("No\n");}}return 1;}递归版（zzg）#include<stdio.h>int fib(int n){if(n<2)return n==0?0:1;elsereturn fib(n-2)+fib(n-1);}int main(){int m,n,a,i,j;scanf("%d",&m);for(i=1;i<=m;i++){scanf("%d %d",&n,&a);for(j=1;j<=n;j++){if(a<=fib(j)){printf("Yes\n");break;}}if(j>n)printf("No\n");}return 1;}注意事项：这题主要考察递归与非递归的用法，还有数值越界的情况。
1）测试数据可取一下1 1和1 3试一下。
2）测试数据可以取一下50 1000和1000 1000。
程序中若考虑到值的越界就没问题或者考虑使用break也可以。
CS2：正整数解求x2+y2=2000的正整数解，输出所有不同的解。
参考程序：#include<stdio.h>#include<math.h>int main(){int x,y,m;m=(int)sqrt(2000);for(x=1;x<=m;x++)for(y=x;y<=m;y++)if(x*x+y*y==2000)printf("%d*%d+%d*%d=2000\n",x,x,y,y);return 0;}注意事项：这题主要考察枚举的用法，还有求平方根（数学函数）的用法。
1）要考虑x和y可调换，所以需要加上y>=x，这样就能保证不会出现重复的解2）考虑一下优化的问题for(y=x;y<=m;y++)可以优化为：for(y=m;y>=x;y--)，甚至还可以int temp=(int)sqrt(2000-x*x)for(y=temp;y>=x;y--)CS3：鸡兔同笼（来源： 2750）问题描述：一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。
已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。
输入：第1 行是测试数据的组数n，后面跟着n行输入。
每组测试数据占1行，包括一个正整数a (a < 32768) 。
输出：n 行，每行输出对应一个输入。
输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。
如果没有满足要求的情况出现，则输出2个0。
输入样例：2320输出样例：0 05 10参考程序：#include<stdio.h>int main(){int nCase,nFeet,i;scanf("%d",&nCase);for(i=1;i<=nCase;i++){scanf("%d",&nFeet);if(nFeet%2 != 0)printf("0 0\n");else if(nFeet%4 != 0)printf("%d %d\n",nFeet/4+1,nFeet/2);elseprintf("%d %d\n",nFeet/4,nFeet/2);}return 0;}解题思路：这个问题可以描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍数，输出N / 4，N / 2，如果N不是4的倍数，输出N/4+1，N/2 。
这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。
题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。
注意事项：这里考察数学计算，出错有一下几种情况：1）因为对问题分析不清楚，给出了错误的计算公式；2）不用数学方法，而试图用枚举所有鸡和兔的个数来求解此题，造成超时；3）试图把所有输入先存储起来，再输出，开的数组太小，因数组越界产生运行错；4）在每行输出末尾缺少换行符；5）对输入输出语法不熟悉导致死循环或语法错。
CS4：棋盘上的距离（来源： 1657）问题描述：国际象棋的棋盘是黑白相间的8 * 8 的方格，棋子放在格子中间。
如图1-1 所示：图1-1 国际象棋棋盘王、后、车、象的走子规则如下：王：横、直、斜都可以走，但每步限走一格。
后：横、直、斜都可以走，每步格数不受限制。
车：横、竖均可以走，不能斜走，格数不限。
象：只能斜走，格数不限。
写一个程序，给定起始位置和目标位置，计算王、后、车、象从起始位置走到目标位置所需的最少步数。
输入：第一行是测试数据的组数t（0 <= t <= 20 ）。
以下每行是一组测试数据，每组包括棋盘上的两个位置，第一个是起始位置，第二个是目标位置。
位置用"字母-数字"的形式表示，字母从“a”到“h”，数字从“1”到“8”。
输出要求：对输入的每组测试数据，输出王、后、车、象所需的最少步数。
如果无法到达，就输出“Inf”。
输入样例2a1 c3f5 f8输出样例2 1 2 13 1 1 Inf解题思路这个问题是给定一个棋盘上的起始位置和终止位置，分别判断王、后、车、象从起始位置到达终止位置需要的步数。
首先，王、后、车、象彼此独立，分别考虑就可以了。
所以这个题目重点要分析王、后、车、象的行走规则特点，从而推出它们从起点到终点的步数。
我们假设起始位置与终止位置在水平方向上的距离是x，它们在竖直方向上的距离是y。
根据王的行走规则，它可以横、直、斜走，每步限走一格，所以需要的步数是min(x,y)+abs(x-y) ，即x，y 中较小的一个加上x 与y 之差的绝对值。
根据后行走的规则，她可以横、直、斜走，每步格数不受限制，所以需要的步数是1（x等于y 或者x 等于0 或者y 等于0）或者2(x不等于y)。
根据车行走的规则，它可以横、竖走，不能斜走，格数不限，需要步数为1 （x 或者y 等于0）或者2（x 和y 都不等于0）。
根据象行走得规则，它可以斜走，格数不限。
棋盘上的格点可以分为两类，第一类是它的横坐标和纵坐标之差为奇数，第二类是横纵坐标之差为偶数。
对于只能斜走的象，它每走一步，因为横纵坐标增加或减小的绝对值相等，所以横坐标和纵坐标之差的奇偶性无论如何行走都保持不变。
因此，上述的第一类点和第二类点不能互相到达。
如果判断出起始点和终止点分别属于两类点，就可以得出它们之间需要无数步的结论。
如果它们属于同一类点，象从起始点走到终止点需要1（x 的绝对值等于y 的绝对值）或者2（x 的绝对值不等于y 的绝对值）。
CS5：校门外的树木（来源： 2808）问题描述：某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。
我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。
这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。
现在要把这些区域中的树（包括区域端点处的两棵树）移走。
你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入：输入的第一行有两个整数L（1 <= L <= 10000）和M（1 <=M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。
