有一个java题需要解答 15

甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a<b<c<....<z),则这个人胜利。两个... 甲乙两个人用一个英语单词玩游戏。两个人轮流进行,每个人每次从中删掉任意一个字母,如果剩余的字母序列是严格单调递增的(按字典序a < b < c <....<z),则这个人胜利。两个人都足够聪明,甲先开始,问他能赢么?
输入: 一连串英文小写字母,长度不超过15,保证最开始的状态不是一个严格单增的序列。
输出:1表示甲可以赢,0表示甲不能赢。
例如: 输入 bad, 则甲可以删掉b或者a,剩余的是ad或者bd,他就赢了,输出1。
又如: 输入 aaa, 则甲只能删掉1个a,乙删掉一个a,剩余1个a,乙获胜,输出0。
函数头部:
Java:public static int who(String in);
展开
 我来答
百度网友799369c
2013-12-04 · TA获得超过562个赞
知道小有建树答主
回答量:514
采纳率:66%
帮助的人:159万
展开全部
足够聪明。。。这是奥数题,不是java题,挺有意思,应该有简便方法

这么久了没人提出个思路,我自己想了个思路,完全可行但是可能略微麻烦
思路:假如有n个字符,那么每两个字符直接都有一个大小关系,总共有n*(n-1)个【关系】。比如说bad,b>a,b<d,a<b,a<d,d>b,d>a这6个【关系】,其中b>a跟a<b是同一个【关系】,所以去掉后剩下b>a,b<d,a<d这三个【关】系n*(n-1)/2。因为你要的是递增,所以b>a不满足,b<d和a<d满足,所以可以认为【关系】b>a是错误的,另外两个是正确的。甲要赢,就必须达到所有【关系】是正确的,所以必须删除单个字母关联【关系】错误最多的那个字母。比如说b,有两个【关系】:b>a:错误,b<d:正确。就是说b的所有【关系】中错1对1。同理,a的【关系】b>a错误,a<d正确。a的所有【关系】中也是错1对1,而d的【关系】就是都对的。甲为了赢,就得删除相关联的【关系】错误最多的字符。这里a和b都是错1对1,而d是对2。所以a和b任意删除一个,甲就赢了。而乙则相反,应该删除对的【关系】最多的那个字符,这里就是d对2,删了乙就赢了。这就是最聪明的删除方法。

程序具体做法:建立一个【关系】的class,里面有三条属性,一是第一个字母,二是第二个字母,三是【关系】的对错。
然后你输入n个字符,就建立n*(n-1)/2个【关系】,通过循环和判断写入属性。
删除的时候自己决定下谁先删(这个随你高兴),删一个字母就删掉所有该字母相关联的【关系】。甲通过循环判断当前字母中谁的关系是错误最多的,删掉该字母和所有该字母相关的【关系】,然后乙继续,删除正确的最多的字符和所有相关【关系】。最后判断不用我说了吧
百度网友9ccec88
2013-12-08 · TA获得超过2018个赞
知道大有可为答主
回答量:2154
采纳率:50%
帮助的人:1599万
展开全部
这跟象棋差多了,两人足够聪明的意思就是指两人看出了此问题的本质,所以能不输,肯定不会输。举个例子.1,abcfd,甲先走,肯定删f,会成abcd,甲胜。但是2,abcgfd,甲聪明就不会先删g或者f,会去找abc里面的删,谁先删了g(或f),另一个人立马删f(或g),就结束了。所以此题是定的,字符串定下,胜负就定了,关键是找出规律。
---其实我是回那个"达摩高僧"的,但以上的话我贴到评论里被评为有不合适的词语,我找了半天楞是找不出来“不合适的词语”,这百度就算算法太搓,你好歹也把我不合适的词标出来行不。。。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
阿Q说
2013-12-02 · 阿Q说创业,创业小点子,营销小故事
阿Q说
采纳数:48 获赞数:163

向TA提问 私信TA
展开全部

public static void main(String[] args) {

String code="abcddsefg"; //单词
code=code.replace("s", ""); //删除,这里可能有点问题,大概就是这样了,你改改就行了
if(win(code))        //这里的判断啥的业务你也自己改改吧,总的留点啥给你做
System.err.println("1");
else
System.err.println("0");
}

public static boolean win(String code){
char[] c=code.toCharArray();
for (int i = 0; i < c.length-1; i++) {
if(c[i] > c[i+1])
return false;
}
return true;
}
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
玖待已归8E
2013-12-04
知道答主
回答量:5
采纳率:100%
帮助的人:7367
展开全部
我的想法是,首先应该找到最优的排序,也就是哪个排列是去掉最少的字母后能够满足递增要求,至于甲是否获胜,判断去掉的字母数就行了,如果是奇数甲获胜,偶数乙获胜。

这个题其实就是找最优排列的,找出最优排列来剩下的就很好判断了。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
达摩高僧
2013-12-03
知道答主
回答量:28
采纳率:0%
帮助的人:31.2万
展开全部
有点问题:两个人都足够聪明,并且都想赢。如果这样设计程序,变数太多了,就像下象棋,可以攻,可以防守,每一次做出决定,都有多种方案,这样对算法要求就高了,不是在这里能解决的。

我觉得可以改一下题目的方向:甲乙两人一起删字母,得到一个最长的严格单增序列。这样的话,这个题目在这里还是可以做做的。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 更多回答(4)
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式