西 安 邮 电 大 学 (计算机学院)
课内实验报告
实验名称: 编辑距离问题
专业名称:班 级: 1101班
学生姓名:
学号(8指导教师: 刘伟
实验日期: 20xx年10月25日
一.实验目的及实验环境
1.实验目的
了解并掌握动态规划的主要思想与基本要素,能够熟练使用动态规划方法求解一些问题。
2.实验环境
CPU:2.40GHz
内存:2.00GB(1.89GB可用)
操作系统:Windows 7 旗舰版
软件平台:Microsoft Visual C++
二.实验内容
用动态规划方法求解编辑距离问题
三.方案设计
在二维数组d[n][m]中,d[i][j]表示字符串a的前i个字符到字符串b的前j个字符的编辑距离。
①若a[i]≠b[j],则d[i][j]为d[i-1][j], d[i][j-1],d[i-1][j-1]三个数中的最小数+1。
②若a[i]=b[j],则d[i][j]为d[i-1][j-1]。
最终结果为d[n][m](n,m分别为字符串a与b的长度)。
四.测试数据及运行结果
图1 图
2
图3 图4
五.总结
1.实验过程中遇到的问题及解决办法;
实验刚开始时,由于动态规划的基本思想掌握的不是很清楚,不知道该如何设计问题,后来仔细复习了本节知识,才有了思绪。最终完成了本次实验。
2.对设计及调试过程的心得体会。
通过本次试验,我复习了C语言的有关知识,对于C语言的认识更加深刻,巩固了以往所学的内容。同时,对于动态规划也有了更好的理解,从中学到了许多新的编程思想,很大地提高了编程效率。可谓是受益匪浅。
六.附录:源代码(电子版)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 50
void Read(char *a, char *b) // 读文件
{
FILE *fp;
fp = fopen("H:\\算法设计与分析\\上机\\程序\\input.txt", "rt"); fgets(a,50,fp);
fgets(b,50,fp);
fclose(fp);
}
void Write(int result) // 写文件
{
FILE *fp;
fp = fopen("H:\\算法设计与分析\\上机\\程序\\output.txt", "wt"); fprintf(fp, "%d", result);
fclose(fp);
}
int Min(int a,int b,int c)
{
int x,min=a;
x=(b<c)?b:c;
if(x < min)
min=x;
return min;
}
int Distance(char s[],char t[])
{
int n = strlen(s)-1;
int m = strlen(t)-1;
int i,j,x;
int **d = (int **)malloc((n+1) * sizeof(int *)); //创建二维数组d,共n+1行
for(i=0; i<=n; ++i)
{
d[i] = (int *)malloc((m+1) * sizeof(int)); //数组d为m+1列 }
if (n == 0) //数组A的个数为0
{
return m; //返回数组B的数据个数,即为交换个数
}
if (m == 0) //数组B的个数为0
{
return n; //返回数组A的数据个数,即为交换个数
}
for (i = 0; i <= n; i++)
{
d[i][0] =i;
}
for (j = 0; j <= m; d[0][j] = j++)
{
d[0][j] =j;
}
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
x = (t[j-1] == s[i-1]) ? 0 : 1;
d[i][j] = Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+x); }
}
return d[n][m]; //返回最小距离
}
int main(int argc, char *argv[])
{
char a[N];
char b[N];
int result;
Read(a, b); // 从文件中读取字符串
} printf("字符串a为:%s", a); printf("字符串b为:%s", b); result = Distance(a, b); // 求编辑距离 Write(result); printf("\n编辑距离为:%d.\n", result); return 0; // 将结果写到文件中
第二篇:数据库实验报告格式 西安邮电大学
1.实验目的
(1) 熟悉SQL Sever2000的环境。
(2) 掌握企业管理器的基本使用方法,对数据库及其对象有基本了解,了解对SQL Sever 2000进行配置的方法。
(3) 掌握查询分析器的基本使用方法以及在查询分析器中执行T-SQL语句的方法。
(4) 了解SQL Sever 2000数据库的逻辑结构和物理结构。
(5) 学会在企业管理器中创建数据库及查看数据库属性。
(6) 学会使用T-SQL语句创建数据库。
(7) 了解SQL Sever 2000的基本数据类型、空值的概念,以及表的结构特点。
(8) 学会使用T-SQL语句和企业管理器创建表结构和修改表结构。
(9) 学会使用SQL Sever 2000提供的数据完整性功能,并在创建表时定义表的数据完整性。通过实验进一步理解数据完整性的概念及分类。
二、实验内容
2.实验内容
(1) 学会使用企业管理器和查询分析器管理工具。
(2) 使用企业管理器创建数据库。
创建一个教务管理数据库,名称为JWGL,数据文件的初始大小为20MB,文件增长方式为自动增长,文件增长增量设为5MB,文件的增长上限为500MB。日志文件的初始大小为10MB,文件增长增量设为1MB,文件的增长限制设为100MB。数据文件的逻辑文件名和物理文件名均采用默认值,分别为JWGL_data和d:\Microsoft SQL Sever\MSSQL\data\JWGL_data.mdf;事务日志文件的逻辑文件名和物理文件名也采用默认值,分别为JWGL_log和d:\Microsoft SQL Sever\MSSQL\data\JWGL_log.ldf。
(3) 在查询分析器中使用T_SQL语句创建数据库。
创建一个名为Market的数据库(注意e盘下应存在sql_data目录)。
CREATE DATABASE Market
ON
(NAME=Market_Data,
FILENAME=’e:\sql_data\Market_Data.mdf’,
SIZE=10,
MAXSIZE=50,
FILEGROWTH=10%)
LOG ON
(NAME=Market_Log,
FILENAME=’e:\sql_data\Market_Log.ldf’,
SIZE=5,
MAXSIZE=15,
FILEGROWTH=10%);
(4) 用企业管理器在教务管理数据库JWGL中创建学生表Student、课程表Course、学生选课表SC,它们的表结构如表B.1所示。
表B.1 教务管理数据库的表结构
学生表Student
课程表Course
学生选课表SC
(5) 用T_SQL语句在Market数据库中创建客户基本信息表Customers、货品信息表Goods、订单信息表Orders,它们的定义如下
CREATE TABLE Customers (
CustomerID int IDENTITY(1,1) PRIMARY KEY,
Cname varchar(8) NOT NULL,
Address varchar(50),
City varchar(10),
Tel varchar(20) UNIQUE
Company varchar(50),
Birthday datetime,
Type tinyint DEFAULT 1);
CREATE TABLE Goods (
GoodsID int CONSTRAINT C1 PRIMARY KEY,
GoodsName varchar(20) NOT NULL,
Price money,
Description varchar(200),
Storage int,
Provider varchar(50),
Status tinyint DEFAULT(0));
CREATE TABLE Orders (
OrderID int IDENTITY(1,1) CONSTRAINT C2 PRIMARY KEY,
GoodsID int NOT NULL REFERENCES Goods(GoodsID) ON DELETE CASCADE,
Quanity int NOT NULL CONSTRAINT C3 CHECK(Quantity>0),
OrderSum money NOT NULL,
OrderDate datetime DEFAULT(getdate()));
三、实验环境
装有SQL Server 2000的实验机
四、实验前准备
1.明确只有系统管理员才能创建数据库,或是被授权使用CREATE DATABASE语句。
2.创建数据库必须要确定数据库名、所有者(即创建数据库的用户)、数据库大小(最初的大小、最大的大小、是否允许增长及增长的方式)和存储数据的文件。
3. 确定数据库包含哪些表以及包含的各表的结构,还要了解SQL Server 的常用数据类型,以创建数据库的表。
4.了解常用的创建数据库和表的方法。
五、实验步骤
1、首先在企业管理器中创建好名称为JWGL的数据库,接着根据实验内容中的要求,把数据输入,使其生成一个基本的数据库。
2、在这个数据库中建立新表,分别为学生表、课程表、学生选课表,
讲三者的完整性和联系都确立好注意:主键,默认值,空值,check约束。。
3、在Market数据库中用查询分析器创建新表:客户基本信息表、货品信息表、订单信息表,注意,sql语句的语法和格式。
4、完成Market数据库中各表的数据完整性
六、实验结果
根据以上关于表的建立操作,可以得到两个较为完整的关系表根据这两个表格我们就可以得到想要获得的信息了,操作截图如下:
(1)学生表
(2)课程表
(3)学生选课表
(3)sql语句创建数据库
(6)sql语句创建Market数据库中的客户信息表,货物信息表以及订货信息表
七、评价分析及心得体会
本次实验主要是熟悉SQL Server 2000中对于数据库和表的建立的基本操作。在查询分析器中创建数据库,尤其是分配数据库的大小,增长,逻辑结构和物理结构比较陌生经过反复练习和老师指导。这次实验,我对数据库和sql语句的基本操作有了了解,为后续实验打下了坚实的基础。