第6xx(算法设计)习题练习答案
*6.22二叉树的遍历算法可写为通用形式。例如通用的中序遍历为：
void Inorder(BinTree,T,void(* visit)(DataType x)){
if (T){
Inorder(T->lchild,Visit);//遍历左子树
Visit(T->data);//通过函数指针调用它所指的函数来访问结点
Inorder(T->rchild,Visit);//遍历右子树}}
其中Visit是一个函数指针，它指向形如void f(DataType x)的函数。因此我们可以将访问结点的操作写在函数f中通过调用语句Inorder(root,f)将f的地址传递给Visit,来执行遍历操作。请写一个打印结点数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。
解：
函数如下：
void PrintNode(BinTree T){printf("%c",T->data);}//定义二叉树链式存储结构typedef char DataType;//定义DataType类型
typedef struct node{
DataType data;
struct node *lchild, *rchild;//左右孩子子树
}BinTNode; //结点类型
typedef BinTNode *BinTree ;//二叉树类型
void Inorder(BinTree T,void(* Visit)(DataType x)){if(T){Inorder(T->lchild,Visit);//遍历左子树
Visit(T->data); //通过函数指针调用它所指的函数访问结点
Inorder(T->rchild,Visit);//遍历右子树}}
6.23以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。
解：
(1)求结点数的递归定义为：
若为空树，结点数为0
若只有根结点，则结点数为1；
否则，结点数为根结点的左子树结点数+右子树结点数+1
(2)求xx数的递归定义为：
若为空树，xx数为0
若只有根结点，则xx数为1；
否则，叶子数为根结点的左子树叶子数+右子树叶子数
typedef char DataType;//定义DataType类型
typedef struct node{
DataType data;
struct node *lchild, *rchild;//左右孩子子树
}BinTNode; //结点类型
typedef BinTNode *BinTree ;//二叉树类型
int Node(BinTree T)
{//算结点数
if (T->lchild==NULL)&&(T->rchild==NULL)
return 1;
else return Node(T->lchild)+Node(T->rchild)+1;
else return 0;}int Leaf(BinTree T)
{ //算xx数
if(T)
if (T->lchild==NULL)&&(T->rchild==NULL)
return 1;
else return Leaf(T->lchild)+Node(T->rchild);
else return 0;}
6.24以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。
解：
(1)根据递归定义：
二叉树的高度为：
当为空树时，高度为0；
当只有一个结点时，高度为1；
其他情况：
高度为max(根的左子树高度，根的右子树高度)+1
int Height(BinTree T){int hl,hr;
{//非空树
if(t->lchild==NUll)&&(t->rchild==NULL)//只含一个根结点
return 1;
else {hl=height(t->lchild);//根的左子树高度
hr=height(t->rchild);//根的右子树高度
if (hl>=hr)
return hl+1;
else return h2+1;}}
else return 0;}(2)要求二叉树的宽度的话，则可根据树的高度设置一个数组temp。temp[i]用于存放第i层上的结点数(即宽度)。在访问结点时,把相应计算该结点下一层的孩子数并存入相应数组元素中，遍历左子树后向上返回一层计算右子树的宽度，并取出最大的一个数组元素作为树的宽度。
#define M 10 //假设二叉树最多的层数
int Width(BinTree T){int static n[M];//向量存放各层结点数
int static i=1;
int static max=0;//最大宽度
if(T){if(i==1) //若是访问根结点{n[i]++; //第1层加1
i++; //到第2层
if(T->lchild)//若有左孩子则该层加1
n[i]++;
if(T->rchild)//若有右孩子则该层加1
n[i]++;}else
{ //访问xx结点
i++; //下一层结点数
if(T->lchild)
n[i]++;
if(T->rchild)
n[i]++;}if(max Width(T->lchild);//遍历左子树 i--; //往上退一层 Width(T->rchild);//遍历右子树}return max; }//算法结束 6.25以二叉链表为存储结构，写一算法交换各结点的左右子树。 答： 要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。 void ChangeBinTree(BinTree *T) { //交换子树 if(*T) { //这里以指针为参数使得交换在实参的结点上进行后序遍历 BinTree temp; ChangeBinTree(&(*T)->lchild); ChangeBinTree(&(*T)->rchild); temp=(*T)->lchild; (*T)->lchild=(*T)->rchild; (*T)->rchild=temp;}} 6.26以二叉链表为存储结构，写一个拷贝二叉树的算法void CopyTree(BinTree root,BinTree *newroot),其中新树的结点是动态申请的，为什么newroot要说明为BinTree型指针的指针? 解： 因为调用函数只能进行值传递,当返回类型为void时，就必须把实参的地址传给函数，否则函数不会对实际参数进行任何操作,也就得不到所需结果了。所以，newroot要说明为BinTree型指针 void CopyTree(BinTree root,BinTree *newroot) { //拷贝二叉树 if(root)//如果结点非空 { //按前序序列拷贝 *newroot=(BinTNode *)malloc(sizeof(BinTNode));//生成新结点 (*newroot)->data=root->data;//拷贝结点数据 CopyTree(root->lchild,&(*newroot)->lchild);//拷贝左子树 CopyTree(root->rchild,&(*newroot)->rchild);//拷贝右子树}else //如果结点为空 *newroot=NULL;//将结点置空}6.27以二叉链表为存储结构，分别写出在二叉树中查找值为x的结点及求x所在结点在树中层数的算法。 解： 根据上几题的算法可以得出本题的算法如下： #define M 10 //假设二叉树最多的层数 BinTree SearchBTree(BinTree *T,DataType x) {//以前序遍历算法查找值为x的结点 if(*T){if((*T)->data==x )return *T; SearchBTree(&(*T)->lchild,x); SearchBTree(&(*T)->rchild,x);}} int InLevel(BinTree T,DataType x){int static l=0;//设一静态变量保存层数 if(T){if(l==0)//若是访问根结点{l++;//第1层 if(T->data==x)return l; if(T->lchild||T->rchild) l++;//若根有子树，则层数加1}else { //访问xx结点 if(T->data==x)return l; if(T->lchild||T->rchild) l++;//若该结点有子树，则层数加1 else return 0;}InLevel(T->lchild,x);//遍历左子树 InLevel(T->rchild,x);//遍历右子树}} 6.28一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。 解： 以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放的，可以根据课本第74页的内容设计出算法： typedef char DataType;//设结点数据类型为char #define M 100//设结点数不超过100 typedef DataType BinTree[M]; void Preorder(BinTree T) { //前序遍历算法 int n=T[0]; int p[M];//设置一队列存放结点值 int i,j; for(i=1;i<=n;i++){if (i==1)//根结点 j=1; else if(2*j<=n)//左子树 j=2*j; else if(j%2==0&&j j=j+1; else if(j>1)//双亲之右兄弟 j=j/2+1; p[i]=T[j];//入队 printf("%c",p[i]);//打印结点值}} 6.29以二叉链表为存储结构，一算法对二叉树进行层次遍历(层次遍历的定义见6.13).提示： 应使用队列来保存各层的结点。 答： #define M 100 //假设结点数最多为100 typedef char DataType;//队列结点值类型typedef struct//定义一个队列{int front; int rear; int count; DataType data[M]; }QBTree; static QBTree Q;//设一全局静态变量保存遍历结果void Levelorder(BinTree T) {//层次遍历 if(T){if(QueEmpty(&Q)) { //根结点及子树结点入队 EnQue(&Q,T->data); if(T->lchild) EnQue(&Q,T->lchild->data); if(T->rchild) EnQue(&Q,T->rchild->data);}else { //xx结点入队 if(T->lchild) EnQue(&Q,T->lchild->data); if(T->rchild) EnQue(&Q,T->rchild->data);}Levelorder(T->lchild);//遍历左子树 Levelorder(T->rchild);//遍历右子树}} 6.30以二叉链表为存储结构，写一算法用括号形式(key LT,RT)打印二叉树，其中key是根结点数据，LT和RT是括号形式的左子树和右子树。并且要求空树不打印任何信息，一个结点x的树的打印形式是x而不是(x,)的形式。 答： 算法如下： void PrintTree(BinTree T) {//打印二叉树(以前序遍历实现) if(T)//非空树{printf("%c",T->data);//打印结点值 if(T->lchild||T->rchild) printf("(");//打印括号 PrintTree(T->lchild);//打印左子树 if(T->lchild&&T->rchild) printf(",");//若存在两棵子树打印逗号 PrintTree(T->rchild);//打印右子树 if(T->lchild||T->rchild) printf(")");}} void PrintTree1(BinTree T) { //由于题目存在两义性，所以这里另作了一个打印算法打印二叉树(以前序遍历实现)if(T)//非空树{printf("(%c",T->data);//打印括号和结点值 PrintTree1(T->lchild);//打印左子树 if(T->lchild&&T->rchild) printf(","); PrintTree1(T->rchild);//打印右子树 printf(")");}} 6.31以线索链表作为存储结构。分别写出在前序线索树中查找给定结点*p 的前序后继，以及在后序线索树中查找*p的后序前趋的算法。 解： 算法如下： BinThrNode * SearchPostInPre(BinThrNode *p) {//查找结点*p的前序xx if(p){if(p->rtag==Link)&&(p->ltag==link)//当左、右都为孩子指针 return p->lchild;//*p的前序后继为左孩子 else return p->rchild;}} BinThrNode *SearchPreInPost(BinThrNode *p) { //查找*p结点的后序前趋 if(p){if(p->ltag==thread)||(p->rtag==thread)//当有左线索或无有孩子 return p->lchild;//*p的后续前趋为p->lchild else return p->rchild;}} 6.32完成6.6.1节算法CreatHuffmanTree中调用的三个函数： InitHuffmanTree,InputWeight 和SelectMin。解： 整个程序如下： #define n 7 //叶子数目,根据实际需要定义 #define m 2*n-1 //结点数目 typedef struct {float weight; int lchild,rchild,parent;//左右孩子及双亲指针 }HTNode; typedef HTNode HuffmanTree[m];//是向量类型的void InitHuffmanTree(HuffmanTree T) {//初始化 int i; for (i=0; i T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1;}} void InputWeight(HuffmanTree T) {//输入权值 float w; int i; for (i=0; i ",i+1); scanf("%f",&w); T[i].weight=w;}} void SelectMin(HuffmanTree T, int i, int *p1,int *p2) {//选择两个小的结点 float min1=999;//预设两个值 float min2=999;//并使它大于可能出现的最大权值 int j; for (j=0;j<=i;j++) if(T[j].parent==-1) if(T[j].weight *p2=*p1; *p1=j;}else if(T[j].weight {min2=T[j].weight;//改变次小权及位置 *p2=j;} }//选择结束 习题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 for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< 《计算机算法设计与分析》习题及答案 一．选择题 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 ）。 设计学概论试卷答案A卷（仅供内部人员专用，禁止外传）一．填空题 1. 文艺复兴；绘画雕塑建筑 2.. 功能性审美性 3. 借用解构装饰参照创造 4. 艺术；实体虚体技术经济；美学 5. 生产技术 二．名词解释 美学： 美学是以人类审美为自身特殊领域，以审美活动为具体研究对象，通过探讨审美活动中起主导作用的人的精神世界，来追踪、建构人类审美价值体系的人文学科。[1] 美学是以对美的本质及其意义的研究为主题的学科。美学是哲学的一个分支。研究的主要对象是艺术，但不研究艺术中的具体表现问题，而是研究艺术中的哲学问题，因此被称为“美的艺术的哲学”。美学的基本问题有美的本质、审美意识同审美对象的关系等。 艺术； 我们将“艺术”定义为人类通过借助特殊的物质材料与工具，运用一定的审美能力和技巧，在精神与物质材料、心灵与审美对象的相互作用下，进行的充满激情与活力的创造性劳动。可以说它是一种精神文化的创造行为，是人的意识形态和生产形态的有机结合体。 设计； 设计是把一种计划、规划、设想通过视觉的形式传达出来的活动过程。 人类通过劳动改造世界，创造文明，创造物质财富和精神财富，而最基础、最主要的创造活动是造物。设计便是造物活动进行预先的计划，可以把任何造物活动的计划技术和计划过程理解为设计。 随着现代科技的发展、知识社会的到来、创新形态的嬗变，设计也正由专业设计师的工作向更广泛的用户参与演变，以用户为中心的、用户参与的创新设计日益受到关注，以用户体验 为核心的设计的创新2.0模式正在逐步形成。 （这三个名词的解释，大家还可以上网去找找，也许会有更好的答案） 三．简答题 1.作为设计师，你如何看待设计与艺术的关系？ 艺术是指文学、绘画、音乐、舞蹈、戏剧、电影、雕塑、建筑等，是社会意识形态的一部分，它是以生动的、可感觉的形象或声音来反映现实、复制现实，并以此提高人们认识、把握美的能力，艺术建立的是美学。艺术意识就是欣赏艺术美的总和的意识活动，它以情感为中介、核心，把感知、理解、想象、认知等心理因素融合成一种独特的活动形式。艺术思维属于形象思维，具有很强的整体性。 设计也是一门艺术，和绘画相比，绘画是将画家的思维表现在画面上，让别人去读画家的思维。 设计呢，设计是要将客户的主张、思想，以客户想要表现的形式表现出来；就是让客户的受众去从你的设计中读到客户的主张和思想。 R语言-决策树算法 决策树算法 决策树定义 首先，我们来谈谈什么是决策树。我们还是以鸢尾花为例子来说明这个问题。 观察上图，我们判决鸢尾花的思考过程可以这么来描述：花瓣的长度小于 2.4cm的是setosa(图中绿色的分类)，长度大于1cm的呢?我们通过宽度来判别，宽度小于1.8cm的是versicolor(图中红色的分类)，其余的就是 virginica(图中黑色的分类) 我们用图形来形象的展示我们的思考过程便得到了这么一棵决策树： 这种从数据产生决策树的机器学习技术叫做决策树学习, 通俗点说就是决策树，说白了，这是一种依托于分类、训练上的预测树，根据已知预测、归类未来。 前面我们介绍的k-近邻算法也可以完成很多分类任务，但是他的缺点就是含义不清，说不清数据的内在逻辑，而决策树则很好地解决了这个问题，他十分好理解。从存储的角度来说，决策树解放了存储训练集的空间，毕竟与一棵树的存储空间相比，训练集的存储需求空间太大了。 决策树的构建 一、KD3的想法与实现 下面我们就要来解决一个很重要的问题：如何构造一棵决策树?这涉及十分有趣的细节。 先说说构造的基本步骤，一般来说，决策树的构造主要由两个阶段组成:第一阶段，生成树阶段。选取部分受训数据建立决策树，决策树是按广度优先建立直到每个叶节点包括相同的类标记为止。第二阶段，决策树修剪阶段。用剩余数据检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树进行修剪直到建立一棵正确的决策树。这样在决策树每个内部节点处进行属性值的比较，在叶节点得到结论。从根节点到叶节点的一条路径就对应着一条规则，整棵决策树就对应着一组表达式规则。 问题：我们如何确定起决定作用的划分变量。 我还是用鸢尾花的例子来说这个问题思考的必要性。使用不同的思考方式，我们不难发现下面的决策树也是可以把鸢尾花分成3类的。 为了找到决定性特征，划分出最佳结果，我们必须认真评估每个特征。通常划分的办法为信息增益和基尼不纯指数，对应的算法为C4.5和CART。 关于信息增益和熵的定义烦请参阅百度百科，这里不再赘述。 直接给出计算熵与信息增益的R代码： 《临床科研设计》模拟试题 —省住院医师培训必修课统一考试 试题1： 一、单项选择题（10分） 1、在下列研究设计方法中，按临床科研设计论证强度排列，一般认为最强的是：C A、前瞻性队列研究 B、病例对照研究 C、随机对照研究 D、横断面调查 2、在科研选题、立题时，不必考虑下列哪项因素：C A、可行性 B、价值和水平 C、临床阳性结果 D、临床意义 3、在选研究方法时应当考虑的因素中，最重要的是：A A、科研目的 B、可行性 C、样本量 D、创新性 4、研究设计中要估计样本量，主要是因为：B A、样本量过小容易犯第二类错误 B、样本量过小容易犯第一类错误 C、样本量过大会影响结果的准确性 D、样本越大，可行性越差 5、研究对象分组方法设计最重要的指导思想是：A A、两组研究前的基线状况一致 B、两组研究条件要一致 C、两组分组方法要一致 D、两组研究对象年龄、性别要一致 6、分层分析可控制 C A、选择偏倚 B、信息偏倚 C、混杂偏倚 D、信息偏倚和混杂偏倚 7、用住院病人作研究对象容易发生：A A、选择偏倚 B、信息偏倚 C、混杂偏倚 D、选择偏倚和混杂偏倚 8、采用拉丁方设计具有如下要求，但不包括：D B A、三个研究因素 B、水平数可以不等 C、利用标准方 D、不考虑交互作用 9、三个因素各两水平，若采用析因分析设计时，至少要设的组数：B C A、5 B、6 C、8 D、9 10、被认为是论文核心部分的是：B A、材料与方法 B、结果 C、讨论 D、摘要 二、填空题（10分） 1、临床科研选题原则有：创新性原则、科学性原则、可行性原则、需要性原则、效益性原则。 2、临床科研设计的原则有：随机化原则、盲法原则、对照原则、重复原则。 3、临床科研设计的要素是：处理因素、受试对象、试验效应。 三、简答题（28分） 1、简述临床科研的基本步骤。五步骤：科研选题，科研设计，实施方法，设计分析和总结归纳。 2、为什么说偏倚是系统误差，它具有哪些基本属性？系统误差是在调查或测量时，由于某种确定的原因，如实验方法不当、仪器不准等原因造成的，使调查结果偏大或偏小。偏倚是指医学研究中的系统误差以及结果解释、推论中的片面性，使得研究结果与真实性值出现偏倚性的差异。按偏倚的性质分三大类：选择偏倚、信息偏倚、混杂偏倚 3、简述随机化抽样的常用类型以及实施随机化的意义。常用类型有单纯随机抽样、系统随机抽样、分层抽样和整群抽样方法。意义：随机化抽样的最大优点是在根据样本资料推论总体时，可用概率的方式客观地测量推论值的可靠程度，从而使这种推论建立在科学的基础上。 4、常用的诊断试验真实性的评价指标有哪些，各评价的是诊断试验的哪方面？一灵敏度。灵敏度表示试验方法对疾病的检出能力。二特异度。特异度表示试验方法对无病的检出能 第一章 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 第一章导论：设计学的研究范围及其现状 一、选择题 1．二战期间发展起来的( ) ，科学的考虑了人的舒适性和工作的效率。 1设计文化学2人机工程学3设计美学4设计史学 2．( )是近现代旨在保存自然资源、防止工业污染破坏生态平衡的一场设计运动。 1波普运动2新艺术运动 3 绿色设计运动 4 装饰艺术运动 3．按照( )的说法：“普通符号科学——它有各种名称：符号学(semiotics，semiology) 或语义学(semasiology) ，这些术语来自希腊语的sema( 符号) 。” 1 毕加索 2 贡布里希3索特萨斯4莫里斯 4．( )理论自60年代后期由法国哲学家德里达在其《论语法学》一书中确立。 1解构主义 2 抽象主义 3 立体主义4符号学 5．( )试图通过所领导的工艺美术运动提高工艺的地位，用手工制作来反对机器和工业化。 1格罗佩斯2贡布里希 3 米斯4莫里斯 二、简答题 窗体底端 1．简述设计的目标 设计就是设想、运筹、计划与预算，它是人类为实现某种特定目的而进行的创造性活动。设计的终极目标永远是功能性与审美性。 2．简述设计学的划分 我们一般将设计学划分为设计史、设计理论与设计批评三个分支。通过学科方向的确定，以及对相关学科的认识，我们便能理解研究设计史必然要研究科技史与美术史，研究设计理论必然要研究相关的工程学、材料学和心理学，研究设计批评必然要研究美学、民俗学和伦理学的理论要求。 3．简述当今设计学研究的现状 设计学研究是一个开放的系统，除了从自己的种学科——美术学那里继承了一套较完善的体系之外，它还要广泛地从那些相关的学科，如哲学、经济学、社会学、心理学、建筑学、机械学那里获得启发，借用词汇，吸收观点，消化方法。这便是当今设计学研究的现状。 4．简述设计学各领域的代表人物与代表著作 曾任英国美术史协会主席的佩夫斯纳爵士，在其《社会美术史》研究中，就已经孕育了对现代设计的倡导；他在1936年出版的《现代运动的先锋》更是现代设计的宣言而为西方的所有设计专业学生所必读。德国建筑家、理论家森珀是将达尔文进化论运用于美术史研究的第一人。他在1860年至1863年期间出版了极富思辨性的三卷本巨著《工艺美术与建筑的风格》，着重探讨装饰与功能之间的适当联系。奥地利美术史学家阿洛伊斯?里格尔，于1893年出版了被认为是有关装饰艺术历史的最重要的著作——《风格问题》5．简述当代西方设计思潮 1．符号学理论。根据符号学的理论，人类的思维和语言交往都离不开符号，而人的意识过程就是一个符号化过程，思维无非是对符号的一种组合、转换、再生的操作过程。符号是人类认识事物的媒介，符号又是表达思想情感的物质手段，简言之，人类的意识领域就是一个符号的世界。 2．结构主义。结构主义理论是一种社会学方法，其目的在于给人们提供理解人类思维活动的手段。 3．解构方法。按照解构主义理论，我们可以运用科学的符号学原理来分析图像，并且分别说明其视觉的、文化的、以及语言的意义，这一分析过程被解构主义理论家称之为解码(Decoding)。 4．混沌理论。混沌理论是要向我们说明，我们才刚刚开始理解自然界的复杂性，即自然现象及其事件的连锁反应。 5．绿色设计。起自于旨在保存自然资源、防止工业污染破坏生态平衡的一场运动，虽然它迄今仍处于萌芽阶段，但却已成为一种极其重要的新趋向。 CHAID算法（Chi-Square Automatic Interaction Detection） CHAID提供了一种在多个自变量中自动搜索能产生最大差异的变量方案。 不同于C＆R树和QUEST节点，CHAID分析可以生成非二进制树，即有些分割有两个以上的分支。 CHAID模型需要一个单一的目标和一个或多个输入字段。还可以指定重量和频率领域。 CHAID分析，卡方自动交互检测，是一种用卡方统计，以确定最佳的分割，建立决策树的分类方法。 1.CHAID方法（卡方自动交叉检验） CHAID根据细分变量区分群体差异的显著性程度（卡方值）的大小顺序，将消费者分为不同的细分群体，最终的细分群体是由多个变量属性共同描述的，因此属于多变量分析。 在形式上，CHAID非常直观，它输出的是一个树状的图形。 1.它以因变量为根结点，对每个自变量（只能是分类或有序变量，也就是离散性的，如果是连续 变量，如年龄，收入要定义成分类或有序变量）进行分类，计算分类的卡方值(Chi-Square-Test)。如果 几个变量的分类均显著，则比较这些分类的显著程度（P值的大小），然后选择最显著的分类法作为子节点。 2.CHIAD可以自动归并自变量中类别，使之显著性达到最大。 3.最后的每个叶结点就是一个细分市场 CHAID 自动地把数据分成互斥的、无遗漏的组群,但只适用于类别型资料。 当预测变量较多且都是分类变量时，CHAID分类最适宜。 2.CHAID分层的标准：卡方值最显著的变量 3.CHAID过程：建立细分模型，根据卡方值最显著的细分变量将群体分出两个或多个群体，对 于这些群体再根据其它的卡方值相对最显著的细分变量继续分出子群体，直到没有统计意义上显著的细分变量可以将这些子群体再继续分开为止。 4.CHAID的一般步骤 -属性变量的预处理 -确定当前分支变量和分隔值 属性变量的预处理： -对定类的属性变量，在其多个分类水平中找到对目标变量取值影响不显著的分类，并合并它们； -对定距型属性变量，先按分位点分组，然后再合并具有同质性的组； -如果目标变量是定类变量，则采用卡方检验 -如果目标变量为定距变量，则采用F检验 （统计学依据数据的计量尺度将数据划分为三大类，即定距型数据（Scale）、定序型数据（Ordinal）和定类型数据（Nominal）。定距型数据通常指诸如身高、体重、血压等 的连续性数据，也包括诸如人数、商品件数等离散型数据；定序型数据具有内在固有大 小或高低顺序，但它又不同于定距型数据，一般可以数值或字符表示。如职称变量可以 有低级、中级和高级三个取值，可以分别用1、2、3等表示，年龄段变量可以有老、中、青三个取值，分别用A、B、C表示等。这里无论是数值型的1、2、3还是字符型的A、B、C，都是有大小或高低顺序的，但数据之间却是不等距的。因为低级和中级职称之间的差距与中级和高级职称之间的差距是不相等的；定类型数据是指没有内在固定大小或高低 顺序，一般以数值或字符表示的分类数据。） F检验：比较两组数据的方差2s， 2 2 s F s 大 小 ，假设检验两组数据没有显著差异，F 现代机械设计方法试题-----复习使用 考试形式：闭卷（带计算器与尺） 一、图解题 1．图解优化问题：min F (X)=(x 1-6)2+(x 2-2)2 s ．t ． 0．5x 1+x 2≤4 3x 1+x 2≤9 x 1+x 2≥1 x 1≥0, x 2≥0 求最优点和最优值。 最优点就是切点坐标：X1=2.7,x2=0.9 最优值：12.1【带入公式结果】 2．若应力与强度服从正态分布，当应力均值μs 与强度均值μr 相等时，试作图表示两者的干涉情况，并在图上示意失效概率F 。 参考解： 3 ．已知某零件的强度r 和应力s 均服从正态分布，且μr >μs ,σr <σs ，试用图形表示强度r 和应力s 的分布曲线，以及该零件的分布曲线和可靠度R 的范围。 参考解： f (s) f (r) Y >0安全状态；Y <0安全状态；Y =0极限状态 f (Y) 强度r 与应力s 的差可用一个多元随机函数Y =r -s =f (x 1,x 2,…,x n )表示，这又称为功能函数。 设随机函数Y 的概率密度函数为f (Y )，可以通过强度r 与应力s 的概率密度函数为f (r )和f (s )计算出干涉变量Y =r-s 的概率密度函数f (Y )，因此零件的可靠度可由下式求得： Y Y f Y p R ?∞ =>=0d )( )0( 从公式可以看出，因为可靠度是以Y 轴的右边对f (Y )积分，因此可靠度R 即为图中Y 轴右边的阴影区域。而失效概率F =1-R ，为图中Y 轴左边的区域。 4．用图表示典型产品的失效率与时间关系曲线，其失效率可以分为几个阶段，请分别对这几个阶段进行分析。 失效率曲线：典型的失效率曲线。失效率（或故障率）曲线反映产品总 体寿命期失效率的情况。图示13.1-8为失效率曲线的典型情况，有时形象地 称为浴盆曲线。失效率随时间变化可分为三段时期： (1) 早期失效期，失效率曲线为递减型。产品投于使用的早期，失效率较高 而下降很快。主要由于设计、制造、贮存、运输等形成的缺陷，以及调试、 跑合、起动不当等人为因素所造成的。当这些所谓先天不良的失效后且运转 也逐渐正常，则失效率就趋于稳定，到t 0时失效率曲线已开始变平。t 0以前 称为早期失效期。针对早期失效期的失效原因，应该尽量设法避免，争取失 效率低且t 0短。 (2) 偶然失效期，失效率曲线为恒定型，即t 0到t i 间的失效率近似为常 数。失效主要由非预期的过载、误操作、意外的天灾以及一些尚不清楚的偶 然因素所造成。由于失效原因多属偶然，故称为偶然失效期。偶然失效期是 能有效工作的时期，这段时间称为有效寿命。为降低偶然失效期的失效率而 增长有效寿命，应注意提高产品的质量，精心使用维护。加大零件截面尺寸 可使抗非预期过载的能力增大，从而使失效率显著下降，然而过分地加大， 将使产品笨重，不经济，往往也不允许。 (3) 耗损失效期，失效率是递增型。在t 1以后失效率上升较快，这是由于产品已经老化、疲劳、磨损、蠕变、腐蚀等所谓有耗损的原因所引起的，故称为耗损失效期。针对耗损失效的原因，应该注意检查、监控、预测耗损开始的时间，提前维修，使失效率仍不上升，如图13.1-8中虚线所示，以延长寿命不多。当然，修复若需花很大费用而延长寿命不多，则不如 报废更为经济。 第一章导论:设计学的研究范围及其现状 1.简述设计的目标 设计就是设想、运筹、计划与预算,它是人类为实现某种特定目的而进行的创造性活动。设计的终极目标永远是功能性与审美性。 2.简述设计学的划分 我们一般将设计学划分为设计史、设计理论与设计批评三个分支。通过学科方向的确定,以及对相关学科的认识,我们便能理解研究设计史必然要研究科技史与美术史,研究设计理论必然要研究相关的工程学、材料学和心理学,研究设计批评必然要研究美学、民俗学和伦理学的理论要求。 3.简述当今设计学研究的现状 设计学研究是一个开放的系统,除了从自己的种学科——美术学那里继承了一套较完善的体系之外,它还要广泛地从那些相关的学科,如哲学、经济学、社会学、心理学、建筑学、机械学那里获得启发,借用词汇,吸收观点,消化方法。这便是当今设计学研究的现状。 4.简述设计学各领域的代表人物与代表著作 曾任英国美术史协会主席的佩夫斯纳爵士,在其《社会美术史》研究中,就已经孕育了对现代设计的倡导;他在1936年出版的《现代运动的先锋》更是现代设计的宣言而为西方的所有设计专业学生所必读。德国建筑家、理论家森珀是将达尔文进化论运用于美术史研究的第一人。他在1860年至1863年期间出版了极富思辨性的三卷本巨著《工艺美术与建筑的风格》,着重探讨装饰与功能之间的适当联系。奥地利美术史学家阿洛伊斯?里格尔,于1893年出版了被认为是有关装饰艺术历史的最重要的著作——《风格问题》 5.简述当代西方设计思潮 1.符号学理论。根据符号学的理论,人类的思维和语言交往都离不开符号,而人的意识过程就是一个符号化过程,思维无非是对符号的一种组合、转换、再生的操作过程。符号是人类认识事物的媒介,符号又是表达思想情感的物质手段,简言之,人类的意识领域就是一个符号的世界。 2.结构主义。结构主义理论是一种社会学方法,其目的在于给人们提供理解人类思维活动的手段。 3.解构方法。按照解构主义理论,我们可以运用科学的符号学原理来分析图像,并且分别说明其视觉的、文化的、以及语言的意义,这一分析过程被解构主义理论家称之为解码(Decoding)。 4.混沌理论。混沌理论是要向我们说明,我们才刚刚开始理解自然界的复杂性,即自然现象及其事件的连锁反应。 5.绿色设计。起自于旨在保存自然资源、防止工业污染破坏生态平衡的一场运动,虽然它迄今仍处于萌芽阶段,但却已成为一种极其重要的新趋向。 6.信息技术。对于设计学而言,计算机技术和通信技术这两大领域的发展,已经改变了20世纪以来设计的过程和生产。 三、思考题 1.设计学是怎样作为一门独立的学科出现的 2.设计史、设计理论与设计批评对于设计实践分别具有怎样的意义 3.如何看待中国古代设计思想对现代设计的意义 第二章设计的多重特征 1.设计的基本特征是什么 设计是一种产品生产,这种产品具有物理的属性,可批量生产,它满足商品的价值规律,反映着 3.1 分类与决策树概述 3.1.1 分类与预测 分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。这些过程的一个共同特点是：根据数据的某些属性，来估计一个特定属性的值。例如在信用分析案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值，来估计该用户“信用度”属性的值应该取“好”还是“差”，在这个例子中，所研究的属性“信用度”是一个离散属性，它的取值是一个类别值，这种问题在数据挖掘中被称为分类。 还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数，这里所研究的属性“大盘指数”是一个连续属性，它的取值是一个实数。那么这种问题在数据挖掘中被称为预测。 总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时，这就是预测。 3.1.2 决策树的基本原理 1.构建决策树 通过一个实际的例子，来了解一些与决策树有关的基本概念。 表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本，每一列是一个属性（字段）。这里把这个表记做数据集D。 银行需要解决的问题是，根据数据集D，建立一个信用等级分析模型，并根据这个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时，依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级，以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。在这个案例中，研究的重点是“信用等级”这个属性。给定一个信用等级未知的客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这3个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数据集D中“信用等级”属性的全部取值就构成了类别集合：Class={“优”， 2016新课程教学设计一试题及答案 一. 单选题（共20题,共40分） 1. ( )课程的过程性评价主要考查学生学习本学科的态度、参与课堂活动的积极程度、独立思考主动探究的能力、与他人合作交流情况、完成书面作业情况、实践操作能力、综合运用知识的能力。（2 2. 知识存在于个人和群体的行动中，随着个人参与到新的情境中并在新情境中进行协调，知识产生了，知识和能力的发展，就像语言的发展，发生于真实情境中不断进行的利用知识的活动中。这是 3. （）是对需要得到帮助的学生与学习活动互动的方式做出决策，它涉及动机激发技术、个 4. 通过观察他人在一定情境的行为，能够有效地促进学习活动的发生。这是( )的观点。（2 5. 学校意义上的“教学”可以理解为：教学是以课程内容为中介，学生在教师的指导下共同开展的 6. （）涉及设计教学活动的决策，包括对教学活动的呈现类型、程序及其结构，学生练习 7. 讲和读在教学活动中是交叉进行的，同时可能还穿插着练习活动。教学中既有教师的讲和读，也 8. （）是对信息传递给学生的方式所做出的决策，对教学媒体的选择有较强的指导作用。（2分） 9. 一位心理学家将儿童认知发展划分为4个阶段:感知运动阶段(0 ^-2岁);前运算阶段(2^-7岁); 10. ( )，教学媒体有助于传递教学信息标准化，使教学活动生动有趣，有效的运用学习理论 11. 为了把一个任务迁移到另一个任务，学生需要对技能迁移进行练习。如果学生从来就没有练习 12. 一位心理学家认为，在学习者尚未表现出足够的学习动机的情况之下，没有必要推迟学习活动。对于那些学习动机不强的学习者来说，最好的办法就是通过有效的教学，使他们尝到学习的甜头，而这有 14. （）是列出一系列相关的问题要求媒体选择者回答，通过对这些问题的逐一回答，来比较清楚地发现适用于一定教学目标(或一定教学情景)的媒体。问题的提出可根据教学媒体的选择原则给出。（2 15. 在当代心理学家凯斯提出的与儿童认知加工有效性相关的变化机制中，将个体的心理区域分成 17. （）认为，知识是分布式存在的，即知识普遍存在于学习者、日常生活工具、媒体、教材与文化脉络中。或者说，知识的意义分散在人们所处的情境中，是人与情境交互作用的产物，因而，是无法从情境中单独隔离出来的。（2分） 算法设计与分析习题答案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 精品文档习题胡明-版)-王红梅-算法设计与分析(第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 智慧树知到《设计学概论》章节测试【完整 答案】 智慧树知到《设计学概论》章节测试答案 第一章 1、最著名的结构主义倡导者是法国人类学家是()。 莱维?施特劳斯 福柯 罗兰?巴特 索绪尔 答案:莱维?施特劳斯 2、中国工业设计协会成立于()年? 1987年 1988年 1989年 1990年 答案:1987年 3、英国著名艺术评论家和美学家()提出了“艺术是有意味的形式”的著名论点 罗杰?弗莱 亚里士多德 苏格拉底 克莱夫?贝尔 答案:克莱夫?贝尔 4、()从一开始就将艺术因素纳入整个设计教育结构体系中,将艺术与设计作为一个不可分割的有机体。 包豪斯 乌尔姆设计学院 德国工业同盟 荷兰风格派 答案:包豪斯 5、()是先秦最重要的设计著作。 《考工记》 《老子》 《墨子》 《孟子》 答案:《考工记》 6、设计就是设想、运筹、计划与预算，它是人类为实现某种特定目的而进行的创造性活动。设计的终极目的就是改善人的环境、工具以及人自身。 对 错 答案:对 7、混沌理论是要向我们说明，我们才刚刚开始理解自然界的复 杂性，即自然现象及其事件的连锁反应。 对 错 答案:对 8、我们一般将设计学划分为设计史、设计理论与()三个分支。 设计批评 设计评价 设计思维 设计美学 答案:设计批评 9、明代徐光启的《农政全书》与《齐民要术》、()一起被视为我国农业著述中的不朽丰碑。 《天工开物》 《汜胜之书》 《农桑辑要》 《农书》 答案:《天工开物》 10、()理论自60年代后期由法国哲学家德里达在其《论语法学》一书中确立 抽象主义 解构主义 立体主义 结构主义 答案:解构主义 第二章 1、()是指以古今纯艺术或设计艺术为对象，根据设计的需要，进行符号意义的分解，分解成语词、纹样、标识、单形、乐句之类，使之进入符号储备，有待设计重构。 创造 解构 借用 参照 答案:解构 2、()方法是以系统整体分析及系统观点来解决各种领域具体问题的科学方法。 结构论 控制论 信息论 系统论 答案:系统论 3、90年代的市场竞争主要是文化的竞争，而文化竞争又取决于()的竞争。 经济 设计 算法设计课程习题答案 第一章 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-6章
《计算机算法设计与分析》习题及答案
设计学概论试卷答案--A卷
R语言-决策树算法知识讲解
临床科研设计模拟试题_附答案
算法设计与分析C++语言描述(陈慧南版)课后答案
算法设计与分析课后部分习题答案
设计学概论-练习题以及答案
Clementine决策树CHAID算法
现代机械设计方法复习题【答案2】
尹定邦--设计学概论-考题与答案(1).
决策树算法介绍(DOC)
2016新课程教学设计一试题及答案 (1)
算法设计与分析习题答案1-6章
算法设计与分析第2版 王红梅 胡明 习题答案
智慧树知到《设计学概论》章节测试【完整答案】
算法设计课程习题答案
相关主题
文本预览