标题:[求助]一道竞赛问题求解
只看楼主
x5471140
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2006-6-19
 问题点数:0 回复次数:27 
[求助]一道竞赛问题求解
给出一列数字,求其中最长不上升序列长。
例如:
589,58,79,26,12
最长序列为:589,58,26,12或589,79,26,12 长度为4
搜索更多相关主题的帖子: 问题求解 竞赛 序列 数字 
2006-06-20 09:19
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
得分:0 

楼主的问题其实就是

〖问题描述〗拦截敌国飞弹问题

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹
能够达到任意的高度,但是以后每一发炮弹都不能高于前
一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该
系统还在使用阶段,所以只有一套系统,因此有可能不能
拦截所有的导弹。输入导弹依次飞来的高度(雷达给出高
度数据是不大于30000的正整数) 计算这套系统最多能拦
截多少导弹?

输入 第一行 为导弹的个数

第二行 为使用逗号分隔的导弹依次飞来的高度
(雷达给出的高度数据是不大于30000 的正整数)

输出 这套系统最多能拦截多少导弹

测试输入

9 <回车>

190,207,155,300,299,170,800,158,650 <回车>

期待的输出 This machine can hold up 4 missles.

----------------------------------------------

#include<math.h>
#include<stdio.h>
#include<stdlib.h>

main()
{
int func(int*,int,long);
int num,*high,h,i;
int hit=0;//统计击落的飞弹
int HIT=0;//记录最大击落量
long st1,st2,sta;//状态变量
long STA;//状态(最大击落时)
printf("飞弹总数=");
scanf("%d",&num);
high=(int*)malloc(num*sizeof(int));

for(i=0;i<num;i++){
printf("飞弹No.%d高度=",i+1);
scanf("%d",&high[i]);}

st1=0;//一个都不拦截
st2=(long)pow(2,num)-1;//(企图)个个拦截
for(sta=st1;sta<=st2;sta++)
{
hit=func(high,num,sta);
if(hit<=HIT)continue;
HIT = hit;//刷新记录
STA = sta;//保存状态
}

printf("\n事后诸葛亮式的最佳对策是\n");
for(hit=i=0;i<num;i++)
{ char
b=STA%2;STA/=2;
if(b)
{
printf("主动拦截No.%d飞弹,",i+1);
if(hit==0||high[i]<=h)
{
printf("将其击落\n");
h=high[i];hit++;
}
else
printf("未能击落\n");
}
else
printf("放弃拦截No.%d飞弹\n",i+1);
}
printf("据此方案,共击落敌国飞弹%d枚\n",hit);
//或printf("据此方案,共击落敌国飞弹%d枚\n",HIT);
free(high);
}

int func(int*a,int n,long sta)
{
int k,func=0;
long high=999999;
char b;
if(sta>0)
for(k=0;k<n;k++)
{ b=sta%2;sta/=2;
if(!b)continue;//主动放弃
if(a[k]>high)break;
func++;
high=a[k];
}
return func;
}


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-06-20 10:17
x5471140
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2006-6-19
得分:0 
版主是否能给出具体的文字算法描述?
谢谢
2006-06-20 19:07
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
得分:0 
以下是引用x5471140在2006-6-20 19:07:41的发言:
版主是否能给出具体的文字算法描述?

不能,因我从来不画流程图。俺认为代码本身
就是算法+数据结构+程序员的风格+……

一个不肯花工夫读代码的人是走不了多远的


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-06-20 19:13
x5471140
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2006-6-19
得分:0 
用win-tc编译不能通过
2006-06-20 19:24
x5471140
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2006-6-19
得分:0 
谢谢版主批评,我会认真阅读
2006-06-20 19:28
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
得分:0 
回复:(x5471140)用win-tc编译不能通过
以下是引用x5471140在2006-6-20 19:24:49的发言:
用win-tc编译不能通过

建议你删除 “//及其后面跟的注释”
然后再试。


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-06-20 22:21
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
得分:0 

嘿嘿,楼上斑竹不画流程图这样的想法是及其错误的。正真做开发,一定要先画流程图,有个大概的思想,然后再根据大概的思想来讨论细节,这样写的程序才可以有效的模块化,如果只有个大概的思路就立刻写的话,很容易就给某个细节而捆住,而且写出来的程序肯定没有模块化的,通常都是一个函数就几个功能,这样既不利于调试,又不利于从用,又没有考虑到其他的细节。似乎你没有具备开发经验跟软件工程的思想

[此贴子已经被作者于2006-6-20 23:14:51编辑过]


c++/C + 汇编 = 天下无敌
2006-06-20 23:05
穆扬
Rank: 1
等 级:禁止发言
帖 子:1910
专家分:0
注 册:2006-6-1
得分:0 
提示: 作者被禁止或删除 内容自动屏蔽

2006-06-20 23:20
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
得分:0 
那拜托楼上二位中任何一位
写个快速排序(stdlib.h中的qsort)函数的流程图,OK?

我还是那句话:

画流程图是哄孩子玩的。
真正的流程图在脑袋里。
李昌镐、马晓春有流程图么?


还有注释与可读性正相关么?
全是聪明人骗呆子的鬼把戏。


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-06-21 05:49



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-73508-1-1.html




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

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