设为首页收藏本站

切换到窄版

鱼C论坛 › 日志

日志

数据结构与算法|

分享算法导论第六章6.5有限队列中的6.5-9课后练习: E=MC2 2014-1-5 19:47; 由题目提示知，需要用到归并排序，又要用到最小堆，那么我想到用含有最小堆排序的归并排序对k个有序数组进行合并因为链表可以看成特殊的动态数组，那么我把链表替换成数组求解。先把k个数组放入到一个新数组A中，那么一共就有k=n/a个数组(a为k个元素数组中所含最多元素的数量) view plain copy ...; 个人分类: 数据结构与算法|230 次阅读|0 个评论

分享算法导论第六章堆排序所给的伪代码转换具体程序: E=MC2 2014-1-4 09:29; 首先show下我自己写的不带类的C++代码 #includeiostream using namespace std; const length=100; int A ={1,9,10,2,7,5,6,4,13,3,18,11,100}; int Heap_size( int A , int ...; 个人分类: 数据结构与算法|219 次阅读|0 个评论

分享算法导论第六章6.3建堆和6.4堆排序算法课后答案: E=MC2 2014-1-2 19:39; 6.3-2 在BUILD-MAX-HEAP的第2行代码中，为什么希望循环下标i从向下取整leghth /2降到1，而不是从1升到向下取整leghth /2？因为如果用递增循环从下标i=1开始，那么i的两个左右子树对于任意排序的数组来说就可能出现左右子树不是最大堆的情况（使用MAX-HEAPIFY(A,i)函数必须满足左右子树是最大堆）。 & ...; 个人分类: 数据结构与算法|731 次阅读|0 个评论

分享算法导论第六章6.2维护堆的性质课后答案: E=MC2 2014-1-1 20:34; 6.2-1参照图6.2的方法，说明MAX-HEAPIFY(A,3)在数组A={27,17,3,16,13,10,1,5,7,12,4,8,9,0} 上的操作过程。操作过程参照书中图6.2，非常类似。 6.2-2参考过程MAX-HEAPIFY，写出能够维护相应最小堆的MIN-HEAPIFY(A,i)的伪代码，并比较 MIN-HEAPIFY与MAX-HEAPIFY的运行时间。把原书伪代码A A 与A A 都改成小于 ...; 个人分类: 数据结构与算法|1257 次阅读|0 个评论

分享算法导论第六章6.1堆课后答案: E=MC2 2014-1-1 20:33; 6.1-1在高度为h的堆中，元素个数最多和最少分别是多少？最少是最底层只有一个叶子结点:2^0+2^1+...+2^(h-1)+1=2^h 最多是这个堆（包括最底层）是一个完全二叉树:2^0+2^1+...+2^(h-1)+2^h=2^(h+1)-1 6.1-2证明：含n个元素的堆的高度为lgn. 设这个堆的高度为h 这个堆的总结点2^0+2^1+...+2^(h-1)+O(2^h)=n 其中 ...; 个人分类: 数据结构与算法|478 次阅读|0 个评论

分享算法导论第五章5.4和思考题: E=MC2 2013-12-27 20:54; 算法导论第5章概率分析和随机算法 5.4在我CSDN博客上面 http://blog.csdn.net/z84616995z/article/details/17616767 算法导论第五章概率分析和随机算法最后思考题 http://blog.csdn.net/z84616995z/article/details/17618953; 个人分类: 数据结构与算法|265 次阅读|0 个评论

分享算法导论第五章5.3随机算法: E=MC2 2013-12-24 10:33; 5.3-1 Marceau教授对引理5.5证明过程中使用的循环不变式表示异议。他对在第1次迭代之前循环不变式是否为真提出质疑。他得理由是人们可以容易地宣城空数组不包含0排列。因此空数组包含0排列的概率应该是0.所以在第1次迭代之前循环不变式无效。请改写过程RANDOMIZE-IN-PLACE，使其相关的循环不变式在第1次迭代之前对非空数组 ...; 个人分类: 数据结构与算法|570 次阅读|0 个评论

分享第五章5.2指示器随机变量课后答案研究: E=MC2 2013-12-24 10:32; 5.2-1HIRE-ASSISTANT中，假设应聘者以随机顺序出现，正好雇佣一次的概率是多少？正好雇佣n次的概率是多少？正好雇佣一次的概率是从n个应聘者选择一个所以是1/n 正好雇佣n次的概率是首次雇佣时候有n个应聘者概率是1/n，第二次雇佣的时候还剩n-1个应聘者所以其概率是1/(n-1)......第n次雇佣应聘者，只剩下最后1人 ...; 个人分类: 数据结构与算法|369 次阅读|0 个评论

分享算法导论第五章5.1雇佣问题课后答案研究: E=MC2 2013-12-24 10:30; 5.1-1证明：假设在程序HIRE-ASSISTANT的第四行中，我们总是能够决定哪一个应聘者最佳，这就蕴含我们知道应聘者排名的总次序。这就相当于一个排序，哪种排序都要进行元素之的比较，所以元素间的比较就是排序的关键，而此时是两个应聘者之间的比较。 5.1-2描述RANDOM(a,b)过程的一种实现，它只调用RANDOM(0, ...; 个人分类: 数据结构与算法|284 次阅读|0 个评论

分享算法导论第四章最后思考题。: E=MC2 2013-12-19 21:30; 由于时间紧迫，所以我把这篇文章发到CSDN上了，所以这里就不重复发了。。有兴趣请看。 http://blog.csdn.net/z84616995z/article/details/17425039; 个人分类: 数据结构与算法|478 次阅读|0 个评论

123 / 3 页下一页

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-5-22 13:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

返回顶部