回 帖 发 新 帖 刷新版面

主题:第45次编程比赛的结果

[color=000080]第45次编程比赛的结果[/color]
第二题出的比较失败,没有人愿意做。...可能是这道题太常见了吧。我的本意是看中了这道题中有个栈的数据结构,让刚入门的同学练习的。
再说第一题,做的人也不多,但并不是没有可比性。syslwx和do熊都对自己第一次做出的程序进行了优化,虽然效率依然不是很高,但毕竟有所进步。syslwx、goal00001111和do熊的程序基本的思想都是一致的,即通过搜索找到满足条件的答案。但运行的效率却不一样。说明仍有需改进的地方。而tiancai007的程序的计算速度十分惊人。我帮他改了一下数据类型,将ulong 改为__int64。可以在瞬间算出n=13的情况。在n=14的情况下溢出。而我自己的程序用的也是__int64,在n=12时就溢出了。所以,第45次编程比赛的胜出者是[color=800000]tiancai007[/color],在此祝贺他。[color=FF0000]并请他准备下次比赛的题目。[/color]
对于BigCarrot所说的可以算到n=100的情况,实在是无语了,欺负我不会Java。不过如果有一个合适的巨型数运算类的话,我想我的程序和tiancai007的程序也许也能算到n=100。
这道题是比较的偏向数学,我也承认我就是用排列组合做的,但并不是每个人都能用排列组合做出这道题,我也不认为有人能不用计算机就算出n>10的情况。电脑和编程本来就是工具,是用来解决各个学科的问题的,哪有万能的算法?哪有最好的算法?何必就因为它不是一道动态规划或网络流的问题就不愿去做呢?
小弟初来,顺便问一下,是不是出过题后要潜水一段时间?因为我发现前几次比赛的优胜者基本上都不见了,是不是这也是一个规矩呢?

回复列表 (共4个回复)

沙发

楼主把第二题的做法贴出来看看……
编程比赛看来是考算法的,我真是不才啊,见笑了。。。
是有必要多研究研究算法了。
我还有个问题,就是通过你们的程序可以把所有的可能情况打印出来吗?
如果可以,需要如何做呢?

板凳

用排列组合的方法不能把可能情况printf出来。第二题嘛,基本的NOI练习题,在网上搜索"单向双轨道"就行了。编程比赛并不考什么东西,只是给大家一个写代码,动脑子的机会。以及一个大家互相交流的平台。我是这么觉的。

3 楼

用java做实在是很抱歉,我现在这台机器上确实只有jdk, 没有vc
是否能算到100还是1000,是否用了高精度数其实并不重要
重要的是算法的效率,算法的时间复杂度,空间复杂度
还有算法是否简洁漂亮

本来我也是用int, 那样看上去和c几乎就是一抹一样了
但是发现这个问题的答案实在是大,
很快就溢出了
正好java有现成的高精度数的实现
就拿了过来

"我也不认为有人能不用计算机就算出n>10的情况"
用我的算法
只要按顺序计算两个数组的值
即使手算,算到n>10并不复杂
肯定比我写这个程序要快得多

4 楼

BigCarrot 的算法我看过了

算法复杂度是  o(n*n*logn),不是 o(n)

我来回复

您尚未登录,请登录后再回复。点此登录或注册