实验1 中点画线和Bresenham画线算法的实现

计算机图形学实验报告

实验1 使用画线算法，绘制直线段

一．实验目的及要求

（1）掌握图形学中常用的三种画线算法：数值微分法、中点画线法和Bresenham画线算法。

（2）掌握绘制直线的程序设计方法。

（3）掌握使用文件来保存直线段的方法。

（4）掌握从文本文件中恢复出直线的方法。

二．实验内容

使用VC++ 6.0开发环境，分别实现中点画线算法和Bresenham画线算法，绘制直线（注意，不能使用VC中已有的绘制直线的函数），并以文本文件的形式保存绘制的结果，可以从文本文件中恢复出以前绘制过的直线。

三．算法设计与分析

Bresenham算法绘制直线的程序（仅包含整数运算）。

void MidBresenhamLine(int x0,int y0,int x1,int y1,int color)

{

int dx,dy,d,UpIncre,DownIncre,x,y;

if(x0>x1){

x=x1;x1=x0;x0=x;

y=y1;y1=y0;y0=y;

}

x=x0;y=y0;

dx=x1-x0;dy=y1-y0;

d=dx-2*dy;

UpIncre=2*dx-2*dy;DownIncre=-2*dy;

while(x<=x1){

putpixel(x,y,color);

X++;

if(d<0){

y++;

d+=UpIncre;

}

else d+=DownIncre;

}

}

四．程序调试及运行结果的自我分析与自我评价

// testView.cpp : implementation of the CTestView class

#include "stdafx.h"

#include "test.h"

#include "testDoc.h"

#include "testView.h"

#include // ifstream、ofstream等位于其中

#include

#include // string类型需要

#include "DlgInput.h" //CDlgInput类的头文件

using namespace std;

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

// CTestView

IMPLEMENT_DYNCREATE(CTestView, CView)

BEGIN_MESSAGE_MAP(CTestView, CView)

//{{AFX_MSG_MAP(CTestView)

ON_COMMAND(ID_MENUITEM32771, OnMenuitem32771)

ON_COMMAND(ID_MENUBRESENHAMLINE, OnMenubresenhamline) ON_COMMAND(ID_MENUCLEARVIEW, OnMenuclearview)

ON_COMMAND(ID_FILE_OPEN, OnFileOpen)

ON_COMMAND(ID_FILE_SA VE, OnFileSave)

//}}AFX_MSG_MAP

// Standard printing commands

ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)

ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)

ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview) END_MESSAGE_MAP()

// CTestView construction/destruction

CTestView::CTestView()

{

// TODO: add construction code here

m_nFlag = -1; // 不是任何绘图类型

}

CTestView::~CTestView()

{

}

BOOL CTestView::PreCreateWindow(CREATESTRUCT& cs)

{

// TODO: Modify the Window class or styles here by modifying

// the CREATESTRUCT cs

return CView::PreCreateWindow(cs);

}

// CTestView drawing

void CTestView::OnDraw(CDC* pDC)

{

CTestDoc* pDoc = GetDocument();

ASSERT_V ALID(pDoc);

// TODO: add draw code for native data here

if(1==m_nFlag) // 中点画线

{

MidPointLine(m_X0, m_Y0, m_X1, m_Y1, RGB(255,0,0) );

}

else if(2==m_nFlag) // Bresenham画线

{

BresenhamLine(m_X0, m_Y0, m_X1, m_Y1, RGB(0,255,0) );

}

}

// CTestView printing

BOOL CTestView::OnPreparePrinting(CPrintInfo* pInfo)

{

// default preparation

return DoPreparePrinting(pInfo);

}

void CTestView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)

{

// TODO: add extra initialization before printing

}

void CTestView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)

{

// TODO: add cleanup after printing

}

// CTestView diagnostics

#ifdef _DEBUG

void CTestView::AssertValid() const

{

CView::AssertValid();

}

void CTestView::Dump(CDumpContext& dc) const

{

CView::Dump(dc);

}

CTestDoc* CTestView::GetDocument() // non-debug version is inline

{

ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CTestDoc)));

return (CTestDoc*)m_pDocument;

}

#endif //_DEBUG

// CTestView message handlers

void CTestView::OnMenuitem32771()

{

// TODO: Add your command handler code here

m_nFlag = 1; // 中点画线

CDlgInput dlg;

if(IDOK==dlg.DoModal())

{

m_X0=dlg.m_nX0;

m_Y0=dlg.m_nY0;

m_X1=dlg.m_nX1;

m_Y1=dlg.m_nY1;

RedrawWindow(); //重绘窗口

}

}

void CTestView::OnMenubresenhamline()

{

// TODO: Add your command handler code here

m_nFlag = 2; // Bresenham画线

CDlgInput dlg;

if(IDOK==dlg.DoModal())

{

m_X0=dlg.m_nX0;

m_Y0=dlg.m_nY0;

m_X1=dlg.m_nX1;

m_Y1=dlg.m_nY1;

RedrawWindow(); //重绘窗口

}

}

// 算法: 中点画线

// 输入: 起点(x0,y0),终点(x1,y1);

// 输入要求x0<=x1;

void CTestView::MidPointLine( int x0, int y0, int x1, int y1, int color )

{

CDC * pDC=GetDC();

int a,b,d0,d1,d2,d3,d4,d5,d,x,y;

a=y0-y1;

b=x1-x0; // 之前的设置已经保证始终有x1>=x0

d=2*a+b;

d0=2*a-b;

d1=2*a;

d2=2*(a+b);

d3=2*b;

d4=2*(a-b);

d5=a-2*b;

x=x0;

y=y0;

pDC->SetPixel(x,y,color);

if(x==x1) // 斜率k为无穷大

{

if(y<=y1)

{

while(y<=y1)

{

pDC->SetPixel(x,y,color);

y++;

}

}

else

{

while(y>=y1)

{

pDC->SetPixel(x,y,color);

y--;

}

}

}// if 斜率k为无穷大

else // 斜率k为有限值

{

// double k=-a/b;

// if( k+1>1e-6 && k-1<1e-6 || fabs(k-1)<1e-6 || fabs(k+1)<1e-6) // |k|<=1(即：-1<= k <=1)，与1e-6比较是浮点数比较方法

if( -b<=-a && -a<=b ) // 用浮点数比较在|k|=1.0f时容易出问题，所以直接用整数比较（将斜率k转换为a与b的比较；之前的设置已经保证b为正数）

{

if(y<=y1)

{

while(x

{

if(d<0)

{x++;y++;d+=d2;}

else

{x++;d+=d1;}

pDC->SetPixel(x,y,color);

}

}

else

{

while(x

{

if(d0<0)

{ x++;d0+=d1;}

else

{ x++;y--; d0+=d4; }

pDC->SetPixel(x,y,color);

}

}

}// if( |k|<=1 )

else // |k|>1

{

if(y<=y1)

{

while(x

{

if(d<0)

{y++;d+=d3;}

else

{y++;x++;d+=d2;}

pDC->SetPixel(x,y,color);

}

}

else

{

while(x

{

if(d5<0)

{ x++;y--; d5+=d4;}

else

{y--; d5+=-2*b;}

pDC->SetPixel(x,y,color);

}

}

}// else( |k|>1 )

}// else 斜率k为有限值

ReleaseDC(pDC);

}

// 算法: Bresenham画线

// 输入: 起点(x0,y0),终点(x1,y1);

// 输入要求x0<=x1;

void CTestView::BresenhamLine( int x0, int y0, int x1, int y1, int color )

{ CDC * pDC=GetDC();

int x,y,dx,dy,e;

dx=x1-x0;

dy=y1-y0;

e=-dx;

x=x0;y=y0;

while(x<=x1)

{ pDC->SetPixel(x,y,color);

x++;

e=e+2*dy;

if(e>0)

{y++;

e=e-2*dx;

}

}

}

void CTestView::OnMenuclearview()

{

// TODO: Add your command handler code here

m_X0=0;

m_Y0=0;

m_X1=0;

m_Y1=0;

RedrawWindow();//重绘窗口

}

// 打开过去保存的文件，该文件包含直线的端点坐标

void CTestView::OnFileOpen()

{

// TODO: 在此添加命令处理程序代码

if( m_nFlag!=1 && m_nFlag!=2 )

{

MessageBox("请先在菜单中选择绘制直线的方法!","提示",MB_ICONWARNING);

return;

}

CFileDialog dlgFile (TRUE, _T("txt"), _T(""),

OFN_FILEMUSTEXIST| OFN_HIDEREADONL Y, _T("线段端点坐标文件(*.txt)|*.txt||"), this);

if( IDOK == dlgFile.DoModal())

{

CString fileName = dlgFile.GetFileName();

ifstream rFile;

rFile.open(fileName,ios::in);

if ( ! rFile.is_open() )

{

MessageBox("文件打开失败!","提示",MB_ICONW ARNING);

return;

}

CString strLine0;

string strLine;

int nX,nY;

// 起点、终点，两个坐标

rFile>>strLine;

strLine0 = strLine.c_str();

nX = atoi( strLine0.Left( strLine0.Find(",") ) ); // 解析文件，如“220,221”表示一个点的x、y坐标

nY = atoi( strLine0.Mid( strLine0.Find(",")+1 ) );

m_X0 = nX;

m_Y0 = nY;

rFile>>strLine;

strLine0 = strLine.c_str();

nX = atoi( strLine0.Left( strLine0.Find(",") ) );

nY = atoi( strLine0.Mid( strLine0.Find(",")+1 ) );

m_X1 = nX;

m_Y1 = nY;

RedrawWindow();

rFile.close();

}

}

// 保存当前视图上绘制的所有直线的端点坐标

void CTestView::OnFileSave()

{

// TODO: 在此添加命令处理程序代码

CFileDialog dlgFile(FALSE, _T("txt"), _T(""), OFN_OVERWRITEPROMPT, _T("线段端点坐标文件(*.txt)|*.txt||"), this);

if( IDOK == dlgFile.DoModal()) // 保存文件

{

CString strFileName = dlgFile.GetFileName(); // 包含完整路径的文件名称

ofstream wFile;

wFile.open(strFileName,ios::out|ios::ate|ios::app);

if ( ! wFile.is_open() )

{

MessageBox(strFileName+"文件创建失败!","提示",MB_ICONW ARNING);

return;

}

wFile<

wFile<

五．实验心得及建议

实验心得：Bresenham算法是一种很方便很实用很简单的算法，它对任意斜率的直线段具有通用性。对于斜率为正且大于1的直线段，只需交换x和y之间的规则。对于负斜率，除了一个坐标递减而另一个坐标递增外，其余的程序是类似的。另外，水平、垂直和斜率的绝对值为1的直线可以直接装入帧缓冲储存器而无须进行画线算法处理。

建议：这个程序还不是最简单的，还有改进的空间，希望能把程序变得更简洁些。

算法设计与分析实验指导2014版

算法分析 设计与实验 王 源 二0一四年十月

实验一：分治算法及其应用 实验要求： 掌握分治算法的原理. 掌握递归算法及递归程序的设计. 能用程序设计语言设计求解典型问题的算法 实验题： 1、棋盘覆盖问题：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。 2、最近对问题：设p 1=(x 1,y 1), p 2=(x 2,y 2), …, p n =(x 1,y 1)，是平面上n 个点构成的集合S ，最近对问题就是找出集合S 中距离最近的点对。 3、（选作）最大子段和问题：给定由n 个整数（可能有负整数）组成的序列(a 1, a 2, …, a n )， 最大子段和问题要求该序列形如 的最大值（1≤i ≤j ≤n ），当序列中所有整数均为负 整数时，其最大子段和为0。例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为 。 ∑=j i k k a ∑==4 220 k k a

实验要求： 基本动态规划法的原理方法； 能用程序设计语言实现求解背包问题的算法 实验题： 1、最长公共子序列问题：对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk)，Z是X的子序列当且仅当存在一个递增下标序列(i1, i2,…, ik)，使得对于所有j=1, 2, …, k，有（1≤ij ≤m）。给定两个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列最长公共子序列问题就是在序列X和Y中查找最长的公共子序列。 2、（选作）多段图的最短路径问题：设图G=(V, E)是一个带权有向图，如果把顶点集合V 划分成k个互不相交的子集Vi (2≤k≤n, 1≤i≤k)，使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m (1≤i≤k, 1＜i+m≤k)，则称图G为多段图，称s∈V1为源点，t∈Vk为终点。多段图的最短路径问题求从源点到终点的最小代价路径。 3、

算法设计与分析实验报告贪心算法

算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include float small1,small2; int flag1,flag2,count; typedefstructHuffmanTree { float weight; intlchild,rchild,parent; }huffman; huffmanhuffmantree[100]; void CreatHuffmanTree(intn,int m) { inti; void select(); printf("请输入%d个节点的权值:",n); for(i=0;i

printf("\n"); for(i=0;i

c语言经典算法

C语言的学习要从基础，100个经典的算法 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ ________________________________________________________________ 程序分析：兔子的规律为数列1,1,2,3,5,8,13,21.... __________________________________________________________________ 程序源代码： main() { long f1,f2; int i; f1=f2=1; for(i=1;i<=20;i++) { printf("%12ld %12ld",f1,f2); if(i%2==0) printf("\n");/*控制输出，每行四个*/ f1=f1+f2;/*前两个月加起来赋值给第三个月*/ f2=f1+f2;/*前两个月加起来赋值给第三个月*/ } } 上题还可用一维数组处理，you try! 题目：判断101-200之间有多少个素数，并输出所有素数。 _________________________________________________________________ 程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。 ___________________________________________________________________ 程序源代码： #include "math.h" main() { int m,i,k,h=0,leap=1; printf("\n"); for(m=101;m<=200;m++) { k=sqrt(m+1); for(i=2;i<=k;i++) if(m%i==0) {leap=0;break;} if(leap) {printf("%-4d",m);h++; if(h%10==0) printf("\n"); } leap=1; } printf("\nThe total is %d",h); } 题目：打印出所有的“水仙花数”，所谓“水仙花数”是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个“水仙花数”，因为153=1的三次方＋5的三次方＋3的三次方。 __________________________________________________________________ 程序分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位。 ___________________________________________________________________ 程序源代码：

算法设计实验3

实验三：动态规划法 【实验目的】 应用动态规划算法思想求解矩阵连乘的顺序问题。 【实验要求】 应用动态规划算法的最优子结构性质和子问题重叠性质求解此问题。分析动态规划算法的基本思想，应用动态规划策略写出算法及相应的程序，求解此题。要读懂读透A[i,j]， A[1,n]=A[1,k] ×A[k+1,n]，m[i][j]，s[i][j]各式所表达的含义并正确加以应用。m[i][j]的递归定义： 0 （i=j ） m[i][j]= min{m[i][k]＋m[k+1][j]+n i-1n k n j （i #include class MatrixChain { public: MatrixChain(int mSize); //创建二维数组m和s，一维数组p，并初始化

《算法设计与分析》实验指导

《算法分析与设计》实验指导.

实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能参赛一次； （3）循环赛在n-1天内结束。 请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3） 图1 2个、4个和8个选手的比赛日程表 图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这

样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。

北京理工大学《数据结构与算法设计》实验报告实验一

《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名：

一、实验目的 1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC环境，加强编程、调试的练习； 3.用C语言编写函数，实现循环链表的建立、插入、删除、取数据等基本操作； 4.理论知识与实际问题相结合，利用上述基本操作实现约瑟夫环。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的 结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到 第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点 的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 三、程序设计 1、概要设计 为实现上述程序功能，应用单向环表寄存编号，为此需要建立一个抽象数据类型：单向环表。 （1）、单向环表的抽象数据类型定义为： ADT Joseph{ 数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ |ai∈D,i=1,2,……,n} 基本操作： create(&L,n) 操作结果：构造一个有n个结点的单向环表L。 show(L) 初始条件：单向环表L已存在。 操作结果：按顺序在屏幕上输出L的数据元素。 Josephf( L,m,s,n) 初始条件：单向环表L已存在， s>0,n>0，s

C语言经典算法100例题目

看懂一个程序，分三步：1、流程；2、每个语句的功能；3、试数； 小程序：1、尝试编程去解决他；2、看答案；3、修改程序，不同的输出结果； 4、照答案去敲； 5、调试错误； 6、不看答案，自己把答案敲出来； 7、实在不会就背会。。。。。周而复始，反复的敲。。。。。 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ ============================================================== 【程序3】 题目：一个整数，它加上100后是一个完全平方数，再加上168又是一个完全平方数，请问该数是多少？============================================================== 【程序4】 题目：输入某年某月某日，判断这一天是这一年的第几天？ ============================================================== 【程序5】 题目：输入三个整数x,y,z，请把这三个数由小到大输出。 ============================================================== 【程序6】 题目：用*号输出字母C的图案。 ============================================================== 【程序7】 题目：输出特殊图案，请在c环境中运行，看一看，Very Beautiful! ============================================================== 【程序8】 题目：输出9*9口诀。 ============================================================== 【程序9】 题目：要求输出国际象棋棋盘。 ============================================================== 【程序10】 题目：打印楼梯，同时在楼梯上方打印两个笑脸。 -------------------------------------------------------------------------------- 【程序11】 题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月 后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？ ==============================================================

实验一 简单算法设计

实验一简单算法设计 一.实验目的和要求 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力； 二．实验内容 (一)相等元素问题 1.问题描述先排序函数，再查找函数。 #define size 100 Typedef strat { Int Array[size] Int listlength }List List a; Main() { 1、输入 2、排序 3、查找 4、输出 } 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 测试数据 输入： 9 71 25 64 38 52 5 31 19 45 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No 3. 设计与实现的提示 算法最坏情况和平均情况的时间复杂性是衡量算法优劣的重要指标，算法设计要求尽可能设计比较高效的算法。 (二) 整数集合分解（选做） 1.问题描述

设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 测试数据 输入： 68 25 34 16 2 37 3 95 76 57 21 13 4 78 29 6 17 39 51 20 43 12 28 3 48 59 14 32 47 51 42 61 9 24 52 78 65 2 37 78 51 73 29 7 26 95 37 2 输出： 2 3 4 6 12 13 16 17 20 21 25 29 34 37 39 43 51 57 68 76 78 95 2 2 3 7 9 1 4 24 26 28 29 32 37 37 42 47 48 51 51 52 59 61 62 65 73 78 95 3. 设计与实现的提示 本题可以有多种方法。算法时间复杂性是选取算法的重要依据。输出的两个新整数集合要求按照从小到大排序后输出。该排序步骤对算法时间复杂性的影响在此不计。

算法设计与实验报告讲解

算法设计与分析实验报告 学院：信息学院 专业：物联网1101 姓名：黄振亮 学号：20113379 2013年11月

目录 作业1 0-1背包问题的动态规划算法 (7) 1.1算法应用背景 (3) 1.2算法原理 (3) 1.3算法描述 (4) 1.4程序实现及程序截图 (4) 1.4.1程序源码 (4) 1.4.2程序截图 (5) 1.5学习或程序调试心得 (6) 作业2 0-1背包问题的回溯算法 (7) 2.1算法应用背景 (3) 2.2算法原理 (3) 2.3算法描述 (4) 2.4程序实现及程序截图 (4) 2.4.1程序源码 (4) 2.4.2程序截图 (5) 2.5学习或程序调试心得 (6) 作业3循环赛日程表的分治算法 (7) 3.1算法应用背景 (3) 3.2算法原理 (3) 3.3算法描述 (4) 3.4程序实现及程序截图 (4)

3.4.1程序源码 (4) 3.4.2程序截图 (5) 3.5学习或程序调试心得 (6) 作业4活动安排的贪心算法 (7) 4.1算法应用背景 (3) 4.2算法原理 (3) 4.3算法描述 (4) 4.4程序实现及程序截图 (4) 4.4.1程序源码 (4) 4.4.2程序截图 (5) 4.5学习或程序调试心得 (6)

作业1 0-1背包问题的动态规划算法 1.1算法应用背景 从计算复杂性来看,背包问题是一个NP难解问题。半个世纪以来,该问题一直是算法与复杂性研究的热点之一。另外,背包问题在信息加密、预算控制、项目选择、材料切割、货物装载、网络信息安全等应用中具有重要的价值。如果能够解决这个问题那么则具有很高的经济价值和决策价值，在上述领域可以获得最大的价值。本文从动态规划角度给出一种解决背包问题的算法。 1.2算法原理 1.2.1、问题描述： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi ∈{0,1}, ?∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 1.2.2、最优性原理： 设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则(y2,…,yn)是下面相应子问题的一个最优解: 证明:使用反证法。若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而(y2,y3,…,yn)不是它的最优解。显然有 ∑vizi > ∑viyi (i=2,…,n) 且 w1y1+ ∑wizi<= c 因此 v1y1+ ∑vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3.4.1)0-1背包问题的一个更优解,导出(y1,y2,…,yn)不是背包问题的最优解,矛盾。 1.2.3、递推关系：

C语言经典算法100例(1---30)

2008-02-18 18:48 【程序1】 题目：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？ 1.程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去 掉不满足条件的排列。 2.程序源代码： main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } } ============================================================== 【程序2】 题目：企业发放的奖金根据利润提成。利润(I)低于或等于10万元时，奖金可提10%；利润高 于10万元，低于20万元时，低于10万元的部分按10%提成，高于10万元的部分，可可提 成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；40万到60万之间时高于 40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%，高于 100万元时，超过100万元的部分按1%提成，从键盘输入当月利润I，求应发放奖金总数？ 1.程序分析：请利用数轴来分界，定位。注意定义时需把奖金定义成长整型。 2.程序源代码： main() { long int i; int bonus1,bonus2,bonus4,bonus6,bonus10,bonus; scanf("%ld",&i); bonus1=100000*0.1;bonus2=bonus1+100000*0.75; bonus4=bonus2+200000*0.5; bonus6=bonus4+200000*0.3; bonus10=bonus6+400000*0.15; if(i<=100000)

算法设计与分析实验指导书样本

算法设计与分析实验指导书

实验一 C/C++环境及递归算法( 4学时) 一、实验目的与要求 1、熟悉C/C++语言的集成开发环境; 2、经过本实验加深对递归过程的理解 二、实验内容: 掌握递归算法的概念和基本思想, 分析并掌握排列问题的递归算法和Hanoi塔问题的递归算法。 三、实验题 1、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。任意输入一 串整数或字符, 输出结果能够用递归方法实现整数或字符的全排列。 2、设a,b,c是3个塔座。开始时, 在塔座a上有一叠共n个圆盘, 这些圆 盘自下而上, 由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上, 并仍按同样顺序叠置。 四、实验步骤 1．理解算法思想和问题要求; 2．编程实现题目要求; 3．上机输入和调试自己所编的程序; 4．验证分析实验结果; 5．整理出实验报告。 实验提示 1、 #include inline void swap(int &a,int &b) { int temp=a; a=b;

b=temp; } void perm(int list[],int k,int m) { if(k==m) { for(int i=0;i<=m;i++) cout<

银行家算法设计实验报告

银行家算法设计实验报告

银行家算法设计实验报告 一．题目分析 1.银行家算法： 我们可以把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求资源相当于客户向银行家贷款。操作系统按银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程尚需求的资源量，若是系统现存的资源可以满足它尚需求的资源量，则按当前的申请量来分配资源，否则就推迟分配。 当进程在执行中继续申请资源时，先测试该进程申请的资源量是否超过了它尚需的资源量。若超过则拒绝分配，若没有超过则再测试系统尚存的资源是否满足该进程尚需的资源量，若满足即可按当前的申请量来分配，若不满足亦推迟分配。 2.基本要求： （1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。 （2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。

（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况： A. 所申请的资源大于其所需资源，提示分配不合理不予分配并返回 B. 所申请的资源未大于其所需资源， 但大于系统此时的可利用资源，提 示分配不合理不予分配并返回。 C. 所申请的资源未大于其所需资源， 亦未大于系统此时的可利用资源，预 分配并进行安全性检查： a. 预分配后系统是安全的，将该进 程所申请的资源予以实际分配并 打印后返回。 b. 与分配后系统进入不安全状态，提示系统不安全并返回。 （4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。 3.目的： 根据设计题目的要求，充分地分析和理解题 目，叙述系统的要求，明确程序要求实现的功能以及限制条件。 明白自己需要用代码实现的功能，清楚编写每部分代码的目的，做到有的放矢，有条理不遗漏的用代码实现银行家算法。

算法设计实验报告一(简单算法设计)

实验报告一 课程C++ 实验名称简单算法设计第 1 页专业_数学与应用数学_ __ 班级__ 双师一班学号105012011056 姓名陈萌 实验日期：2013 年 3 月9 日报告退发(订正、重做) 一、实验目的 1. 理解算法设计与分析的基本概念，理解解决问题的算法设计与实现过程； 2. 掌握简单问题的算法设计与分析，能设计比较高效的算法； 3. 熟悉C/C++语言等的集成开发环境，掌握简单程序设计与实现的能力。 二、实验内容 (一)相等元素问题 1.问题描述 元素唯一性问题：给出一个整数集合，假定这些整数存储在数组A[1…n]中，确定它们中是否存在两个相等的元素。请设计出一个有效算法来解决这个问题，你的算法的时间复杂性是多少？ 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1767题 输入：输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n<=500)，表示整数序列的长度，第二行给出整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出一行，若该组测试例中存在两个相等的元素则输出”Yes”，否则，输出”No”。每个测试例的输出数据用一行表示。 3. 测试数据 输入：3 10 9 71 25 64 38 52 5 31 19 45 16 26 35 17 92 53 24 6 57 21 12 34 2 17 86 75 33 20 15 87 32 7 84 35 26 45 78 96 52 22 37 65 9 43 21 3 33 91 输出：No Yes No (二) 整数集合分解 1.问题描述 设计算法把一个n个元素的整数集合（n为偶数）分成两个子集S1和S2，使得：每个新的集合中含有n/2个元素，且S1中的所有元素的和与S2中的所有元素的和的差最大。 2. 具体要求（若在ACM平台上提交程序，必须按此要求）――平台上1768题 输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n (n为偶数，且n<=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。 输出：对于每个测试例输出两行，分别表示新生成的整数集合。其中，第一行是元素和比较小的整数集合，第二行是元素和比较大的整数集合，整数之间用一个空格隔开。两个测

算法设计与分析课程设计-实验指导书

算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系

一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。

南京邮电大学算法设计实验报告——动态规划法

实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++

三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。

算法与设计实验报告

算法与分析实验报告软件工程专业 安徽工业大学 指导老师：许精明

实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 一：实验目的 1：掌握动态规划算法的基本思想，学会用其解决实际问题。 2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。 二：实验内容 1：杨辉三角 2：背包问题 3：汉诺塔问题 实验一：杨辉三角

问题分析： ①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 ②第n行数之和为2^n。 ③下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码： public void yanghui(int n) { int[] a = new int[n]; if(n==1){ System.out.println(1); }else if(n==2) { System.out.print(1 + " " +1); }else{ a[1]=1; System.out.println(a[1]); a[2]=1;

System.out.println(a[1]+" "+a[2]); for(int i=3;i<=n;i++){ a[1]=a[i]=1; for(int j=i-1;j>1;j--){ a[j]=a[j]+a[j-1]; } for(int j=1;j<=i;j++){ System.out.print(a[j]+" "); } System.out.println(); } } } 实验结果：n=10 实验二：0-1背包问题 问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就 j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数: (1) V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) j

算法设计与分析实验报告 统计数字问题

算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int s[10]; //记录0~9出现的次数 int a[10]; //a[i]记录n位数的规律 void sum(int n,int l,int m) { if(m==1) {

int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i

算法设计实验报告(川大陈瑜)

《算法设计》课程报告 课序号： 01 学号： 2012141461134 姓名：刘佳玉 任课教师：陈瑜 评阅成绩： 评阅意见： 提交报告时间：2014年 6 月 16 日

贪心算法 1、问题描述 （这是我在soj上找的一道题，以前没做出来，现在用贪心的思想做出来了） 约翰要去钓鱼。他有h小时可用（1≤h≤16），在这个地区有n个湖泊（2≤n≤25），所有的湖泊沿着一条单行道可到达。约翰从湖泊1开始，他可以在任何湖泊结束。他只能从一个湖，到下一个，但他没有必要停在任何湖除非他想停。对于每个i = 1，……，n-1，ti 表示从湖i到湖i+1的5分钟的时间间隔（0 < ti < = 192）。例如，t3 = 4意味着它从湖3湖4需要20分钟的时间。 为了帮助他们规划自己的钓鱼旅行，约翰已经收集了一些关于湖泊信息。对于每个湖泊的i，能钓到的鱼在最初的5分钟的数量，用fi表示（fi > = 0），是已知的。每钓5分钟的鱼，能钓到的鱼在接下来的5分钟的间隔降低一个恒定的数di（di＞＝0）。如果能钓到的鱼在一个时间区的数量小于或等于di，将不会有更多的鱼留在湖里在下一个时间间隔。为了简化规划，约翰认为没有人会在影响他期待钓到的鱼的数量的湖里钓鱼。 写一个程序来帮助约翰计划他的最大化期望钓到的鱼的数量的钓鱼之旅。在每个湖花费的时间数必须是5的倍数。 这个问题包含多个测试案例！ 一个多输入的第一行是一个整数N，然后一个空白行后的N个输入块。每个输入块由问题描述中的格式表示的。每个输入块之间有一个空行。 输出格式包含N个输出块。输出块之间要有一个空白行。 输入 在输入中，会给你一个案例输入的数量。每一种情况下，以n开始，其次是h，接下来有一行n个整数指定fi（1 < =i< = n），然后有一行n个整数di（1≤i＜＝n），最后，有一行n - 1的整数ti（1≤i＜＝n-1）。输入在n=0的情况下终止。 输出