实验一全排列和会场安排问题
一、实验要求
1.全排列：要求键盘输入若干个不同的字符，然后产生并显示所有的排列
会场安排问题：
1.要求按贪心法求解问题；
2.要求读文本文件输入活动安排时间区间数据（数据在文件中的格式如下）；
3.不能改变活动的编号，排序时不能移动活动的所有信息；
4.按选择顺序显示活动的编号、开始时间和结束时间。

输入数据的文本文件格式：第1行为活动个数，第2行开始每行一个活动，每个活动的数据有活动编号、开始时间、结束时间，用空格隔开。

如：data.txt
18
1 6 9
2 2 7
┋有18行
┋
2.18 3 5
二、实验平台
1、编程环境：Microsoft Visual Studio 2010
2、运行环境：windows7
三、核心代码
全排列：
#include<tchar.h>
#include"iostream"
using namespace std;
void Permutation(char* letter, int* record, int length, int n)
{
if ( n == length )
{
static int count = 0;
count++;
cout << count << "->:\t ";
for ( int i = 0; i < length; i++ )
{
cout << letter[record[i]];
}
cout << endl;
return;
}
for ( int i = 0; i < length; i++ )
{
//确ā?定¨当獭?前°结á点?的?字?符?是?什?么′，?不?能ü和í已?经-确ā?定¨的?字?符?相à同?
int j;
for ( j = 0; j < n; j++ )
{
if ( i==record[j] )
break;
}
if ( j != n )
continue;
//确ā?定¨当獭?前°字?符?
if ( j == n )
record[n] = i;
Permutation(letter,record,length,n+1);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
char* letter = "abcd";
int length = strlen(letter);
int* record = new int[length];
Permutation(letter,record,length,0);
system("pause");
return 0;
}
会场安排问题（贪心算法）：
#include<iostream>
#include<fstream>
using namespace std;
#define N 50
#define TURE 1
#define FALSE 0
int Partition(int *b,int *a,int p,int r);
void QuickSort(int *b,int *a,int p,int r);
int A[N];
void GreedySelector(int n,int start[],int end[],int *A)
{
A[1]=true;
int j=1;
for(int i=2;i<=n;i++)
{
if(start[i]>=end[j])
{
A[i]=true;
j=i;
}
else A[i]=false;
}
}
//快ì速ù排?序î
void QuickSort(int *b,int *a,int p,int r)
{
int q;
if(p<r)
{
q=Partition(b,a,p,r);
QuickSort(b,a,p,q-1);/*对?左哩?半?段?排?序î*/
QuickSort(b,a,q+1,r);/*对??半?段?排?序î*/ }
}
//中D间?数簓
int Partition(int *b,int *a,int p,int r)
{
int k,m,y,i=p,j=r+1;
int x=a[p];y=b[p];
while(1) {
while(a[++i]<x);
while(a[--j]>x);
if(i>=j) break;
else {
k=a[i];
a[i]=a[j];
a[j]=k;
m=b[i];
b[i]=b[j];
b[j]=m;
}
}
a[p]=a[j];
b[p]=b[j];
a[j]=x;
b[j]=y;
return j;
}
int main()
{
fstream fin;
fin.open("input.txt",ios::in);
cout<<"在input.txt文件中输入数据，数据格式为：第1行为活动个数，第2行开始每行一个活动，每个活动的数据有活动编号，开始时间，结束时间，用空格隔开\n如：\n18\n1 6 9\n2 2 7\n.\n.\n.\n18 3 5\n\n";
if(fin.fail())
{
cout<<"文件不存在!"<<endl;
cout<<"退出程序..."<<endl;
return 0;
}
int n;
fin>>n;
int *a=new int[n];
int *b=new int[n];
int *c=new int[n];
for(int i=0;i<=n;i++)
{
fin>>a[i];
fin>>b[i];
fin>>c[i];
}
QuickSort(b,c,1,n);//按恪?结á束?时骸?间?非?减?序î排?
printf(":\n"); /*输?出?排?序î结á果?*/
printf("\n 序号\t开始时间结束时间\n");
printf("-------------------------\n");
for(int i=2;i<=n;i++)
printf(" %d\t %d\t %d\n",i,b[i],c[i]);
printf("-------------------------\n");
GreedySelector(n,b,c,A);
printf("安排的活动序号依次为：");
for(int i=2;i<=n;i++)
{
if(A[i]) printf("\n%d %d-->%d",i,b[i],c[i]);
}
printf("\n");
//int mm=Greedyplan(n,b,c,A);
//fstream fout;
//fout.open("output.txt",ios::out);
//fout<<mm;
//cout<<"答鋏案?请?打洙?开aoutput.txt查é看′\n\n";
fin.close();
//fout.close();
system("pause");
return 0;
}
四、实验结果截图
1.全排列：
2.会场安排问题：
实验者姓名：实验报告日期：2015年1月1日。