2008 年文章归档
共 4 篇文章
算法导论思考题:6-3Young 矩阵
三.Young 氏矩阵的相关算法. 题:一个 m*n 的 Young 氏矩阵(Young tableau) 是一个 m*n 的矩阵,其中每一行的数据都从左到右排序,第一列的数据都从上到下排序.Young氏矩阵中可能会有一些∞ 数据项,表示不存在的元素.所以,Young 氏矩阵可以用来存放 r<= mn 个有限的元素. a).画一个包含{9,16,3,2,4,8,5,14,12} 的4*4 的Young 氏矩阵. b).给出一个在非空 m*n 的 Young 氏矩阵上实现 EXTRACT-MIN 算法,使其运行时间为O(m+n). c).说明如何在O(m+n)时间内,将一个新元素手入到一个未满…
2008-10-30 21:41
算法导论习题2.3-7
题目:请给出一个时间复杂度为nlogn的算法,使之能够在给定一个由n个整数的构成的整合S和另一个整数x时,判断出S中是否存在有两个其和等于x的元素。 解答: 首先对S进行排序,使用合并算法进行排序,排序算法的时间复杂度为nlogn。 然后对排序的S从左到右(即从大到小)进行算法,首先锁定一个数i,这个数小于x的一半,然后从这个数的右边开始查找x-i,使用2分法查找,算法的时间复杂度小于nlogn,所以总的时间复杂度还是nlogn。 #include<iostream> constintMAXINT=0xFFFF-1; voidMerge(intA[],intstart,intmid,inte…
2008-10-25 15:36
在nlgn时间内实现逆序对数的计算
数组中逆序对的数量是同运行插入排序产生的移动的数量是相同的,但是选择排序的最差的时间复杂度是n的平方次,但是合并排序最差的是nlogn的时间复杂度。所以应该修改合并排序来计算逆序对数量。在L和R合并的过程中,如果没有移动的话,序列是L+R,所以计算移动的数量就是元素没有移动过R与L与R合并后的位置之间的差值就是移动的数量。 以下代码是实现的算法: #include<iostream> constintMAXINT=0xFFFF-1; voidInversionMerge(intA[],intstart,intmid,intend,int&c) { intlen1=mid-start+1+1;…
2008-10-25 11:05
类MFC实现无参数函数指针保存有参数函数指针
#include <iostream> using namespace std; class A; typedef void ( A:: * PFN)(void); class A { public: void FunA(int num) { cout<<"FunA in A num ="<<num<<endl; } }; union MM { PFN pfn; void (A:: * pfn_vi)(int); }; int main(void) { PFN pfn; A a; pfn =(PFN)(a.FunA); MM mm; mm.pfn=pfn; (a.*mm.pfn_vi)(3)…
2008-08-01 16:49