当前位置：文档之家› 北京大学-算法分析与设计1

北京大学-算法分析与设计1

算法设计与分析(作业三)

算法设计与分析实验报告学院信息科学与技术学院专业班级软件工程3班学号 20122668 姓名王建君指导教师尹治本 2014年10月

实验四矩阵相乘次序一、问题提出用动态规划算法解矩阵连乘问题。给定n 个矩阵{A 1,A 2,…,A n }，其中A i 与A i+1是可乘的，i=1,2,…,n-1。要算出这n 个矩阵的连乘积A 1A 2…A n 。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A 是完全加括号的，则A 可表示为2个完全加括号的矩阵连乘积B 和C 的乘积并加括号，即A=(BC)。例如，矩阵连乘积A 1A 2A 3A 4有5种不同的完全加括号的方式：（A 1（A 2（A 3A 4））），（A 1（（A 2A 3）A 4）），（（A 1A 2）（A 3A 4）），（（A 1（A 2A 3））A 4），（（（A 1A 2）A 3）A 4）。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。若A 是一个p ×q 矩阵，B 是一个q ×r 矩阵，则计算其乘积C=AB 的标准算法中，需要进行pqr 次数乘。（3）为了说明在计算矩阵连乘积时，加括号方式对整个计算量的影响，先考察3个矩阵{A 1,A 2,A 3}连乘的情况。设这三个矩阵的维数分别为10×100，100×5，5×50。加括号的方式只有两种：（（A 1A 2）A 3），（A 1（A 2A 3）），第一种方式需要的数乘次数为10×100×5＋10×5×50＝7500，第二种方式需要的数乘次数为100×5×50＋10×100×50＝75000。第二种加括号方式的计算量时第一种方式计算量的10倍。由此可见，在计算矩阵连乘积时，加括号方式，即计算次序对计算量有很大的影响。于是，自然提出矩阵连乘积的最优计算次序问题，即对于给定的相继n 个矩阵{A 1,A 2,…,A n }（其中矩阵Ai 的维数为p i-1×p i ，i ＝1,2,…,n ），如何确定计算矩阵连乘积A 1A 2…A n 的计算次序（完全加括号方式），使得依此次序计算矩阵连乘积需要的数乘次数最少。二、求解思路本实验采用动态规划算法解矩阵连乘积的最优计算次序问题。本实验的算法思路是： 1)计算最优值算法MatrixChain()：建立两张表（即程序中的**m 和**s ，利用二维指针存放），一张表存储矩阵相乘的最小运算量，主对角线上的值为0，依次求2个矩阵、3个矩阵…、直到n 个矩阵相乘的最小运算量，其中每次矩阵相乘的最小运算量都在上一次矩阵相乘的最小运算量的基础上求得，最后一次求得的值即为n 个矩阵相乘的最小运算量；另一张表存储最优断开位置。 2)输出矩阵结合方式算法Traceback()：矩阵结合即是给矩阵加括号，打印出矩阵结合方式，由递归过程Traceback()完成。分三种情况：（1）只有一个矩阵，则只需打印出A1；（2）有两个矩阵，则需打印出（A1A2）；（3）对于矩阵数目大于2，则应该调用递归过程Traceback()两次，构造出最优加括号方式。三、算法复杂度该算法时间复杂度最高为）（n 3 O 。四、实验源代码

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

《算法分析与设计》实验指导书本书是为配合《算法分析与设计实验教学大纲》而编写的上机指导，其目的是使学生消化理论知识，加深对讲授容的理解，尤其是一些算法的实现及其应用，培养学生独立编程和调试程序的能力，使学生对算法的分析与设计有更深刻的认识。上机实验一般应包括以下几个步骤：（1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。（2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。（3）、上机结束后，整理出实验报告。实验报告应包括： 1）问题分析 2）算法描述 3）运行结果、 4）算法性能分析。实验一实验名称：贪心算法应用及设计实验学时：6学时实验类型：验证实验目的： 1.理解贪心算法的基本思想 2.掌握利用贪心算法求解问题的求解步骤实验容 1.活动选择问题（2学时）问题描述：设有11个会议等待安排，用贪心法找出满足目标要求的会议集合，这些会议按结束时间的非减序排列如下表。实验实现提示：１)数据结构设计：将会议开始时间存储在数组B中，结束时间存储在数组E中，数组下标为会议的代码。结果存储在数组A中，其元素A[i]==true，表示会议i被选中。２）算法： void GreedySelect(int n, struct time B[], struct time E[], bool A[]) { int i,j;

A[1]=true; j=1; i=2; while( i<=n) if (B[i]>=E[j]) { A[i]=true; j=i;} else A[i]=false; } 思考题：证明所得的解是最优解？ 2.单源点最短路径问题。（2学时）问题描述如图所示的有向带权图中，求源点0到其余顶点的最短路径及最短路径长度。并对算法进行性能分析。实现提示 1）数据结构设计：将图存储在邻接矩阵C中，结点个数为n，源点编号为u, 源点u到其余顶点的最短路径长度存储在dist[],最短路径存储在p[]。 2) 算法 void Dijkstra(int C[n][n], int n,int u,float dist[],int p[]) { bool s[n]; for( int i=1; i<=n; i++) { dist[i]=C[u][i]; s[i]=false; if (dist[i]=∞) p[i]=-1; else p[i]=u; } p[u]=-1; s[u]=true; for( i=1; i<=n; i++) { int temp= ∞; int t=u; for( int j=1;j<=n;j++)

2018年北京大学创意写作考研真题回忆

2018年北京大学创意写作考研真题回忆注：填空题题目顺序和个别措辞与真题有差异。科目一文学基础一、填空题（每空2分，共40分） 1.《两都赋》的作者是_________。 2.《赵氏孤儿》是_________ 的作品；后被法国著名思想家、作家________ 改编为《中国孤儿》。 3.宋代诗人_________ 提出了“诗穷而后工”。 4.宋代诗人_________ 提出了“点铁成金”。 5.侯方域是戏剧《_________》中的角色。 6.元代王冕的《墨梅》：__________________，__________________。不要人夸颜色好，只留清气满乾坤。 7.“冬天来了，春天还会远吗？”出自德国诗人雪莱的《_________》。 8.“诗____________，赋体物而浏亮。”出自陆机《文赋》。 9.莎士比亚四大悲剧为《奥赛罗》《李尔王》《哈姆雷特》和《_________》。 10.孔子：“诗可以兴，可以________，可以________，可以________，迩之事父，________，多识于鸟兽草木之名。 11.席勒的《________》被称为德国第一部具有政治倾向的喜剧。 12. ________在《失乐园》中刻画了撒旦形象来象征资本主义。 13．《荷马史诗》包含了《________》，《________》。 14.鲁迅关于文学创作弊病的名言填空。咨询考研家吴老师薇：要三三溜溜汽酒欺凌丝丝二、名词解释（每题10分，共50分） 1.《新青年》 2.《北京人》 3.狂飙突进运动 4.“多余人”形象 5.“二次元” 三、论述题（30分）西方文学不乏对大自然的向往的作品；中国古典诗歌中山水田园诗更是源远流长。请结合中西文学中具体作家作品比较中西文学对倾慕自然的倾向的异同。四、就《墓碣文》写一篇赏析文章。（30分）我梦见自己正和墓碣对立，读着上面的刻辞。那墓碣似是沙石所制，剥落很多，又有苔藓丛生，仅存有限的文句—— ……于浩歌狂热之际中寒；于天上看见深渊。于一切眼中看见无所有；于无所希望中得救。……

北大屈婉玲算法分析与设计习题解答4

Exercise1 说明：对于算法设计的习题，解题要求如下：先用一段简短的文字说明算法的主要设计思想，其中所引入的符号要给出必要的说明，是否给出伪码根据题目要求确定. 可以调用书上的算法作为子过程，最后对所设计的算法需要给出时间复杂度的分析. 1. 对以下函数，按照他们的阶从高到低排列；如果f (n )与g (n )的阶相等，表示为f (n )=Θ(g (n )). n n n n n n n n n n n n n n n n n n n n n log ,2,,log ,log log ,,,2,)(log ,log , )2/3(,,2,!,1,log ),!log(log 3log log 2log log /12 2. 求解以下递推方程： (1) ?????=++=1 )1(,)4()2()(T c cn n T n T n T 为常数 (2) ???=+=1 )1()log ()2/(5)(2 T n n n T n T 3．设A 是含有n 个元素的数组，如果元素x 在A 出现的次数大于n /2，则称x 是A 的主元素. (1) 对于可排序的数组，设计一个测试算法. (2) 如果A 中元素只能进行“是否相等”的测试，但是不能排序，设计一个算法判断A 中是否存在主元素. 4．设X [0:n ?1]和Y [0:n ?1]为2个数组，每个数组含有n 个已排好序的数。试设计一个O (log n )时间的算法，找出X 和Y 的2n 个数的中位数. 5．设S 是含有n 个数的数组，k 是给定正整数，k i k ，那么就称(i j ,i k )是这个排列的一个逆序. 一个排列含有逆序的个数称为这个排列的逆序数. 例如排列263451含有8个逆序(2,1), (6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，它的逆序数就是8. 显然，由1,2,…,n 构成的所有n !个排列中，最小的逆序数是0，对应的排列就是12…n ；最大的逆序数是n (n ?1)/2，对应的排列就是n (n ?1)…21. 逆序数越大的排列与原始排列的差异度就越大. 利用二分归并排序算法设计一个计数给定排列逆序的分治算法，并对算法进行时间复杂度的分析.

算法分析与设计作业及参考答案样本

《算法分析与设计》作业( 一) 本课程作业由两部分组成。第一部分为”客观题部分”, 由 15个选择题组成, 每题1分, 共15分。第二部分为”主观题部分”, 由简答题和论述题组成, 共15分。作业总分30分, 将作为平时成绩记入课程总成绩。客观题部分: 一、选择题( 每题1分, 共15题) 1、递归算法: ( C ) A、直接调用自身 B、间接调用自身 C、直接或间接调用自身 D、不调用自身 2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题, 这些子问题: ( D ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 3、备忘录方法的递归方式是: ( C ) A、自顶向下 B、自底向上 C、和动态规划算法相同 D、非递归的 4、回溯法的求解目标是找出解空间中满足约束条件的: ( A )

A、所有解 B、一些解 C、极大解 D、极小解 5、贪心算法和动态规划算法共有特点是: ( A ) A、最优子结构 B、重叠子问题 C、贪心选择 D、形函数 6、哈夫曼编码是: ( B) A、定长编码 B、变长编码 C、随机编码 D、定长或变长编码 7、多机调度的贪心策略是: ( A) A、最长处理时间作业优先 B、最短处理时间作业优先 C、随机调度 D、最优调度 8、程序能够不满足如下性质: ( D ) A、零个或多个外部输入 B、至少一个输出 C、指令的确定性 D、指令的有限性 9、用分治法设计出的程序一般是: ( A ) A、递归算法 B、动态规划算法

C、贪心算法 D、回溯法 10、采用动态规划算法分解得到的子问题: ( C ) A、相互独立 B、与原问题相同 C、相互依赖 D、相互独立且与原问题相同 11、回溯法搜索解空间的方法是: ( A ) A、深度优先 B、广度优先 C、最小耗费优先 D、随机搜索 12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法: ( C ) A、所需时间变化 B、一定找到解 C、找不到所需的解 D、性能变差 13、贪心算法能得到: ( C ) A、全局最优解 B、 0-1背包问题的解 C、背包问题的解 D、无解 14、能求解单源最短路径问题的算法是: ( A ) A、分支限界法 B、动态规划 C、线形规划 D、蒙特卡罗算法 15、快速排序算法和线性时间选择算法的随机化版本是:

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

算法设计与分析实验报告贪心算法班级：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

北大中文系推免生培养方案

北大中文系推免生培养方案一、北大中文系推免生专业研究方向名称：新闻与传播硕士专业学位（MJC）创意写作（CreativeWriting）方向。主要研究内容、特色与意义：研究古今各类文体写作的要求和特点，研究创造性思维的特点和形成规律，研究和掌握中外文学、文化基础知识，研究现代传媒与文化发展的主要特征和基本走势，推动中国当代文化事业和文化产业的繁荣发展。二、北大中文系推免生培养目标通过对古今各类文体经典和范本的系统研习，激发创造性思维习惯，在大量创意写作实践的基础上，培养各类文体的写作能力和创新性思维能力，成为具有系统的专业知识和高水平创作能力的高层次的应用型专才，成为从事当代文化发展所需要的创新性人才。具体而言，也就是培养从事文学创作的作家、诗人、剧作家；新闻媒体、影视、动漫、视频等文化创意产业的创作人员；新闻、出版、广告、大型文化活动策划书和文案的写作人员；国家机关、企事业单位公文和日常应用文书的写作人员等。三、学习年限及应修学分学制：2年制，全日制班（全脱产）。应修学分：总学分不少于32学分，其中必修课20学分(公共必修课4学分，专业必修课16学分)，选修课不少于12学分。四、北大中文系推免生课程设置必修课程20学分 A．公共必修课程4学分 1、英语（2学分）（第一学期） English 2、马克思主义文艺理论（2学分）（第二学期） Theliterary&arttheoryofMarxism B.专业必修课程16学分 1、传播学理论与研究方法（2学分） Theoryandresearchmethodsofcommunication 2、新媒体理论与实践（2学分） Theoryandpracticesofnewmedia 3、广告及创意策划案例解析（2学分） Advertisingandcreativeplanning 4、古代诗文研究与创作（2学分） ResearchandwritingofChineseclassicalpoetryandprose 5、现代诗文研究与创作（2学分） ResearchandwritingofChinesemodernpoetryandprose 6、现代小说研究与创作（2学分） ResearchandwritingofChinesemodernnovels 7、创意写作（2学分） Creativewriting 8、专业实习（2学分） Internship 不少于四周时间，在新闻机构、新媒体、作协、影视公司、广告文化公司等教学实习基地进行。完成实习作品并

北大屈婉玲算法分析与设计习题解答5.pdf

Exercise2 要求：对变量给出说明，动态算法要给出优化函数的递推方程、标记函数等，并给出时间复杂度分析。是否需要写伪码，看题目要求。对于给定实例，求出这个实例的解。 1. 有n 个底面为长方形的货柜需要租用库房存放. 如果每个货柜都必须放在地面上，且所有货柜的底面宽度都等于库房的宽度，那么第i 个货柜占用库房面积大小只需要用它的底面长度l i 来表示，i =1, 2, …, n . 设库房总长度是L ，且L l n i i >∑=1. 设库房单位长度的租金是常数c ，如果要求库房出租的收益达到最大，如何选择放入库房的货柜？设计一个算法求解这个问题，给出算法的伪码描述. 2. 设有n 种不同面值的硬币，第i 种硬币的币值是v k (其中v 1=1)，重量是w i ，i =1,2,…,n 且现在购有某些总价值为y 的商品，需要用这些硬币付款，如果每种钱币使用的个数不限，问如何选择付款的方法使得付出钱币的总重量最轻？设计一个求解该问题的算法. 假设问题的输入实例是： v 1=1, v 2=4, v 3=6, v 4=8 w 1=1, w 2=2, w 3=4, w 4=6 y =12 给出算法在该实例上计算的备忘录表和标记函数表，并说明付线的方法. 3. 有n 项作业的集合J ={1,2,…,n }，每项作业i 有加工时间t (i )∈Z +，效益值v (i )，任务的结束时间D ∈Z +，其中Z +表示正整数集合. 一个可行调度是对J 的子集A 中任务的一个安排，对于i ∈A ，f (i )是开始时间，且满足下述条件： f (i )+t (i )≤f (j ) 或者f (j )+t (j )≤f (i ), j ≠ i i , j ∈A D k t A k ≤∑∈)( 设机器从0时刻开动，只要有作业就不闲置，求具有最大总效益的调度. 给出算法的伪码. 4. 把0-1背包问题加以推广. 设有n 种物品，第i 种物品的价值是v i , 重量是w i ，体积是c i ，且装入背包的重量限制是W ，体积是V . 问如何选择装入背包的物品使得其总重不超过W ，总体积不超过V 且价值达到最大？ 5. 有n 个分别排好序的整数数组A 0，A 1, …, A n －1，其中A i 含有x i 个整数，i = 0,1,…,n －1. 已知这些数组顺序存放在一个圆环上，现在要将这些数组合并成一个排好序的大数组，且每次只能把两个在圆环上处于相邻位置的数组合并. 问如何选择这n －1次合并的次序以使得合并时总的比较次数达到最少？

2020-2021年北京大学085209集成电路工程、招生情况、复试分数线、考研经验、参考书目等考研经验

2020-2021年北京大学085209集成电路工程、招生情况、复试分数线、考研经验、参考书目等考研经验学科概况此专业为专业硕士。专业硕士和学术学位处于同一层次，培养方向各有侧重。专业硕士主要面向经济社会产业部门专业需求，培养各行各业特定职业的专业人才，其目的重在知识、技术的应用能力招生情况复试分数线考研排名

参考书目《计算机组成原理》第2版唐朔飞高等教育出版社《C语言程序设计》第4版谭浩强清华大学出版社《电子技术基础》（数字部分）康华光高等教育出版社考研建议 1、零基础复习阶段（6月前) 本阶段根据考研科目，选择适当的参考教材，有目的地把教材过一遍，全面熟悉教材，适当扩展知识面，熟悉专业课各科的经典教材。这个期间非常痛苦，要尽量避免钻牛角尖，遇到实在不容易理解的内容，先跳过去，要把握全局。系统掌握本专业理论知识。

对各门课程有个系统性的了解，弄清每本书的章节分布情况，内在逻辑结构，重点章节所在等，但不要求记住，最终基本达到北理本科水平。 2、基础复习阶段（6－8月) 本阶段要求考生熟读教材，攻克重难点，全面掌握每本教材的知识点，结合真题找出重点内容进行总结，并有相配套的专业课知识点笔记,进行深入复习，加强知识点的前后联系，建立整体框架结构，分清重难点，对重难点基本掌握。同时多练习相关参考书目课后习题、习题册，提高自己快速解答能力，熟悉历年真题，弄清考试形式、题型设置和难易程度等内容。要求吃透参考书内容，做到准确定位，事无巨细地对涉及到的各类知识点进行地毯式的复习，夯实基础，训练思维，掌握一些基本概念和基本模型。 3、强化提高阶段（9月－11月）本阶段要求考生将知识积累内化成自己的东西，动手做真题，形成答题模式，做完的真题可以请考上目标院校的师兄、师姐帮忙批改，注意遗漏的知识点和答题模式；总结并熟记所有重点知识点，包括重点概念、理论和模型等，查漏补缺，回归教材。师兄师姐可以通过新祥旭的辅导班认识，并学习。

算法分析与设计实验报告

算法设计与分析学院：计算机科学与技术学号：129074106 姓名：张淼淼 2014 11 14

1、当问题规模100 N 时，快速排序和插入排序各需多少时间？写清机器配置，列出五种快速排序所需时间(ms) 插入排序所需时间（ms ）两者相差多少 N=100 0.00600 0.019000 -0.013000 N=1000 0.074000 0.724000 -0.650000 N=10000 0.032000 64.657000 -64.625000 N=100000 13.300000 50.900000 -37.600000 N=1000000 53.500000 117.700000 -64.200000 Window 7 32位 Cpu ：Inter(R) Core(TM) i3-2120 cpu@3.30GHz AMD Radeon HD 6450 Graphics

程序： #include #include #include #include int a[1000000];

int b[1000000]; void QuickSort(int low ,int high) { long i,j; int x; i=low; j=high; x=a[i]; while(i=x&&i(j+1)) QuickSort(j+1,high); } void BinaryInsertSort(int length) { int low,high,mid; int i,j,m;//m为保存待插入的元素 for(i=1;i=b[mid]) low=mid+1; else high=mid-1; } for(j=i-1;j>=high+1;j--)//high为插入位置 b[j+1]=b[j];//后移元素，留出插入的空位b[high+1]=m;//将元素插入正确的位置 }

创意写作教育教学问题研究专辑_葛红兵

第40卷第1期2016年1月湘潭大学学报（哲学社会科学版） Journal of Xiangtan University （Philosophy and Social Sciences ）Vol．40No．1Jan．，2016 “创意写作教育教学问题研究”专辑（笔谈4篇，主持人：葛红兵）主持人语：2014年10月世界华文创意写作协会在澳大利亚墨尔本成立， 2014年12月上海大学创意写作学科获批中国第一个中文目录外自主创设学科点资质，开始招收创意写作硕士、博士研究生， 2015年6月世界华文创意写作大会在上海召开……这些事件标志着华文创意写作学科的诞生，同时也标志着华文创意写作走出校园，向文化产业、文化事业方向发展。但是，华文创意写作无论是作为文化产业业态，还是作为公共文化服务形态，其根本在人才培养和作品培育两个环节，由此，我们特地编选了一组关于创意写作教育教学问题的论文，以飨读者。其中有就中国创意写作学科发展的经验进行总结的，也有研究美国创意写作学科发展史，进而对比中国化进程提出问题加以讨论的，还有通过教学方式和方法的研究来讨论中国创意人才的培养问题的，等等，希望这组论文能引起读者对高校中文教育教学改革的重视，以及对创意写作这个新生学科的重视。（葛红兵：上海大学文学与创意写作研究中心主任，博士生导师）中国化的创意写作学科体系猜想 * 陈晓辉（西北大学文学院，陕西西安710127）摘要：中国化的创意写作学科体系是一个亟需解决的问题，而仅非一个研究对象。解决该问题需要学生培养与教师培养并重；理论课与实践课并重；思维训练与创作训练并重；学者教学与作家教学并重；日常教学与学科建设并重；课堂教学与企业实践并重；创意培养与产业孵化并重。只有做好上述七个“并重”，才能建成“和而不同”的中国化的创意写作学科体系，创意写作才有可能变成转变目前高校文学教育，甚至转变人们文学思维方式的利器，其本身也可以得到健康、良性的发展。关键词：创意写作；学科体系；中国化；并重中图分类号：G112；I0－02文献标识码：A 文章编号：1001－5981（2016）01－0085－05 自从葛红兵教授在英国访学之后，“创意写作”①这一概念就进入中国学界。上海大学敢为天下先，复旦大学、人民大学、北京大学等国内著名高校纷纷用开设专业、招收硕士生等方式力挺。与此同时，浙江大学、武汉大学、同济大学等也都纷纷进入创意写作的专业建设当中。在某种程度上，可以说中国已经进入了创意写作时代。在这种背景下，我们西北大学于2012年招收了第一届创意写作本科生，就这几年的学生培育与学科发展情况而言，我以为是该建构中国化的创意写作学科体系的时候了。原因有二：一是学科本身具有的地域性差异。创意写作源起美国，兴盛于美、英、奥等国，但欧美国家的文化环境与中国不同，他们的教学方式、教学经验等，未必全部适合中国学生、中国文化；二是学科良性发展的刚性需要。按照目前中国大学教育的实际情况，创意写作要想获得良性发展，就必须从课程设置、期刊阵地、学术机构、学科平台、管理制度等各个层面进行建设，以期获得相应的学科地位。进言之，所谓“中国化”的创意写作学科体系建 5 8* ①收稿日期：2015－08－12 作者简介：陈晓辉（1978－），男，陕西千阳人，文学博士，西北大学文学院副教授，从事文学理论和批评、创意写作的教学与研究。基金项目：陕西省社会科规划项目“文学叙事空间研究”（13J040），陕西省教育厅科研项目“文学叙事空间研究”（14JK0250），西北大学教学质量与教学改革工程项目 “创意写作教学改革与实践研究”（JX13030）、“创意写作教学团队”（JX14069）的阶段性成果之一。据目前所见资料，Creative Writing 一词是汪正龙教授引进中国的。在2007年版的《关键词：文学、批评与理论导论》一书中，汪正龙写道：“‘创意写作’（Creative Writing ），也可译为‘创造性写作’，原指英美大学语文系开设的一门与文学创作有关的写作课程及其写作形式。本章主要讨论这种写作对文学创作的启示，即真正的‘创意写作’应该是挑战写作自身、挑战作者自身经验极限、挑战语言表达的极限的写作。”（安德鲁·本尼特，尼古拉·罗伊尔．关键词：文学、批评与理论导论［M ］．汪正龙等，译．桂林：广西师范大学出版社， 2007．p．83译注）。然而，通过笔者考察，汪教授既不是刻意引进该概念，又无意对其深入研究，而葛教授正好与汪教授相反，而且在上海大学创意写作丛书总序中，葛教授提到他2004年从英国访学归国后就跟钱伟长校长提到“创意写作”的概念，故我认为，虽然葛红兵教授的研究文章发表略晚，但应认定为是葛教授将此概念引入中国学界。 DOI:10.13715/https://www.doczj.com/doc/5b2696822.html,ki.jxupss.2016.01.016 DOI:10.13715/https://www.doczj.com/doc/5b2696822.html,ki.jxupss.2016.01.017

OpenJudge算法设计与分析习题解答

1、硬币面值组合描述使用1角、2角、5角硬币组成n 角钱。设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。输入一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。输出输出有若干行，每行的形式为： i a b c 第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。

源代码： #include #include int main(){ int t=1; int i,j,k; int n; scanf("%d",&n); int A=n,B=n/2,C=n/5; for(i=0;i<=C;i++){ for(j=0;j<=B;j++){ for(k=0;k<=A;k++){ if(i*5+j*2+k*1==n){ printf("%03d%12d%12d%12d\n",t,k,j,i); t++; } } } } getchar(); return 0; } 2、比赛排名描述 5名运动员参加100米赛跑，各自对比赛结果进行了预测：A说：E是第1名。 B说：我是第2名。 C说：A肯定垫底。 D说：C肯定拿不了第1名。

E说：D应该是第1名。比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。请编程判断5位选手各是第几名。输入无输出输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。样例输入样例输出源代码： #include int main() { printf("5\n"); printf("2\n"); printf("1\n"); printf("3\n"); printf("4\n"); return 0; } 3、鸡兔同笼描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。

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

《计算机算法设计与分析》实验指导书（第一版）

前言计算机算法分析与设计是面向设计的，它是计算机科学的核心。无论是计算机系统、系统软件和解决计算机的各种应用问题都可归结为算法的设计。通过本课程的学习，使学生掌握计算机领域中许多常用的非数值的算法描述：分治法、贪心法、动态规划、回溯法、分枝限界等算法，并掌握算法分析的方法，从而把学生的分析问题和解决问题能力提高到理论的高度。前期课程为程序设计语言、数据结构、高等数学，即学生应该具备一门高级语言程序设计编程基础，学习基本的数据结构知识，还要求学生掌握较好的数学基础。开发环境不限，本书采用C/C++语言的集成开发环境等。实验完成后书写实验报告，包含实验问题、基本思想、关键算法流程图、测试数据及运行结果（截图）、调试心得和源程序。总实验学时为16学时。

目录预备实验验证算法的方法 (4) 实验目的： (4) 实验课时： (4) 实验原理： (4) 实验题目： (6) 基本题： (6) 提高题： (6) 实验一递归与分治 (7) 实验目的： (7) 实验课时： (7) 实验原理： (7) 实验题目： (7) 基本题： (7) 提高题： (8) 思考问题： (8) 实验二动态规划算法 (9) 实验目的： (9) 实验课时： (9) 实验原理： (9) 实验题目： (9) 基本题： (9) 提高题： (10) 思考问题： (10) 实验三贪心选择算法 (11) 实验目的： (11) 实验课时： (11) 实验原理： (11) 实验题目： (11) 基本题： (11) 提高题： (12) 思考问题： (12) 实验四回溯算法 (13) 实验目的： (13) 实验课时： (13) 实验原理： (13) 实验题目： (14) 基本题： (14) 提高题： (14) 思考问题： (14)

2019年北大中国现当代文学考研复试时间复试内容复试流程复试资料及经验

2019年北大中国现当代文学考研复试时间复试内容复试流程复试资料及经验随着考研大军不断壮大，每年毕业的研究生也越来越多，竞争也越来越大。对于准备复试的同学来说，其实还有很多小问题并不了解，例如复试考什么？复试怎么考？复试考察的是什么？复试什么时间？复试如何准备等等。今天启道小编给大家整理了复试相关内容，让大家了解复试，减少一点对于复试的未知感以及恐惧感。准备复试的小伙伴们一定要认真阅读，对你的复试很有帮助啊！专业介绍中国现当代文学是中国语言文学之下的一个二级学科硕士点，源于五四新文化运动，它的发生和发展与近、现代中华民族的历史命运休戚相关。加强中国现当代文学的研究，可以帮助人们反思近百年来中华民族的历史命运，在特殊的审美感受中受到启迪和鼓舞。中国现当代文学是在中国文学的大背景下，以五四以来的文学为重点研究对象的学科，研究内容包括现代以来各个文学思潮和流派、作家群体、作家作品和文学风格的嬗变，以及从文体的角度包括诗歌、小说、戏剧、散文、影视等文学艺术样式的理论批评和研究等。我系该学科的特色在于：从新诗创作与批评的实际出发，注重对新诗的文本意识以及汉语诗性智慧研究;注重运用当代理论批评现当代小说、戏剧、影视等;重点培养学生科研创新能力。复试时间学术及专业硕士2017年3月20日(周一)8：30—10：30在人文学苑6-115报到。学术硕士3月21日（周二）、进行面试。专业硕士3月22日(周三)、进行面试外语听力考试安排：学术型硕士各专业：3月20日下午2:00-2:20，地点：人文学苑6-B122 专硕创意写作方向：3月20日下午3:00-3:20，地点：人文学苑6-B122 面试进行期间，考生可在人文学苑6-B122候考。复试内容（科目）

北大PKU 慕课 EDX 数据结构与算法第七章图 quiz答案与解析

第七章树

PROBLEM 2 (1/1 分) 一个深度为h的满k叉树，最多有多少个结点？（独根树深度为0）There is a full k-ary tree, whose depth is h. How many nodes can it have at most? (The depth of a tree, which only has a root node, is 0.) k^(h-1) k^h (k^(h+1)-1)/(k-1) (k^(h+1)-1)/(k-1) - 正确 (k^h-1)/(k-1) Explanation 层数---节点数 number of levels---number of nodes 0---1 1---k 2---k^2 3---k^3 .... h---k^h 所以答案是： so, the answer is： 1+k+k^2+k^3+...+k^h = (k^(h+1)-1)/(k-1)

PROBLEM 3 (1/1 分) 2-3树是一种特殊的树，它满足两个条件：（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同；如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。(多项) 2-3 tree is a special kind of tree, it satisfy: （1）Every internal node has 2 or 3 child nodes. (2)All the leaf nodes have the same length of the path to the root node. If a 2-3 tree has 9 leaf nodes, then it may have __________ non-leaf nodes.（There are more than one correct answers） 4, 7, - 正确 4 5 6 7 Explanation 倒数第二层若是3个结点，深度为2，加上根结点，一共4个非叶子结点。倒数第二层若是4个结点，深度为3，倒数第三层（第二层）有2个结点，一共4+2+1=7个非叶子结点。 If the second level from the bottom has 3 nodes, the depth of tree will be 2, and the tree will has 4 non-leaf nodes, including the root node. If the second level from the bottom has 4 nodes, the depth of tree will be 3, the third level from the bottom will has 2 nodes, and the tree will has 4+2+1=7 non-leaf nodes

《算法分析与设计》作业参考答案

《算法分析与设计》作业参考答案作业一一、名词解释： 1.递归算法：直接或间接地调用自身的算法称为递归算法。 2.程序：程序是算法用某种程序设计语言的具体实现。二、简答题： 1.算法需要满足哪些性质？简述之。答：算法是若干指令的有穷序列，满足性质：（1）输入：有零个或多个外部量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令清晰、无歧义。（4）有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。 2.简要分析分治法能解决的问题具有的特征。答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 3.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。答：将递归算法转化为非递归算法的方法主要有：（1）采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。（2）用递推来实现递归函数。（3）通过Cooper 变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。三、算法编写及算法应用分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 do for j ←1 to n-i do if a[j]

文档之家