[ACM实验六]ACM程序设计基础(4)

蓝飞 蓝飞 | 时间:2012-05-22, Tue | 8,559 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

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

这道题明显用贪心算法,每次只要先举办最早结束的活动,就能挤出更多的时间来进行其它活动,即按结束时间排序,取第一个活动,然后每次去开始时间大于等于上一个结束时间的活动,每取一个活动计数器加一,最终得出的便是题目所求答案。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct T{
	int i;
	int s;
	int f;
	bool operator <(const T t){
		return f < t.f;
	}
};

int main(){
	T t;
	int n, i, num = 0, endtime = 0;
	vector<T> v;
	scanf("%d", &n);
	for(i = 0; i < n; ++i){
		int s, f;
		scanf("%d%d", &s, &f);
		t.i = i + 1;
		t.s = s;
		t.f = f;
		v.push_back(t);
	}
	sort(v.begin(), v.end());
	for(i = 0; i < n; ++i){
		if(v[i].s >= endtime){
			++num;
			endtime = v[i].f;
			printf("%d ", v[i].i);
		}
		//printf("%d %d %d\n", v[i].i, v[i].s, v[i].e);
	}
	printf("(%d)\n", num);
	return 0;
}

2.用KMP算法实现实验,输入两个只包含小写字母的字符串,判断第二个字符串是否是第一个字符串的子串,是则输出第二字符串在第一个字符串的起始位置,不是则输出NO。

KMP算法等有空另开一文详细研究下,最近很多要操心的事,暂时先不讲思路了。。

#include<iostream>
#include<string>
using namespace std;

int getIndex(string str, string sub){
	int i = 1, j = 0, next[100];
	next[1] = 0;
	str = " " + str;
	sub = " " + sub;
	while(i < sub.length()){
		if(j == 0 || sub[i] == sub[j]){
			++i;
			++j;
			next[i] = j;
		}else{
			j = next[j];
		}
	}
	i = 1;j = 1;
	while(i < str.length()){
		if(j == 0 || str[i] == sub[j]){
			++i;
			++j;
		}else{
			j = next[j];
		}
		if(j >= sub.length())
			return i - sub.length() + 1;
	}
	return -1;
	cout << str << endl;
	cout << sub << endl;
	cout << " ";
	for(i = 1; i < sub.length(); ++i){
		cout << next[i];
	}
	cout << endl;
}

int main(){
	string str = "abedsadfdseg", sub = "dsa";
	cout << getIndex(str, sub) << endl;
	return 0;
}

3. Crashing Balloon问题,详见Crashing Balloon

如需转载请注明出处:蓝飞技术部落格

当前暂无评论 »