免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: dbcat

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

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

  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. }
复制代码


能说一下思路吗? 谢谢.

我测了一下:

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 编辑 ]

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

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

其实再考虑以下这种情况就可以了:
以N表负数,P表正数,序列可以看作由若干个负数分割,求出两个负数之间的正数的最大乘积和你所求出的最大值相比,取最大数就可以了
  1. double
  2. max_subsequence_mul( double a[], unsigned int n, int *begin, int *end )
  3. {
  4.     double this_mul, max_mul;
  5.     int    best_i, best_j, i = 0, j;
  6.     this_mul = max_mul = 1; best_i = best_j = -1;

  7.     double max;

  8.     int pos_i, pos_j, pos_start = 0;
  9.     double pos_mul, max_pos;
  10.     pos_mul = max_pos = 1; pos_i = pos_j = -1;
  11.     for( j=0; j<n; j++ )
  12.     {
  13.         pos_mul *= a[j];
  14.         if( pos_mul > max_pos)
  15.         {
  16.             max_pos = pos_mul;
  17.             pos_i = pos_start;
  18.             pos_j = j;
  19.         }
  20.         else if(pos_mul < 1)
  21.         {
  22.             pos_start = j + 1;
  23.             pos_mul = 1;
  24.         }
  25.         this_mul *= a[j];
  26.         if( this_mul > max_mul )
  27.         {
  28.             max_mul = this_mul;
  29.             best_i = i;
  30.             best_j = j;
  31.         }
  32.         else if( fabs(this_mul) < 1)
  33.         {
  34.             i = j + 1;
  35.             this_mul = 1;
  36.         }
  37.     }
  38.     if(max_pos > max_mul)
  39.     {
  40.         *begin = pos_i;
  41.         *end   = pos_j;
  42.         max = max_pos;
  43.     }
  44.     else
  45.     {
  46.         *begin = best_i;
  47.         *end   = best_j;
  48.         max = max_mul;
  49.     }
  50.     return( max );
  51. }
复制代码

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

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



  1. double maxprod(double x[],int n)
  2. {
  3.     int i;
  4.     double best = 1,bcurrent = 1,wcurrent = 1,t;

  5.     for(i = 0;i<n;++i){
  6.         bcurrent *= x[i];
  7.         wcurrent *= x[i];
  8.         if(wcurrent>bcurrent)
  9.             t = bcurrent,bcurrent = wcurrent,wcurrent = t;
  10.         if(bcurrent>best) best = bcurrent;
  11.         if(bcurrent<1) bcurrent = 1;
  12.         if(wcurrent>1) wcurrent = 1;
  13.     }
  14.     return best;
  15. }

复制代码

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

评分

参与人数 1可用积分 +3 收起 理由
win_hate + 3 原创内容

查看全部评分

论坛徽章:
0
发表于 2006-01-18 12:33 |显示全部楼层
emacsnw的和我的程序都有问题
5
-0.01  2  -4  3  -0.5

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

论坛徽章:
0
发表于 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),不知道应该是多少?

论坛徽章:
0
发表于 2006-01-18 14:17 |显示全部楼层
是我看错了,sorry!

论坛徽章:
7
荣誉版主
日期:2011-11-23 16:44:17子鼠
日期:2014-07-24 15:38:07狮子座
日期:2014-07-24 11:00:54巨蟹座
日期:2014-07-21 19:03:10双子座
日期:2014-05-22 12:00:09卯兔
日期:2014-05-08 19:43:17卯兔
日期:2014-08-22 13:39:09
发表于 2006-01-18 16:20 |显示全部楼层
原帖由 emacsnw 于 2006-1-18 13:27 发表


我的程序返回12.0 (2*-4*3*-0.5),不知道应该是多少?

试试这组数

-0.01, 5, -4, 3

论坛徽章:
0
发表于 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 是同一个起点吗?

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

论坛徽章:
7
荣誉版主
日期:2011-11-23 16:44:17子鼠
日期:2014-07-24 15:38:07狮子座
日期:2014-07-24 11:00:54巨蟹座
日期:2014-07-21 19:03:10双子座
日期:2014-05-22 12:00:09卯兔
日期:2014-05-08 19:43:17卯兔
日期:2014-08-22 13:39:09
发表于 2006-01-18 18:35 |显示全部楼层
没有环境实际测试,不过通过推理,emacsnw的代码是经得起推敲的。
BTW: if(wcurrent>1) wcurrent = 1;这行应该可以省略。
如下
  1. double maxprod(double x[],int n)
  2. {
  3.     int i;
  4.     double best = 1,bcurrent = 1,wcurrent = 1,t;

  5.     for(i = 0;i<n;++i){
  6.         bcurrent *= x[i];
  7.         wcurrent *= x[i];
  8.         if(wcurrent>bcurrent)
  9.             t = bcurrent,bcurrent = wcurrent,wcurrent = t;
  10.         if(bcurrent>best) best = bcurrent;
  11.         if(bcurrent<1) bcurrent = 1;
  12.     }
  13.     return best;
  14. }
复制代码
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP