求解一道高中向量几何题在扇形OAB中,∠AOB=60°,C为弧AB上一动点.若OC向量=xOA向量+yOB向量,则x+3y的取值范围————
OC²=OA²=OB² →x²+xy+y²=1又x≥0,y≥0故x+3y∈[1,3]
故前面，y≥0后面是什么步骤？
为您推荐：
其他类似问题
扫描下载二维码工具类服务
编辑部专用服务
作者专用服务
利用向量知识求解高中数学题的体会
高中数学是高中课程中较为重要的科目，涉及到很多的定理、推论和公式，题型复杂，学习过程中也会让我们感到枯燥和乏味。而通过向量知识解答数学题可以让数学变得更加有趣，向量知识在三角、几何、代数等问题中应用广泛，是高中数学课程中必不可少的内容，而且在高中数学学习中运用向量知识来解决代数和几何问题效率更高。本文主要针对高中数学题目中应用向量知识解题的过程和思路进行分析，探究其效果和存在的问题。
作者单位：
重庆第二外国语学校 重庆 400060
年，卷(期)：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社平面向量解题技巧_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
平面向量解题技巧
上传于||暂无简介
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩4页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢求最大和连续子向量问题的算法分析 - lienhua34 - 博客园
随笔 - 108, 文章 - 0, 评论 - 106, 引用 - 0
1 问题描述
这是从《编程珠玑(第 2 版)》的第 8 章&算法设计技术&中看到的一个问题。问题的描述是这样的，
&问题的输入是具有 n 个浮点数的向量 x，输出是输入向量的任何连续子向量中的最大和。例如，如果输入向量包含下面 10个元素:(31,-41,59,26,-53,58,97,-93,-23,84) 那么该程序的输出为x[2...6] 的总和，即 187。&
当所有的数都是正数时，问题很容易解决，此时最大的子向量就是输入向量本身。但如果输入向量中含有负数时就不好处理了。另外，为了使问题的定义更加完整，我们认为当所有的输入都是负数时，总和最大的子向量为空向量，总和为 0。
2 问题分析
2.1 最简单直接算法
看到问题,想到的最简单直接的算法就是双层嵌套循环遍历所有的连续子向量，记录下遇到过的最大和,并持续更新。该算法的伪代码为，
1 maxSum = 0;
2 for i = 0 -& n-1
subVecSum = 0;
for j = i+1 -& n-1
subVecSum = subVecSum + x[j];
if (subVecSum & maxSum) then
maxSum = subVecSum;
这是一种简单粗暴的算法，算法复杂度为 O(n2 )，效率太低了。
如何进行改进呢？在上述的双层循环中，除了含有输入向量首元素的连续子向量只被扫描 1 次之外，其他连续子向量都至少被扫描过 2 次。例如，子向量 (-41,59) 被扫描了两次,、，在扫描子向量 (31,-41,59) 处理过一次(未特殊处理，也没有记录)，在扫描子向量 (-41,59) 本身时又被处理了一次。实际上，连续子向量被处理的次数跟该子向量的首元素所在输入向量中的位置有关，如果连续子向量首元素在输入向量的第 m 位(从 1 开始)，则该子向量被处理过 m 次，其中 m-1 次没有进行记录。通过上面分析，我们发现这种简单算法的大部分效率消耗在了连续子向量的重复处理上。那么，我们进行算法优化的思路就是如何减少连续子向量的重复处理?
2.2 扫描算法
我们用 sum(i . . . j) 来表示连续子向量 x[i . . . j] 的总和。我们假设连续子向量 x[m . . . k] 的总和是最大，即
sum(m & 1 . . . k) & sum(m . . . k) & sum(m . . . k + 1)
也就是说，
sum(h . . . k) & sum(m . . . k)&&&& & h & [m, k)&&&&& & & (1)
sum(l . . . k) & sum(m . . . k) & & & l & [0, m) & & & & & & (2)
对于表达式 (1)，我们得到下面的推导：
0 + sum(h . . . k) & sum(m . . . h) + sum(h . . . k)
表达式两边减去 sum(h . . . k)，得到
0 & sum(m . . . h)
于是,我们得到结论 1：如果某个连续子向量的和大于零，则以该子向量为前缀的连续子向量的和可能会更大。
对于表达式 (2)，我们得到下面的推导：
sum(l . . . m & 1) + sum(m . . . k) & 0 + sum(m . . . k)
表达式两边减去 sum(m . . . k)，得到
sum(l . . . m & 1) & 0
于是,我们得到结论 2：如果某个连续子向量的和小于或等于零，则以该子向量为前缀的连续子向量的和不可能大于去掉该子向量前缀之后的子向量的和。
根据结论 1 和结论 2，我们就可以得到下面这个只需要扫描一遍输入向量 x 的算法。
1 maxVecBegin = maxVecEnd = -1;
2 maxSum = 0;
3 cursorVecBegin = cursorVecEnd = 0;
4 cursorVecSum = 0;
5 while (cursorVecEnd & n)
cursorVecSum = cursorVecSum + x[cursorVecEnd];
if (cursorVecSum & maxSum) then
maxSum = cursorVecSum;
maxVecBegin = cursorVecBegin;
maxVecEnd = cursorVecEnd;
else if (cursorVecSum &= 0) then
cursorVecSum = 0;
cursorVecBegin = cursorVecEnd + 1;
cursorVecEnd = cursorVecEnd + 1;
17 endwhile
以 maxSum 记录连续子向量的最大和，maxVecBegin 和 maxVecEnd 记录和最大的连续子向量开始位置和结束位置。另外有个游标向量用于扫描输入向量，游标向量的结束位置从输入向量的首元素移动到末尾元素，而游标向量的开始位置则随着扫描情况可能需要进行向后调整。
每将游标向量的结束位置 cursorVecEnd 向后移动一位时，做以下处理：
1. 计算游标向量的和 cursorVecSum；
2. 根据游标向量的和 cursorVecSum，做以下处理，
&&& & 游标向量总和 cursorVecSum 大于最大和 maxVecSum，更新最大和 maxVecSum 为游标向量的和 cursorVecSum，并更新最大和连续子向量为游标向量(即 maxVecBegin=cursorVecBegin和 maxVecEnd=cursorVecEnd)；
&&& & 或者,游标向量的和小于或等于零，抛弃该游标向量,将游标向量开始位置调整当前扫描位置之后，即 cursorVecBegin=cursorVecEnd+1(根据结论 2)；
&&& & 否则保留当前游标向量,继续将游标向量结束位置后移一位(根据结论 1)。
我们以问题描述中给的输入向量用例
(31,-41,59,26,-53,58,97,-93,-23,84)
来 对 上 述 算 法 进 行 验 证。 表 格 (1) 根 据 游 标 向 量 结 束 位 置 cursorVecEnd 来列表各轮循环中 cursorVecSum的值，以及该轮循环之后cursorVecBegin、cursorVecSum、maxVecBegin、maxVecEnd和 maxVecSum 的值。
cursorVecEnd
cursorVecSum
cursorVecBegin
cursorVecSum
maxVecBegin
根据最后的结果得出，和最大的连续子向量即为 x[2 . . . 6],总和为187。
该算法只扫描了输入向量一遍，则该算法的复杂度为 O(n)。这是一个线性算法，已经是最优的了。
3 问题来历
该问题出现在布朗大学的 Ulf Grenander 所面对的一个模式识别问题中,问题的最初形式为下面的二维形式。
&给定 n & n 的实数数组,求出矩形子数组的最大总和。&
在二维形式的问题中，最大总和子数组是数字图像中某种特定模式的最大似然估计量。因为二维问题的求解需要太多时间，所以 Grenander 将它简化为一维问题，以深入了解其结构。
最近看到这个问题问题才想起来,两年前毕业找工作的时候，就被一个面试官问到过这个二维问题。那时胡乱讲了一通，最后面试当然就悲剧了。后面找个空闲时间再好好思考一下吧。}