约瑟夫环问题

米落,2009年10月29日

问题描述: n个人围成一圈,并依次编号1～n。从编号为1的人开始，按顺时针方向每隔一人选出一个，剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个幸运儿，请问开始时应该站在什么位置？（设3<=n<=50）
输入：开始时的人数n
输出：第1行是选出顺序，第2行是两名幸运儿的开始位置（按升序排列），位置编号之间用一个空格分开。
示例
输入：
12
输出：
2 4 6 8 10 12 3 7 11 5
1 9

More...

more...

分类: Programer | Tags: JavaScript  题目  算法   | 评论:0

每天几百行的练习

米落,2009年10月28日

    才在机房感受没几天,就被告知要去参加个比赛,具体内容未知,不过是能敲代码的事儿,咱都得搀和一下,不然对不上咱这程序员的目标哈.
    一次选拔后就直接培训了,国庆中秋都没回去,母亲大人电话里唠唠叨叨的,说什么翅膀硬了就像飞走了,家都不要了.我乐得,笑着说,哪能,是真的有个很重要的比赛,需要提前准备.母亲也不情愿的同意了.
    得知不就是ACM地区选拔么,我也无心把精力放在算法上,因为咱只是个瞎搅和的coder,也知道自己有几斤几辆,那种纯理论的啥确实很咱不容易打到一起去,一般直接拖来个类库调用下api 也就不错了.^_^
    系里派出了四个代表队,开始还吓唬说只放三个去比赛,得淘汰一个,后来就知道了不过是个激将法.四个都去成了,虽然结果很悲剧.
    两个队用 C,两个队用 Java, 虽然我们大部分都是学.net /C# 的.可惜比赛不让用,不然前期的熟悉时间也省了,可是自己也想多开阔下眼界,使用下Java 也不坏.这么一安排就出现了一些争论也就是关于C 和 Java 的. 虽然只是停留在很浅的层次上不过还是拿出来献献丑吧.
    C 小组们说的是 Java 之类成熟的框架已经将程序员变弱智了,很多不知道一点点数据结构,一点点算法的人就在摆弄什么什么框架,什么什么架构,用来用去都是别人的东西,自己反倒是一点点长进都没有.
    Java 小组则是争锋相对,"站在巨人的肩膀上让我们看得更远", 算法,数据结构 这些前人也深入的足够了,我们现在所做的不过是重复,还不如用来熟悉其他更能加快我们开发的东西,我们是搞商品的,不是搞科研的,只要保证认得什么是快 排,他和冒泡有多大的效率区别就足够了,Java 随便一个api调用就得让 C 小组写个十几行了.
    当然这些都不是绝对的,C 组的指针传来传去传得正欢的时候,我们正在为类型转换而发愁, C# 用爽了 Convert 到了Java 却要一个个基础类型自己去转换,而且基础类型也要包装,实在痛苦.而且使用的是jdk 1.4 ,没有泛型,一直都在不停的装箱拆箱.
    更郁闷的是,到了考点(湖南林业科技大学) 却发现是jdk 1.6,当时砸电脑的心都有了,因为有些类库并不是都兼容的,特别是有泛型这一特性,还有集合里的方法多了许多,于是在比赛的前一晚看了一宿的api.
    比赛来的很突然,也没太多准备,十月十七比赛,九月底才被告知一起集训,熟悉Java.此前确实摸过Java,写了一Hello World.
    然后是近半个月的数据结构以及算法的学习,链串栈队列树图,冒泡,插入,快排.....以前也学过,不过都是为了完成作业才会去思考怎么用的,而现在确实 实打实的需要这些工具,不然自己的思路土方法也太不明智了.(一次别人回溯十几行的代码解决的问题,我自己写的字符串解析应是到了一两百行都还没解出问 题),结果是颇有成效,知道在什么情况下该用些什么结构,并且一些简单的算法的使用了,最后有难度的就是DP(动态规划) 的学习,因为一般递归后面就是贪心,然后就是动态规划了,我是照这个思路来的,所以还算能够上手,边界,备忘录之类的还算能理解,不过在最优子递归的时候 就很难设计出一个合理的循环了,不是死循环就是全部情况没能考虑,残念.

    比赛就是三人一台电脑,一共八道题,做出一道提交后通过裁判系统看返回结果,Yes就直接通过,其他则为出错,这款程序本身除了submit 还有一个 test, 但是在这次比赛里却没作用,后来发现提交错误后直接修改了再提交就是了,根本不会有加时,因为本身提交的就少,做出来个就更少了,连所有名次都排不满,怎 么还会去比时间.
    答对一道就会有一个气球奖励,插在桌面上,有鼓励的意思,更多的是炫耀吧,当然,我也只是吃不到葡萄说葡萄是酸的.
    我们组的结果很悲剧,第一题是道模拟一群小球的在有限区域里的相互碰撞,这个在Flash里做多了,就直接对着翻起来(从C++ 翻到 Java) ,前面都没怎么细看,后来才发现有几个功能函数自己不会,要一点数学基础,什么点积之类的,就郁闷了,自己回想一些Flash 里的脚本,好像是要用到三角函数之类的,于是乱套,结果很悲剧,实例都没过,就没提交.
    有了第一道的悲剧,就读全部题目才会开始动笔,而且决定一题就对不放,后来想到也没什么可放的,一道题就要一个多小时,我一个人编的话更慢.
    第二道是选的一道中文题,模拟窗体之间的事件操作,主要是有一个子窗体有一些判断需要,输入的是一些操作步骤,还要验证那些操作是无效的,也是看题不仔 细,没看到一个要求排序的要求,结果就那个排序耗了很多时间(对三个字段按顺序排序),做出来的时候测试过了,提交却返回结果错误,我也觉得这个题目没选 好,因为根本都不知道错在哪,真要写选择树都不知道要耗几个小时.总之结果很杯具.
    其他的题目也就看了几眼,三道英文题也在同组队员翻译完后发现剩余的时间不够了,反正回来的时候都不太想说话了.

    这就是牺牲了国庆,中秋假期的结果,相当不甘.
    实力差距吧,又让我知道了我不是一个人,还有成百上千的同僚们正在沉寂在代码的乐园中,我不是一个人.

    回来后发现自己的时候突然多了很多,自由的不太熟悉了,班上的同学们也都好像不认识我了,又是一段新的开始,充满了挑战,充满了希望.
    因为难,才好玩.

More...

more...

分类: Booooer. | Tags: | 评论:1

分页:[«]1[»]