动态规划 练习题

一：选择题：

1.It suddenly snowed while Mary ____for the bus.

A.waited B.waits C.was waiting D.was waited

2.A big power station______in my home town now.

A.has been built B.is being built C.has built D. is building

3.Stamps______by people for sending letters.

A. use B. using ed D. are used.

4.Must old people_____to politely?

A. speak B. spoken C. be spoke D. be spoken

5.Bike mustn’t _____everywhere.

A. be up B. be put C. put C. putting

6.The woman fell off the bike and ____on the road.

A. lay B. was lain C. lied D. has lain

7.The old man and the children_____in our country.

A.must take good care B.must be take good care of

C. must take good care of D. must be taken good care of

8.Granny Wang told the little children that the sun___

From the east.

A. has risen B. rise C. rises D. is risen

动态规划练习题

USACO 2.2 Subset Sums

题目如下：

对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。

举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：

and {1,2}

这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）

如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:

{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}

{2,5,7} and {1,3,4,6}

{3,4,7} and {1,2,5,6}

{1,2,4,7} and {3,5,6}

给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。

PROGRAM NAME: subset

INPUT FORMAT

输入文件只有一行，且只有一个整数N

SAMPLE INPUT (file subset.in)

7

OUTPUT FORMAT

输出划分方案总数，如果不存在则输出0。

SAMPLE OUTPUT (file subset.out)

4

参考程序如下：

#include

using namespace std;

const unsigned int MAX_SUM = 1024;

int n;

unsigned long long int dyn[MAX_SUM];

ifstream fin ("subset.in");

ofstream fout ("subset.out");

int main() {

fin >> n;

fin.close();

int s = n*(n+1);

动态规划

动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。

动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。由于它所具有独特的解题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。

第 一 节 动态规划的基本方法

多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。

例1：最短路线问题

某工厂需要把一批货物从城市A运到城市E，中间可经过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？

6

3

8 4 5

5 6

4

9 8

NOI练习题

一、基础算法

1.1 递归算法

1. 请编写一个C++函数，实现求斐波那契数列的第n项。

2. 编写一个C++函数，实现计算阶乘n!。

1.2 循环算法

3. 编写一个C++程序，实现输出1到100之间所有偶数。

4. 编写一个C++程序，计算1到100之间所有奇数的和。

1.3 排序算法

5. 编写一个C++程序，使用冒泡排序算法对数组进行从小到大排序。

6. 编写一个C++程序，使用快速排序算法对数组进行从小到大排序。

二、数据结构

2.1 线性表

7. 编写一个C++程序，实现单链表的创建、插入、删除和查找操作。

8. 编写一个C++程序，实现顺序表的创建、插入、删除和查找操作。

2.2 栈和队列

9. 编写一个C++程序，实现栈的基本操作：入栈、出栈、查看栈顶元素。 10. 编写一个C++程序，实现队列的基本操作：入队、出队、查看队首元素。

2.3 树和图

11. 编写一个C++程序，实现二叉树的创建、遍历（前序、中序、后序）。

12. 编写一个C++程序，实现图的邻接矩阵表示和邻接表表示。

三、数学问题

3.1 素数问题

13. 编写一个C++程序，判断一个整数是否为素数。

14. 编写一个C++程序，输出1到100之间的所有素数。

3.2 最大公约数和最小公倍数

15. 编写一个C++程序，计算两个整数的最大公约数。

16. 编写一个C++程序，计算两个整数的最小公倍数。

四、搜索算法

4.1 暴力搜索

17. 编写一个C++程序，实现全排列算法。

18. 编写一个C++程序，实现组合算法。

4.2 深度优先搜索

19. 编写一个C++程序，使用深度优先搜索解决迷宫问题。

20. 编写一个C++程序，使用深度优先搜索求解N皇后问题。

五、动态规划

5.1 斐波那契数列

21. 编写一个C++程序，使用动态规划求解斐波那契数列的第n项。

5.2 最长公共子序列 22. 编写一个C++程序，使用动态规划求解两个字符串的最长公共子序列。