落絮飞雁的个人网站

顺流而下,把梦做完

图论:最大流的各种变体

已知了最小费用流和最小割的性质,写写最大流的各种变体。 READ MORE →

图论:最小费用流与Bellman-Ford算法

最小传输费用问题

READ MORE →

稀疏矩阵转置之快速转置法

数据结构作业题目 = =
前情回顾:矩阵转置-简单代码

READ MORE →

一个简单的约瑟夫环代码

动态链表的课后作业。直接上代码:
READ MORE →

矩阵转置-简单代码

利用数组对两个矩阵进行转置。附上简单代码:
READ MORE →

区间调度问题

题目描述:

有n项工作,每项工作分别在si时间开始,ti时间结束。对于每项工作,你都可以选择参加或不参加,但选择了参加某项工作就必须至始至终参加全程参与,即参与工作的时间段不能有重叠(即使开始的瞬间和结束的瞬间重叠也是不允许的)。

你的目标是参与尽可能多的工作,那么你最多能参与多少项工作呢?

限制条件:

1<=n<=100000

1<=si<=ti,=10^9


这个问题首先想到的就是贪心算法。但设计算法时容易出现错误。

比较容易想到的算法如:

  • 在可选工作中,每次选取最先开始的工作
  • 在可选工作中,每次选取用时最短的工作
  • 在可选工作中,每次选取与最少可选工作有重叠的工作
  • 在可选工作中,每次选取结束时间最早的工作

而很显然,前三项算法都不具有普适性(例如:一项开头早,持续时间长的工作和两项开头晚的工作)。

关于最后一种算法的解释:

结束时间早,对应的可选工作就越多。当然也可以用归纳法来证明。

代码实现:

 

栈是支持push和pop的数据结构。

push是在栈的顶端放入一组数据;pop是在栈的顶端取出一组数据。

Last in first out(LIFO):最后进入栈的一组数据会被最先取出.


 

样例:

 


返回栈顶元素:

哈夫曼编码

已知某系统在通信联络中只可能出现8种字符,其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计哈夫曼编码。

综合训练:试编写一个将百分制分数转换为五级分制的程序。要求其时间性能尽可能好(即平均比较次数尽可能少)。假设学生成绩的分布情况如下:
分数 0-59 60-69 70-79 80-89 90-100
比例 0.05 0.15 0.40 0.30 0.10

快速幂取余算法例题

问题描述:
求 B ^ P % M = ?

代码实现:

辗转相除法

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12105 = 21 × 5);因为252 − 105 = 147,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式

例题: