当前位置:文档之家› 算法题目及答案

算法题目及答案

算法题目及答案
算法题目及答案

根据两个有序单链表生成一个新的有序单链表,原有单链表保持不变。要求新生成的链表中不允许有重复元素。

算法如下

ListNode * Merge ( ListNode * L1, ListNode * L2 )

{//根据两个带表头结点的有序单链表L1和L2, 生成一个新的有序单链表

ListNode *first = new ListNode;

ListNode *p1 = L1->link, *p2 = L2->link, *p = first, *q;

while ( p1 != NULL && p2 != NULL )

{

q = new ListNode;

if ( p1->data == p2->data )

{ q->data = p1->data; p2 = p2->link; p1 = p1->link; }

else if ( p1->data < p2->data )

{ q->data = p1->data; p1 = p1->link; }

else

{ q->data = p2->data; p2 = p2->link; }

p->link = q; p = q;

}

while ( p1 != NULL )

{

q = new ListNode; q->data = p1->data; p1 = p1->link;

p->link = q; p = q;

}

while ( p2 != NULL )

{

q = new ListNode; q->data = p2->data; p2 = p2->link;

p->link = q; p = q;

}

p->link = NULL;

return first;

}

2.

设有一个线性表(e0, e1, …, e n-2, e n-1) 存放在一个一维数组A[arraysize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置,即将数组的前n个原址内容置换为(e n-1, e n-2, …, e1, e0)。

数组原地逆置算法

参数表中给出数组A[ ] 及指定的数组中前n个元素,函数执行后从A[ ] 中得到数组原地逆置后的结果。

Template

void inverse ( T A[ ], int n )

{ T tmp;

for ( int I = 0; I <= ( n-1 ) / 2; I++ )

{ tmp = A[I]; A[I] = A[n-I-1]; A[n-I-1] = tmp;}

3.

设有两个整数类型的顺序表A(有m个元素)和B(有n个元素),其元素均以从小到大的升序排列。试编写一个函数,将这两个顺序表合并成一个顺序表C,要求C的元素也以从小到大的升序排列。

合并两个升序排列的顺序表的算法

参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。

算法中用到顺序表的4个共有函数:Length( ) 求表的当前长度;maxLength( ) 求表的最大允许长度;getData(k) 提取第k个元素的值;setData(k) 修改第k个元素的值。

Template

void merge ( SeqList& A, SeqList& B, SeqList& C )

{ int m = A.Length( ), n = B.Length( ), mpn = m + n;

if ( mpn > C.maxLength( ) )

{ cerr << “合并后表的长度超出表的最大允许长度”<< endl;

exit (1);

}

int I = 0, j = 0, k = 0, av = A.getData(I), bv = B.getData(j);

while ( I < m && j < n )

if ( av <= bv )

{ C.setData(k++, av); av = A.getData(++I); }

else

{ C.setData(k++, bv); B.getData(++j); }

if ( I < m )

while ( k < mpn ) { C.setData(k++, av); av = A.getData(++I); }

else

while ( k < mpn ) { C.setData(k++, bv); B.getData(++j); }

}

4.

已知一个带表头结点的单链表中包含有三类字符(数字字符、字母字符和其他字符),试编写一个函数,构造三个新的单链表,使每个单链表中只包含同一类字符。要求使用原表的空间,表头结点可以另辟空间。

算法如下

typedef char elemType;

void Separate ( ListNode * LA, ListNode * LB, ListNode * LC )

{ //原来的单链表是LA, 新的三个单链表是LA, LB, LC ListNode * p = LA->link;

ListNode * pa = LA, * pb = LB, * pc = LC;

while ( p != NULL )

{ if ( isdigit (p->data) ) { pa->link = p; pa = p; }

else if ( isalpha (p->data) )

{ pb->link = p; pb = p; }

else

{ pc->link = p; pc = p; }

p = p->link;

}

pa->link = NULL; pb->link = NULL; pc->link = NULL;

}

5.

一颗具有n个结点的完全二叉树以顺序方式存储在数组A中,设计一个算法构造该二叉树的二叉链存储结构。

算法如下

void ctree(BTNode *&t,ElemType a[],int i,int n)

{ if(i>n)

t=NULL;

else

{ t=(BTNode*)malloc(sizeof(BTNode));

t->data=a[i-1];

ctree(t->lchild,a,2*i,n);

ctree(t->rchild,a,2*i+1,n);

}

}

6.

编写一个算法frequency,统计在一个输入字符串中各个不同字符出现的频度。算法返回两个数组:A[ ]记录字符串中有多少种不同的字符,C[ ]记录每一种字符的出现次数。此外,还要返回不同字符数。

求输入字符串中各种不同字符出现频度的算法

由于需要返回多种信息,参数表中引入引用参数:A[ ]中记录字符串中有多少种不同的字符,C[ ]中记录每一种字符的出现次数,k返回不同字符数。

#include

#include "string1.h"

void frequency( String& s, char A[ ], int C[ ], int &k )

{ int I, j, len = s.Length( );

if ( !len )

{ cout << "The string is empty. " << endl; k = 0; return; }

else

{ A[0] = s[0]; C[0] = 1; k = 1;

for ( I = 1; I < len; I++ ) C[I] = 0;

for ( I = 1; I < len; I++ )

{ for ( j = 0; j < k && A[j] != s[I]; j++ );

if ( j == k )

{ A[k] = s[I]; C[k]++; k++; }

else

C[j]++;

}

}

}

7.

已知二叉树中的结点类型用BinTreeNode表示,被定义为:

struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域,leftChild和rightChild分别为指向左、右子女结点的指针域,根据下面函数声明编写出求一棵二叉树高度的算法,该高度由函数返回。假定根结点的层次为0,参数BT初始指向这棵二叉树的根结点。Int BTreeHeight ( BinTreeNode* BT );

算法如下

int BTreeHeight ( BinTreeNode* BT )

{ if ( BT == NULL ) return –1; //对于空树,返回-1并结束递归,else

{ int h1 = BTreeHeight ( BT->leftChild ); //计算左子树的高度,

int h2 = BTreeHeight (BT->rightChild ); //计算右子树的高度,

if ( h1 > h2 )

return h1+1;

else

return h2+1; //返回树的高度,

}

}

8.

已知二叉树中的结点类型用BinTreeNode表示,被定义为:

struct BTreeNode { char data;BinTreeNode *leftChild, *rightChild; };

其中data为结点值域,leftChild和rightChild分别为指向左、右子女结点的指针域,根据下面函数声明编写出求一棵二叉树中结点总数的算法,该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。Int BTreeCount ( BinTreeNode* BT );

算法如下

int BTreeCount ( BinTreeNode* BT )

{ if ( BT == NULL ) return 0;

else

return BTreeCount ( BT->leftChild ) + BTreeCount ( BT->rightChild ) + 1;

}

9.

已知二叉树中的结点类型用BinTreeNode表示,被定义为:

struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域,leftChild和rightChild分别为指向左、右子女结点的指针域,根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法,该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。Int BTreeLeafCount ( BinTreeNode* BT );

算法如下

int BTreeLeafCount ( BinTreeNode* BT )

{ if ( BT == NULL )

return 0;

else if (BT->leftChild == NULL && BT->rightChild == NULL)

return 1;

else

return BTreeLeafCount ( BT->leftChild ) + BTreeLeafCount ( BT->rightChild );

}

10.

已知二叉树中的结点类型用BinTreeNode表示,被定义为:

struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域,leftChild和rightChild分别为指向左、右子女结点的指针域,根据下面函数声明编写出删除一棵二叉树中所有结点的算法,并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点。V oid ClearBinTree ( BinTreeNode*& BT);

算法如下

void ClearBinTree ( BinTreeNode*& BT )

{ if ( BT!=NULL ) //

{ ClearBinTree ( BT->leftChild ); //递归删除左子树,ClearBinTree ( BT->rightChild ); //递归删除右子树,

delete BT; //回收根结点,

BT = NULL; //置根指针为空,}

}

11.

已知二叉树中的结点类型用BinTreeNode表示,被定义为:

struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域,leftChild和rightChild分别为指向左、右子女结点的指针域,根据下面函数声明编写出复制一棵二叉树的算法,并返回复制得到的二叉树的树根指针。算法中参数BT初始指向待复制二叉树的根结点。BinTreeNode* BTreeCopy ( BinTreeNode* BT );

算法如下

BinTreeNode* BtreeCopy ( BinTreeNode* BT )

{ if ( BT == NULL ) return NULL; //1分

else

{ BinTreeNode* pt = new BinTreeNode; //得到新结点,

pt->data = BT->data; //复制根结点值,

pt->leftChild = BtreeCopy ( BT->leftChild ); //复制左子树,

pt->rightChild = BTreeCopy ( BT->rightChild ); //复制右子树,

return pt; //返回新树的树根指针,}

}

12.

已知二叉树中的结点类型用BinTreeNode表示,被定义为:

struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域,leftChild和rightChild分别为指向左、右子女结点的指针域,根据下面函数声明编写出从一棵二叉树中求出结点值大于x的结点个数的算法,并返回所求结果。算法中参数BT初始指向二叉树的根结点。Int BTreeCount ( BinTreeNode* BT, ElemType x ); 算法如下

//统计出二叉树中大于给定值x的结点个数,该统计值由函数返回

int BtreeCount ( BinTreeNode* BT, ElemType x )

{ if ( BT == NULL )

return 0;

else if ( BT->data > x )

return BtreeCount ( BT->leftChild, x ) + BtreeCount ( BT->rightChild, x ) + 1;

else

return BtreeCount ( BT->leftChild, x ) + BtreeCount ( BT->rightChild, x );

}

13.

试编写函数用邻接表存储结构实现

template int AdjTable ::GetFirstNeighbor ( int v );

//给出顶点位置为v 的第一个邻接顶点的位置,如果找不到,则函数返回-1

算法实现如下

template int AdjTable ::GetFirstNeighbor ( int v )

{ //给出顶点位置为v 的第一个邻接顶点的位置,如果找不到,则函数返回-1 if ( v != -1 )

{ Edge *p = NodeTable (v).adj;

if ( p != NULL ) return p->dest;

}

return –1;

}

14.

试编写函数用邻接表存储结构实现

template int AdjTable ::GetNextNeighbor ( int v, int w );给出顶点v的邻接顶点w的下一个邻接顶点的位置,若没有下一个邻接顶点,则函数返回-1

算法实现如下

template int AdjTable ::GetNextNeighbor ( int v, int w )

{/*给出顶点v的邻接顶点w的下一个邻接顶点的位置,若没有下一个邻接顶点,则函数返回-1*/

if ( v != -1 )

{ Edge * p = NodeTable[v].adj;

while ( p != NULL )

if (p->dest == w && p->link != NULL )

return p->link->dest;

else

p = p->link;

}

return –1;

}

15.

假定元素类型为ElemType的一维数组R[n] 中保存着按关键码升序排列的n个对象,对象的关键码域key的类型为KeyType,试按照下面的函数声明编写一个非递归算法,从一维数组R[n]中用折半搜索法找出关键码等于k的对象,若搜索成功则返回对象位置(即元素下标),否则返回-1。Int BinSearch ( ElemType R[ ], int n, KeyType k );

算法如下:

int BinSearch ( ElemType R[ ], int n, KeyType k )

{ int low = 0, high = n-1; //赋初值2分

while ( low <= high )

{//循环条件1分

int mid = (low + high) / 2; //中点位置1分

if ( k == R[mid].key )

return mid; //成功返回1分

else if ( k < R[mid].key)

high = mid-1; //向左半区查找1分

else

low = mid+1; //向右半区查找1分}

return -1; //失败返回1分

}

16.

已知二叉搜索树中的结点类型用BinTreeNode表示,被定义为:

struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; };

其中data为结点值域,leftChild和rightChild分别为指向左、右子女结点的指针域。假定具有BinTreeNode * 类型的指针参数BST指向一棵二叉搜索树的根结点,试根据下面的函数声明编写一个非递归算法,从BST树中查找出具有x参数值的结点,若查找成功则返回该结点的地址,否则返回NULL。BinTreeNode* Find ( BinTreeNode* BST, ElemType& x );

算法如下:

BinTreeNode* Find ( BinTreeNode* BST, ElemType& x )

{ while ( BST != NULL )

{ //循环条件1分

if ( x == BST->data )

return BST; //成功返回2分

else if ( x < BST->data )

BST = BST->leftChild; //向左孩子查找2分

else

BST = BST->rightChild; //向右孩子查找2分}

return NULL; //失败返回1分

}

17.

试设计一个算法,改造一个带表头结点的双向循环链表,所有结点的原有次序保持在各个结点的右链域rLink中,并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。算法如下

void OrderedList ( DblNode * L )

{ //利用左链域llink把所有结点按照其值从小到大的顺序连接起来

DblNode * endp = L, * pr, * p, *s, *q = L->llink;

s = q->llink; q->llink = endp; //2分

while ( s != endp )

{ pr = endp; p = pr->llink; //2分

while ( p != endp )

if ( p->data > s->data )

break;

else

{ pr = p; p = p->llink; }

q = s->llink; pr->llink = s; s->llink = p; //3分

s = q; //1分

}

}

18.

编写一个程序实现直接插入排序算法。

void InsertSort(RecType R[],int n) /*对R[0..n-1]按递增有序进行直接插入排序*/ { int i,j,k;

RecType tmp;

for (i=1;i

{ tmp=R[i];

j=i-1; /*从右向左在有序区R[0..i-1]中找R[i]的插入位置*/

while (j>=0 && tmp.key

{ R[j+1]=R[j]; /*将关键字大于R[i].key的记录后移*/ j--;

}

R[j+1]=tmp; /*在j+1处插入R[i]*/

printf("i=%d: ",i);

for (k=0;k

printf("%d ",R[k].key);

printf("\n");

}

}

19.

编写一个程序实现冒泡排序算法。

#include

#define MaxSize 20

typedef int KeyType; /*定义关键字类型*/

typedef char InfoType[10];

typedef struct /*记录类型*/

{ KeyType key; /*关键字项*/

InfoType data; /*其他数据项,类型为InfoType*/

} RecType; /*排序的记录类型定义*/

void BubbleSort1(RecType R[],int n)

{ int i,j,k,exchange;

RecType tmp;

for (i=0;i

{ exchange=0;

for (j=n-1;j>i;j--) /*比较,找出最小关键字的记录*/

if (R[j].key

{ tmp=R[j]; /*R[j]与R[j-1]进行交换,将最小关键字记录前移*/

R[j]=R[j-1];

R[j-1]=tmp;

exchange=1;

}

printf("i=%d: ",i);

for (k=0;k

printf("%d ",R[k].key);

printf("\n");

if (exchange==0) /*中途结束算法*/

return;

}

}

20.

假设图G以采用邻接表存储,编写一个算法实现图G的深度优先遍历算法。void DFS(ALGraph *G,int v)

{ ArcNode *p;

visited[v]=1; /*置已访问标记*/

printf("%d ",v); /*输出被访问顶点的编号*/

p=G->adjlist[v].firstarc; /*p指向顶点v的第一条弧的弧头结点*/ while (p!=NULL)

{ if (visited[p->adjvex]==0) /*若p->adjvex顶点未访问,递归访问它*/ DFS(G,p->adjvex);

p=p->nextarc; /*p指向顶点v的下一条弧的弧头结点*/ }

}

21.

编写算法实现图G的邻接矩阵的存储结构。

MGraph creat_mg()

{ int i,j,k,h;

char b,t;

MGraph mg;

printf("input vex and arc:");

scanf("%d,%d",&i,&j);

mg.n=i; mg.e=j;

for (i=0;i

{ printf("number %d verinfo:",i);

getchar();

scanf("%d",&mg.vexs[i]);}

for (i=0;i

for (j=0;j

mg.edges[i][j]=0;

for (k=1;k<=mg.e;k++)

{ printf("num %d adge:",k);

scanf("%d,%d",&i,&j);

while (i<0||i>mg.n||j<0||j>mg.n)

{ printf("input error,repeat input:");

scanf("%d,%d",&i,&j);

}

printf("the value is:");

scanf("%d",&h);

mg.edges[i][j]=h;

}

return mg;

}

22.

编写程序实现二叉树的先序、中序、后序遍历的递归算法。

void PreOrder(BTNode *b) /*先序遍历的递归算法*/

{ if (b!=NULL)

{ printf("%c ",b->data); /*访问根结点*/

PreOrder(b->lchild);

PreOrder(b->rchild);

}

}

void InOrder(BTNode *b) /*中序遍历的递归算法*/

{ if (b!=NULL)

{ InOrder(b->lchild);

printf("%c ",b->data); /*访问根结点*/

InOrder(b->rchild);

}

}

void PostOrder(BTNode *b) /*后序遍历递归算法*/

{ if (b!=NULL)

{ PostOrder(b->lchild);

PostOrder(b->rchild);

printf("%c ",b->data); /*访问根结点*/

}

}

23.

设计一个算法,对于给定的二叉排序树中的结点*p,找出其左子树中的最大结点和右子树中的最小结点。

KeyType maxnode(BSTNode *p) /*返回一棵二叉排序树中的最大结点*/

{ while (p->rchild!=NULL)

p=p->rchild;

return(p->key);

}

KeyType minnode(BSTNode *p) /*返回一棵二叉排序树中的最小结点*/

{ while (p->lchild!=NULL)

p=p->lchild;

return(p->key);

}

void maxminnode(BSTNode *p)

{ if (p!=NULL)

{ if (p->lchild!=NULL)

printf("左子树的最大结点为:%d\n",maxnode(p->lchild));

if (p->rchild!=NULL)

printf("右子树的最小结点为:%d\n",minnode(p->rchild));

}

}

24.设二叉树以二叉链表为其存储结构,其定义如下:

typedef struct BiTNode

{TElemType data;

struct BiTNode lc,rc; //lc指向左子树

} BiTNode, *BiTree; //rc指向右子树

试编写一个求二叉树上度为2的结点个数的递归算法。

Int count(BiTree T)

{ if (T!=NULL)

{ if (T->lc!=NULL && T->rc!=NULL) n++;

count(T->lc);

count(T->rc);

}

return n;

}

算法设计与分析习题答案1-6章

习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707—1783)提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现 在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次, 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。 编写程序,求n 至少为多大时,n 个“1”组成的整数能被2013整除。 #include using namespace std; int main() { double value=0; 图 七桥问题

for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< using namespace std; int main () { double a,b; double arctan(double x);圣经上说:神6天创造天地万有,第7日安歇。为什么是6天呢?任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间? 由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如: 第一趟:甲,乙过桥且甲回来

《计算机算法设计与分析》习题及答案

《计算机算法设计与分析》习题及答案 一.选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是(A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5.下列算法中通常以自底向上的方式求解最优解的是(B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是( D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是(A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9.下面不是分支界限法搜索方式的是(D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10.下列算法中通常以深度优先方式系统搜索问题解的是(D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法

11.备忘录方法是那种算法的变形。( B ) A、分治法 B、动态规划法 C、贪心法 D、回溯法 12.哈夫曼编码的贪心算法所需的计算时间为(B )。 A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 13.分支限界法解最大团问题时,活结点表的组织形式是(B )。 A、最小堆 B、最大堆 C、栈 D、数组 14.最长公共子序列算法利用的算法是(B)。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.实现棋盘覆盖算法利用的算法是(A )。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是(C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素( D ) A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略(B ) A.递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. (D)是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由( B )设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时,活结点表的组织形式是( A )。

递归算法与递归程序#

一、教学目标 1、知识与技能 (1).认识递归现象。 (2).使用递归算法解决问题往往能使算法的描述乘法而易于表达 (3).理解递归三要素:每次递归调用都要缩小规模;前次递归调用为后次作准备:递归调用必须有条件进行。 (4).认识递归算法往往不是高效的算法。 (5).了解递归现象的规律。 (6).能够设计递归程序解决适用于递归解决的问题。 (7).能够根据算法写出递归程序。 (8).了解生活中的递归现象,领悟递归现象的既有重复,又有变化的 特点,并 且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远,但方法和答案却是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点,综合反映出递归算法的特点,以及递归算法解答某些实践问题通常得很简洁,从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1)了解递归现象和递归算法的特点。

(2)能够根据问题设计出恰当的递归程序。 2、教学难点 (1)递归过程思路的建立。 (2)判断问题是否适于递归解法。 (3)正确写出递归程序。 三、教学环境 1、教材处理 教材选自《广东省普通高中信息技术选修一:算法与程序设计》第四章第五节,原教材的编排是以本节以斐波那契的兔子问题引人,导出递归算法,从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后,让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远,但方法和答案却都是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识 学生已掌握了用计算机解决问题的过程,掌握了程序设计基础,掌握了解析法、穷举法、查找法、排序法设计程序的技巧。 3、硬件要求 建议本节课在多媒体电脑教室中完成,最好有广播教学系统或投影仪,为拓展学习,学生机应允许上互联网。 4、所需软件 学生机要安装VB6.0或以上版本。 5、所需课时 2课时(90分钟)

数值计算方法试题及答案

【 数值计算方法试题一 一、 填空题(每空1分,共17分) 1、如果用二分法求方程043=-+x x 在区间]2,1[内的根精确到三位小数,需对分( )次。 2、迭代格式)2(2 1-+=+k k k x x x α局部收敛的充分条件是α取值在( )。 3、已知?????≤≤+-+-+-≤≤=31)1()1()1(211 0)(2 33x c x b x a x x x x S 是三次样条函数, 则 a =( ), b =( ), c =( )。 4、)(,),(),(10x l x l x l n 是以整数点n x x x ,,,10 为节点的Lagrange 插值基函数,则 ∑== n k k x l 0)(( ), ∑== n k k j k x l x 0 )(( ),当2≥n 时 = ++∑=)()3(20 4x l x x k k n k k ( )。 ; 5、设1326)(2 47+++=x x x x f 和节点,,2,1,0,2/ ==k k x k 则=],,,[10n x x x f 和=?07 f 。 6、5个节点的牛顿-柯特斯求积公式的代数精度为 ,5个节点的求积公式最高代数精度为 。 7、{}∞ =0)(k k x ?是区间]1,0[上权函数x x =)(ρ的最高项系数为1的正交多项式族,其中1)(0=x ?,则?= 1 4)(dx x x ? 。 8、给定方程组?? ?=+-=-2211 21b x ax b ax x ,a 为实数,当a 满足 ,且20<<ω时,SOR 迭代法收敛。 9、解初值问题 00 (,)()y f x y y x y '=?? =?的改进欧拉法 ??? ??++=+=++++)],(),([2),(] 0[111] 0[1n n n n n n n n n n y x f y x f h y y y x hf y y 是 阶方法。

算法设计与分析C++语言描述(陈慧南版)课后答案

第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数,程序1-2的while 循环体做了10次,程序1-3的while 循环体做了14141次(14142-2循环) 若考虑其他语句,则没有这么多,可能就601倍。 第二章 32P 2-8.(1)画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 (2)画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 (3 )画线语句的执行次数为 。O 。 (4)当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++, 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.(1)当1n ≥时,225825n n n -+≤,所以,可选5c =,01n =。 对于0n n ≥,22 ()5825f n n n n =-+≤,所以,22 582()n n n -+=O 。 (2)当8n ≥时,2222 582524n n n n n -+≥-+≥,所以,可选4c =,08n =。对于0n n ≥, 22()5824f n n n n =-+≥,所以,22582()n n n -+=Ω。 (3)由(1)、(2)可知,取14c =,25c =,08n =,当0n n ≥时,有22212582c n n n c n ≤-+≤,所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时,3 log log n n n <<,所以()20log 21f n n n n =+<,3 ()log 2g n n n n =+>。可选21 2 c = ,03n =。对于0n n ≥,()()f n cg n ≤,即()(())f n g n =O 。注意:是f (n )和g (n )的关系。 (2)当4n ≥时,2 log log n n n <<,所以2 2 ()/log f n n n n =<,2 2 ()log g n n n n =≥。可选1c =,04n =。对于0n n ≥,2 ()()f n n cg n <≤,即()(())f n g n =O 。 (3)因为log log(log )()(log ) n n f n n n ==,()/log log 2n g n n n n ==。当4n ≥时,log(log )()n f n n n =≥,

算法设计与分析课后部分习题答案

算法实现题3-7 数字三角形问题 问题描述: 给定一个由n行数字组成的数字三角形,如图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。编程任务: 对于给定的由n行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入: 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n,1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出: 程序运行结束时,将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序: #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in,out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中

for(i=0;i=0;row--)//从上往下递归计算 for(int col=0;col<=row;col++) if(triangle[row+1][col]>triangle[row+1][col+1]) triangle[row][col]+=triangle[row+1][col]; else triangle[row][col]+=triangle[row+1][col+1]; out=fopen("output.txt","w"); fprintf(out,"%d",triangle[0][0]);//将最终结果输出到output.txt中 } 算法实现题4-9 汽车加油问题 问题描述: 一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。并证明算法能产出一个最优解。编程任务: 对于给定的n和k个加油站位置,编程计算最少加油次数。数据输入: 由文件input.txt给出输入数据。第1行有2个正整数n和k ,表示汽车加满油后可行驶nkm,且旅途中有k个加油站。接下来的1行中,有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。第

《递归算法与递归程序》教学设计

递归算法与递归程序 岳西中学:崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素:每次递归调用都要缩小规模;前次递归调用为后次作准备:递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象,领悟递归现象的既有重复,又有变化的特点,并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远,但方法和答案却是完全相同的练习,体会其中的奥妙,加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点,综合反映出递归算法的特点,以及递归算法解答某些实践问题通常得很简洁,从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修:算法与程序设计》第五章,原教材的编排是以本节以斐波那契的兔子问题引人,导出递归算法,从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后,让同学们玩汉诺塔的游戏,导入递归问题,从用普通程序解决斐波那契的兔子问题入手,引导学生用自定义了一个以递归方式解决的函数过程解决问题,同时让同学们做三个递归练习,巩固提高。然后让学生做练习⑵ 和练习

2013华科计算机学院硕士学位研究生复试细则

关于做好2013年计算机学院硕士学位研究生复试、录取工作的通知根据教育部《2013年招收攻读硕士学位研究生管理规定》和《2013年招收攻读硕士学位研究生管理规定实施细则》、《教育部关于加强硕士研究生招生复试工作的指导意见》(教学【2006】4号),学校《关于做好2013年硕士研究生复试、录取工作的通知》,现将我院硕士学位研究生复试、录取工作通知如下。 一、复试、录取工作原则 1、坚持德智体全面衡量、保证质量、科学选拔、择优录取、宁缺勿滥的原则。 2、严格按照初试成绩确定参加复试考生名单并实行差额复试。 3、根据初、复试总成绩决定正式录取名单并公示。 4、坚持公正、公平、公开,各工作环节保证做到有章可循。 二、复试、录取工作组织领导 1、我院成立招生复试工作领导小组,具体领导、组织学院的复试、录取工作。 2、成立复试小组,在学校招生工作领导小组和学院招生复试工作领导小组指导下开展复试工作。 3、成立监察小组,检查我院在招生录取工作中对国家招生政策、法律、制度和纪律的贯彻执行情况,依法对参与招生工作人员履行职责情况进行监督。 三、硕士生入学考试考生参加复试分数线基本要求 1、学术型学位:总分基本要求320分,政治理论50分,英语一50分,数学一80分,计算机学科专业基础综合80分。 2、专业学位:总分基本要求320分,政治50分,英语二50分,数学二80分,计算机学科专业基础综合80分。 3、强军计划:总分基本要求245分,政治40分,英语40分,数学40分,计算机学科专业基础综合40分。 4、少数民族高层次骨干计划:按国家规定执行。 四、复试、录取工作具体办法及时间安排 1、我院复试时间是3月14日至18日。 2、参加复试考生名单见研究生院招生信息网,实行差额复试。我院不再以邮寄等其它方式发复试通知单。 3、我院将按照专业进行复试。参加复试的考生须填报志愿(见附件)、并于3 月12日前发送到指定的邮箱。 4、3月14日,考生凭身份证、准考证,毕业证书原件(非应届生)或学生证(应届生),直接到计算机学院研究生科(南一楼西侧438室)报到。报到时,每位考生需交复试费100元并领取银行记账凭证。考生的资格审查在复试报到时进行,凡未进行资格审查或资格审查未通过的考生一律不予录取。

递归算法和非递归算法的区别和转换

递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题;另外,有些程序设计语言不支持递归,这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法,一种是直接求值,不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。 尾递归是指在递归算法中,递归调用语句只有一个,而且是处在算法的最后。例如求阶乘的递归算法: long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时,是返回到上一层递归调用的下一条语句,而这个返回位置正好是算法的结束处,所以,不必利用栈来保存返回信息。对于尾递归形式的递归算法,可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法: long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句,但各递归调用语句的参数之间没有关系,并且这些递归调用语句都处在递归算法的最后。显然,尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下: int f(int n) {

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-6章

算法设计与分析习题答案1-6章 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler,1707—1783) 提出并解决了该问题。七桥问题是这样描述的:北区 一个人是否能在一次步行中穿越哥尼斯堡(现在东区叫加里宁格勒,在波罗的海南岸)城中全部的七岛区 座桥后回到起点,且每座桥只经过一次,图1.7 南区是这条河以及河上的两个岛和七座桥的草图。请 图1.7 七桥问题将该问题的数据模型抽象出来,并判断此问题是 否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1,一次步行 2,经过七座桥,且每次只经历过一次 3,回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个 奇点的图形。 2(在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n

2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3(设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey) --high; b[low]=b[high]; while (low

算法设计与分析第2版 王红梅 胡明 习题答案

精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题)—1783Leonhard Euler,17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(提 出并解决了该问题。七桥问题是这样描述的:北区一个人是否能在一次步行中穿越哥尼斯堡(现东区在叫加里宁格勒,在波罗的海南岸)城中全部岛区的七座桥后回到起点,且每座桥只经过一次,南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点一次步行1,经过七座桥,且每次只经历过一次2,回到起点3,该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。)用的不是除法而是减最初的欧几里德算法2.在欧几里德提出的欧几里德算法中(即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 .设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档. 精品文档 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey)

ACM经典算法及配套练习题

POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:

算法设计课程习题答案

算法设计课程习题答案 第一章 1-1什么是算法?它与计算过程和程序有什么区别? 算法是指求解一个问题所需要的具体步骤和方法。它是指令的有限序列。算法有一系列明确定义的基本指令序列所描述的,求解特定问题的过程,它能够对合法的输入,在有限时间内产生所要求的输出,取消有穷性限制则是计算过程;而程序是算法的描述。 1-11使用归纳法证明汉诺塔函数的正确性。 用数学归纳法证明汉诺塔函数对任何n (即n 可以是任何正整数)有解。 (1)当盘子数n =1时,只需直接将此盘从A 柱搬到C 柱即可。 (2)现假设n =k 时有解,即可以将k 个盘子(在不违反规则的情况下)从一个源柱,通过一个中间柱移到目的柱上。 (3)现在证明n =k +1时也有解。开始时A 柱上的k +1个盘子可以看成由k 个盘和最底下的一个最大盘组成。根据归纳假设这k 个盘可以(在不违反规则的情况下)通过C 柱移到B 柱上(在这k 个盘的移动过程中,最大盘可以看成不存在)。完成这一大步后,只要将A 柱上的最大盘直接搬到C 柱上。再根据归纳假设B 柱上的这k 个盘可以(在不违反规则的情况下)通过A 柱移到C 柱上。 至此证明结束。 第二章 2-8确定下列各程序段的程序步,确定划线语句的执行次数,计算它们的渐近时间复杂度。 (1)程序步为n log 1+画线语句的执行次数为log n ????。(log )n O 。划线语句的执行次数 应该理解为一个整体。 (2)画线语句的执行次数为 111 (1)(2)16 j n i i j k n n n ===++= ∑∑∑。3 ()n O 。 (3)画线语句的执行次数为 。O 。 (4)当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++, 当n 为偶数时画线语句的执行次数为 2(2)4 n +。2 ()n O 。 2-11设有)(f n 和)(n g 如下所示,分析)(f n 为))((n g O 、))((n g Ω还是))((n g Θ。 (1) 当3n ≥时,3 log log n n n <<,所以 ()20log 21f n n n n =+<, 3()log 2g n n n n =+>。可选 21 2 c = ,03n =。对于0n n ≥,()()f n cg n ≤,即()(())f n g n =O 。注意:是f (n )和g (n )的关系。 (2) 当4n ≥ 时,2 log log n n n <<,所以2 2 ()/log f n n n n =<, 2 2 ()log g n n n n =≥。可选 1c =,04n =。对于 0n n ≥,2 ()()f n n cg n <≤,即 ()(())f n g n =O 。

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分,衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

高中信息技术 算法与程序设计-递归算法的实现教案 教科版

递归算法的实现 【基本信息】 【课标要求】 (三)算法与问题解决例举 1. 内容标准 递归法与问题解决 (1)了解使用递归法设计算法的基本过程。 (2)能够根据具体问题的要求,使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容,本节课是“递归算法的程序实现”,前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习,在学习自定义函数的基础上,学习递归算法的程序实现是自定义函数的具体应用,培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点,在PASCAL和C语言等程序语言的学习过程中,往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲,作者对教材的分析与把握是准确的,思路是清晰的,目标是明确的。』 【学情分析】 教学对象是高中二年级学生,前面学习了程序设计的各种结构,在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力,特别是在学习循环语句的过程中,应用了大量的“递推”算法。前一节课学习了如何自定义函数,在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题,在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推,而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况,对递归算法的本质与特征也分析的很透彻,可以说作者对教学任务的分析是很成功的,接来就要看,在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】

算法设计与分析试卷及答案

湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型:开卷 试卷类型:C 卷 考试时量:120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?,则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中,可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限,这个下限的阶越___________,结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人

递归算法详解

递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构,如果在其定义或说明内部直接或间接地出现对其本身的引 用,或者是为了描述问题的某一状态,必须要用至它的上一状态,而描述上一状态,又必须用到它的上一状态……这种用自己来定义自己的方法,称之为递归或递归定义。在程序设计中,函数直接或间接调用自己,就被称为递归调用。 二、递归的最简单应用:通过各项关系及初值求数列的某一项。 在数学中,有这样一种数列,很难求出它的通项公式,但数列中各项间关系却很简单,于是人们想出另一种办法来描述这种数列:通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式,至少要提供两个信息:一是最前面几项的数值,一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它,应该是: ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值,那么可以很容易地写成这样:

这就是递归函数的最简单形式,从中可以明显看出递归函数都有的一个特点:先处理一 些特殊情况——这也是递归函数的第一个出口,再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模,直到简单到可以作为 特殊情况处理而得出直接的结果,再通过递归关系逐层返回到原来的数据规模,最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时,由于3不是特殊值,因此需要计 算)2(*3f ,但)2(f 是对它自己的调用,于是再计算)2(f ,2也不是特殊值,需要计算 )1(*2f ,需要知道)1(f 的值,再计算)1(f ,1是特殊值,于是直接得出1)1(=f ,返回上 一步,得2)1(*2)2(==f f ,再返回上一步,得62*3)2(*3)3(===f f ,从而得最终解。 用图解来说明,就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为

大学计算机专业课程介绍

大学计算机专业课程介绍 课程名称:面向对象程序设计课程编码:1015501 适用专业:计算机科学与技术 课程内容:本课程主要介绍面向对象程序设计原理和方法,内容有:1.面向对象程序设计概述,数据的抽象和封装,继承性,多态性;2.C++源程序的构成,C++在非面向对象方面的一些新的扩展;3.类和对象;4.派生类与继承;5.多态性等。 教材:《C++面向对象程序设计教程》陈维兴林小茶编著清华大学出版社 课程名称:软件工程课程编码:1020602 适用专业:计算机科学与技术 课程内容:本课程主要介绍软件工程原理,内容有:1.软件危机与软件工程;2.可行性研究;3.需求分析;4.总体设计;5.详细设计;6.编码;7.软件测试;8.维护;9.面向对象方法学引论;10.面向对象分析;11.面向对象设计;12.面向对象的实现等 教材:《软件工程导论》(第三版)张海藩编清华大学出版社 参考书:《实用软件工程》郑人杰等清华大学出版社 课程名称:离散数学课程编码:1014601 适用专业:计算机科学与技术 课程内容:本课程主要介绍离散数学原理,内容有:1.集合论:集合、关系、映射;2.图的基本概念、图的遍历、平面图、有向图;3.代数系统:代数结构,概念、性质、运算,半群、独异点、群与子群,陪集与拉格朗日定理,同态与同构、环;4.数理逻辑:命题逻辑、谓词逻辑等。 教材:《离散数学》第一版郭希娟主编吉林科技出版社 参考书:《离散数学》赵树春辽宁教育出版社 课程名称:计算机组成原理课程编码:1014801 适用专业:计算机科学与技术 课程内容:本课程主要介绍计算机组成原理,内容有:1.计算机系统概论;2.数据化信息编码与数据表示;3.计算机的逻辑部件;4.运算器;5.指令系统;6.中央处理器部件(CPU);7.存储系统;8.辅助存储器;9.输入输出设备;10.输入输出系统;11.计算机系统等。 教材:《计算机组成与结构》(第二版)王爱英主编清华大学出版社 参考书:《计算机组成原理》(第二版)白中英科学技术出版社 课程名称:高级语言及程序设计课程编码:1020501 适用专业:计算机科学与技术 课程内容:本课程主要介绍数据库常用开发工具,内容有:1.C语言概述;2.数据类型、运算符与表达式;3.最简单的C程序设计;4.逻辑运算和判断选取控制;5.循环控制;6.数组;7.函数;8.编译预处理;9.指针;10.结构体与共

相关主题
相关文档 最新文档