以求算法

① 一段长40分钟的视频，如果以1.2倍速度播放，那实际用时是多少求算法，谢谢。

40乘以60秒/分钟等于2400秒，2400秒再除以1.2/1.0=2400/1.2=2000秒

② 求一个算法(贪心算法)

贪心算法

一、算法思想

贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；

二、例题分析

1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30

分析：

目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略。 ?

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）

================================
三个经典的贪心算法

有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学。有人说贪心算法是最复杂的算法，原因也很简单：这世上贪的人太多了，那轮到你我的份？

不论难度如何，贪心算法都是一个很重要的算法，我在网上N多Online Judge中的题目中，总结了三类较为常见，也十分经典的贪心算法，发布在这儿Just For Fun。

（注：由于没有现成的名字可用，这三种类型贪心算法的名字都是我自己取的，如果你听着别扭，请见谅。）

No 1.线段覆盖（linescover）

题目大意：

在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。

解题思路：

将线段按其坐标进行排序（排序的具体方法:按起始坐标排，起始坐标相同的按终止坐标排，都是小在前大在后）,使之依次递增，并按顺序分别编号为X(i),X(i).a代表其起始坐标，X(i).b代表其终止坐标。

然后按排好的顺序依次处理：定义一个变量last记录考虑到当前线段之时被线段覆盖的最大的坐标值，再定义一个变量length记录当前线段覆盖的长度。对于后面的线段，我们把它看成由两个部分组成，即把它分成last之前的线段和last之后的线段。（如果线段全部处在last之后，其last之前的部分不存在。）由于我们排过序，我们可以肯定当前考虑的线段X(i)其处在last之前的部分不会对length造成影响（因为X(i-1).b=last，X(i).a>=X(i-1).a,即X(i)在last之前的部分所处位置肯定被线段X(i-1)覆盖过），所以会对length产生影响的即是X(i)处在last之后的部分。

所以我们可以依次对每条线段做如下处理：（初始化length为零，last为负无穷）

length+=X(i).b-last (X(i).a<=last 且 X(i).b>=last)

length+=X(i).b-X(i).a (X(i).a>last)

last=X(i).b;

最后length就为我们所需要的答案。

No 2.最优数对（bestpair）

题目大意：

按递增的顺序告诉你N个正整数和一个实数P，要求求出求出该数列中的比例最接近P的两个数（保证绝对没有两个数使得其比值为P）。

解题思路：

定义两个指针i和j，先初始化i=j=1，然后进行如下操作：

当code[j]/code[i]>p时，inc（j）；

当code[j]/code[i]<p时，inc（i）。

记录其中产生的最优值即为答案。

No 3.连续数之和最大值（maxsum）

题目大意：

给出一个长度为N的数列（数列中至少有一个正数），要求求出其中的连续数之和的最大值。（也可以加入a和b来限制连续数的长度不小于a且不大于b）。

解题思路：

先说不加限制的那种，定义一个统计变量tot，然后用循环进行如下操作：inc（tot，item） 其中如果出现tot<0的情况，则将tot赋值为0。在循环过程之中tot出现的最大值即为答案。

如果加入了限制条件的话，问题就变得难一些了（这句真的不是废话）。为此我们先定义数组sum[i]来表示code[1]到code[i]之和（这样的话code[a]~code[b]的和我们就可以用sum[b]-sum[a-1]来表示了。）。

再维护一个数组hash[i]来表示满足条件的sum[a-1]的下标，并使之按递增顺序排列，这样当前以第i的数为终止的数列的最大值肯定就是sum[i]-sum[hash[1]]。

现在我们来讨论hash数组之中的数据需要满足的条件和如何维护的具体问题：

当考虑到以第i个数为结尾时，hash[i]所表示的下标需要满足的第一个条件就是题目规定的长度限制，我们需要实时的加入满足长度规定的下标，删除不符合要求的下标。其次，与不加限制条件时相同，若sum[i]-sum[hash[1]]的值小于零，则清空数组hash。

维护时可以这样，当考虑到第i个数时，我们就将下标i-a+1加入到hash中，因为hash中原来已经排好序，因此我们我们可以用插入排序来维护hash的递增性，然后我们考察hash[1]，若hash[1]<i-b+1，则证明其已超出长度限制，我们就将其删除，接着再考虑更新后的hash[1],如此重复直至找到一个满足条件的hash[1]为止。

我们可以用链表来表示hash，这样就可以减少数据加入和删除时频繁数据移动的时间消耗。

记录下sum[i]-sum[hash[1]]的最大值即为答案。

③ 设计算法以求解从集合{1..n}中选取k(k<=n)个元素的所有组合

C(k,n-1)=∏(n-k,n-1)/k!
C(k-1,n-1)=∏(n-k+1,n-1)/(k-1)!
C(k-1,n)+C(k-1,n-1)
=∏(n-k,n-1)/k!+∏(n-k+1,n-1)/(k-1)!
=∏(n-k,n-1)/k!+k·∏(n-k+1,n-1)/k!
=[(n-k)·∏(n-k+1,n-1)!+k·∏(n-k+1,n-1)]/(k-1)!
=[n·∏(n-k+1,n-1)]/k!
=∏(n-k+1,n)]/k!
=C(k,n)
即：C(k-1,n)+C(k-1,n-1)=C(k,n)
说简单点，就是杨辉三角形的元素算法。
此原理应用到你的问题上，重点是：结果集合的每个元素又是个集合。
若通用集合类Set(其实java中Set就是)；
new Set{value...}为构造方法，-{value..}为集合差，+{value...}为集合和，Set(i)和集合第i个元素；
对于n个元素的集合Sn，如果有函数Set combine(k,Sn)，产生n个元素中选k个元素集合的集合；那么，当a是n个元素中的任意一个时，combine(k,Sn)=combine(k,Sn-{a})+combine(k-1,Sn-{a})。
由此可以产生递归算法：
Set Sn=new Set{a0,a1,...an-1};
Set result=Sn.combine(k,Sn);
...........................

...........................
function Set combine(int count,Set S){
if(count==S.size()){
return new Set{S};//这是集合S仅为结果集的一个元素
}
if(count+1==S.size()){
Set result=new Set{};
for(Element a:S){
result+=new Set{S-{a}};//集合依次排除一个元素产生的子集作为结果的一个元素
}
return result;
}
Set S2=combine(count-1,S-S(0));//对应YH公式的后一项，S(0)为集合S的第一个元素
for(Set Si:S2){
Si+={S(0)};//Si是缺了一个元素的
}
Set S1=combine(count,S-S(0));//这个是个数整好的，YH公式的前一项
return S1+S2;//YH公式
}
这个问题比较有意思，不知道谁出的。没有中学组合知识或YH公式，真困难了。
要是谁有更好算法，不妨交流一下。
这题分给的够低了，纯属兴趣做一下玩。

④ 旋转角度坐标移动 求算法

旋转基点是哪里？逆时针转是顺时针转？

假设基点为O(a,b)

A(m,n)，以O为基点旋转角度α（以逆时针转为正，顺时针转为负）！

旋转后的点为B(x,y)

那么△OAB为等腰三角形，OA＝OB，∠AOB＝α

以基点为原点建立二维坐标系（如图）

其中OA与x轴的夹角设为β(0～2π)，tanβ＝(n-b)/(m-a),可求出β.

而OB与x轴的夹角设为(α+β)(0～2π)，tan(α+β)＝(y-b)/(x-a);

又tan(α+β)＝(tanα+tanβ)/(1-tanα·tanβ)

可求出tanα为一个用a、b、m、n和x、y表示的式子------（1）

OA＝OB，可求出：(x-a)^2+(y-b)^2＝(m-a)^2+(n-b)^2------（2）

再由正弦定理：OA/sin(90-α/2)＝AB/sinα------(3)

由以上3式可求出xy（关于abmn表示的式子）

可求出OB的直线方程，再求出沿OB向前100的坐标！

⑤ 若已知角度为20°的扇形，则变为弧度是（）rad。 求算法 谢谢！

π/9
首先，一个圆，360°=2π
则该题弧度算法：20°÷360°×2π=π/9

⑥ 求算法：假设以块链结构表示串

#include <stdio.h>
#include <string.h>
#include <malloc.h>

typedef struct _ChNode
{
int ch;
struct _ChNode *next;
} ChNode;

ChNode* cncreate(const char *str)
{
ChNode *head = NULL, *tail, *node;

while (*str)
{
node = (ChNode *)malloc(sizeof(ChNode));
node->ch = *str;
node->next = NULL;
if (head == NULL)
{
head = node;
tail = node;
}
tail->next = node;
tail = node;
str++;
}
return head;
}

ChNode* cnchr(ChNode *node, int ch)
{
while (node)
{
if (node->ch == ch)
{
return node;
}
node = node->next;
}
return NULL;
}

ChNode* cntail(ChNode *node)
{
while (node->next)
{
node = node->next;
}
return node;
}

void cnins(ChNode *a, ChNode *b)
{
ChNode *btail = cntail(b);
btail->next = a->next;
a->next = b;
}

void cncat(ChNode *a, ChNode *b, int ch)
{
ChNode *node = cnchr(a, ch);
if (node == NULL)
{
node = cntail(a);
}
cnins(node, b);
}

void cnprint(ChNode *node)
{
while (node)
{
printf("%c", node->ch);
node = node->next;
}
printf("\n");
}

void main()
{
ChNode *list1, *list2;

list1 = cncreate("show me the money!");
cnprint(list1);
list2 = cncreate("give me five!");
cnprint(list2);
cncat(list1, list2, 'w');
cnprint(list1);
}

⑦ 给出一组数字,求公式算法

从A的x到B的x，方程是y=1.3625x-127.8

我用matlab描点画图得到一条几乎笔直的线
然后进行1次拟合，代码如下
x=[400,440,480,520,560];
y=[416,473,526,582,634];
plot(x,y,'o')
a=polyfit(x,y,1)
a
拟合结果：
a = 1.3625 -127.8000

所以就是这样的。既然楼主说近似，绝对没错咯！呵呵

⑧ 高分求算法：寻找与特定对象距离最近的对象

用现在的ID,X,Y三个元素来找最近点的话无论什么办法,都至少要与每个点进行一次距离的判断,比较X或者Y也好,计算距离(当然这个距离是不用开平方的,与其他所有点的距离都不开平方也能比较相对的距离长短)也好,所以如果只有这三个元素的话,其实再怎么改也不会有太大的优化的。

最好还是添加一些辅助信息，比较常用的就是以划分网格的方法，将所有点分派在不同的网格中，然后以网格为基础找最近点，这样的话就要加一个网格的结构（以空间换时间），里面存放的就是属于这个网格的点的ID，通过编号规则可以很快的找最近的网格，然后再找里面的点，这样可以提高点查找速度。

呵呵,不好意思,没想清楚就写了:P,改一下,改一下,再加一步就好了

1.给点添加一个所属网格的信息:
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
}
2.构造一个点链表,这是为了减少空间和方便处理而加的,后面的算法里会感觉到用处
(为每个点对象建立一个点链表节点)
Class I
{
public A *pAObject; //指向一个点对象
publci I *pNextA; //指向下一个
}
3.构件一个网格信息结构
Class G
{
public int ID; //网格编号
public I *pAObjects; //指向一个点链表(至于这个是带头节点还是不带头节点的都一样啦)
//这里用链表比较好
//第一,因为点可移动,那么点对象个数可以随意,可以发挥链表的扩展性
//第二,不需要取中间节点,也就没有用到数组的长处
}
4.构建网格,比如以1000为长度(长度可以自己定义,关键是平衡空间和速度关系),建立正方形的网格,那么(0,0)到(1000000,1000000)就是有1000*1000个网格(在给网格编号的时候最好有规律,那么就能通过List或者其他数组容器的下标来获得网格信息)
5.添加点的时候,先判断属于哪个网格,然后在点信息中添加网格编号,同时构建对应的点链表节点,并添加到所属网格的链表中
6.最后就是查询点了,首先获得出发点中的所属网格信息,看这个网格中是否有其他点:有,则一个个的判断距离(距离的平方),那么最近点一定在这些点里面(如果点还是太多,那么就考虑缩小网格的范围);没有,那就找所属网格周边8个网格中是否有点,有,则再找最近点,没有就再往外扩(如果感觉网格太多,可以加大网格的范围)
7.以找到的最近点到出发点的距离为基准,看看出发点到周边网格在这个距离内会接触到的(没有在6中遍历过的)有几个网格,把这些网格中的点再查看有没有更近的就行了

注:
1.如果还要优化就是加大网格的层次,可以用多层网格,这就会更复杂一点
2.在网格信息结构(G)中,因为点会移动,那么删点链表节点会有一个查找过程,如果觉得这个慢,那么就在点对象结构体中加一个所属点链表的指针:
class I;
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
publci I *pI;
}
....

呵呵，看了lipai006的回答，想了下似乎也是可以实现的，只要多花点内存就可以达到比较好的速度了，而且也不需要真的从X坐标出发这样慢慢的以扇形扩展了啦，通过做一些辅助结构，就直接可以从出发点的X坐标出发，找同X不同Y中Y坐标与出发点最近的就行啦，循环结束条件就是X的扩展距离已经大于当前最小距离，因为再往外也肯定比当前最小距离大了。这个方法也就是要更复杂一些的辅助结构做索引，添加点的时候也要多做些事情，而且实现上的代码相对网格方法复杂一些，但查找速度应该比网格会快一点，因为毕竟是直接找点去了，其实网格方法就是把一批点的X，Y坐标看成是一样的，这样先过滤一批而已，是个速度与复杂度的折中。

xx_lzj:划分区域的目的就是为了使每个区域内的点不能太多，根据我的结构，每个区域有没有点，一个bool判断就够了，不会存在太稀疏影响效率的事情，不过最坏的情况的确会退化到遍历整个点空间，所以这个方法的时间复杂度仍然是O(n)。
你的方法其实和lipai006说的原理是差不多的（如果我对你们链表结构的猜想准确的话），无非就是通过X,Y坐标形成一个二维双向链表，在形成这个链表的过程会比网格相对复杂一点，而且也不是像你想的只要判断8个点就够的，当只有一个点在中间，其他点分布成以这个点为圆心的圆周上时，按照贴主的要求，难道只有8个最近点吗？？在这个情况下，你的最坏复杂度还是O(n)，但就如我说过的，这个方法的平均时间复杂度在参数上是会比网格的低一点，但是算法本身的代码复杂度上会高一点，而且在插入点的过程中的时间消耗会大一点而已。我觉得这是一个整体的过程，不能为了查找的快速牺牲太多其他的时间。
*************
xx_lzj:不好意思，你的链表我还有些不明白的地方:1.二维双向链表每个节点有4个指针，你能否把这4个指针如何获得的说一下，最好不要取边界线上的点，取中间的一个点进行介绍。2.对于初始化和修改点坐标的时候，现有数据如果是链表结构（不是数组），如何能不依靠其他辅助数据进行折半查找？3.修改某个点坐标之后，根据你的链表结构，我感觉不是删除、插入节点这么简单的，能不能具体点说明。