算法设计与分析实验报告
算法设计与程序分析
实验报告
姓名：
学号：
班级：
指导老师：
实验1：汉诺塔问题
程序代码：
#include <stdio.h>
//第一个塔为初始塔，中间的塔为借用塔，最后一个塔为目标塔
int i=1;//记录步数
void move(int n,char from,char to) //将编号为n的盘子由from移动到to
{printf("第%d步:将%d号盘子%c---->%c\n",i++,n,from,to);
}
void hanoi(int n,char from,char denpend_on,char to)//将n个盘子由初始塔移动到目标塔(利用借用塔)
{
if (n==1)
move(1,from,to);//只有一个盘子是直接将初塔上的盘子移动到目的地
else
{
hanoi(n-1,from,to,denpend_on);//先将初始塔的前n-1个盘子借助目的塔移动到借用塔上
move(n,from,to); //将剩下的一个盘子移动到目的塔上
hanoi(n-1,denpend_on,from,to);//最后将借用塔上的n-1个盘子移动到目的塔上
}
}
void main()
{
printf("请输入盘子的个数:\n");
int n;
scanf("%d",&n);
char x='A',y='B',z='C';
printf("盘子移动情况如下:\n");
hanoi(n,x,y,z);
}
实验结果：
实验2：杨辉三角：
程序代码：
#include<stdio.h>
void print(int *row,int n)
{
int i;
for(i=1;i<n;i++)
{
if(row[i]!=0)
{
printf("%d",row[i]);
row[i]=0;//置为初始态，方便保存下一行
}
else
printf(" ");
}
printf("\n");
}
void initia(int num)
{
int up_row[20];
int next_row[20];
int i,j;
for(i=0;i<=num*2;i++)
{
up_row[i]=0;
next_row[i]=0;
}
up_row[num]=next_row[num]=1;
for(i=0;i<num;i++)//控制行
{
for(j=1;j<num+i+1;j++)
{
up_row[j]=next_row[j];//保存当前输出行
}
print(next_row,num+i+1);//本行输出的有效数据个数为当前行数
for(j=1;j<=num+i+1;j++)//0号位的值保留以便下行计算
{
next_row[j]=up_row[j-1]+up_row[j+1];//下一行相应位置的值是上一行相应位置左右值的和
}
}
}
int main(void)
{
int num_row;
printf("确定行数(小于10)：");
scanf("%d",&num_row);
initia(num_row);
return 0;
}
实验结果：
方法2：动态规划实现：
程序代码：
#include <stdio.h>
#define MAXH 31
int main(void)
{
unsigned long num[MAXH]={0};
int i,j,k;
int n;
printf("Input a number to set row:");
scanf("%d",&n);
num[0]=1;
i=0;
for(i=0;i<n;i++)
{
for(k=n-i;k>0;k--)
printf(" ");
for(j=i;j>0;j--)
{
num[j] = num[j] + num[j-1];
printf("%d ",num[j]);
}
printf(" %d \n",1);
}
return 0;
}
实验3：背包问题：
程序代码：
#include<stdio.h>
int c[10][100];/*对应每种情况的最大价值*/
int knapsack(int m,int n)
{
int i,j,w[10],p[10];
printf("\n输入每个物品的重量及价值：\n");
for(i=1;i<=n;i++)
scanf("%d,%d",&w[i],&p[i]);
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化数组*/
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
/*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
/*大于上一次选择的最佳方案则更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main()
{
int m,n;
int maxvalue;
printf("输入背包的承重量：");
scanf("%d",&m);
printf("\n输入物品的总个数：");
scanf("%d",&n);
maxvalue = knapsack(m,n);
printf("\n背包能装的最大总价值为%d",maxvalue);
printf("\n");
return 0;
}
实验结果：
实验4：斐波那契数列：
程序代码：
#include<stdio.h>
void main()
{
int Fibonacci(int n);
int n,i;
long int c=0;
printf("求斐波那契数组：\n");
printf(" | 0 n=0\n");
printf("F(n) = { 1 n=1\n");
printf(" | F(n-1)+F(n-2) n>1\n");
printf("请输入n的值:");
scanf("%d",&n);
for(i=1; i<=n; i++)
{
c = Fibonacci(i);
printf("%-10ld",c);
if(i%5==0) //每输出5个换一行；
printf("\n");
}
printf("\n");
}
int Fibonacci(int n)//函数部分；
{
long int fib;
if(n==0)
{
fib=0;
}
else if(n==1 || n==2)
{
fib=1;
}
else if(n>=3)
{
fib = Fibonacci(n-1) + Fibonacci(n-2);
}
return fib;
}
实验结果：
实验5：归并排序
程序代码：
#include <iostream.h>
int *a=new int[20];
int n=0;
//归并排序，排序结果放到了b[]中
void Merge(int a[],int b[],int left ,int mid,int right)//此处的right指向数组中左后一个元素的位置
{
int i=left;
int j=mid+1;
int k=left;
while(i<=mid&&j<=right)
{
if(a[i]<=a[j])b[k++]=a[i++];
else b[k++]=a[j++];
}
while(i<=mid)b[k++]=a[i++];
while(j<=right)b[k++]=a[j++];
}//从b[]中又搬到了a[]中
void Copy(int a[],int b[],int left,int right)//right同上
{
for(int i=left;i<=right;i++)
a[i]=b[i];
}//划分并排序
void MergeSort(int a[],int left,int right)//同上
{
int *b = new int[right+1];
if(left<right)
{
//将当前传经来的数组划分成更小的大小几乎相同的数组
int i=(left+right)/2;
MergeSort(a,left,i);
MergeSort(a,i+1,right);
//将小数组合成大数组，同时排序，结果放到b[]中
Merge(a,b,left,i,right);
//从b[]中挪到a[]中
Copy(a,b,left,right);
}
}void Input()
{
cout<<"Please Input array's size:";
cin>>n;
cout<<"Array's elemants:"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
//调用算法
MergeSort(a,0,n-1);
}void Output()
{
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}void main()
{
Input();
Output();
}
实验结果：
实验6:二分查找：
程序代码：
#include <stdio.h>
int search ( int a[],int s,int r,int key )
{
int low=s,high=r,mid;
if ( s<=r )
{
mid=(high+low)/2;
if ( a[mid]==key )
return mid;
if ( a[mid]<key )
return search ( a,mid+1,high,key );
if ( a[mid]>key )
return search ( a,low,mid-1,key );
}
else
return -1;
}
int main ()
{
int n,a[10000],key,k,i;
printf("请输入数组大小：\n");
while ( scanf ("%d",&n)!=EOF )
{
for ( i=0;i<n;i++ )
scanf ("%d",&a[i]);
printf("请输入要查找的数：");
scanf ("%d",&key);
k=search(a,0,n-1,key);
if ( k==-1 )
printf("NO\n未找到!\n");
else
{
printf("YES\n");
printf("该数位置在第%d位！\n",k+1);
}
}
return 0;
}
实验结果：
第二篇：算法设计与分析实验报告—01背包问题
算法设计与分析
实验报告
—0/1背包问题
-
【问题描述】
给定n种物品和一个背包。物品i的重量是
，其价值为
，背包容量为C。问应该如何选择装入背包的物品，使得装入背包中物品的总价值最大？
【问题分析】
0/1背包问题的可形式化描述为：给定C>0, 
>0, 
>0,
，要求找出n元0/1向量
，使得
，而且
达到最大。因此0/1背包问题是一个特殊的整数规划问题。
【算法设计】
设0/1背包问题的最优值为m( i, j )，即背包容量是j，可选择物品为i,i+1,…,n时0/1背包问题的最优值。由0/1背包问题的最优子结构性质，可以建立计算m( i, j )的递归式如下：
max{m( i+1, j ), m( i+1, j-)+} 
m( i, j )=
m(i+1,j)
m(n,j)=
0
【算法实现】
#include <iostream.h>
#include<string.h>
#include<iomanip.h>
int min(int w, int c)
{
int temp;
if (w < c) temp = w;
else
temp = c;
return temp;
}
Int max(int w, int c)
{
int temp;
if (w > c) temp = w;
else
temp = c;
return temp;
}
void knapsack(int v[], int w[], int** m, int c, int n) //求最优值
{
int jmax = min(w[n]-1, c);
for (int j = 0; j <= jmax; j++)
m[n][j] = 0;
for (int jj = w[n]; jj <= c; jj++)
m[n][jj] = v[n];
for(int i = n-1; i > 1; i--) //递归部分
{
jmax = min(w[i]-1, c);
for(int j = 0; j <= jmax; j++)
m[i][j] = m[i+1][j];
for(int jj = w[i]; jj <= c; jj++)
m[i][jj] = max(m[i+1][jj], m[i+1][jj-w[i]]+v[i]);
}
m[1][c] = m[2][c];
if(c >= w[1])
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
cout << endl << "最优值：" << m[1][c] << endl;
cout<<endl;
cout<< "&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&" << endl;
}
int traceback(int x[], int w[], int** m, int c, int n) //回代，求最优解
{
out << endl << "得到的一组最优解如下: " << endl;
for(int i = 1; i < n; i++)
{
if(m[i][c] == m[i+1][c]) x[i] = 0;
else
{
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c]) ? 1:0;
for(int y = 1; y <= n; y++)
cout << x[y] << "\t";
cout << endl;
return x[n];
}
void main()
{
int n, c;
int **m;
cout << "&&&&&&&&&&&&&&&&&&&&&欢迎使用0-1背包问题程序&&&&&&&&&&&&&&&&&&&" << endl;
cout << "请输入物品个数: ";
cin >> n ;
cout << endl << "请输入背包的承重：";
cin >> c;
int *v = new int[n+1];
cout << endl << "请输入每个物品的价值 (v[i]): " << endl;
for(int i = 1; i <= n; i++)
cin >> v[i];
int *w = new int[n+1];
cout << endl << "请输入每个物品的重量 (w[i]): " << endl;
for(int j = 1; j <= n; j++)
cin >> w[j];
int *x = new int[n+1];
m = new int* [n+1]; //动态的分配二维数组
for(int p = 0; p < n+1; p++)
m[p] = new int[c+1];
knapsack (v, w, m, c, n);
traceback(x, w, m, c, n);
}
【运行结果】
-
算法设计与分析实验报告
算法设计与分析课程报告课题名称算法设计与分析课题负责人名学号同组成员名单角色指导教师评阅成绩评阅意见提交报告时间20xx年6月12…
-
算法设计与分析实验报告1
攀枝花学院实验报告实验名称算法设计与分析课程实验实验内容比较排序算法的效率实验日期20xx0326院系数学与计算机姓名吴永昊学号2…
-
算法分析与设计实验报告
排序问题求解实验日志实验题目排序问题求解实验目的1以排序分类问题为例掌握分治法的基本设计策略2熟练掌握一般插入排序算法的实现3熟练…
-
算法设计与分析实验报告格式
算法设计与分析实验报告班级姓名学号20xx年11月18日目录实验一二分查找程序实现01页实验二棋盘覆盖问题04页实验三01背包问题…
-
算法设计与分析实验报告
算法分析与设计实验报告实验报告题目实验一递归与分治策略一实验目的1加深学生对分治法算法设计方法的基本思想基本步骤基本方法的理解与掌…
-
算法设计与分析实验报告格式
算法设计与分析实验报告班级姓名学号20xx年11月18日目录实验一二分查找程序实现01页实验二棋盘覆盖问题04页实验三01背包问题…
-
算法设计与分析实验报告
算法分析与设计实验报告实验报告题目实验一递归与分治策略一实验目的1加深学生对分治法算法设计方法的基本思想基本步骤基本方法的理解与掌…
-
算法设计与分析实验报告
算法设计与分析实验报告实验一递归与分治策略应用基础学号姓名班级日期20xx20xx学年第1学期第九周一实验目的1理解递归的概念和分…
-
算法设计与分析实验报告格式
算法设计与分析实验报告一实验名称统计数字问题评分实验日期年月日指导教师刘长松姓名刘飞初专业班级计算机0901学号10一实验要求1掌…
-
算法设计与分析试验报告
武汉理工大学学生实验报告书实验课程名称算法设计与分析开课学院计算机科学与技术学院指导老师姓名何九周学生姓名王鹏学生专业班级软件10…
-
算法实验报告
算法设计与分析实验报告班级姓名学号年月日目录实验一二分查找程序实现03页实验二棋盘覆盖问题分治法08页实验三01背包问题的动态规划…