请教大家一个算法题目 。

atg

来看看!

foolishfox

原帖由 emacsnw 于 2006-1-18 04:33 发表


[code]
#include <stdio.h>
                                                                                
double maxprod(double x[],int n)
{
    int i;
    double best = 1,worst =  ...

不明白为什么要加一行        if(bcurrent<1) bcurrent = 1;

如果这样,实际结果小于的序列,算出来的结果都等于1了

kinzz

服了U

emacsnw

原帖由 yzc2002 于 2006-1-18 00:54 发表
我的那个算法是错的，我知道问题在哪，但不想改下去了，因为意义不大~~~
emacsnw是基于如下的想法：
设有队列x_1, x_2, ... x_i, 其中到x_i为止的连续积中，最大的为bcurrent(>0)， 最小的为wcurrent(主要要 ...

这位兄弟说的对，上次因为有点事情急着走了，贴了代码没来得及仔细解释一下。btw，我这段小程序能够通过上面几位的数据测试。

这个问题其实可以简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。

我们让bcurrent表示当前最大乘积的candidate，wcurrent反之，表示当前最小乘积的candidate。这里我用candidate这个词是因为只是可能成为新一轮的最大/最小乘积，而best则记录到目前为止所有最大乘积candidates的最大值。

由于空集的乘积定义为1，在搜索数组前，bcurrent,best,wcurrent都赋为1。
假设在任何时刻你已经有了bcurrent和wcurrent这两个最大/最小乘积的candidates，新读入数组的元素x(i)后，新的最大乘积candidate只可能是bcurrent或者wcurrent与x(i)的乘积中的较大者，如果x(i)<0导致bcurrent<wcurrent，需要交换这两个candidates的值。

当任何时候bcurrent<1，由于1（空集）是比bcurrent更好的candidate，所以更新bcurrent为1，类似的可以更新wcurrent。任何时候bcurrent如果比最好的best大，更新best。

算法其实比较简单，本人表达能力不行，大家将就着看吧。

emacsnw

原帖由 r2007 于 2006-1-18 02:35 发表
没有环境实际测试，不过通过推理，emacsnw的代码是经得起推敲的。
BTW: if(wcurrent>1) wcurrent = 1;这行应该可以省略。
如下
[code]double maxprod(double x[],int n)
{
    int i;
    double best = ...

简单看一下，好像是可以删掉这一行，多谢！

win_hate

原帖由 emacsnw 于 2006-1-19 14:41 发表


这位兄弟说的对，上次因为有点事情急着走了，贴了代码没来得及仔细解释一下。btw，我这段小程序能够通过上面几位的数据测试。

这个问题其实可以简化成这样：数组中找一个子序列，使得它的乘积最大；同时找 ...

r2002 给出的数据：

-0.01 5 -4 3

这个用你的代码算出 5， 实际应该是 6

emacsnw

原帖由 win_hate 于 2006-1-19 00:11 发表



r2002 给出的数据：

-0.01 5 -4 3

这个用你的代码算出 5， 实际应该是 6

是max{0.6,5} = 5，如果把-0.01改成-0.1就是6了。

[eon:tmp]$ ./a.out
4
-0.01 5 -4 3
5.000000
[eon:tmp]$ ./a.out
4
-0.1 5 -4 3
6.000000

win_hate

恩，是我看错了。

yzc2002

可以证明emacsnw的方法是正确的,而且if(wcurrent>1) wcurrent = 1;这一句也的确可以去掉.
设序列为
p...pN1p...pN2p...pNkp....p
其中p表示正数,Ni表示负数,min{Ni}表示到Ni为止(包括Ni)乘积中最小的, 而max{Ni}为最大的,以下用归纳法证明bcurrent=max{Ni}, wcurrent=min{Ni};
(1)经过第一个负数N1时,bcurrent<0, wcurrent<0, 而且bcurrent=min{N1}, 交换后,wcurrent=min{N1},而bcurrent=1,成立
(2)设经过第i-1个负数Ni-1后, bcurrent=max{Ni-1}, wcurrent=min{Ni-1}, 队列为:
....Ni-1p....PNip....
则在经过Ni前, bcurrent=max{P},wcurrent是连乘积<0,经过Ni后
bcurrent=min{Ni}<0, wcurrent>0, 又因为Ni<0,所以包括Ni的乘积要大于0,必然要包括Ni-1,也就是要包括Ni-1到Ni之间的所有正数,而在经过Ni-1后,wcurrent=min{Ni-1},所以经过Ni后wcurrent=max{Ni}>0,交换后得到bcurrent=max{Ni}, wcurrent=min{Ni},于是得证

win_hate

我明白了。

设给定的串为 x_1...x_n, emacsnw 的算法对 k 依次求出 x_1...x_k， 中的最大连续乘积。bcurrent 的实质是第 k 步中以 x_k 结尾的串的最大值，而 wcurrent 则是以 x_k 结尾的串中的最小值，其中包括空串。在下面我把 bcurrent 和 wcurrent 简写为 bc(k) 和 wc(k)，看成 k 的函数。

考虑 x_1...x_k 过渡到 x_1...x_{k＋1} 的情形，新增的串均以 x_{k+1} 结尾，我们只需要把新增串的值与 MAX  比较即可。新增串的值不必一一求出，只需求出这些串的最大值，也即 bc(k+1)。而 bc(k+1) 可通过 bc(k) 和 wc(k) 估计出来。设任一新增串为 s.x_{k+1}, 则有

(1) x_{k+1} >= 0
wc(k)<= s <= bc(k) --> wc(k)*x_{k+1} <= s.x_{k+1} <＝bc(k)*x_{k+1} --> wc(k+1)=wc(k)*x_{k+1} 或 1（新增串可为空串）；bc(k+1)=bc(k)*x_{k+1} 或 1。

(2) x_{k+1} <0
wc(k)<= s <= bc(k) --> wc(k)*x_{k+1} >= >=s.x_{k+1} >= bc(k)*x_{k+1} --> wc(k+1)=bc(k)*x_{k+1} 或 1；bc(k+1)=wc(k)*x_{k+1} 或 1。

q.e.d




跟各位讨论大有收益，谢谢！ 尤其是 emacsnw 给出了漂亮的代码。yzc2002 给出的漂亮证明，我在他的证明中理解了 bcurrent 的真正含义。

[ 本帖最后由 win_hate 于 2006-1-19 19:08 编辑 ]