hetumessi's Blog

Saving James Bond - Hard Version This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the b ...

列出连通集 给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。 输入格式 输入第1行给出2个整数N(0<N≤10)N(0<N≤10)N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。 输出格式 按照"{ v1 v2 … vk}"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。 输入样例 8 6 0 7 0 1 2 0 4 1 2 4 3 5 输出样例 { 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 } ac代码 #include<iostream> #include<queue> #define maxinte 10 using ...

Huffman Codes In 1953, David A. Huffman published his paper “A Method for the Construction of Minimum-Redundancy Codes”, and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string “aaaxuaxz”, we can observe that the frequencies of the characters ‘a’, ‘x’, ‘u’ and ‘z’ are 4, 2, 1 and 1, respectively. We may either encode the symbols ...

List Leaves Given a tree, you are supposed to list all the leaves in the order of top down, and left to right. Input Specification Each input file contains one test case. For each case, the first line gives a positive integer N(≤10)N(≤10)N(≤10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will b ...

二分查找 二分查找伪代码 int binarysearch(int i,int array[],int up,int bottom){ int Mid = (up + bottom) / 2; if 下界超过上界时，说明没有找到，返回错误状态-1 else if x比中间位置的数字大，则以M为新bottom值重新查找，递归调用 binarysearch(i,array,mid-1,bottom) else if x比中间位置的数字小，则以M为新up重新查找，递归调用 binarysearch(i,array,up,mid+1) else if x与中间位置的数字相等，则返回数字位置 Mid+1 } 题目 函数接口定义： Position BinarySearch( List L, ElementType X ); 其中List结构定义如下： typedef int Position; typedef struct LNode *List; struct LNode { El ...

Qt介绍 Qt是跨平台的开发库，主要是开发图形用户界面(Graphical User Interface，GUI)应用程序，当然也可以开发非图形的命令行(Command User Interface，CUI)应用程序。 Qt支持众多的操作系统平台，如通用操作系统Windows、Linux、Unix，智能手机系统Android、iOS、WinPhone，嵌入式系统QNX、VxWorks等等，应用广泛。当然Qt库本身包含的功能模块也日益丰富，一直有新模块和第三方模块扩充。除了与操作系统底层结合特别紧密的，如驱动开发，需要利用操作系统本身的函数库实现之外，其他大部分的应用程序开发都可以用Qt实现的。Qt本身是纯c++开发的，此外Qt还存在Python、Ruby、Perl等脚本语言的绑定，也可以使用脚本语言开发基于Qt的程序。 在Qt4以前的时代主流的是传统部件(或叫控件)编程，所用的语言一般是c++。Qt5诞生之时，正是手机移动设备蓬勃发展的时候，而传统的c++部件编写的界面对手机应用程序不是很方便，比如手机屏幕显示需要满足随意翻转功能，而这在传统桌面程序里基本遇不到。为了适应手机移动应用 ...

GNU工具链 在上个世纪八十年代，计算机都是奢侈品，操作系统里最著名的是Unix家族，当时还没有Windows、Linux之类的，Unix系统都是商业软件，里面的应用软件也是商业软件，全是封闭的环境。 系统程序员Richard M.Stallman(RMS)在此环境下创立了与众不同的GNU项目(GNU’s Not Unix)，以及推进自由软件发展的Free Software Foundation(FSF)自由软件基金会。GNU项目是为了创建自由的类Unix系统，也因此开发出来很多开源的系统工具，其中非常著名的就是GCC(GNU Compiler Collection，GNU编译器套件)。 GNU工具链(GNU toolchain)是一个包含了由GNU项目所产生的各种开发工具的集合，这些工具形成了一条工具链(串行使用的一组工具)。GNU工具链在针对嵌入式系统的Linux内核、BSD及其它软件的开发中起着至关重要的作用，其中的部分工具也被Solaris、Mac OS X、Microsoft Windows(via Cygwin和MinGW/MSYS)and Sony PlayStatio ...

makefile 本系列参考 一起跟我写makefile，在此向原作者致谢。文章经过了我个人的整理、补充、修正、再次排版而完成，记录在此以供大家学习分享。 另附GNU make中文手册以供参考(两者内容高度重合，也许这就是中文社区特色吧，还是推荐看中文手册，表述更清晰准确)。 注：本系列内容大部分是基于GNU make的标准，其中cc命令默认调用Linux自带的c编译器程序 makefile介绍 makefile编写(1)：规则 makefile编写(2)：变量 makefile编写(3)：条件执行和函数 为什么使用makefile 虽然可以直接调用编译器如g++编译程序，但是如果项目里的代码文件变多了，哪些代码文件更新了需要重新编译，哪些代码没有改不需要重新编译等等，靠程序员自己记忆去处理是比较麻烦的事，还有哪些代码需要预处理或是链接哪些库文件，这些都是繁杂的过程。为了规范程序的编译生成过程，产生了规范化的生成脚本，就是makefile，生成器make可以依据规范的makefile自动生成目标程序或库文件。makefile也是一个研究项目的利器，很多项目可能文 ...

各种排序 给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下： 数据1：只有1个元素； 数据2：11个不相同的整数，测试基本正确性； 数据3：103个随机整数； 数据4：104个随机整数； 数据5：105个随机整数； 数据6：105个顺序整数； 数据7：105个逆序整数； 数据8：105个基本有序的整数； 数据9：105个随机正整数，每个数字不超过1000。 输入格式 输入第一行给出正整数N（≤105）N（≤10^5）N（≤105），随后一行给出N个（长整型范围内的）整数，其间以空格分隔。 输出格式 在一行中输出从小到大排序后的结果，数字间以1个空格分隔，行末不得有多余空格。 输入样例 11 4 981 10 -17 0 -20 29 50 8 43 -5 输出样例 -20 -17 -5 0 4 8 10 29 43 50 981 #include<iostream> #define maxnum 10050 using namespace std; int n; long a[ ...

词频统计 散列表应用：文件中单词词频统计 例：给定一个英文文本文件，统计文件中所有单词出现的频率，并输出词频最大的前10%的单词及其词频，假设单词字符定义为大小写字母、数字和下划线，其他字符均认为是单词分隔符，不予考虑 分析 关键：对新读入的单词在已有的单词表中查找，如果已经存在，则将该单词的词频加1；如果不存在，则插入该单词并记词频为1 如何设计该单词表的数据结构才可以进行快速的查找和插入：应用散列表 int main(){ int TableSize=10000; //散列表估计大小 int wordcount=0,length; HashTable H; ElementType word; FILE*fp; char document[30]="HarryPotter.txt"; //要被统计词频的文件名 H=InitializeTable(TableSize); ...