Chinaunix

标题: 请教大家一个算法题目。 [打印本页]

作者: dbcat 时间: 2006-01-16 16:52
标题: 请教大家一个算法题目。
题目如下：

令 X（1）， X（2），X（3）， X（4）。。。X（n）是一串实数（不需要一定为正数）。
设计一个O（n）的算法，寻找一个（连续的）子序列X（i），X（i+1）。。。X（j），使得它
们的乘积在所有子序列乘积中最大。空子序列的乘积定义为1。

谢谢大家。

作者: win_hate 时间: 2006-01-16 18:21
这个题目跟以前那个最大连续子列和是类似的。

便于讨论，我们先假定 x_1, ..., x_n 中没有负数，则 x_1, ..., x_n 的最大连续子列积对应于 log(x_1), ...,log(x_n) 的最大局部子列和。由于空串有值1，所以最后应把上面求得的串值与1比较。

若 x_1, ..., x_n 中存在负数，则含负数的串不合要求，因为空串值更大。

不过，实现时无需取对数，当前乘积值s为1，x_1 起向后搜索，s = s*x_i, 若 s<1 则从　x_{i+1} 起重新搜索，当前最大值不变；否则，若s大于当前最大值，则更新当前最大值。

作者: win_hate 时间: 2006-01-16 18:34
上面说错了，负数的情况比较复杂，因为含有偶数个负数的串乘积仍是正的。

修改方案为：求绝对值的乘积，并用一个变量记录当前乘积的符号，若负则不更新最大值。即前面的 s=s*x_i 改为 s=s*|x_i|.

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

作者: dbcat 时间: 2006-01-17 08:34
to win_hate
谢谢啊。。。。，我会再想想

作者: foolishfox 时间: 2006-01-17 12:32
空子序列的乘积定义为1。

这个是什么意思?

作者: woxinfeixiang 时间: 2006-01-17 16:13
提示: 作者被禁止或删除内容自动屏蔽

作者: win_hate 时间: 2006-01-17 16:20

原帖由 woxinfeixiang 于 2006-1-17 16:13 发表

和当前值比较的时候，是每乘以一个数就比较一次吗~~~最好给出一个算式。脑袋笨转不过来！~
等待指教！

先参考这个帖子第6页

http://bbs.chinaunix.net/viewthr ... p;extra=&page=6

看 yzc2002 的代码和我给出的说明。这两个问题是类似的。

作者: win_hate 时间: 2006-01-18 01:15

很遗憾，我上面给出的算法有严重的 bug, 它在序列全为正数时工作得很好，但不能处理负数的情况。

负数该如何处理，我还没想好，期待高手指点。

作者: emacsnw 时间: 2006-01-18 04:33

原帖由 dbcat 于 2006-1-16 00:52 发表
题目如下：

令 X（1）， X（2），X（3）， X（4）。。。X（n）是一串实数（不需要一定为正数）。
设计一个O（n）的算法，寻找一个（连续的）子序列X（i），X（i+1）。。。X（j），使得它
们的乘积在所有 ...

#include <stdio.h>
double maxprod(double x[],int n)
{
int i;
double best = 1,worst = 1,bcurrent = 1,wcurrent = 1,t;
for(i = 0;i<n;++i){
bcurrent *= x[i];
wcurrent *= x[i];
if(bcurrent>best) best = bcurrent;
if(wcurrent>best) best = wcurrent;
if(bcurrent<worst) worst = bcurrent;
if(wcurrent<worst) worst = wcurrent;
if(wcurrent>bcurrent)
t = bcurrent,bcurrent = wcurrent,wcurrent = t;
if(bcurrent<1) bcurrent = 1;
if(wcurrent>1) wcurrent = 1;
}
return best;
}
int main()
{
int n,i;
double x[100];
scanf("%d",&n);
for(i = 0;i<n;++i) scanf("%lf",&x[i]);
printf("%lf\n",maxprod(x,n));
}

复制代码

作者: dbcat 时间: 2006-01-18 10:09

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

[code]
#include <stdio.h>

double maxprod(double x[],int n)
{
int i;
double best = 1,worst = ...

干的漂亮，太感谢了！

作者: win_hate 时间: 2006-01-18 10:26

#include <stdio.h>



double maxprod(double x[],int n)

{

int i;

double best = 1,worst = 1,bcurrent = 1,wcurrent = 1,t;



for(i = 0;i<n;++i){

      bcurrent *= x[i];

      wcurrent *= x[i];

      if(bcurrent>best) best = bcurrent;

      if(wcurrent>best) best = wcurrent;

      if(bcurrent<worst) worst = bcurrent;

      if(wcurrent<worst) worst = wcurrent;

      if(wcurrent>bcurrent)

         t = bcurrent,bcurrent = wcurrent,wcurrent = t;

      if(bcurrent<1) bcurrent = 1;

      if(wcurrent>1) wcurrent = 1;

}

return best;

}



int main()

{

int n,i;

double x[100];



scanf("%d",&n);

for(i = 0;i<n;++i) scanf("%lf",&x[i]);

printf("%lf\n",maxprod(x,n));

}

复制代码

能说一下思路吗?

谢谢.

我测了一下:

cc 1.c
./a.out

4
2.0 -2.0 2.0 2.0
1.00000

［更正］上面算出1估计是终端跟我开的玩笑，我把数据写到一个文件中，然后用 ./a.out <data 就好用了。

[ 本帖最后由 win_hate 于 2006-1-18 16:38 编辑 ]

作者: yzc2002 时间: 2006-01-18 11:27

原帖由 win_hate 于 2006-1-16 18:34 发表
上面说错了，负数的情况比较复杂，因为含有偶数个负数的串乘积仍是正的。

修改方案为：求绝对值的乘积，并用一个变量记录当前乘积的符号，若负则不更新最大值。即前面的 s=s*x_i 改为 s=s*|x_i|.

其实再考虑以下这种情况就可以了：
以N表负数，P表正数，序列可以看作由若干个负数分割，求出两个负数之间的正数的最大乘积和你所求出的最大值相比，取最大数就可以了

double
max_subsequence_mul( double a[], unsigned int n, int *begin, int *end )
{
double this_mul, max_mul;
int best_i, best_j, i = 0, j;
this_mul = max_mul = 1; best_i = best_j = -1;
double max;
int pos_i, pos_j, pos_start = 0;
double pos_mul, max_pos;
pos_mul = max_pos = 1; pos_i = pos_j = -1;
for( j=0; j<n; j++ )
{
pos_mul *= a[j];
if( pos_mul > max_pos)
{
max_pos = pos_mul;
pos_i = pos_start;
pos_j = j;
}
else if(pos_mul < 1)
{
pos_start = j + 1;
pos_mul = 1;
}
this_mul *= a[j];
if( this_mul > max_mul )
{
max_mul = this_mul;
best_i = i;
best_j = j;
}
else if( fabs(this_mul) < 1)
{
i = j + 1;
this_mul = 1;
}
}
if(max_pos > max_mul)
{
*begin = pos_i;
*end = pos_j;
max = max_pos;
}
else
{
*begin = best_i;
*end = best_j;
max = max_mul;
}
return( max );
}

复制代码

[ 本帖最后由 yzc2002 于 2006-1-18 12:48 编辑 ]

作者: emacsnw 时间: 2006-01-18 11:39

原帖由 win_hate 于 2006-1-17 18:26 发表

能说一下思路吗? :D 谢谢.

我测了一下:

在我这儿没问题：
./a.out
4
2.0 -2.0 2.0 2.0
4.000000

由于不要求最小乘积，函数中可以不用求worst以及更新它，因此循环中可以再减少两个if语句。大概思路就是同时记下目前为止可以得到的最大(bcurrent)和最小(wcurrent)乘积，下一步的最大乘积只可能是 max{bcurrent*x(i),wcurrent*x(i),1}
由于有可能有负数，乘上x(i)后有可能bcurrent和wcurrent要互换。

double maxprod(double x[],int n)
{
int i;
double best = 1,bcurrent = 1,wcurrent = 1,t;
for(i = 0;i<n;++i){
bcurrent *= x[i];
wcurrent *= x[i];
if(wcurrent>bcurrent)
t = bcurrent,bcurrent = wcurrent,wcurrent = t;
if(bcurrent>best) best = bcurrent;
if(bcurrent<1) bcurrent = 1;
if(wcurrent>1) wcurrent = 1;
}
return best;
}

复制代码

[ 本帖最后由 emacsnw 于 2006-1-17 19:59 编辑 ]

作者: yzc2002 时间: 2006-01-18 12:33
emacsnw的和我的程序都有问题
5
-0.01 2 -4 3 -0.5

[ 本帖最后由 yzc2002 于 2006-1-18 13:05 编辑 ]

作者: emacsnw 时间: 2006-01-18 13:27

原帖由 yzc2002 于 2006-1-17 20:33 发表
emacsnw的和我的程序都有问题
5
-0.01 2 -4 3 -0.5

我的程序返回12.0 （2*-4*3*-0.5），不知道应该是多少？

作者: yzc2002 时间: 2006-01-18 14:17
是我看错了,sorry!

作者: r2007 时间: 2006-01-18 16:20

原帖由 emacsnw 于 2006-1-18 13:27 发表

我的程序返回12.0 （2*-4*3*-0.5），不知道应该是多少？

试试这组数

-0.01, 5, -4, 3

作者: win_hate 时间: 2006-01-18 16:36
yzc2002 兄的代码似乎有问题，算法我没看明白。

double
max_subsequence_mul( double a[], unsigned int n, int *begin, int *end )
{
double this_mul, max_mul;
int best_i, best_j, i = 0, j;
this_mul = max_mul = 1; best_i = best_j = -1;

double max;

int pos_i, pos_j, pos_start = 0;
double pos_mul, max_pos;
pos_mul = max_pos = 1; pos_i = pos_j = -1;
for( j=0; j<n; j++ )
{
      pos_mul *= a[j];
      if( pos_mul > max_pos)
      {
         max_pos = pos_mul;
         pos_i = pos_start;
         pos_j = j;
      }
      else if(pos_mul < 1)
      {
         pos_start = j + 1;
         pos_mul = 1;
      }
      this_mul *= a[j];
      if( this_mul > max_mul )
      {
         max_mul = this_mul;
         best_i = i;
         best_j = j;
      }
      else if( fabs(this_mul) < 1)
      {
         i = j + 1;
         this_mul = 1;
      }
}
if(max_pos > max_mul)
{
      *begin = pos_i;
      *end = pos_j;
      max = max_pos;
}
else
{
      *begin = best_i;
      *end = best_j;
      max = max_mul;
}
return( max );
}

2,2, -2,0.5, 0.5, -2,2, 2, 2, 2, -4

算出来是 64.0，实际应当是 128

我很想把这个问题搞清楚，希望大家能把想法写清晰一些。

to emacsnw: 你所说的 bcurrent 当然有一个起点，这个起点是如何变化的呢？跟 wcurrent 是同一个起点吗？

作者: yzc2002 时间: 2006-01-18 16:54
我的那个算法是错的，我知道问题在哪，但不想改下去了，因为意义不大~~~
emacsnw是基于如下的想法：
设有队列x_1, x_2, ... x_i, 其中到x_i为止的连续积中，最大的为bcurrent(>0)，最小的为wcurrent(主要要用<0的值)，当x_{i+1}加入队列时，若x_{i+1} > 0，则考虑bcurrent * x_{i+1}，否则考虑wcurrent*x_{i+1}，这两个的最大值与max相比，比max大就说明有更大的连续积，再次修正最大积和最小积

但 if(wcurrent>1) wcurrent = 1;能保证得到最小积吗？emacsnw能不能证明一下？

[ 本帖最后由 yzc2002 于 2006-1-18 17:00 编辑 ]

作者: r2007 时间: 2006-01-18 18:35
没有环境实际测试，不过通过推理，emacsnw的代码是经得起推敲的。
BTW: if(wcurrent>1) wcurrent = 1;这行应该可以省略。
如下

double maxprod(double x[],int n)
{
int i;
double best = 1,bcurrent = 1,wcurrent = 1,t;
for(i = 0;i<n;++i){
bcurrent *= x[i];
wcurrent *= x[i];
if(wcurrent>bcurrent)
t = bcurrent,bcurrent = wcurrent,wcurrent = t;
if(bcurrent>best) best = bcurrent;
if(bcurrent<1) bcurrent = 1;
}
return best;
}

复制代码

作者: atg 时间: 2006-01-18 19:26
来看看!

作者: foolishfox 时间: 2006-01-19 01:20

原帖由 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 时间: 2006-01-19 12:06
服了U

作者: emacsnw 时间: 2006-01-19 14:41

原帖由 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 时间: 2006-01-19 14:55

原帖由 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 时间: 2006-01-19 16:11

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

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

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

r2002 给出的数据：

-0.01 5 -4 3

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

作者: emacsnw 时间: 2006-01-19 16:29

原帖由 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 时间: 2006-01-19 16:31
恩，是我看错了。

作者: yzc2002 时间: 2006-01-19 17:21
可以证明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 时间: 2006-01-19 19:05
我明白了。

设给定的串为 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 编辑 ]

作者: pcboyxhy 时间: 2006-01-19 20:57
很明显
是动态规划

作者: dbcat 时间: 2006-01-20 09:33
Excelent！

谢谢各位高手的耐心解答，我又从中学到了不少东西。
再次向各位致敬

作者: macrodba 时间: 2006-01-25 16:53
学习ｉｎｇ　　！！！！

作者: ArXoR 时间: 2006-01-25 22:52
dp...
记录到当前位置的最大值和最小值就可以了

作者: zwylinux 时间: 2006-11-15 00:54
我写的一个
#include<stdio.h>
#define SIZE 5
main ()
{
  int max = 0; //记录最大值
  int i;
  int m = 0;//m用来记录出现的第一个非负数的位置
  int k = 0;//k用来记录出现的第一个负数的位置
  int this = 1;//this记录当前积的大小
  int j = 1;//j控制k只记录第一个负数的位置
  int A[SIZE] = {-1,-2,-3,-4,-5 };
  for (i = 0; i < SIZE; i++)
{
   if (A[i] == 0)//如果遇到0，this重新开始
      {
      j = 1;
      m = i + 1;
      this = 1;
      continue;
      }
   if (A[i] < 0 && j)//j在这里控制k只记录第一个负数的位置
      {
      k = i;
      j = 0;
      }
   this *= A[i];
max = this > max ? this : max;
}
  for (i = m; i <= k; i++)
this /= A[i];
  max = this > max ? this : max;
  printf ("Max=%d\n", max);
}

作者: zhangjinsuo 时间: 2008-05-28 17:33
Code还是有Bug，没有考虑到0的问题
动态规划，应该是MSRA的面试题

作者: tyz 时间: 2008-05-28 17:57
牛B啊
自惭形秽啊
亏得自己还是科班出身

作者: tyz 时间: 2008-05-28 18:09

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

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

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

哥，你是咋想到的啊

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)