免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
1234下一页
最近访问板块 发新帖
查看: 9476 | 回复: 37

[算法] 请教大家一个算法题目 。 [复制链接]

论坛徽章:
0
发表于 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。

谢谢大家。

论坛徽章:
0
发表于 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大于当前最大值,则更新当前最大值。

论坛徽章:
0
发表于 2006-01-16 18:34 |显示全部楼层
上面说错了,负数的情况比较复杂,因为含有偶数个负数的串乘积仍是正的。

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

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

论坛徽章:
0
发表于 2006-01-17 08:34 |显示全部楼层
to win_hate
谢谢啊。。。。,我会再想想

论坛徽章:
0
发表于 2006-01-17 12:32 |显示全部楼层
空子序列的乘积定义为1。


这个是什么意思?
woxinfeixiang 该用户已被删除
发表于 2006-01-17 16:13 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
0
发表于 2006-01-17 16:20 |显示全部楼层
原帖由 woxinfeixiang 于 2006-1-17 16:13 发表



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


先参考这个帖子第6页

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

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

论坛徽章:
0
发表于 2006-01-18 01:15 |显示全部楼层


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

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

论坛徽章:
0
发表于 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),使得它
们的乘积在所有 ...


  1. #include <stdio.h>
  2.                                                                                 
  3. double maxprod(double x[],int n)
  4. {
  5.     int i;
  6.     double best = 1,worst = 1,bcurrent = 1,wcurrent = 1,t;
  7.                                                                                 
  8.     for(i = 0;i<n;++i){
  9.         bcurrent *= x[i];
  10.         wcurrent *= x[i];
  11.         if(bcurrent>best) best = bcurrent;
  12.         if(wcurrent>best) best = wcurrent;
  13.         if(bcurrent<worst) worst = bcurrent;
  14.         if(wcurrent<worst) worst = wcurrent;
  15.         if(wcurrent>bcurrent)
  16.             t = bcurrent,bcurrent = wcurrent,wcurrent = t;
  17.         if(bcurrent<1) bcurrent = 1;
  18.         if(wcurrent>1) wcurrent = 1;
  19.     }
  20.     return best;
  21. }
  22.                                                                                 
  23. int main()
  24. {
  25.     int n,i;
  26.     double x[100];
  27.                                                                                 
  28.     scanf("%d",&n);
  29.     for(i = 0;i<n;++i) scanf("%lf",&x[i]);
  30.     printf("%lf\n",maxprod(x,n));
  31. }

复制代码

论坛徽章:
0
发表于 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 =  ...




干的漂亮,太感谢了!
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP