[code]
Problem 4.18 Task Scheduling
Problem 4.19 N-nary Huffman Codes
Problem 4.20 N-nary Huffman Code Variations
Problem 4.21 Interval Intersections
Problem 4.22 Task Scheduling
Problem 4.23 Optimal Partitions
Problem 4.24 Optimal Partitions with Repetitions
Problem 4.25 Optimal Combinatorial Partitions
Problem 4.26 Planning Traveling
Problem 4.27 Robot Climber
[color=FF00FF]Chapter 5 Backtracking[/color]
Problem 5.1 Subset Sum
Problem 5.2 Minimum Length Board Arrangement
Problem 5.3 Minimum Weight Machine Design
Problem 5.4 Maximum Preferences
Problem 5.5 No Separation Dictionary
Problem 5.6 No Sum Sets
Problem 5.7 Instant Insanity
Problem 5.8 Integer Transformation
Problem 5.9 Latin squares
Problem 5.10 Jewel Arrangements
Problem 5.11 Latin squares with Repetition
Problem 5.12 Maze of Romeo and Juliet
Problem 5.13 Work Assignment
Problem 5.14 Hi-Q
Problem 5.15 Pentominoe Configuration
Problem 5.16 Board Permutation
Problem 5.17 Optimal Scheduling
Problem 5.18 Computation without Priority
Problem 5.19 Museum Guards
Problem 5.20 Unique Museum Guards
Problem 5.21 2´2´2 Rubik’s Cube
Problem 5.22 Rubik’s Cube
Problem 5.23 24 Points
Problem 5.24 m Points
Problem 5.25 Railroad Cars
Problem 5.26 Railroad Cars with Many Holding Tracks
Problem 5.27 Tribe Troops
Problem 5.28 Corroded Expressions
Problem 5.29 Complete Circle Sequences
Problem 5.30 Discrete 01 Strings
Problem 5.31 Painting Robots
Problem 5.32 Subset Trees
Problem 5.33 0-1 Knapsack
Problem 5.34 Permutation Trees
Problem 5.35 General Search
Problem 5.36 Shortest Addition Chains
Problem 5.37 n2-1 Puzzle
[color=FF00FF]Chapter 6 Branch and Bound[/color]
Problem 6.1 Minimum Length Board Arrangement
Problem 6.2 Minimum Length Board Arrangement
Problem 6.3 Minimum Weight Vertex Cover
Problem 6.4 Maximum Cut
Problem 6.5 Minimum Weight Machine Design
Problem 6.6 Maximal Preferences
Problem 6.7 n Queens
Problem 6.8 Circle Permutation
Problem 6.9 Board Permutation
Problem 6.10 Optimal Scheduling
Problem 6.11 Computation without Priority
Problem 6.12 Museum Guards
Problem 6.13 Subset Trees
Problem 6.14 Permutation Trees
Problem 6.15 General FIFO Branch and Bound
Problem 6.16 Subset Trees
Problem 6.17 Permutation Trees
Problem 6.18 General Priority Branch and Bound
Problem 6.19 Knight’s Tour
Problem 6.20 Push Box
Problem 6.21 Graph Transformation
Problem 6.22 Row and Column Transformation
Problem 6.23 n2 Puzzle
Problem 6.24 The Most Distant State
[color=FF00FF]Chapter 7 Randomized Algorithms[/color]
Problem 7.1 Modular Square Roots
Problem 7.2 Primality Testing
Problem 7.3 Set Equality
Problem 7.4 Inverse Matrix
Problem 7.5 Multiplication of Polynomials
Problem 7.6 Queen Control
Problem 7.7 3SAT
Problem 7.8 Combat Vehicles
Problem 7.9 Circle Permutation
Problem 7.10 Knight’s Control
Problem 7.11 Attacking Knights
[color=FF00FF]Chapter 8 Linear Programming and Network Flows[/color]
Problem 8.1 Pilot Match
Problem 8.2 Space Shuttle Experiments
Problem 8.3 Minimum Path Cover
Problem 8.4 Magic Balls
Problem 8.5 Round Tables
Problem 8.6 Longest Increasing Sequences
Problem 8.7 Exercise Data Bases
Problem 8.8 Motion Planning on Trees
Problem 8.9 Number Grids
Problem 8.10 Napkin Planning
Problem 8.11 Airlines
Problem 8.12 Software Patches
Problem 8.13 Space Shuttles
Problem 8.14 Rescue
Problem 8.15 Car Traveling
Problem 8.16 Number Trapezoids
Problem 8.17 Transportation
Problem 8.18 Assignment
Problem 8.19 Load Balancing
Problem 8.20 Deep-Sea Robots
Problem 8.21 Longest k Intersection Interval Set
Problem 8.22 Longest k Intersection Line Segment Set
Problem 8.23 Explore Mars
Problem 8.24 Peaceful Knights
[color=FF00FF]Chapter 9 NP-Completeness and Approximation Algorithms[/color]
Problem 9.1 Approximation Algorithm for TSP
Problem 9.2 Approximation Algorithm for SAT
Problem 9.3 Approximation Algorithm for MAX-SAT
Problem 9.4 Approximation Algorithm for Subset Sum
Problem 9.5 Polynomial Approximation for Subset Sum
Problem 9.6 Linear Time Algorithm for 2SAT
Problem 9.7 Linear Time Implement of greedySetCover
[color=0000ff]
Midterm Exam 1
Problem 1 Maximum Sequence Differences
Problem 2 Bitonic Tours
Problem 3 Optimal Scheduling
Midterm Exam 2
Problem 1 Pebble Merging
Problem 2 Integer Factorization
Problem 3 Oiling Car
Final Exam 1
Problem 1 Multiplication Table
Problem 2 Work Assignment
Problem 3 Pilot Match
Final Exam 2
Problem 1 k Median of Line
Problem 2 Graph Transformation
Problem 3 Maximum Cut
[/color]
[/code]

第一部分：
[
Chapter 1 Introduction
Problem 1.1 Counting
Problem 1.2 Dictionary
Problem 1.3 Divisors
Problem 1.4 Coin Array
Problem 1.5 Maximum Gap
第1章 算法概述
算法实现题1-1 统计数字问题
算法实现题1-2 字典序问题
算法实现题1-3 最多约数问题
算法实现题1-4 金币阵列问题
算法实现题1-5 最大间隙问题
]

---------------------- ALGO_NO. 1----------------------------------
===========================BEGIN===============================

算法实现题1-1 统计数字问题

问题描述：
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，
每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数
字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，
2，…，9。

编程任务：

给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用
到多少次数字0，1，2，…，9。

数据输入：

输入数据由文件名为input.txt的文本文件提供。
每个文件只有1 行，给出表示书的总页码的整数n。

结果输出:

程序运行结束时，将计算结果输出到文件output.txt中。输出文件共有10行，在第k行
输出页码中用到数字k-1 的次数，k=1，2，…，10。
输入文件示例 输出文件示例
input.txt 
11

output.txt
1
4
1
1
1
1
1
1
1
1
===================================================================
算法实现题1-2 字典序问题

问题描述：

在数据加密和数据压缩中常需要对特殊的字符串进行编码。给定的字母表A 由26 个小
写英文字母组成A={a,b,…,z}。该字母表产生的升序字符串是指字符串中字母按照从左到
右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1 次。例如，
a,b,ab,bc,xyz 等字符串都是升序字符串。现在对字母表A 产生的所有长度不超过6 的升序
字符串按照字典序排列并编码如下。
1 2 … 26 27 28 …
a b … z ab ac …
对于任意长度不超过6 的升序字符串，迅速计算出它在上述字典中的编码。

编程任务：

对于给定的长度不超过6 的升序字符串，编程计算出它在上述字典中的编码。

数据输入：

输入数据由文件名为input.txt的文本文件提供。
文件的第一行是一个正整数k，表示接下来共有k 行。
接下来的k行中，每行给出一个字符串。

结果输出:

程序运行结束时，将计算结果输出到文件output.txt 中。文件共有k 行，每行对应于一
个字符串的编码。
输入文件示例 输出文件示例
input.txt 
2
a
b

output.txt
1
2
====================================================================
算法实现题1-3 最多约数问题

问题描述：

正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如，1，2，
5，10 都是正整数10 的约数，且div(10)=4。设a 和b 是2 个正整数，a≤b，找出a 和b
之间约数个数最多的数x。
 
编程任务：
对于给定的2 个正整数a≤b，编程计算a 和b 之间约数个数最多的数。
 

数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1 行有2 个正整数a和b。

结果输出:
程序运行结束时，若找到的a 和b 之间约数个数最多的数是x，将div(x)输出到文件
output.txt中。

输入文件示例 输出文件示例
input.txt  output.txt
1 36            9

===========================================================

 算法实现题1-4 金币阵列问题

问题描述：

有m x n (m<=100, n<=100 ) 个金币在桌面上排成一个m行n 列的金币阵列。每一枚金
币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。
金币阵列游戏的规则是：
（1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选2 列，交换这2 列金币的位置。

编程任务：

给定金币阵列的初始状态和目标状态，编程计算按金币游戏规则，将金币阵列从初始状
态变换到目标状态所需的最少变换次数。

数据输入：

由文件input.txt给出输入数据。文件中有多组数据。文件的第1行有1 个正整数k，表
示有k 组数据。每组数据的第1 行有2 个正整数m 和n。以下的m行是金币阵列的初始状
态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。接着的
m行是金币阵列的目标状态。

结果输出:

将计算出的最少变换次数按照输入数据的次序输出到文件output.txt。相应数据无解时
输出-1。
输入文件示例 输出文件示例
input.txt 
2
4 3
1 0 1
0 0 0
1 1 0
1 0 1
1 0 1
1 1 1
0 1 1
1 0 1
4 3
1 0 1
0 0 0
1 0 0
1 1 1
1 1 0
1 1 1
0 1 1
1 0 1

output.txt

2
-1

===============================================================


算法实现题1-5 最大间隙问题
 
问题描述：
最大间隙问题：给定n 个实数x1, x2 ,..., xn，求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整函数耗时O(1)，设计解最大间隙问题的线性时间算法。
 
编程任务：
对于给定的n 个实数x1,x2,...,xn，编程计算它们的最大间隙。

数据输入：
输入数据由文件名为input.txt的文本文件提供。文件的第1 行有1 个正整数n。接下来
的1 行中有n个实数 x1,x2,...,xn 。

结果输出:

程序运行结束时，将找到的最大间隙输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt 
5
2.3 3.1 7.5 1.5 6.3

output.txt

3.2


=============================  END ============================

第二部分:
[
Chapter 2 Recursion and Divide and Conquer
Problem 2.1 Pipeline
Problem 2.2 Majority
Problem 2.3 Post Office
Problem 2.4 Knight’s Hamilton Tour
Problem 2.5 Half Multiset
Problem 2.6 Half Set
Problem 2.7 Soldiers
Problem 2.8 Permutation with Repetition
Problem 2.9 Lexicographic Order
Problem 2.10 Set Partition
Problem 2.11 Set Partition 2
Problem 2.12 Bicolor Towers of Hanoi
Problem 2.13 Standard 2&acute;n Table
Problem 2.14 Integer Factorization

第2章 递归与分治策略
算法实现题2-1 输油管道问题
算法实现题2-2 众数问题
算法实现题2-3 邮局选址问题
算法实现题2-4 马的Hamilton周游路线问题
算法实现题2-5 半数集问题
算法实现题2-6 半数单集问题
算法实现题2-7 士兵站队问题
算法实现题2-8 有重复元素的排列问题
算法实现题2-9 排列的字典序问题
算法实现题2-10 集合划分问题
算法实现题2-11 集合划分问题2
算法实现题2-12 双色Hanoi塔问题
算法实现题2-13 标准2维表问题
算法实现题2-14 整数因子分解问题
]

-------------------ALGO NO.2------------------------------
==========================================================
算法实现题2-1 输油管道问题

问题描述：

某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油
田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油
井的位置,即它们的x 坐标（东西向）和y 坐标（南北向）,应如何确定主管道的最优位置,
即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道
的最优位置。

编程任务：

给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。

数据输入：

由文件input.txt 提供输入数据。文件的第1 行是油井数n，1&pound;n&pound;10000。接下来n 行是
油井的位置，每行2个整数x和y，-10000&pound;x，y&pound;10000。

结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是油井到
主管道之间的输油管道最小长度总和。
输入文件示例 输出文件示例
input.txt 
5
1 2
2 2
1 3
3 -2
3 3

output.txt

6

==============================================================

算法实现题2-2 众数问题
&laquo;问题描述：
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重
集S中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。
多重集S的众数是2，其重数为3。
&laquo;编程任务：
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。
&laquo;数据输入：
输入数据由文件名为input.txt的文本文件提供。
文件的第1行多重集S中元素个数n；接下来的n 行中，每行有一个自然数。
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt中。输出文件有2 行，第1 行给
出众数，第2 行是重数。
输入文件示例 输出文件示例
input.txt 
6
1
2
2
2
3
5

output.txt

2
3

===============================================================

算法实现题2-3 邮局选址问题
&laquo;问题描述：
在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的
街区中。用x 坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。
街区中任意2 点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。
居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。
&laquo;编程任务：
给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。
&laquo;数据输入：
由文件input.txt 提供输入数据。文件的第1 行是居民点数n，1<=n<=10000。接下来n 行
是居民点的位置，每行2 个整数x 和y，-10000<=x，y<=10000。
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是n 个居
民点到邮局的距离总和的最小值。
输入文件示例 输出文件示例
input.txt 
5
1 2
2 2
1 3
3 -2
3 3

output.txt

10

==============================================================

算法实现题2-4 马的Hamilton周游路线问题
&laquo;问题描述：
8&acute;8 的国际象棋棋盘上的一只马，恰好走过除起点外的其它63 个位置各一次，最后回
到起点。这条路线称为一条马的Hamilton 周游路线。对于给定的m&acute;n 的国际象棋棋盘，m
和n均为大于5 的偶数，且|m-n|≤2，试设计一个分治算法找出一条马的Hamilton周游路线。
&laquo;编程任务：
对于给定的偶数m，n≥6，且|m-n|≤2，编程计算m&acute;n 的国际象棋棋盘一条马的Hamilton
周游路线。
&laquo;数据输入：
由文件input.txt给出输入数据。第一行有2个正整数m和n，表示给定的国际象棋棋盘
由m行，每行n个格子组成。
&laquo;结果输出:
程序运行结束时,将计算出的马的Hamilton周游路线用下面的2 种表达方式输出到文件
output.txt中。
第1 种表达方式按照马步的次序给出马的Hamilton 周游路线。马的每一步用所在的方
格坐标(x，y)来表示。x表示行的坐标，编号为0，1，…，m-1；y表示列的坐标，编号为0，
1，…，n-1。起始方格为（0，0）。
第2 种表达方式在棋盘的方格中标明马到达该方格的步数。（0，0）方格为起跳步，并
标明为第1步。
输入文件示例 输出文件示例
input.txt 
6 6 

output.txt

(0,0) (2,1) (4,0) (5,2) (4,4) (2,3)
(0,4) (2,5) (1,3) (0,5) (2,4) (4,5)
(5,3) (3,2) (5,1) (3,0) (1,1) (0,3)
(1,5) (3,4) (5,5) (4,3) (3,1) (5,0)
(4,2) (5,4) (3,5) (1,4) (0,2) (1,0)
(2,2) (0,1) (2,0) (4,1) (3,3) (1,2)
1 32 29 18 7 10
30 17 36 9 28 19
33 2 31 6 11 8
16 23 14 35 20 27
3 34 25 22 5 12
24 15 4 13 26 21

============================================================

算法实现题2-5 半数集问题
&laquo;问题描述：
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集是多重集。
&laquo;编程任务：
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
&laquo;数据输入：
输入数据由文件名为input.txt的文本文件提供。
每个文件只有1 行，给出整数n。(0<n<1000)
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。输出文件只有1 行，给出半
数集set(n)中的元素个数。
输入文件示例 输出文件示例
input.txt
6
output.txt
6

=================================================================

====================================================

算法实现题2-6 半数单集问题
&laquo;问题描述：
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集不是多重集。集合中已经有的元素不再添加到集合中。
&laquo;编程任务：
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
&laquo;数据输入：
输入数据由文件名为input.txt的文本文件提供。
每个文件只有1 行，给出整数n。(0<n<201)
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。输出文件只有1 行，给出半
数集set(n)中的元素个数。
输入文件示例 输出文件示例
input.txt
6

output.txt
6 

========================================================

算法实现题2-7 士兵站队问题
&laquo;问题描述：
在一个划分成网格的操场上，n个士兵散乱地站在网格点上。网格点由整数坐标(x,y)表
示。士兵们可以沿网格边上、下、左、右移动一步，但在同一时刻任一网格点上只能有一名
士兵。按照军官的命令，士兵们要整齐地列成一个水平队列，即排列成
(x,y),(x+1,y),…,(x+n-1,y)。如何选择x 和y的值才能使士兵们以最少的总移动步数排成一列。
&laquo;编程任务：
计算使所有士兵排成一行需要的最少移动步数。
&laquo;数据输入：
由文件input.txt 提供输入数据。文件的第1 行是士兵数n，1<=n<=10000。接下来n 行是
士兵的初始位置，每行2 个整数x 和y，-10000<=x，y<=10000。
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是士兵排
成一行需要的最少移动步数。
输入文件示例 输出文件示例
input.txt 
5
1 2
2 2
1 3
3 -2
3 3

output.txt

8

===========================================================

算法实现题2-8 有重复元素的排列问题
&laquo;问题描述：
设R={ r1, r2, ..., rn }是要进行排列的n个元素。其中元素r1,r2,...,rn可能相同。试设计
一个算法，列出R的所有不同排列。
&laquo;编程任务：
给定n 以及待排列的n 个元素。计算出这n 个元素的所有不同排列。
&laquo;数据输入：
由文件input.txt 提供输入数据。文件的第1 行是元素个数n，1<=n<=500。接下来的1 行
是待排列的n个元素。
&laquo;结果输出:
程序运行结束时，将计算出的n 个元素的所有不同排列输出到文件output.txt 中。文件
最后1 行中的数是排列总数。
输入文件示例 输出文件示例
input.txt 
4
aacc

output.txt

aacc
acac
acca
caac
caca
ccaa
6


============================================================

算法实现题2-9 排列的字典序问题
&laquo;问题描述：
n个元素{1,2,..., n }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，
n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：
字典序值: 0  1   2   3   4   5
排列 :   123 132 213 231 312 321
&laquo;编程任务：
给定n 以及n 个元素{1,2,..., n }的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第1 行是元素个数n。接下来的1 行是n个元素
{1,2,.., n }的一个排列。
&laquo;结果输出:
程序运行结束时，将计算出的排列的字典序值和按字典序排列的下一个排列输出到文件
output.txt中。文件的第一行是字典序值，第2行是按字典序排列的下一个排列。
输入文件示例 输出文件示例
input.txt 
8
2 6 4 5 8 1 7 3

output.txt

8227
2 6 4 5 8 3 1 7

===========================================================

算法实现题2-10 集合划分问题
&laquo;问题描述：
n个元素的集合{1,2,..., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：
{{1}，{2}，{3}，{4}}，
{{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}，
{{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}，
{{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}，
{{1，2}，{3，4}}，
{{1，3}，{2，4}}，
{{1，4}，{2，3}}，
{{1，2，3}，{4}}，
{{1，2，4}，{3}}，
{{1，3，4}，{2}}，
{{2，3，4}，{1}}，
{{1，2，3，4}}
&laquo;编程任务：
给定正整数n，计算出n 个元素的集合{1,2,..., n }可以划分为多少个不同的非空子集。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第1 行是元素个数n。
&laquo;结果输出:
程序运行结束时，将计算出的不同的非空子集数输出到文件output.txt中。
输入文件示例 输出文件示例
input.txt 
5

output.txt

52

==================================================================

========================================================

算法实现题2-11 集合划分问题
&laquo;问题描述：
n个元素的集合{1,2,..., n }可以划分为若干个非空子集。例如，当n=4 时，集合{1，2，3，4}可以划分为15 个不同的非空子集如下：
{{1}，{2}，{3}，{4}}，
{{1，2}，{3}，{4}}，
{{1，3}，{2}，{4}}，
{{1，4}，{2}，{3}}，
{{2，3}，{1}，{4}}，
{{2，4}，{1}，{3}}，
{{3，4}，{1}，{2}}，
{{1，2}，{3，4}}，
{{1，3}，{2，4}}，
{{1，4}，{2，3}}，
{{1，2，3}，{4}}，
{{1，2，4}，{3}}，
{{1，3，4}，{2}}，
{{2，3，4}，{1}}，
{{1，2，3，4}}
其中，集合{{1，2，3，4}}由1 个子集组成；集合{{1，2}，{3，4}}，{{1，3}，{2，
4}}，{{1，4}，{2，3}}，{{1，2，3}，{4}}，{{1，2，4}，{3}}，{{1，3，4}，{2}}，{{2，
3，4}，{1}}由2 个子集组成；集合{{1，2}，{3}，{4}}，{{1，3}，{2}，{4}}，{{1，4}，
{2}，{3}}，{{2，3}，{1}，{4}}，{{2，4}，{1}，{3}}，{{3，4}，{1}，{2}}由3 个子集组
成；集合{{1}，{2}，{3}，{4}}由4 个子集组成。
&laquo;编程任务：
给定正整数n 和m，计算出n 个元素的集合{1,2,..., n }可以划分为多少个不同的由m 个
非空子集组成的集合。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第1 行是元素个数n和非空子集数m。
&laquo;结果输出:
程序运行结束时，将计算出的不同的由m个非空子集组成的集合数输出到文件output.txt
中。
输入文件示例 输出文件示例
input.txt 
4 3

output.txt
6

=========================================================

算法实现题2-12 双色Hanoi塔问题
&laquo;问题描述：
设A、B、C是3 个塔座。开始时，在塔座A 上有一叠共n 个圆盘，这些圆盘自下而上，
由大到小地叠在一起。各圆盘从小到大编号为1，2，……，n，奇数号圆盘着蓝色，偶数号
圆盘着红色，如图所示。现要求将塔座A 上的这一叠圆盘移到塔座B 上，并仍按同样顺序叠
置。在移动圆盘时应遵守以下移动规则：
规则(1)：每次只能移动1 个圆盘；
规则(2)：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；
规则(3)：任何时刻都不允许将同色圆盘叠在一起；
规则(4)：在满足移动规则(1)-(3)的前提下，可将圆盘移至A，B，C 中任一塔座上。

试设计一个算法，用最少的移动次数将塔座A 上的n个圆盘移到塔座B 上，并仍按同样
顺序叠置。
&laquo;编程任务：
对于给定的正整数n，编程计算最优移动方案。
&laquo;数据输入：
由文件input.txt给出输入数据。第1 行是给定的正整数n。
&laquo;结果输出:
将计算出的最优移动方案输出到文件output.txt。文件的每一行由一个正整数k 和2 个
字符c1 和c2组成，表示将第k个圆盘从塔座c1移到塔座c2上。
输入文件示例 输出文件示例
input.txt 
3 

output.txt
1 A B
2 A C
1 B C
3 A B
1 C A
2 C B
1 A B


=====================================================
算法实现题2-13 标准2维表问题
&laquo;问题描述：
设n 是一个正整数。2 x n 的标准2 维表是由正整数1，2，…，2n 组成的2 x n 数组，该数组的每行从左到右递增，每列从上到下递增。2 x n的标准2 维表全体记为Tab(n)。例如，
当n=3时Tab(3)如下：
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5
4 5 6 3 5 6 3 4 6 2 5 6 2 4 6
&laquo;编程任务：
给定正整数n，计算Tab(n)中2 x n的标准2 维表的个数。
&laquo;数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数n。
&laquo;结果输出:
将计算出的Tab(n)中2 x n的标准2 维表的个数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt 
3 

output.txt

5

=========================================================

算法实现题2-14 整数因子分解问题
&laquo;问题描述：
大于1 的正整数n可以分解为：n=x1*x2*…*xm。
例如，当n=12 时，共有8 种不同的分解式：
12=12；
12=6*2；
12=4*3；
12=3*4；
12=3*2*2；
12=2*6；
12=2*3*2；
12=2*2*3。
&laquo;编程任务：
对于给定的正整数n，编程计算n共有多少种不同的分解式。
&laquo;数据输入：
由文件input.txt给出输入数据。第一行有1 个正整数n (1≤n≤2000000000)。
&laquo;结果输出:
将计算出的不同的分解式数输出到文件output.txt。
输入文件示例 输出文件示例
input.txt 
12

output.txt

8

=================END===============================

第三部分:
[
Chapter 3 Dynamic Programming
Problem 3.0 Independent Task Scheduling
Problem 3.1 Coin Changing
Problem 3.2 Relation Ordering
Problem 3.3 Counting Powers
Problem 3.4 Edit Distance
Problem 3.5 Pebble Merging
Problem 3.6 Number Triangles
Problem 3.7 Multiplication Table
Problem 3.8 Renting Boats
Problem 3.9 Car Traveling
Problem 3.10 Minimal m Sums
Problem 3.11 Circle Multiplication
Problem 3.12 Maximum Cube
Problem 3.13 Regular Expressions
Problem 3.14 Bitonic Tours
Problem 3.15 Maximum k Multiplications
Problem 3.16 Cheapest Shopping
Problem 3.17 Collecting Samples
Problem 3.18 Optimal Scheduling
Problem 3.19 String Comparison
Problem 3.20 k Median of Directed Trees
Problem 3.21 k Independent Median of Directed Trees
Problem 3.22 k Median of Directed Line
Problem 3.23 2 Median of Directed Line
Problem 3.24 Maximum Connected Component of Trees
Problem 3.25 k Median of Line
Problem 3.26 k Cover of Line
Problem 3.27 m Processors
Problem 3.28 Red Nodes of Red-Black Trees

第3章 动态规划
算法实现题3-0 独立任务最优调度问题
算法实现题3-1 最少硬币问题
算法实现题3-2 序关系计数问题
算法实现题3-3 多重幂计数问题
算法实现题3-4 编辑距离问题
算法实现题3-5 石子合并问题
算法实现题3-6 数字三角形问题
算法实现题3-7 乘法表问题
算法实现题3-8 租用游艇问题
算法实现题3-9 汽车加油行驶问题
算法实现题3-10 最小m段和问题
算法实现题3-11 圈乘运算问题
算法实现题3-12 最大长方体问题
算法实现题3-13 正则表达式匹配问题
算法实现题3-14 双调旅行售货员问题
算法实现题3-15 最大k乘积问题
算法实现题3-16 最少费用购物
算法实现题3-17 收集样本问题
算法实现题3-18 最优时间表问题
算法实现题3-19 字符串比较问题
算法实现题3-20 有向树k中值问题
算法实现题3-21 有向树独立k 中值问题
算法实现题3-22 有向直线m中值问题
算法实现题3-23 有向直线2中值问题
算法实现题3-24 树的最大连通分支问题
算法实现题3-25 直线k中值问题
算法实现题3-26 直线k覆盖问题
算法实现题3-27 m处理器问题
算法实现题3-28 红黑树的红色内结点问题

]

=====================ALGO NO.3===============================

算法实现题3-0 独立任务最优调度问题（习题3-3）
&laquo;问题描述：
用2 台处理机A 和B 处理n 个作业。设第i 个作业交给机器A 处理时需要时间ai，若
由机器B 来处理，则需要时间bi 。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai>=bi ，而对于某些j,j≠i，有aj<bj。既不能将一个作业分开由2 台机器处理，也没有一台机器能同时处理2 个作业。设计一个动态规划算法，使得这2 台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。研究一个实例：
(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。
&laquo;编程任务：
对于给定的2 台处理机A 和B处理n 个作业，找出一个最优调度方案，使2台机器处理
完这n 个作业的时间最短。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第1行是1个正整数n, 表示要处理n个作业。
接下来的2行中，每行有n 个正整数，分别表示处理机A 和B 处理第i 个作业需要的处理时
间。
&laquo;结果输出:
程序运行结束时，将计算出的最短处理时间输出到文件output.txt 中。
输入文件示例 输出文件示例
input.txt 
6
2 5 7 10 5 2
3 8 4 11 3 4

output.txt

15

============================================================

算法实现题3-1 最少硬币问题
&laquo;问题描述：
设有n 种不同面值的硬币，各硬币的面值存于数组T［1:n］中。现要用这些面值的硬
币来找钱。可以使用的各种面值的硬币个数存于数组Coins［1:n］中。
对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。
&laquo;编程任务：
对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，
以及钱数m，0≤m≤20001，编程计算找钱m的最少硬币数。
&laquo;数据输入：
由文件input.txt 提供输入数据，文件的第一行中只有1 个整数给出n的值,第2 行起每
行2 个数，分别是T[j]和Coins[j]。最后1 行是要找的钱数m。
&laquo;结果输出:
程序运行结束时，将计算出的最少硬币数输出到文件output.txt中。问题无解时输出-1。
输入文件示例 输出文件示例
input.txt 
3
1 3
2 3
5 3
18

output.txt
5

==========================================================

算法实现题3-2 序关系计数问题
&laquo;问题描述：
用关系“<”和“=”将3 个数A、B和C依序排列时有13 种不同的序关系：
A=B=C，A=B<C，A<B=C，A<B<C，A<C<B，A=C<B，B<A=C，B<A<C，B<C<A，
B=C<A，C<A=B，C<A<B，C<B<A。
将n 个数（1 <=  n <= 50）依序排列时有多少种序关系。
&laquo;编程任务：
编程计算出将n 个数（1 <= n <= 50）依序排列时有多少种序关系。
&laquo;数据输入：
由文件input.txt提供输入数据。文件只有一行，提供一个数n 。
&laquo;结果输出:
程序运行结束时，将找到的序关系数输出到文件output.txt的第1 行中。
输入文件示例 输出文件示例
input.txt 
3 

output.txt
13

=============================================================

算法实现题3-3 多重幂计数问题
&laquo;问题描述：
设给定n 个变量x1 ,x2 ,…, xn 。将这些变量依序作底和各层幂，可得n重幂!
这里将上述n 重幂看作是不确定的，当在其中加入适当的括号后，才能成为一个确定的
n 重幂。不同的加括号方式导致不同的n 重幂。例如，当n=4 时，全部4重幂有5个。
&laquo;编程任务：
对n个变量计算出有多少个不同的n重幂。
&laquo;数据输入：
由文件input.txt提供输入数据。文件只有一行，提供一个数n 。
&laquo;结果输出:
程序运行结束时，将找到的序关系数输出到文件output.txt的第1 行中。
输入文件示例 输出文件示例
input.txt 
4

output.txt

5

======================================================

算法实现题3-4 编辑距离问题
&laquo;问题描述：
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符串B。这里所说的
字符操作包括
(1)删除一个字符；
(2)插入一个字符；
(3)将一个字符改为另一个字符。
将字符串A变换为字符串B 所用的最少字符操作数称为字符串A到B 的编辑距离，记为
d(A,B)。试设计一个有效算法，对任给的2 个字符串A和B，计算出它们的编辑距离d(A,B)。
&laquo;编程任务：
对于给定的字符串A和字符串B，编程计算其编辑距离d(A,B)。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第一行是字符串A，文件的第二行是字符串B。
&laquo;结果输出:
程序运行结束时，将编辑距离d(A,B)输出到文件output.txt的第1 行中。
输入文件示例 输出文件示例
input.txt 
fxpimu
xwrs

output.txt

5

=========================================================

算法实现题3-5 石子合并问题
&laquo;问题描述：
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只
能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。
&laquo;编程任务：
对于给定n堆石子,编程计算合并成一堆的最小得分和最大得分。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第1 行是正整数n，1<=n <= 100，表示有n堆石子。
第二行有n个数，分别表示每堆石子的个数。
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是最小得
分；第2 行中的数是最大得分；。
输入文件示例 输出文件示例
input.txt 
4
4 4 5 9

output.txt
43
54

=========================================================

======================================================

算法实现题3-6 数字三角形问题
&laquo;问题描述：
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形
的顶至底的一条路径，使该路径经过的数字总和最大。
        7
      3   8
    8   1   0
  2   7   4  4
4   5   2   6  5
&laquo;编程任务：
对于给定的由n 行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数
字和的最大值。
&laquo;数据输入：
由文件input.txt 提供输入数据。文件的第1 行是数字三角形的行数n，1&pound;n&pound;100。接下
来n行是数字三角形各行中的数字。所有数字在0..99之间。
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是计算
出的最大值。
输入文件示例 输出文件示例
input.txt 
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

output.txt
30

=====================================================

算法实现题3-7 乘法表问题
&laquo;问题描述：
定义于字母表S={a,b,c}上的乘法表如下
  | a  b  c
-------------
a | b  b  a
b | c  b  a
c | a  c  c
-------------
依此乘法表，对任一定义于S上的字符串，适当加括号后得到一个表达式。例如，对于字符
串x=bbbba，它的一个加括号表达式为(b(bb))(ba)。依乘法表，该表达式的值为a。试设计
一个动态规划算法，对任一定义于S上的字符串x=x1x2x3x4...xn，计算有多少种不同的加括号
方式，使由x 导出的加括号表达式的值为a。
&laquo;编程任务：
对于给定的字符串 x=x1x2x3...xn ，计算有多少种不同的加括号方式，使由x 导出的加括号
表达式的值为a。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第1 行中给出一个字符串。
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是计算出的加
括号方式数。
输入文件示例 输出文件示例
input.txt 
bbbba 

output.txt
6

==========================================================

算法实现题3-8 租用游艇问题
&laquo;问题描述：
长江游艇俱乐部在长江上设置了n 个游艇出租站1，2，…，n。游客可在这些游艇出租
站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i 到游艇出租站j 之间
的租金为r(i,j),1<=i<j<=n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需
的最少租金。
&laquo;编程任务：
对于给定的游艇出租站i 到游艇出租站j 之间的租金为r(i,j),1<=i<j<=n，编程计算从
游艇出租站1 到游艇出租站n所需的最少租金。
&laquo;数据输入：
由文件input.txt 提供输入数据。文件的第1 行中有1 个正整数n（n<=200），表示有n
个游艇出租站。接下来的n-1 行是r(i,j),1<=i<j<=n。
&laquo;结果输出:
程序运行结束时，将计算出的从游艇出租站1 到游艇出租站n所需的最少租金输出到文
件output.txt中。
输入文件示例 输出文件示例
input.txt 
3
5 15
7

output.txt
12

=========================================================

算法实现题3-9 汽车加油行驶问题
&laquo;问题描述：
给定一个N*N 的方形网格，设其左上角为起点◎，坐标为（1，1），X轴向右为正，Y
轴向下为正，每个方格边长为1。一辆汽车从起点◎出发驶向右下角终点▲，其坐标为（N，N）。在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中
应遵守如下规则：
（1）汽车只能沿网格边行驶，装满油后能行驶K 条网格边。出发时汽车已装满油，在
起点与终点处不设油库。
（2）当汽车行驶经过一条网格边时，若其X 坐标或Y 坐标减小，则应付费用B，否则
免付费用。
（3）汽车在行驶过程中遇油库则应加满油并付加油费用A。
（4）在需要时可在网格点处增设油库，并付增设油库费用C（不含加油费用A）。
（5）(1)～(4)中的各数N、K、A、B、C均为正整数。
&laquo;编程任务：
求汽车从起点出发到达终点的一条所付费用最少的行驶路线。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第一行是N，K，A，B，C的值，2 &pound; N &pound; 100，
2 <= K <= 10。第二行起是一个N*N 的0-1方阵，每行N 个值，至N+1行结束。方阵的第i
行第j 列处的值为1 表示在网格交叉点（i，j）处设置了一个油库，为0 时表示未设油库。
各行相邻的2 个数以空格分隔。
&laquo;结果输出:
程序运行结束时，将找到的最优行驶路线所需的费用，即最小费用输出到文件output.txt
中。文件的第1 行中的数是最小费用值。
输入文件示例 输出文件示例
input.txt 
9 3 2 3 6
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 1 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 1
1 0 0 1 0 0 1 0 0
0 1 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0 1
1 0 0 1 0 0 0 1 0
0 1 0 0 0 0 0 0 0

output.txt

12

=========================================================

算法实现题3-10 最小m段和问题
&laquo;问题描述：
给定n 个整数组成的序列，现在要求将序列分割为m 段，每段子序列中的数在原序列
中连续排列。如何分割才能使这m段子序列的和的最大值达到最小？
&laquo;编程任务：
给定n 个整数组成的序列,编程计算该序列的最优m 段分割，使m 段子序列的和的最大
值达到最小。
&laquo;数据输入：
由文件input.txt提供输入数据。文件的第1行中有2个正整数n和m。正整数n是序列
的长度；正整数m是分割的断数。
接下来的一行中有n个整数。
&laquo;结果输出:
程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是计算出
的m段子序列的和的最大值的最小值。
输入文件示例 输出文件示例
input.txt 
1 1
10

output.txt

10

==================================================================