大学计算机基础大学计算机基础 (38).ppt
《大学计算机基础大学计算机基础 (38).ppt》由会员分享,可在线阅读,更多相关《大学计算机基础大学计算机基础 (38).ppt(15页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、Typical algorithm III:divide-and-conquer and backtrackingDivide-and-conquerThe basic idea of divide-and-conque is to divide a problem with scale of n into several smaller subproblems which are similar to the original problem,then solve these subproblems respectively,finally combine the results of ea
2、ch subproblem to get the solution of the whole problem.The divided subproblem is usually similar to the original problem,so the divide-and-conquer strategy can be used recursively to solve it.Example:find the position of integer x in an ascending order of N integers R n.Analysis:the integer sequence
3、 to be searched has been sorted in ascending order,using the method of binsearch.The basic idea is:the ordered data to be searched is divided into two subsets by the intermediate element,one of which is RL,the value of the element is less than or equal to the intermediate element,and the other is RH
4、,the value of the element is more than or equal to the intermediate element.If the value of the intermediate element is equal to the given value x,the search is successful;if the value of the intermediate element is more than the given value x,do binsearch in the subset RL;otherwise,if the value of
5、the intermediate element is less than the given value x,do binsearch in the subset RH.startinput digit groupoutputendQuestionWhat other questions are suitable for solving using divide-and-conquer?BacktrackingBacktracking is also called cut-and-try method.Its basic idea is:in the process of solving s
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学计算机基础大学计算机基础 38 大学计算机 基础 38
限制150内