vxzv 发表于 2013-11-27 12:59:29

学算法有用吗？说有用的就进来做个题试试

甲乙两个人用一个英语单词玩游戏。两个人轮流进行，每个人每次从中删掉任意一个字母，如果剩余的字母序列是严格单调递增的（按字典序a < b < c <....<z)，则这个人胜利。两个人都足够聪明，甲先开始，问他能赢么？

输入： 一连串英文小写字母，长度不超过15,保证最开始的状态不是一个严格单增的序列。

输出：1表示甲可以赢，0表示甲不能赢。

例如: 输入 bad， 则甲可以删掉b或者a,剩余的是ad或者bd，他就赢了，输出1。

又如: 输入 aaa， 则甲只能删掉1个a，乙删掉一个a,剩余1个a，乙获胜，输出0。


说实话，好多算法题都不会，挺郁闷！！！

猪猪BBUn咕咕 发表于 2013-11-28 19:24:01

很多都不会拿就慢慢的靴靶

vxzv 发表于 2013-11-28 22:54:22

猪猪BBUn咕咕 发表于 2013-11-28 19:24 static/image/common/back.gif
很多都不会拿就慢慢的靴靶

嗯，加油~！！！！！！！！！！！！！

卧室不要床 发表于 2013-11-29 00:26:20

爱上对方身份

vxzv 发表于 2013-11-29 08:58:45

卧室不要床 发表于 2013-11-29 00:26 static/image/common/back.gif
爱上对方身份

？？？？？？？？？？？？？？？？？？？

shenyaowen 发表于 2013-12-2 23:57:02

这不是庞果网的试题么

vxzv 发表于 2013-12-3 14:38:10

shenyaowen 发表于 2013-12-2 23:57 static/image/common/back.gif
这不是庞果网的试题么

是的，被虐了，做不出来

猪猪BBUn咕咕 发表于 2013-12-18 21:13:15

大家一起加油啊~！！！！！！！！！！

全杨华 发表于 2013-12-18 21:15:09

肯定会有用啊

正在写代码 发表于 2013-12-18 21:27:08

当然有用了

翠竹 发表于 2013-12-18 22:35:22

博弈问题 难度比较大 第一想法肯定是递归 从简单入手 3个元素只有非递增的情况 先手才会是必败态 （cba caa cbb cca ccb ccc aaa bbb非递增） 如果大于3个 那么就循环枚举每一个元素 去掉以后如果是递增序列就先手胜 返回 如果不是递增序列 那么就递归下去 如果返回的是败 那么就说明该层是胜 返回1 这里对于每一个状态 最好都用一个类似哈希表的容器存储字符串的状态值 否则递归需要不断的重复计算 时间复杂度就不只是指数级 而是O(n!)级 时间复杂度就太大了 而采用容器存储方式 时间复杂度则是O(2^n)

后来又考虑逆序对 以DP想法由3向上递推 不过没想到子问题衍生很复杂 等我想好了再写

昵称Jin 发表于 2013-12-21 14:16:48

表示没看懂、。。。。。。

昵称Jin 发表于 2013-12-21 14:17:36

这都是社呢么了？:sweat:

vxzv 发表于 2013-12-21 14:27:20

昵称Jin 发表于 2013-12-21 14:17 static/image/common/back.gif
这都是社呢么了？

哈哈！是编程竞赛题，反正我目前用不到

正在写代码 发表于 2013-12-26 19:27:39

好有趣啊，。。。。

瑞恩 发表于 2014-1-12 07:00:32

算法不一定要你会，当成工具，知道怎么用人家的就好了
页: [1]
查看完整版本: 学算法有用吗？说有用的就进来做个题试试