杰拉斯的博客

实验项目：ACM程序设计基础(6)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1．猜牌游戏问题，请看简单回溯——猜牌游戏（提示：可以参考实验六的最后一题Crashing Balloon）。
2. 给定n个作业的集合Jn，每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先由机器1处理，然后再由机器2处理。求所有作业在机器2上完成处理的时间和最少，并输出最佳调度方案。如：

最佳调度方案为：1 3 2，其完成时间为18。
3. 电路布线问题，请看简单动态规划——电路布线。

(阅读全文…)

]实验项目：ACM程序设计基础(5)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.编写一个函数实现如下功能：
输入：7
输出：

   1   8  14  19  23  26  28
       2   9  15  20  24  27
           3  10  16  21  25
               4  11  17  22
                   5  12  18
                       6  13
                           7

输入：5
输出：

   1   6  10  13  15
       2   7  11  14
           3   8  12
               4   9
                   5

(提示：使用setw（int n）函数对齐，该函数在iomanip.h中，动态二维数组的程序如下：

int **a = new int*[n];	//n行
for(int i = 0; i < n; ++i)
	a[i] = new int[m];	//m列

2.由1..9这九个数字组成九位数（无重复数字）能被11整除，求最大、最小者。
3.附加题：
给定n个矩阵A1A2…An， 其中Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A1A2..An，如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
例如A1=30×35、A2=35×15、A3=15×5、A4=5×10、A5=10×20、A6=20×25
最小乘数为15125。

(阅读全文…)

实验项目：ACM程序设计基础(4)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.设有n个活动的集合E={1,2,…n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi，且Si<Fi，求出最多可以安排多少个活动使用该资源，并给出一个安排方案，如：

最多安排的资源个数为4，安排方案为：11 2 8 1
Sample Input
11 12 14 5 7 0 6 3 5 8 12 5 9 2 13 8 11 3 8 6 10 1 4
Sample Output
11 2 8 1 (4)
2.用KMP算法实现实验，输入两个只包含小写字母的字符串，判断第二个字符串是否是第一个字符串的子串，是则输出第二字符串在第一个字符串的起始位置，不是则输出NO。例如：
输入：abedsadfdseg
dsa
输出：4
3. Crashing Balloon问题，见Crashing Balloon。

(阅读全文…)

实验项目：ACM程序设计基础(3)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.为了对信件保密，需要对信件进行加密，加密方法是每个字母加5，如A写成F，B写成G。输入一行加密的英文句子，输出其解密英文句子，例如：
输入：NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
输出：IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
（提示：getline 是一个函数，它可以接受用户的输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下：
istream& getline(char line[], int size, char endchar = '\n');
char line[]： 就是一个字符数组，用户输入的内容将存入在该数组内。
int size : 最多接受几个字符？用户超过size的输入都将不被接受。
char endchar :当用户输入endchar指定的字符时，自动结束。默认是回车符。
例如用string buf;来保存：getline( cin , buf ); 如果用char buf[ 255 ]; 来保存：cin.getline( buf, 255 )。）

2. 某售货员要到若干城市去推销商品，一直各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。

3. Anagrams by Stack问题，见Anagrams by Stack。

(阅读全文…)

实验项目：ACM程序设计基础(2)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.上地理课时，四个学生回答我国四大淡水湖的大小时说：

• 甲：洞庭湖最大，洪泽湖最小，鄱阳湖第三。{1, 4, 3, 2}
• 乙：洪泽湖最大，洞庭湖最小，鄱阳湖第二，太湖第三。{2, 3, 4, 1}
• 丙：鄱阳湖最小，洞庭湖第三。{0, 0, 1, 3}
• 丁：鄱阳湖最大，太湖最小，洪泽湖第二，洞庭湖第三。{3, 2, 1, 4}

对于每个湖的大小，每人仅答对了一个。请判断四个湖的大小。请用递归算法编写程序实现。

2.以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论，如果有通道，请输出最短路径的通道。例如：

9 8
1 1 9 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 0 0 1
1 1 0 0 0 0 0 0

(阅读全文…)