昌吉编程培训🐷 qwer20050
专注于青少年编程培训!
关注数: 9 粉丝数: 12 发帖数: 386 关注贴吧数: 12
新疆Scratch少儿编程教学贴,培养逻辑思维,由浅入深,长期更新 本帖将从简单的游戏制作到复杂的数据结构及算法,希望想要学习编程的人能提供一点帮助,内容从浅到深循序渐进,程序从简单到复杂,本帖是一个教学推广帖,教大家学习使用Scratch,不会一味地追求高深或复杂的算法,只为培养大家对编程的兴趣,为大家提供一个方向。但是学习的后期我会更新一些复杂的数据结构算法,以便大家能拓展知识。主要涉及的内容包括: 1、学习简单的游戏,本帖为编程教学贴,学习制作游戏是为了让大家更好的了解程序设计思路及各种语法,所以本帖的游戏作品都比较简单而且很多都是网上的作品,但都是我在实际教学过程中用到的,短小而精悍。 2、小学、初中数学知识,编程是对数学的扩展,可以更好地将数学知识应用到程序中,在程序中能更好的直观感受到数学的乐趣,而不是填鸭式的学习数学,不知所云!但是其实你只要有小学数学知识也可以更好的学习scratch。 3、程序中变量及列表的使用。 4:基本算法:枚举、位运算、排序、分治 5:数据结构、链表、栈、队列、二叉树和堆 6:高级数据结构算法:排序搜索算法、动态规划、深度优先搜索、广度优先搜索、矩阵乘法等。 以上内容难度依次递进,本帖将陆续更新。
数据结构--堆排序 堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。 堆的操作编辑: 在堆的数据结构中,堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作: 最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点 创建最大堆(Build Max Heap):将堆中的所有数据重新排序 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算 初始化数组,加入时间复杂度变量,观察其运行时间,记得在加速模式下运行。构建二叉树堆堆内元素调整大顶堆排序堆得时间复杂度分析: 堆排序分为两步,即初始化堆、调整堆。 两个步骤都要调用一个调整结点顺序的函数堆调整Heapify,以大根堆为例,操作为: 1:如果父亲结点“大顶堆[a]”和它的两个孩子结点“大顶堆[2a]”],“大顶堆[2a+1”满足大顶堆[[a] > max{大顶堆[[2a+1], 大顶堆[[2a]},那么返回;因为,scratch的数组下标是从1开始的。所以叶子结点为“大顶堆[[2a+1], 大顶堆[[2a]” 2:如果不满足堆的性质,那么将父亲结点大顶堆[a]和较大孩子结点max{大顶堆[2a+1], 大顶堆[2a]}交换, 3:将原来较大的孩子结点作为父亲结点,重复上述操作,直到孩子结点是叶子结点为止 初始化堆的时间复杂度分析 初始化堆的时候,对于每个非叶子结点,都要调用上述函数,将它与它的孩子结点进行比较和交换,顺序是从后向前。 以操作2作为基本操作,对每一层都完全铺满的堆进行分析, 设元素个数为n,则堆的高度k=log(n+1)≈log n,非叶子结点的个数为2^(k-1)-1 假设每个非叶子结点都需要进行调整,则第i层的非叶子结点需要的操作次数为k-i, 第i层共有2^(i-1)个结点,则第i层的所有结点所做的操作为k*2^(i-1)- i*2^(i-1), 共k-1层非叶子结点,总的操作次数为     化简可得,上式=2^k-k+1,将k=log(n+1)≈log n代入,得n - log n +1, 所以,初始化堆的复杂度为O(n) 调整堆的时间复杂度分析 调整堆的复杂度计算和初始化堆差不多, 假设根节点和排在最后的序号为m的叶子结点交换,并进行调整,那么调整的操作次数 = 原来m结点所在的层数 = 堆的高度(因为m结点在堆的最后)= log m 共n个结点,调整的总操作次数为      化简可得,上式=log (n-1)! ≈ n*log n 所以,调整堆的复杂度为O(n*log n) 所以,总体复杂度为O(n*log n)
昌吉Scratch少儿编程教学贴,培养逻辑思维,由浅入深,长期更新 本帖将从简单的游戏制作到复杂的数据结构及算法,为昌吉市希望想要学习编程的人能提供一点帮助,内容从浅到深循序渐进,程序从简单到复杂,本帖是一个教学推广帖,教大家学习使用Scratch,不会一味地追求高深或复杂的算法,只为培养大家对编程的兴趣,为大家提供一个方向。但是学习的后期我会更新一些复杂的数据结构算法,以便大家能拓展知识。主要涉及的内容包括: 1、学习简单的游戏,本帖为编程教学贴,学习制作游戏是为了让大家更好的了解程序设计思路及各种语法,所以本帖的游戏作品都比较简单而且很多都是网上的作品,但都是我在实际教学过程中用到的,短小而精悍。 2、小学、初中数学知识,编程是对数学的扩展,可以更好地将数学知识应用到程序中,在程序中能更好的直观感受到数学的乐趣,而不是填鸭式的学习数学,不知所云!但是其实你只要有小学数学知识也可以更好的学习scratch。 3、程序中变量及列表的使用。 4:基本算法:枚举、位运算、排序、分治 5:数据结构、链表、栈、队列、二叉树和堆 6:高级数据结构算法:排序搜索算法、动态规划、深度优先搜索、广度优先搜索、矩阵乘法等。 以上内容难度依次递进,本帖将陆续更新,如有疑问可以联系QQ:1462638813
1 下一页