| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2143 人关注过本帖
标题:[求助]一道竞赛问题求解
只看楼主 加入收藏
穆扬
Rank: 1
等 级:禁止发言
帖 子:1910
专家分:0
注 册:2006-6-1
收藏
得分:0 
提示: 作者被禁止或删除 内容自动屏蔽

2006-06-21 07:12
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 

对斑竹:
斑竹的说法有一些不妥之处:
(1)认为代码就表示的算法,但是抽象算法的确是代码不能够替代的,因为同样的思想可能有不同的代码,只给代码的方法把问题给具体化了,而不是从一般的角度去考虑问题;
(2)认为注释和算法解释与可读性不相关的想法有些过于偏执了,如果知道某算法再看代码会轻松地多的.
再看问题,斑竹的代码中,不知道时候诸葛亮式的解答是否一定是最优解答,如果是有没有证明呢?

对楼主:
该问题是一类比较经典的动态规划题目最一般的算法为O(N^2),算法如下:
int d[MAX+1];//MAX为数据个数
状态d[i]记录了序列{a1,a2,a3....ai}的包含第i个数的最长不上升序列长,
//注意这是一个子问题{a1,a2,...ai}是原序列的一个子序列.

再看状态转移,我们从d[1]开始,显然d[1]=1,这时对应的序列{a1}只有1个数,假设在我们已经知道了d[1]到d[i]的值,怎么算d[i+1]的值呢,最长不上升序列中a[i+1]的前一个数,它可以是比a[i+1]大或相等前面任意一个数a[j],当然a[i+1]可能没有前驱,如果a[i+1]能够找到对应的a[j](a[j]可能不止一个)包含a[i]又包含a[j]的最长不上升序列长为(d[j]+1),即该序列为{a1,a2,a3..aj}的包含a[j]的最长不上升序列最后加上一个a[i+1],如果a[i+1]没有前驱,显然d[i+1]=1;
到现在为止可以写出状态转移方程:
d[i]=max{d[j]+1 (high[j]>=high[i]&&j<i) , 1 }

PS:
如果楼主看过动态规划算法的一些内容,那么应该对这个问题很熟悉:
最长公共子序列问题:
给出两个字符串,求它们的最长公共子序列长:
其实这个问题也可以转化到最长公共子序列问题:
即求:
a[1],a[2],a[3],....a[N]
b[1],b[2],b[3].....b[N] //{b[n]}为{a[n]}经过降序排序后得到的序列
最长公共子序列长:

PS2:楼主提出的问题可以利用树一类的辅助优化出(NlogN)的算法,有兴趣的话可以上网用:最长不上升序列为关键字查一下

[此贴子已经被作者于2006-6-21 7:28:57编辑过]


我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2006-06-21 07:21
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 

floor 12:
真是一只扑腾着翅膀向天空飞翔的奇怪乌鸦。
不知高考分出来没有?拟报考哪所心仪学校?
默默为你祝福!愿你进了大学有更大长进。

floor 11:
喜欢你这股子执拗劲,但现实世界难容一根筋的人。
你像陈伯达,当年<红旗>杂志主编,马克思主义理论家。

关于注解与流程图:
1。有了思想才绘得出流程图
2。有了代码才谈得上写注释
3。那些始终写不好C程序的人
难道思路清晰仅仅是不会画流程图?
4。知道某算法再看代码轻松得多,OK!

PS:不信调查坛子里发帖跟帖人,有几人
是先画好流程图再将它转换成C代码的?


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-06-21 09:05
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 
以下是引用–★–在2006-6-21 9:05:32的发言:

floor 12:
真是一只扑腾着翅膀向天空飞翔的奇怪乌鸦。
不知高考分出来没有?拟报考哪所心仪学校?
默默为你祝福!愿你进了大学有更大长进。

floor 11:
喜欢你这股子执拗劲,但现实世界难容一根筋的人。
你像陈伯达,当年<红旗>杂志主编,马克思主义理论家。

关于注解与流程图:
1。有了思想才绘得出流程图
2。有了代码才谈得上写注释
3。那些始终写不好C程序的人
难道思路清晰仅仅是不会画流程图?
4。知道某算法再看代码轻松得多,OK!

PS:不信调查坛子里发帖跟帖人,有几人
是先画好流程图再将它转换成C代码的?

由于楼主缺乏开发真正应用程序的经验,导致出现轻视画流程图错误的结论。首先抛开数据结构与算法。假使你会C#或者VC++(这两个语言可以连接SQL server)并假定你都会连接数据库。
现在要求你做一个登陆,就是验证用户名跟密码是否正确。
如果我画了流程图。我就会知道获取密码其实可以写成一个 bool GetPassword(string Account ,string &password);就可以了
于是整个大概流程就是
bool Login(string Account, string Password)
{
string temPasswrod = "";
bool flag = GetPassword(Account,tempPassword);
if(flag)
return Password == tempPassword;
else
return false;
}
(在C里面 char *相当于C++/c#的string, bool可以看成 typedef int bool; true可以看成 #define true 1,false 就是0)
这样。因为就算出错我都可以不检查Login函数,直接检查GetPassword函数就可以了.
那样就可以快速定位错误在哪里。
当然,GetPassword里面的判断是否非法字符,连接数据库,打开数据库,查询sql的语句,又可以另外写一个函数。这需要画流程图一步步分析才可以清晰的。
当你真是这样实现了,那你写的函数的重用性就高,例如程序有很多地方要调用判断是否非法字符的函数。
通过画流程图,你就可以很清晰的分析问题。如果不画,我想大多数人都会将以上几个功能和在GetPassword里面。这样调试的时候就会很麻烦。
楼上的斑竹不要以为玩弄一下跟数学趣味题有关的程序就武断地说不用画流程图。这是因为你解题的思路其实就是用到数学的知识,用到程序方面的知识就少了点,所以就错误的认为流程图在脑里面,不用画。

[此贴子已经被作者于2006-6-21 10:48:17编辑过]


c++/C + 汇编 = 天下无敌
2006-06-21 10:19
–★–
Rank: 3Rank: 3
等 级:新手上路
威 望:6
帖 子:1512
专家分:0
注 册:2006-5-1
收藏
得分:0 
混淆概念了吧?你那叫“模块化”程序设计
或者C++的所谓对象“封装”跟流程图挨得上么?
至于代码的“重用性”,别见他母亲的鬼了。
几版windows以来连向上的兼容性都完了(比DOS还差)。
幸亏盗版大普及,要不然净花钱买升级版了。
一个滥VC++6.0占用那么多硬盘,还为它唱赞歌?
想想当年你怎么被骗的?
说DOS有系统漏洞,所以闹病毒,有没有这回事?
现在呢?各版windows闹得更邪乎,怎么解释呀?
病毒来得快,打补丁也快,我算是服了流程图!
嘿嘿。

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


落霞与孤鹜齐飞,秋水共长天一色! 心有多大,路有多宽。三教九流,鸡鸣狗盗。兼收并蓄,海纳百川。
2006-06-21 11:22
穆扬
Rank: 1
等 级:禁止发言
帖 子:1910
专家分:0
注 册:2006-6-1
收藏
得分:0 
提示: 作者被禁止或删除 内容自动屏蔽

2006-06-21 11:42
热情依然
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:22
帖 子:715
专家分:0
注 册:2005-4-5
收藏
得分:0 

你才概念混淆了,良好的模块化设计你不画流程图是分析不出来的。一个功能强大的开发环境必然占的硬盘多,Microsoft Visual Studio .NET 2003占用硬盘1.3G,但是很多公司都用来开发网站。你现在用的很多软件都是用VC++6.0写出来的,(例如QQ,eMule,都是基于MFC写的),有本事你就不要用。

(至于代码的“重用性”,别见他母亲的鬼了。)这句就可以看出楼上斑竹的知识浅薄,代码的重用性跟软件的兼容性是有差别的,你以上说的那个window的问题是软件的兼容有问题。但是开发的时候肯定是拿回以前window 2000的一些底层框架来写的(这是代码重用)。算拉,楼上的斑竹都是合适只做数学的趣味题算了.


c++/C + 汇编 = 天下无敌
2006-06-21 11:45
乌鸦丘比特
Rank: 1
等 级:新手上路
威 望:2
帖 子:625
专家分:0
注 册:2004-7-19
收藏
得分:0 
以下是引用–★–在2006-6-21 9:05:32的发言:

floor 12:
真是一只扑腾着翅膀向天空飞翔的奇怪乌鸦。
不知高考分出来没有?拟报考哪所心仪学校?
默默为你祝福!愿你进了大学有更大长进.

..今天出成绩呢.
斑竹好象还没有回答我的问题_也是我有些懒,没仔细看你的代码,你的算法能够保证得到绝对正确的答案么?


我喜欢创造,一只扑腾着翅膀向天空飞翔的乌鸦
2006-06-21 14:10
feng1256
Rank: 4
等 级:贵宾
威 望:14
帖 子:2899
专家分:0
注 册:2005-11-24
收藏
得分:0 
以下是引用乌鸦丘比特在2006-6-21 14:10:15的发言:

..今天出成绩呢.
斑竹好象还没有回答我的问题_也是我有些懒,没仔细看你的代码,你的算法能够保证得到绝对正确的答案么?

今天出?这么快?快查查! 想起了当年


叁蓙大山:工謪、稅務、嗣發 抱歉:不回答女人的问题
2006-06-21 14:12
lxgaaa
Rank: 1
等 级:新手上路
帖 子:59
专家分:0
注 册:2006-5-17
收藏
得分:0 

漂过,萝卜青菜个有所爱


天高任鸟飞,海阔任鱼翱
2006-06-21 15:28
快速回复:[求助]一道竞赛问题求解
数据加载中...
 
   



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

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