[ACM实验六]ACM程序设计基础(4)
杰拉斯 | 时间:2012-05-22, Tue | 16,600 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。
如需转载请注明出处:杰拉斯的博客
当前暂无评论 »