算法设计与分析 例题 绘制Huffman树、循环赛、分治、最短路与动态规划

本文主要是介绍算法设计与分析 例题 绘制Huffman树、循环赛、分治、最短路与动态规划,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码。这些字符出现在文件中

的频数之比为 20:10:6:4:44:16。要求:

(1)(4 分)简述使用哈夫曼算法构造最优编码的基本步骤;

(2)(5 分)构造对应的哈夫曼树,并据此给出a,b,c,d,e,f 的一种最优编码。

解:1)、哈夫曼算法是构造最优编码树的贪心算法。其基本思想是,首先所

有字符对应n 棵树构成的森林,每棵树只有一个结点,根权为对应字符的频率。然后,重复

下列过程n-1 次:将森林中的根权最小的两棵树进行合并产生一个新树,该新树根的两个子

树分别是参与合并的两棵子树,根权为两个子树根权之和。

2)、根据题中数据构造哈夫曼树如下图所示。

由此可以得出 a,b,c,d,e,f 的一组最优的编码:01,0000,00010,00011, 1,001。

2.

设有n=2k个运动员要进行循环赛,现设计一个满足以下要求的比赛日程表:

每个选手必须与其他n-1名选手比赛各一次;每个选手一天至多只能赛一次;

循环赛要在最短时间内完成.
(1)(4分)循环赛最少需要进行( n-1 )天.

(2)(6分)当n=23=8时,请画出循环赛日程表:

1

2

3

4

5

6

7

8

2

1

4

3

6

5

8

7

3

4

1

2

7

8

5

6

4

3

2

1

8

7

6

5

5

6

7

8

1

2

3

4

6

5

8

7

2

1

4

3

7

8

5

6

3

4

1

2

8

7

6

5

4

3

2

1

3.

 请用分治策略设计递归的归并排序算法,并分析其时间复杂性(要求:分别给出divide、conquer、combine这三个阶段所花的时间,并在此基础上列出递归方程,最后用套用公式法求出其解的渐进阶)。

答 : Template <class Type>

void MergeSort (Type a[ ], int left, int right)     

{ if (left<right)                            

           { int i=left+right/2;               

            MergeSorta, left, i;               

            MergeSorta, i+1, right;            

            Merge(a, b, left, right);               

            Copy(a, b, left, right);                 

           }

 }

     Divide 阶段的时间复杂性:    O(1)          

     Conquer阶段的时间复杂性:   2T(n)          

     Combine阶段的时间复杂性:  Θ(n)          

                                               

    用套用公式法:a=2, b=2, nlog ba = n , f(n)=n,   因为f(n)与nlog ba 同阶,

   T(n) =Θ(nlogn)  

     4.

对下图所示的连通网络G,用克鲁斯卡尔(Kruskal)算法求G的最小生成树T,请写出在算法执行过程中,依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想,并简要分析算法的时间复杂度。

TE={(3,4), (2,3),(1,5),(4,6)(4,5)}   

贪心策略是每次都在连接两个不同连通分量的边中选权值最小的边。

基本思想:首先将图中所有顶点都放到生成树中,然后每次都在连接两个不同连通分量的边中选权值最小的边,将其放入生成树中,直到生成树中有n-1条边。

时间复杂度为:O(eloge)  

 5.

用动态规划策略求解最长公共子序列问题:

   (1)给出计算最优值的递归方程。

   (2)给定两个序列X={B,C,D,A},Y={A,B,C,B},请采用动态规划策略求出其最长公共子序列,要求给出过程。

(1)

                                        

                                        

                                       

                                          

这篇关于算法设计与分析 例题 绘制Huffman树、循环赛、分治、最短路与动态规划的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/984518

相关文章

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Python 迭代器和生成器概念及场景分析

《Python迭代器和生成器概念及场景分析》yield是Python中实现惰性计算和协程的核心工具,结合send()、throw()、close()等方法,能够构建高效、灵活的数据流和控制流模型,这... 目录迭代器的介绍自定义迭代器省略的迭代器生产器的介绍yield的普通用法yield的高级用法yidle

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

kotlin中const 和val的区别及使用场景分析

《kotlin中const和val的区别及使用场景分析》在Kotlin中,const和val都是用来声明常量的,但它们的使用场景和功能有所不同,下面给大家介绍kotlin中const和val的区别,... 目录kotlin中const 和val的区别1. val:2. const:二 代码示例1 Java

Go标准库常见错误分析和解决办法

《Go标准库常见错误分析和解决办法》Go语言的标准库为开发者提供了丰富且高效的工具,涵盖了从网络编程到文件操作等各个方面,然而,标准库虽好,使用不当却可能适得其反,正所谓工欲善其事,必先利其器,本文将... 目录1. 使用了错误的time.Duration2. time.After导致的内存泄漏3. jsO