算法设计与分析 例题 绘制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

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

Spring、Spring Boot、Spring Cloud 的区别与联系分析

《Spring、SpringBoot、SpringCloud的区别与联系分析》Spring、SpringBoot和SpringCloud是Java开发中常用的框架,分别针对企业级应用开发、快速开... 目录1. Spring 框架2. Spring Boot3. Spring Cloud总结1. Sprin