| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1168 人关注过本帖
标题:C语言一个贪心算法题目
只看楼主 加入收藏
楓楪
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2009-8-5
结帖率:75%
收藏
已结贴  问题点数:20 回复次数:8 
C语言一个贪心算法题目
题目大意:
给出一个长度为N的数列(数列中至少有一个正数),要求求出其中的连续数之和的最大值。
我已经编了上半部分了
#include<stdio.h>
main()
{
FILE *fp;
int l=1,n,i,j,k,bj=0;
float x1,x2,last=0,len=0,s=0,b[100],a[100];
fp=fopen("sw.in","r");
fscanf(fp,"%d",&n);
for(i=1;i<=n;i++)
{fscanf(fp,"%d",&a[i]);
if(a[i]<0)
bj++;s+=a[i];}
fclose(fp);
fp=fopen("sw.out","w");
if(bj==0)
fprintf(fp,"%f",s);
else
{
i=1,l=1;
while(a[i]<0)
i++;
for(;i<=n;i++)
s+=a[i];
{if(a[i]>0&&a[i+1]<0||a[i]<0&&a[i+1]>0)
b[l++]=s;s=0;}
b[l]=s;
}
这里上面是将数列例如 2 2 -2 -3 -4 5 6 -6 变化成4 -9 11 -6   就是将同符号的加了起来
这里后面就不懂处理了


fclose(fp);
}
搜索更多相关主题的帖子: C语言 算法 贪心 
2009-08-05 12:27
楓楪
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2009-8-5
收藏
得分:0 
回复 楼主 楓楪
求救啊~~~~·各位帮忙啦
2009-08-05 12:34
CrystalFan
Rank: 8Rank: 8
来 自:江苏南京
等 级:蝙蝠侠
帖 子:187
专家分:802
注 册:2009-7-30
收藏
得分:0 
令sum[i][j]表示从下标为i的数到下标为j的数的和,简单的说就是把所有sum[i][j]都求出来。
递推公式:
sum[i][i]=a[i];
sum[i][j]=sum[i][j-1]+a[j];
这种方法效率不是很高,但是在做完楼主那样的优化后,效率就高得多了,数据量为1000左右应该都能很快出解。(注意,不要用递归)

[[it] 本帖最后由 CrystalFan 于 2009-8-5 13:11 编辑 [/it]]
2009-08-05 12:53
楓楪
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2009-8-5
收藏
得分:0 
回复 3楼 CrystalFan
没学过不能用
2009-08-05 13:01
CrystalFan
Rank: 8Rank: 8
来 自:江苏南京
等 级:蝙蝠侠
帖 子:187
专家分:802
注 册:2009-7-30
收藏
得分:10 
在你的优化后:
sum[i][i]=b[i];
sum[i][j]=sum[i][j-1]+b[j];
2009-08-05 13:13
CrystalFan
Rank: 8Rank: 8
来 自:江苏南京
等 级:蝙蝠侠
帖 子:187
专家分:802
注 册:2009-7-30
收藏
得分:0 
贪心法应该是可以做的。我还没想到。等其他NOI或ACM的高手吧。
2009-08-05 13:16
楓楪
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2009-8-5
收藏
得分:0 
回复 6楼 CrystalFan
啊 没人来了
2009-08-05 15:11
godbless
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:216
专家分:950
注 册:2009-7-24
收藏
得分:10 
#include <stdio.h>
#include <stdlib.h>
#define N 6

int main()
{
 int i,j,sum,Max,array[N];
 for(i=0;i<N;++i)
    scanf("%d",&array[i]);
 Max=array[N-1];
 for(i=0;i<N-1;++i)
    {
     sum=array[i];
     if(sum>Max) Max=sum;
     for(j=i+1;j<N;++j)
        {
         sum+=array[j];
         if(sum>Max) Max=sum;
        }
    }
 printf("%d\n",Max);
 system("pause");
 return 0;
}

不知道意思理解错了没有..
2009-08-05 15:35
liyejie3344
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2009-10-12
收藏
得分:0 
  偶是刚接触C 语言的 才鸟  来看 热闹的!!!!
2009-10-13 00:46
快速回复:C语言一个贪心算法题目
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.033325 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved