当前位置：文档之家 › 计算机基础算法实验报告

计算机基础算法实验报告

  • 格式：doc
  • 大小：82.50 KB
  • 文档页数：13

计算机基础算法实验报告班级：08计算机7班学号：0813********姓名：许可完成日期：2009年11月28日实验一：实现两个整数相加1、需求分析：要求用链表(单链表或双向链表)实现任意位数的整数相加(1)输入的形式和输入值的范围：输入任意长度的正整数，回车，再输入任意整数，即可得出结果。

范围是零到正无穷。

(2)输出的形式：以正整数形式输出。

(3)程序所能达到的功能：以链表形式实现任意位数的正整数相加。

(4)测试数据：①正确结果：输入1234567890123456789再输入9876543210987得出结果1234577766666667776.②错误结果：输入-789，再输入78994456 得出789952452、概要设计：(1)抽象数据类型ADT LNode{数据元素：此单向链表中的所有元素类型为字符型的数字字符数据关系：链表中数据元素之间是线性关系。

基本操作：LNode *creat(void)操作结果：创建一个单向链表，并且逆序输入链表元素基本操作：void print(LNode *head)操作结果：输出单向链表基本操作：LNode *Creat(LNode *head1,LNode *head2)操作结果：对两个链表进行相加操作，建立相加后的链表}ADT LNode(2)主程序操作流程：定义三个指针变量head1 head2 head3屏幕输出：Please enter the first number:输入任意位数数字，调用LNode *creat(void)，建立链表head1屏幕输出：Please enter the second number:输入任意位数数字，调用LNode *creat(void)，建立链表head2调用函数Creat(head1,head2)对链表head1,head2进行相加操作，建立新链表head3调用函数print(head3)输出链表head3屏幕输出：The num is:”head3”程序结束(3)调用关系：主函数void main()可调用子函数creat(void)以及子函数Creat(head1,head2)以及子函数print(LNode *head)3、详细设计(1)此算法的基本思想：首先创建逆序链表1，即将输入的数字逆序进入链表，再创建链表2，将输入的数字逆序进入链表。

此时两个链表的头节点的下一个节点均对应为数字的个位数，再对两个链表进行相加操作，分别从两个链表的头节点的下一节点进行两两相加，相加结果临时存入num变量，并且放置整型变量carry储存进位，进行num对10求余，余数存入节点p，carry为整型变量，对carry进行相加结果/10操作，若相加结果小于10，carry=0，若结果大于10，carry=1。

将相加结果存入新链表的头节点的下一节点，循环两个链表，直至两个链表循环结束。

此时新链表即为相加后的链表，理论可以实现任意位数的正整数相加。

(2)调用关系图：4、调试分析(1)测试数据：输入123456789123456789123456789123456789输入：987654321098765432109876543210输出结果：123457776777777887888888898999999999(2)时间复杂度分析：子程序LNode *creat(void)中有while((n=getchar())!='\n')循环语句，语句频度为n子程序void print(LNode *head)中有while(r->next!=NULL)循环语句，语句频度为n子程序LNode *Creat(LNode *head1,LNode *head2)中有while((r!=NULL)&&(s!=NULL))以及while(t!=NULL)两个循环语句，频度均为n所以此程序的时间复杂度为T(n)=O(n)(3)设计和调试时出现的问题：开始的时候编译好程序可以相加，但是只可以是两个数字位数对应且没有进位时结果正确，经检查是创建链表的时候是正序创建，相加是从头节点的下一节点也就是最高位开始相加，所以出现此错误。

后改正为逆序创建链表，测试后结果正确。

(4)算法的改进设想：可以增加分析输入数据正负的函数，并建立相关的负数相加，正负相加，负正相加等函数，实现程序可以进行任意位数的正负数相加的功能。

5、总结(1)实验的收获：通过对实验的思考以及编译过程，我可以对课本所学知识进行熟练运用，包括单链表的建立，正序逆序的分别，单链表的输出，两个单链表的操作，相加以及进位的算法思想的建立以及正确编译。

(2)实验重要性的认识：通过思考以及编译此实验，我认识到链表在程序编译过程中的重要以及便利性，而且通过对单链表的各种建立、输出、操作等过程的实现，进而可以对双链表、循环链表等形式的链表有一定的了解，可以举一反三，获取更多的知识。

实验的实际操作更让我强化了动手动脑能力，以及对程序编译过程中常见的错误的改正能力。

实验2：算术表达式求值1、需求分析：实验要求以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值过程中运算符栈、操作数栈、操作数栈和主要操作的变化过程。

(1) 输入形式和输入值范围：正确输入算术表达式，包括+、-、*、/、(、)等正确的运算符，并且输入完毕后以#结尾。

输入值范围为正负整数，理论可计算100位数字，实际可计算11位数字的+、-、*、/以及（）运算。

(2) 输出形式：计算结果整数六位及六位以内以整型输出，在六位以上以有效数字6位的科学计数法输出。

(3) 程序所能达到的功能：可以计算+、-、*、/以及括号运算，精度达到6位有效数字。

(4) 测试数据：①正确结果：输入1234+(6547-9874)/6321*314# 输出结果1068.73输入(123456789+987654321)*6478# 输出结果1.43956e+012②错误结果：输入214(321-897)(643*64)# 输出结果411522、概要设计(1)抽象数据类型ADT SqStack{数据类型：此链栈中的元素类型为字符型数字字符数据关系：栈中数据元素之间是线性关系。

基本操作：int InitStack(SqStack &S)操作结果：构造一个空栈基本操作：char GetTop(SqStack S,SElemType &e)操作结果：用e返回S的栈顶元素基本操作：int Push(SqStack &S,SElemType e)操作结果：插入元素e为新的栈顶元素基本操作：bool Pop(SqStack &S,SElemType &e)操作结果：删除S的栈顶元素，并用e返回其值}ADT SqStack(2)系统中子程序及功能要求：char Precede(char a,char b)：比较两个运算符的优先级，a是栈顶字符，b是表达式字符。

SElemType Operate(SElemType a,SElemType b,SElemType c)：解析表达式中的双目运算，其返回的结果即为双目运算表达式的值。

int In(char c)：判断输入的字符是否为运算符。

SElemType EvaluateExpression()：这是此程序的核心函数，可以综合其它子函数，实现最终的表达式求解。

(3)主程序的流程：定义SElemType型变量a，屏幕输出：请输入算术表达式（以#结束）:调用SElemType EvaluateExpression()子程序，进行数栈与符栈的初始化以及入栈出栈、调用函数SElemType Operate(SElemType a,SElemType b,SElemType c)进行运算等核心操作，并且将程序返回值赋值给a，屏幕输出：结果是:”a”程序结束(4)调用关系：主函数int main()可调用子程序SElemType EvaluateExpression()，子程序SElemType EvaluateExpression()可调用模块int InitStack(SqStack &S)，模块char GetTop(SqStack S,SElemType &e)，模块int Push(SqStack &S,SElemType e)，模块bool Pop(SqStack &S,SElemType &e)，子程序char Precede(char a,char b)，子程序SElemType Operate(SElemType a,SElemType b,SElemType c)，子程序int In(char c)。

3、详细设计(1)此算法的基本思想：先定义数栈OPND和符栈OPTR，初始化两个栈，把’#’压入符栈底，获取栈顶元素用while判断若当前元素以及栈顶元素不是’#’，则执行下续循环：如果是属于运算符或者’0’到’9’的数字，再执行如下循环：赋值变量i=0；如果是数字，用atof()函数将数字压入栈顶；如果是运算符，调用char Precede(char a,char b)函数判断并返回当前运算符与栈顶预算符的优先值；当优先值是’<’，将当前运算符入栈，继续循环while判断；当优先值是’=’，将栈顶运算符出栈，继续循环while判断；当优先值是’>’，将栈顶运算符出栈，栈顶数字出栈，再栈顶数字出栈，调用SElemType Operate(SElemType a,SElemType b,SElemType c)对两数以及运算符进行双目运算，将运算结果压入数栈，继续while循环；如果既不是数字也不是运算符，那么输出错误信息。

遇到’#’则while循环结束，将数栈栈顶元素输出，即为结果。

(2)调用关系图：4、测试分析：(1)测试数据：输入1234+(6547-9874)/6321*314# 输出结果1068.73输入(123456789+987654321)*6478# 输出结果1.43956e+012(2)时间复杂度分析：在int In(char c)里有for(i = 0;i<7;i++)循环，频度为7；在SElemType EvaluateExpression()里，有while(c>='0'&&c<='9')，时间复杂度为n；所以此程序的时间复杂度T(n)=O(n)(3)设计和调试时存在的问题：模块之间的调用关系出现错误，比如GetTop()返回值出错导致程序循环错误，输出值始终为0。

合集下载

计算机算法分析实验报告

计算机算法分析实验报告

实验一实验名称：二分制法的快速排序实验时间: 2012年12月6日成绩：一、实验目的：利用分治策略的快速排序算法，对一组数按照从小到大的方式进行排序，此算法在C++语言上的实现。

二、实验内容：快速排序法的基本思想为分治法，通过一次分割，将无序序列分为两部分，其中，前一部分的元素值均小于后一部分的元素值。

然后每一部分再各自递归进行上述过程，直到每一部分的长度为1为止。

我们知道排序的计算量通常是与序列长度的平方成正比，所以分治法将序列一分为二，再各自排序，将大大降低计算量，所以快速排序是一种高效的排序方法。

三、实验过程#include<iostream.h>int part(int s[],int p,int r) //把大于s[p]的数放一边,小于它的数放一边{int x = s[p];int i = p+1;int j = r;while(true){while(s[i] < x && i<=r) i++;while(s[j] > x && j>=1) j--;if(i >=j)break;int temp = s[i];s[i] = s[j];s[j] = temp;}s[p] = s[j];s[j] = x;return j;}void quicksort(int s[],int p,int r) {if(p < r){int q = part(s,p,r);quicksort(s, p,q-1);quicksort(s,q+1,r);}}int main(){int s[] = {4,65,12,43,67,5,78,10,3,70}; int p = 0;int r= sizeof s/sizeof *s -1;cout<<"排序前: "<<endl;for(int i=0;i<=r;i++)cout<<s[i]<<" ";cout<<endl;quicksort(s,p,r);cout<<"排序后: "<<endl;for(i=0;i<=r;i++)cout<<s[i]<<" ";cout<<endl;}四、实验结果(总结/方案) 程序运行的结果：实验二实验名称： 应用贪心算法求解背包问题 实验时间: 2012-12-6 成绩：一、实验目的：了解贪心算法的内涵，以及实现求解背包问题。

计算机基础算法实验报告

计算机基础算法实验报告

计算机基础算法实验报告班级：学号：姓名：指导教师：完成日期：实验一实现两个整数相加1.实验任务实现两个长整数相加：要求用链表（单链表或双向链表）实现任意位数的整数相加。

2.设计思想用单链表实现两个任意位整型相加，建立三个动态链表，两个分别用来存入两个加数，第三个链表用来存入和。

考虑到进位以及算术加法习惯，采用逆序插入节点，先存高位再存低位数，头指针指向最后插入的节点。

进行相加后存入第三个链表，最后将结果输出。

3．主要变量说明data 链表结点的数据域*next 链表结点的指针node单链表类型*list 单链表类型指针head 指向链表的头指针l3 指向第三个链表的头指针j 进位标志4.算法描述首先定义单链表的结构体类型，然后输入两个数，调用创建链表函数创建两个单链表将输入的数分别依次逆序存入，高位存入第一个结点，低位存入之后的结点，最后的结点存个位，并不断循环始终使头指针指向新插入的结点。

然后调用相加函数，并动态创建第三个链表将结果仍逆序存入第三个链表中。

最后调用输出函数将结果输出。

5.程序结构List creat()操作结果：构造一个动态链表list add(list l1,list l2)初始条件：链表l1,l2已存在操作结果：将两个链表的数据依次对应相加，并将结果倒叙存入链表l3void out(list l)初始条件：链表已存在操作结果：依次输出链表中的数据主函数：void main(){list l1,l2,l3;printf("请输入第一个整数，末尾输入-1表结束: ");l1=creat();out(l1);printf("请输入第二个整数，末尾输入-1表结束: ");l2=creat();out(l2);printf（”相加结果为: ”）;l3=add(l1,l2);out(l3);}6.运行结果请输入第一个整数，末尾输入-1表结束：1 2 3 4 -14321请输入第二个整数，末尾输入-1表结束：7 8 9 -1987相加结果为：20237.心得体会通过本次编写程序，我对单链表有了更深的理解，由于没有使用双向链表，就采取了逆向插入结点，这使我对逆向插入有更深的理解。

计算机基础实验实验报告

计算机基础实验实验报告

（3）编写一个程序测试该类，测试数据及要求如下：
圆柱体对象：v(1.0,3.0);
本程序的执行结果如下：
圆柱体属性数据：
半径：1米
高度：3米
面积：3.14平方米
体积：9.42立方米
题目：定义一个类为形状，由它公有派生出圆、正方形、长方形。
利用多态性以虚函数的形式完成计算圆、正方形、长方形的面积。
具体要求如ቤተ መጻሕፍቲ ባይዱ：
（1）形状类名为shape,圆、正方形、长方形的类名分别为circle，square，rectangle。
（2）基类shape中只有一个公有的成员函数：virtual double area();用于求面积，操作为空。
（3）各派生类的数据成员均是私有的，数据类型为double型。
圆的半径为r，正方形的边长为a、长方形的边长为a,b,各派生类均需要定义公有的构造函数。
源代码
（10）题目函数递归问题：求n的阶乘，π的近似值
源代码
2.面向对象题目（5题）
设计一个长方体类Box，它能计算并输出长方体的体积和表面积。具体要求如下：
（1）私有数据成员
数据成员floata，b，c;//分别存放长方体的三条边长
数据成员floatvolume，area;//分别存放长方体的体积和表面积
公有成员函数：float getr(); //取圆的半径r
double area(); //求圆的面积
（2）类colum
保护数据成员：float h; //圆柱体的高
公有构造函数：colum(float,float); //初始化r和h
公有成员函数：float geth(); //取圆柱体的高h
double vol (); //求圆柱体的体积
算法课设实验报告(3篇)

算法课设实验报告(3篇)

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。