算法设计基础
一、实验目的：
理解蛮力法的思想及程序的执行过程；
理解递推算法的思想；
能较熟练地编写枚举、递推程序，对给定的问题能设计出相应算法予以解决。
二、实验环境：
Visual C++ 实验环境下实现并进行调试
三、实验内容：
- 编程求和：s=a+aa+aaa+aaaa+ „„+aaaa„aaa(n个)，其中a为1～9中的一个数字。 提示：若第一项为a , 以后每一项由前一项乘以10加上a递推得到，然后求和。
代码：
#include<stdio.h>
int main()
{
int a,n;
int s=0;
int t=0;
printf("输入a n\n");
scanf("%d%d",&a,&n);
printf("输出：\n");
for(int i=0; i<n; i++)
{
t=t*10+a;
s=s+t;
if(i==n-1)
{
printf("%d=",t);
}
else
{
printf("%d+",t);
}
}
printf("%d\n",s);
return 0;
}运行结果：
- 编写程序求500 以内的勾股弦数，即满足 c2=b2+a2的3个数，要求b>a。将所有符合要求的组合存入文本文件中 ，每个组合占一行。
代码：
#include<stdio.h>
int main()
{
int a,b,c;
for(a=1;a<500;a++)
{
for(b=a+1;b<500;b++)
{
for(c=b+1;c<500;c++)
{
if(c*c==a*a+b*b)
{
printf("%d %d %d",a,b,c);
printf("\n");
}
if(c*c-a*a-b*b>0)
break;
}
}
}
return 0;
}运行结果：
- 最近点对问题：求解平面点集n个点中距离最近的两个点之间的问题。（这里用蛮力法）。
代码：
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
double ClosestPoints(int P[][2],int n,int ind1, int ind2);
int main()
{
int n=0;
srand(time(0));
while(n<=1)
{
n=rand()%10;
}
int p[100][2];
printf("随机生成的%d个点为:\n",n+1);
for(int i=0;i<=n;i++)
{
p[i][0]=rand()%10;
p[i][1]=rand()%10;
printf("p%d(%d,%d)\n",i,p[i][0],p[i][1]);
}
double distance=ClosestPoints(p,n,0,0);
distance=sqrt(distance);
printf("最近距离为:%lf\n",distance);
return 0;
}
double ClosestPoints(int P[][2],int n,int ind1, int ind2)
{
double mind=999999;
double dis=0;
for(int i=0; i<=n-2; i++)
{
for(int j=i+1; j<=n-1; j++)
{
dis = (P[j][0]-P[i][0])*(P[j][0]-P[i][0])+(P[j][1]-P[i][1])*(P[j][1]-P[i][1]);
if(dis<mind)
{
mind = dis;
ind1 = i;
ind2 = j;
}
}
}
printf("距离最近的两个点为：p%d(%d,%d)",ind1,P[ind1][0],P[ind1][1]);
printf(",p%d(%d,%d)\n",ind2,P[ind2][0],P[ind2][1]);
return(mind);
}运行结果：
4. 编程实现排序问题中的两个排序算法（选择排序，冒泡排序），要求用函数实现排序算法，主函数中调用。待排序数据用随机数产生（这个过程建议也用一个函数实现。）
代码：
//选择排序
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<string.h>
void SelectionSort(int n,int A[]);
void Getrandom(int n,int a[]);
void swap(int *x,int *y);
int main()
{
int array[100];
int n;
printf("输入要生成的随机数列的数的个数：");
scanf("%d",&n);
printf("生成的随机数列为：");
Getrandom(n,array);
printf("\n");
SelectionSort(n,array);
printf("排序后的数列为：");
for(int i=0;i<n;i++)
{
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
void SelectionSort(int n,int A[])
{
int min;
for(int i=0; i<=n-2;i++)
{
min=i;
for(int j=i+1; j<=n-1;j++)
{
if(A[j]<A[min])
{
min=j;
}
}
swap(&A[i],&A[min]);
}
}
void Getrandom(int n,int a[])
{
srand(time(0));
for(int i=0;i<n;i++)
{
a[i]=rand()%100;
printf("%d ",a[i]);
}
}
void swap(int *x,int *y)
{
int t;
t=*x;
*x=*y;
*y=t;
}运行结果：
//冒泡排序
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<string.h>
void Getrandom(int n,int a[]);
void BubbleSort(int n,int A[]);
void swap(int *x,int *y);
int main()
{
int array[100];
int n;
printf("输入要生成的随机数列的数的个数：");
scanf("%d",&n);
printf("生成的随机数列为：");
Getrandom(n,array);
printf("\n");
BubbleSort(n,array);
printf("排序后的数列为：");
for(int i=0;i<n;i++)
{
printf("%d ", array[i]);
}
printf("\n");
return 0;
}
void BubbleSort(int n,int A[])
{
for(int i=0;i<=n-2;i++)
{
for(int j=0;j<=n-2;j++)
{
if(A[j+1]<A[j])
{
swap(&A[j],&A[j+1]);
}
}
}
}
void Getrandom(int n,int a[])
{
srand(time(0));
for(int i=0;i<n;i++)
{
a[i]=rand()%100;
printf("%d ",a[i]);
}
}
void swap(int *x,int *y)
{
int t;
t=*x;
*x=*y;
*y=t;
}运行结果：
