杰拉斯的博客

标签:ACM实验

[ACM实验八]ACM程序设计基础(6)

杰拉斯 杰拉斯 | 时间:2012-06-03, Sun | 19,121 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 | 5,743 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,248 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,248 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 | 19,734 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

(阅读全文…)