《算法设计与分析》实验教学大纲实验学时：32 实验个数：7 实验学分：1课程性质：适用专业：计算机科学与技术、软件工程教材及参考书：1.《计算机算法设计与分析》，王晓东，北京：电子工业出版社，2005年2.《算法与数据结构》，傅清祥等著，北京：电子工业出版社，20033.《计算机算法导引—设计与分析》，卢开澄著，北京：清华大学出版社，2001 大纲执笔人：刘芳大纲审定人：郭涛一、实验课的性质与任务算法的设计与分析是计算机科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课，其内容是研究计算机领域及其有关领域中的一些非数值计算的常用算法。
课程将覆盖计算机软件实现中常用的、有代表性的算法，并具有一定的深度和广度，通过实验，使学生理解并掌握算法设计的基本技术，让学生具有针对所给的问题设计和实现高效算法的基本能力。
二、实验课程目的与要求计算机科学的一个核心问题是算法理论，本课程介绍非数值算法设计的策略与技术，同时介绍算法的复杂性的概念通过对一些代表性算法的使用达到了解掌握与运用的目的。
通过完成课程实验，使学生达到如下要求：1.熟悉各种基本常用算法的基本思想、适用范围，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。
2.能对给定问题分析出恰当的数学模型，并设计出解决方案，将算法用高级语言（C，VC++等）编程实现。
三、实验内容安排：实验一算法设计基础（验证型、设计型实验4学时）1.实验目的（1）巩固程序设计语言基础知识，熟悉文件操作等。
（2）对给定问题，能设计算法并编程实现问题的求解，并分析算法的时间复杂性。
2.实验要求（1）认真填写实验报告，附加源代码（主要代码）和运行记录；（2）对设计好的算法，测试运行实验数据，检查输出是否正确。
并对算法的时间和空间复杂度进行分析。
3.实验内容：（1）统计数字问题（P8）#include "stdafx.h"#include <iostream>#include <conio.h>#include <string>using namespace std;void read_information(string &Data){//从文件中读出停车场信息，并且存放在数组中cout<<"正在读取数据......"<<endl;FILE *fp;char ch;if((fp=fopen("data.txt","rt+"))==NULL){printf("\nCannot open file strike any key exit!");getch();exit(1);}ch=fgetc(fp);while(ch!=EOF){Data = Data + ch;ch=fgetc(fp);}fclose(fp);cout<<"读取完成......"<<endl;}void save_information(string data){//把数组中的停车场信息存放回文件中cout<<"正在写入文件......"<<endl;FILE *fp;//定义文件流指针，用于打开写操作的文件char ch[2]="\0";//定义一个字符串数组，用于存储读取的字符int i=0;fp = fopen("answer.txt","w");//写方式打开文件a.txtwhile(i < data.length())//逐行读取fp1所指向文件中的内容到text中{ch[0] = data[i++];fputs(ch,fp);//将内容写到fp2所指向文件中}fclose(fp);//关闭文件b.txtcout<<"写入完成......"<<endl;}int main(int argc, char* argv[]){int Page;int Num[10] = {0,0,0,0,0,0,0,0,0,0};string Data;int jishu = 0;read_information(Data);Page = atoi(Data.c_str());cout<<"计算中.\n"<<jishu<<"%"<<endl;;for(int i=1; i<=Page; i++){char sz[10];itoa(i, sz, 10);for(int j=0; sz[j]!='\0'; j++){Num[sz[j]-48]++;}if((int)i/Page*100>jishu){jishu = i/Page*100;cout<<jishu<<"%"<<endl;}}cout<<endl;string answer = "";for (i=0; i<10; i++){char tmp[10];char sz[2];itoa(Num[i], tmp, 10);itoa(i, sz, 10);answer = answer + sz[0];answer = answer + ":";for(int j=0; j<10 && tmp[j]!='\0'; j++){answer = answer + tmp[j];}answer = answer + '\n';}save_information(answer);system("pause");return 0;}字典序问题（P8）（2）最多约数问题（P9）#include "stdafx.h"#include <iostream>#include <string>using namespace std;int yueshuNum(int x){int num = 0;for(int i=1; i<=x; i++){if(x%i == 0){num++;}}return num;}void read_information(string &Data){//从文件中读出停车场信息，并且存放在数组中cout<<"正在读取数据......"<<endl;FILE *fp;char ch;if((fp=fopen("data.txt","rt+"))==NULL){printf("\nCannot open file strike any key exit!");exit(1);}ch=fgetc(fp);while(ch!=EOF){Data = Data + ch;ch=fgetc(fp);}fclose(fp);cout<<"读取完成......"<<endl;}void save_information(string data){//把数组中的停车场信息存放回文件中cout<<"正在写入文件......"<<endl;FILE *fp;//定义文件流指针，用于打开写操作的文件char ch[2]="\0";//定义一个字符串数组，用于存储读取的字符int i=0;fp = fopen("answer.txt","w");//写方式打开文件a.txtwhile(i < data.length())//逐行读取fp1所指向文件中的内容到text中{ch[0] = data[i++];fputs(ch,fp);//将内容写到fp2所指向文件中}fclose(fp);//关闭文件b.txtcout<<"写入完成......"<<endl;}int main(int argc, char* argv[]){int start, end;int Num=0, flag = 1;string data;read_information(data);char tmpstart[10];char tmpend[10];for(int j=0; data[j]!='\0';j++){if(data[j] == ' '){flag = j + 1;}else if(flag == 1){tmpstart[j] = data[j];}else{tmpend[j-flag] = data[j];}}start = atoi(tmpstart);end = atoi(tmpend);for(int i=start; i<=end; i++){int num = yueshuNum(i);if(num > Num){Num = num;}}char answerchar[10];string answer = "";itoa(Num, answerchar, 10);for(i=0; i<10 && answerchar[i]!='\0'; i++){answer = answer + answerchar[i];}save_information(answer);return 0;}（3）最大间隙问题（P10）（4）设计算法求解fibonacci数列的第110项的值，并统计和分析算法的时间性能。
![计算机算法设计与分析(第4版)[王晓东][电子教案]第2章](https://img.taocdn.com/s1/m/6ef58047f7ec4afe04a1df38.png)
