您的位置: 首页  >  文章  >  实验一 算法设计基础

实验一 算法设计基础

分类: 文章 • 2025-02-24 15:51:53

1．分别用穷举法和欧几里德算法实现求两个整数的最大公约数，并比较算法的效率。
穷举法：
#include <stdio.h>
int divisor (int a,int b)
{
int temp;
temp=(a>b)?b:a;
while(temp>0)
{
if (a%temp0&&b%temp0)
break;
temp–;
}
return (temp);
}
int main()
{
int m,n,t1;
printf(“输入两个数:”);
scanf("%d%d",&m,&n);
t1=divisor(m,n);
printf(“这两个数的最大公约数是%d\n”,t1);
return 0;
}
欧几里德算法：
#include <stdio.h>
int divisor (int a,int b)
{
int temp;
if(a<b)
{
temp=a;
a=b;
b=temp;
}
while(b!=0)
{
temp=a%b;
a=b;
b=temp;
}
return (a);
}
int main()
{
int m,n,t1;
printf(“输入两个数:”);
scanf("%d%d",&m,&n);
t1=divisor(m,n);
printf(“这两个数的最大公约数是%d\n”,t1);
return 0;
}

穷举法：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。
时间复杂度为O=n/2。
欧几里得算法：设两数为a,b设其中a 做被除数,b做除数，temp为余数
（1）大数放a中、小数放b中；
（2）求a/b的余数；
（3）若temp=0则b为最大公约数；
（4）如果temp!=0则把b的值给a、temp的值给a；
（5）返回第二步。
时间复杂度为 O(log(n))。

2．排序算法效率比较。编程实现以下几种不同的排序算法（以升序为例）：冒泡排序、选择排序、 希尔排序、快速排序，比较不同的排序过程的运行时间。
具体要求：
（1）为了消除数据之间差异导致排序效果的影响，使用相同的数组进行排序，方法为：首先创建一个数组，数组长度至少为100000，数组元素取值范围在[0, 100000]之间的随机正整数，并将这个数组复制4份，分别用不同的排序算法进行排序。
（2）记录不同排序算法的运行时间。
（3）对完全逆序的情况进行测试，将待排序数组赋值为逆序，即与最终排序要求完全相反。
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>
#define MAX 100000
//快速排序
void swap(int &x,int &y)
{
int z;
z=x;
x=y;
y=z;
}
int median3(int a[],int left,int right)
{
int center=(left+right)/2;
if(a[left]>a[center])
swap(a[left],a[center]);
if(a[left]>a[right])
swap(a[left],a[right]);
if(a[center]>a[right])
swap(a[center],a[right]);
swap(a[center],a[right-1]);
return a[right-1];
}
void insertionsort(int a[],int n)
{
int j,p;
int tmp;
for(p=1;p<=n;p++)
{
tmp=a[p];
for(j=p;j>0&&a[j-1]>tmp;j–)
a[j]=a[j-1];
a[j]=tmp;
}
}
void qsort(int a[],int left,int right)
{
int i,j;
int pivot;
if(left+2<=right)
{
pivot=median3(a,left,right);
i=left;j=right-1;
for(;;）
{
while(a[++i]<pivot){}
while(a[–j]>pivot){}
if(i<j)
swap(a[i],a[j]);
else
break;
}
swap(a[i],a[right-1]);
qsort(a,left,i-1);
qsort(a,i+1,right);
}
else
insertionsort(a+left,right-left+1);
}
void quicksort(int a[],int n)
{
qsort(a,0,n-1);
}
//冒泡排序
void BubbleSort(int r[],int length)
{
int i,j,temp;
for(j=length;j>0;j–)
for(i=0;i<j-1;i++)
if(r[i]>r[i+1])
{
temp=r[i];
r[i]=r[i+1];
r[i+1]=temp;
}
}
//希尔排序
void ShellInsert(int r[],int length,int delta)
{
int i,j;
for(i=1+delta;i<=length;i++)
if(r[i]<r[i-delta])
{
r[0]=r[i];
for(j=i-delta;j>0&&r[0]<r[j];j-=delta)
r[j+delta]=r[j];
r[j+delta]=r[0];
}
}
void ShellSort(int r[], int length, int delt[], int n)
{
int i;
for(i=0;i<=n-1;++i)
ShellInsert(r,length,delt[i]);
}
//选择排序
void SelectSort(int r[],int length)
{
int i,j,k;
int n;
int x;
n=length;
for (i=1;i<=n-1;++i)
{
k=i;
for(j=i+1;j<=n;++j)
if(r[j]<r[k])
k=j;
if( k!=i)
{
x= r[i];
r[i]=r[k];
r[k]=x;
}
}

}
void main()
{
long dwStart,dwStop,runtime;
int num[MAX],a[MAX],i,j;
dwStart=GetTickCount();
srand((unsigned)time(NULL));
for(i=0;i<MAX;i++)
num[i]=rand();
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“生成%d个随机数运行了%ldms\n\n”,MAX,runtime);
printf(“平均排序时间\n”);
for(i=0;i<MAX;i++)
a[i]=num[i];
dwStart=GetTickCount();
quicksort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“快速排序运行了%ldms\n”,runtime);
for(i=0;i<MAX;i++)
a[i]=num[i];
dwStart=GetTickCount();
BubbleSort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“冒泡排序运行了%ldms\n”,runtime);
int delt[10]={100,80,60,40,20,10,5,3,2,1};
for(i=0;i<MAX;i++)
a[i]=num[i];
dwStart=GetTickCount();
ShellSort(a,MAX,delt,10);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“希尔排序运行了%ldms\n”,runtime);
for(i=0;i<MAX;i++)
a[i]=num[i];
dwStart=GetTickCount();
SelectSort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“选择排序运行了%ldms\n”,runtime);
printf("\n最好情况排序时间\n");
for(i=0;i<MAX;i++)
a[i]=i;
dwStart=GetTickCount();
quicksort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“快速排序运行了%ldms\n”,runtime);
for(i=0;i<MAX;i++)
a[i]=i;
dwStart=GetTickCount();
BubbleSort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“冒泡排序运行了%ldms\n”,runtime);
for(i=0;i<MAX;i++)
a[i]=i;
dwStart=GetTickCount();
ShellSort(a,MAX,delt,10);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“希尔排序运行了%ldms\n”,runtime);
for(i=0;i<MAX;i++)
a[i]=i;
dwStart=GetTickCount();
SelectSort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“选择排序运行了%ldms\n”,runtime);
printf("\n最坏情况，逆序，即与最终排序要求完全相反排序时间\n");
for(i=MAX-1,j=0;i<=0,j<MAX;i–,j++)
a[j]=i;
dwStart=GetTickCount();
quicksort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“快速排序运行了%ldms\n”,runtime);
for(i=MAX-1,j=0;i<=0,j<MAX;i–,j++)
a[j]=i;
dwStart=GetTickCount();
BubbleSort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“冒泡排序运行了%ldms\n”,runtime);
for(i=MAX-1,j=0;i<=0,j<MAX;i–,j++)
a[j]=i;
dwStart=GetTickCount();
ShellSort(a,MAX,delt,10);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“希尔排序运行了%ldms\n”,runtime);
for(i=MAX-1,j=0;i<=0,j<MAX;i–,j++)
a[j]=i;
dwStart=GetTickCount();
SelectSort(a,MAX);
dwStop=GetTickCount();
runtime=dwStop-dwStart;
printf(“选择排序运行了%ldms\n”,runtime);
}
实验一 算法设计基础

时间复杂度比较：
最差情况时间复杂度分析：快速排序O(n2)、冒泡排序O(n2)、选择排序O(n2)、希尔排序O(n1.3)
平均时间复杂度比较：快速排序O(n*log2n)、冒泡排序O(n2)、选择排序O(n2)、希尔排序O(n)
空间复杂度比较：快速排序O(log2n)~O(n) 、冒泡排序O(1)、选择排序O(1)、希尔排序O(1)
稳定性比较：快速排序不稳定 、冒泡排序稳定、选择排序稳定、希尔排序不稳定

相关推荐