杰拉斯的博客
[ACM实验八]ACM程序设计基础(6)
杰拉斯 | 时间:2012-06-03, Sun | 19,637 views编程算法
实验项目:ACM程序设计基础(6)
实验目的:掌握C++程序设计基础。
实验要求:使用VC++6.0实现实验要求。
实验内容:
1.猜牌游戏问题,请看简单回溯——猜牌游戏(提示:可以参考实验六的最后一题Crashing Balloon)。
2. 给定n个作业的集合Jn,每一个作业Ji都有两项任务分别在2台机器上完成。每个作业必须先由机器1处理,然后再由机器2处理。求所有作业在机器2上完成处理的时间和最少,并输出最佳调度方案。如:
机器1 | 机器2 | |
作业1 | 2 | 1 |
作业2 | 3 | 1 |
作业3 | 2 | 3 |
最佳调度方案为:1 3 2,其完成时间为18。
3. 电路布线问题,请看简单动态规划——电路布线。
[ACM实验七]ACM程序设计基础(5)
杰拉斯 | 时间:2012-05-24, Thu | 6,139 views编程算法
]实验项目: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实验六]ACM程序设计基础(4)
杰拉斯 | 时间:2012-05-22, Tue | 16,647 views编程算法
实验项目:ACM程序设计基础(4)
实验目的:掌握C++程序设计基础。
实验要求:使用VC++6.0实现实验要求。
实验内容:
1.设有n个活动的集合E={1,2,…n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间Si和一个结束时间Fi,且Si<Fi,求出最多可以安排多少个活动使用该资源,并给出一个安排方案,如:
i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
Si | 12 | 5 | 0 | 3 | 8 | 5 | 2 | 8 | 3 | 6 | 1 |
Fi | 14 | 7 | 6 | 5 | 12 | 9 | 13 | 11 | 8 | 10 | 4 |
最多安排的资源个数为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实验五]ACM程序设计基础(3)
杰拉斯 | 时间:2012-05-09, Wed | 8,724 views编程算法
实验项目: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实验四]ACM程序设计基础(2)
杰拉斯 | 时间:2012-04-12, Thu | 20,264 views编程算法
实验项目: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