gusucode.com > 十大算法matlab程序说明 > 十大算法matlab程序说明/分治算法/中国数学建模-编程交流-分治算法_2.txt
中国数学建模-编程交流-分治算法发短信
我能做什么
我发表的主题
我参与的主题
基本资料修改
用户密码修改
联系资料修改
用户短信服务
编辑好友列表
用户收藏管理
个人文件管理
wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出
>> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱 (0)
中国数学建模 → 学术区 → 编程交流 → 分治算法
您是本帖的第 558 个阅读者
* 贴子主题：分治算法
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 11 楼
其他资料
请参阅以下文章：
递归技术
贪心法
动态规划
分治法问题集
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 16:07:51
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 12 楼
二分查找法 Binary Search
在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L，输出为x在L中的位置或者x不在L中的信息。
比较自然的想法是一个一个地扫描L的所有元素，直到找到x为止。这种方法对于有n个元素的线性表在最坏情况下需要n次比较。一般来说，如果没有其他的附加信息，在有n个元素的线性表中查找一个元素在最坏情况下都需要n次比较。
下面我们考虑一种简单的情况。假设该线性表已经排好序了，不妨设它按照主键的递增顺序排列（即由小到大排列）。在这种情况下，我们是否有改进查找效率的可能呢？
如果线性表里只有一个元素，则只要比较这个元素和x就可以确定x是否在线性表中。因此这个问题满足分治法的第一个适用条件；同时我们注意到对于排好序的线性表L有以下性质：
比较x和L中任意一个元素L[i]，若x=L[i]，则x在L中的位置就是i；如果x<L[i]，由于L是递增排序的，因此假如x在L中的话，x必然排在L[i]的前面，所以我们只要在L[i]的前面查找x即可；如果x>L[i]，同理我们只要在L[i]的后面查找x即可。无论是在L[i]的前面还是后面查找x，其方法都和在L中查找x一样，只不过是线性表的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。很显然此问题分解出的子问题相互独立，即在L[i]的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。
于是我们得到利用分治法在有序表中查找元素的算法。
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 16:08:19
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 13 楼
function Binary_Search(L,a,b,x);beginif a>b then return(-1) else begin m:=(a+b) div 2 if x=L[m] then return(m) else if x>L[m] then return(Binary_Search(L,m+1,b,x)) else return(Binary_Search(L,a,m-1,x)); end; end;
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 16:08:48
b
等级：职业侠客
文章：470
积分：956
门派：黑客帝国
注册：2003-8-28
第 14 楼
在以上算法中，L为排好序的线性表，x为需要查找的元素，b,a分别为x的位置的上下界，即如果x在L中，则x在L[a..b]中。每次我们用L中间的元素L[m]与x比较，从而确定x的位置范围。然后递归地缩小x的范围，直到找到x。
下面分析该算法的复杂性。设在n个元素的数组中查找x需要的比较次数为T(n)，如果每次比较x和L[m]时，总有x<>L[m]，即x根本不在L中，则：
T(n)=2+T(n/2),T(1)=1
该方程的解为T(n)=O(logn)。所以在最坏情况下二分查找法的复杂度为O(logn)。
----------------------------------------------
plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained);
2004-5-28 16:13:40
coby
等级：新手上路
文章：12
积分：131
注册：2004-3-26
第 15 楼
请问楼主
您的这些资料 有没有 具体的来源啊
如果有比较好的查找这方面的网址 可否一并分享啊
感激不尽 或者pm偶啊
2004-6-10 9:14:05
coeeoc
头衔：实习管理员
等级：管理员
文章：47
积分：270
注册：2004-3-12
第 16 楼
谢谢
2004-8-7 16:55:31
lwd1981
等级：新手上路
文章：91
积分：353
门派：☆nudter☆
注册：2004-8-21
第 17 楼
好啊！
2004-8-24 21:11:04
本主题贴数 17 分页：9 1 2 : 跳转论坛至...╋数学建模 ├数模竞赛 ├新手入门 ├数学工具 ├资源与检索╋学术区
├数学思想 ├编程交流 ├学术杂谈 ├English Fans╋休闲专区 ├灌水搞笑专区 ├神秘园╋本站站务 ├站务讨论
├数模管理区 ├回收站
*快速回复：分治算法
发贴表情
段落格式 普通格式标题 1标题 2标题 3标题 4标题 5标题 6标题 7已编排格式地址
字体宋体黑体楷体仿宋隶书幼圆新宋体细明体ArialArial BlackCourierVerdanaWide
LatinWingdings 字号1234567
第 1 页,共 7 页， 49 个
显示签名 内容限制：字节.
管理选项： 专题管理 | 修复 | 锁定 | 解锁 | 提升 | 跟贴管理 | 删除 | 移动 | 设置固顶 | 奖励 | 惩罚 | 发布公告
Copyright ©2002 - 2004 Shumo.Com
执行时间：109.37500毫秒。查询数据库7次。
当前模板样式：[默认模板]