田忌赛马算法

A. 关于c语言的田忌赛马问题。

应该是贪心的思路有点问题：
解题思路：
贪心算法。
如果当前最好的马可以胜齐王最好的马，那么让这两匹马比一场。
如果当前最差的马能胜齐王最差的马，那么让这两匹马比一场。
如果上面两个条件都不满足，那么让当前最差的马和齐王最好的马比一场。

B. 田忌赛马"的故事表现了运筹学的哪一特点

“田忌赛马"的故事表现了运筹学的系统整体性这一特点。田忌赛马这个故事表明，在有双方参加的竞赛或斗争中，策略是很重要的，采用策略适当，就有可能在似乎一定会失败的情况下取得胜利。研究这种竞赛策略的数学分支，叫作博弈论，它是运筹学的重要内容。

运筹学中最初用数学方法研究博弈论是在国际象棋中开始的，旨在用来如何确定取胜的算法。由于是研究双方冲突、制胜对策的问题，所以这门学科在军事方面有着十分重要的应用。

数学家还对水雷和舰艇、歼击机和轰炸机之间的作战、追踪等问题进行了研究，提出了追逃双方都能自主决策的数学理论。随着人工智能研究的进一步发展，对博弈论提出了更多新的要求。决策问题是由决策者和决策域构成的，而决策域又由决策空间、状态空间和结果函数构成。

(2)田忌赛马算法扩展阅读

运筹学理论：

1、排队论，排队论又叫随机服务系统理论。最初是在二十世纪初由丹麦工程师艾尔郎关于电话交换机的效率研究开始的，在第二次世界大战中为了对飞机场跑道的容纳量进行估算，它得到了进一步的发展，其相应的学科更新论、可靠性理论等也都发展起来。

2、可靠性理论，可靠性理论是研究系统故障、以提高系统可靠性问题的理论。可靠性理论研究的系统一般分为两类：不可修系统：如导弹等，这种系统的参数是寿命、可靠度等，可修复系统：如一般的机电设备等，这种系统的重要参数是有效度。

3、对策论，对策论也叫博弈论，前面讲的田忌赛马就是典型的博弈论问题。作为运筹学的一个分支，博弈论的发展也只有几十年的历史。系统地创建这门学科的数学家，冯·诺依曼。

C. usaco题目“田忌赛马”

这样是对的
设一个方案P中.共有W场，赢了N场，平了K场，则输了(W-N-K)场
那么该方案赢得的钱数为200N-200(W-N-K)=400N+200K-200W
因-200W一定..该题就是求最大的400N+200K
现在证明对于N最大，且在N最大的情况下K最大的方案P1,其赢得的钱设为T1,对任意方案Pi,T1>=Ti
1)对于方案Pi,如果Ni=N1,则Ki<=K1（由K1最大）,所以Ti<=T1
2)对于方案Pi,Ni<N1
找到一个在P1中赢了而在Pi中没赢的马(由Ni<N1,这样的马一定找得到)，
设该马为H1,和它比赛的马(P1中)为H'1,和H1比赛的马(Pi)中，为H'2，H'1比赛的马(Pi)中，为H2
我们可以让H1在Pi中和H'1比赛，H2和H'2比赛，这样使Pi多一匹胜马，即H1,而H2和H'2的比赛或胜，或输，或平，明显地，无论哪种情况，这种变换多赢的钱都大于等于零。通过不断地这种变换，我们一定能让方案Pi变成1)中的方案，且变换中多赢的钱大于等于零，因此，可以证明
对于任意Pi,T1>=Ti
即...你的算法是正确的
Q.E.D

...顺手提一句，这题有一个动态规划解，貌似编程复杂度和速度都会比二分图最大匹配好一点...
毕竟...匈牙利算法写起来头疼

D. 田忌赛马 de 算法

原文：
齐使者如梁，孙膑以刑徒阴见，说齐使。齐使以为奇，窃载与之齐。齐将田忌善而客待之。忌数与齐诸公子驰逐重射。孙子见其马足不甚相远，马有上、中、下辈。于是孙子谓田忌曰：“君弟重射，臣能令君胜。”田忌信然之，与王及诸公子逐射千金。及临质，孙子曰：“今以君之下驷彼上驷，取君上驷与彼中驷，取君中驷与彼下驷。”既驰三辈毕，而田忌一不胜而再胜，卒得王千金。于是忌进孙子于威王。威王问兵法，遂以为师。
译文：
齐国使者到大梁来，孙膑以刑徒的身份秘密拜见，用言辞打动齐国使者。齐国使者觉得此人不同凡响，就偷偷地用车把他载回齐国。齐国将军田忌赏识他并像对待客人一样礼待他。田忌经常与齐国诸公子赛马，设重金赌注。孙膑发现他们的马脚力都差不多，可分为上、中、下三等。于是孙膑对田忌说：“您只管下大赌注，我能让您取胜。”田忌相信并答应了他，与齐王和诸公子用千金来赌胜。比赛即将开始，孙膑说：“现在用您的下等马对付他们的上等马，拿您的上等马对付他们的中等马，拿您的中等马对付他们的下等马。”三场比赛完后，田忌一场不胜而两场胜，最终赢得齐王的千金赌注。于是田忌把孙膑推荐给齐威王。威王向他请教兵法后，就把他当作老师。

E. acm田忌赛马问题在线等急求！！

好晕。。田忌赛马问题可用贪心算法进行匹配。
我在这里借花敬佛：
http://blog.sina.com.cn/s/blog_5f0d09840100n7yx.html

F. c语言田忌赛马问题

把双方的马从大到小排序 然后从前往后比较 老田赢了呢 就继续往下比 老田比不过呢 就拉老田最慢的马跟这个比 这里好理解

还有比平的情况 比平了还是从后面找一匹马

找的时候 要是老田后面的马可以赢对应位置的马 就接着往前比 然后找到的那匹就跟前面这匹马比

核心代码：
for(i=0;i<n;i++)
{
if(t[head]>k[i])
{
head++;
ans+=200;
}
else if(t[head]<k[i])
{
tailt--;
ans-=200;
}
else if(t[head]==k[i])
{
for(j=tailt,m=tailk;j>=head;j--,m--)
{
if(t[j]>k[m])
{
ans+=200;
tailt--;
tailk--;
}
else
{
if(t[j]<k[i]) ans-=200;
tailt=--j;
tailk=m;
break;
}
}
}

if(head>tailt) break;
}

G. 田忌赛马是运用了什么数学方法

英语全称为：Operational Research(英国)或者是Operations Research(美国)
在中国战国时期,曾经有过一次流传后世的赛马比赛,相信大家都知道,这就是田忌赛马.田忌赛马的故事说明在已有的条件下,经过筹划、安排,选择一个最好的方案,就会取得最好的效果.可见,筹划安排是十分重要的.
现在普遍认为,运筹学是近代应用数学的一个分支,主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼,然后利用数学方法进行解决.前者提供模型,后者提供理论和方法.
运筹学的思想在古代就已经产生了.敌我双方交战,要克敌制胜就要在了解双方情况的基础上,做出最优的对付敌人的方法,这就是“运筹帷幄之中,决胜千里之外”的说法.
但是作为一门数学学科,用纯数学的方法来解决最优方法的选择安排,却是晚多了.也可以说,运筹学是在二十世纪四十年代才开始兴起的一门分支.
运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题.当然,随着客观实际的发展,运筹学的许多内容不但研究经济和军事活动,有些已经深入到日常生活当中去了.运筹学可以根据问题的要求,通过数学上的分析、运算,得出各种各样的结果,最后提出综合性的合理安排,已达到最好的效果.
运筹学作为一门用来解决实际问题的学科,在处理千差万别的各种问题时,一般有以下几个步骤：确定目标、制定方案、建立模型、制定解法.
虽然不大可能存在能处理及其广泛对象的运筹学,但是在运筹学的发展过程中还是形成了某些抽象模型,并能应用解决较广泛的实际问题.
随着科学技术和生产的发展,运筹学已渗入很多领域里,发挥了越来越重要的作用.运筹学本身也在不断发展,现在已经是一个包括好几个分支的数学部门了.比如：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等.
运筹学有广阔的应用领域,它已渗透到诸如服务、库存、搜索、人口、对抗、控制、时间表、资源分配、厂址定位、能源、设计、生产、可靠性、等各个方面.
运筹学是软科学中“硬度”较大的一门学科,兼有逻辑的数学和数学的逻辑的性质,是系统工程学和现代管理科学中的一种基础理论和不可缺少的方法、手段和工具.运筹学已被应用到各种管理工程中,在现代化建设中发挥着重要作用.
[编辑本段]运筹学的历史
运筹学作为一门现代科学,是在第二次世界大战期间首先在英美两国发展起来的,有的学者把运筹学描述为就组织系统的各种经营作出决策的科学手段. P.M.Morse与G.E.Kimball在他们的奠基作中给运筹学下的定义是：“运筹学是在实行管理的领域,运用数学方法,对需要进行管理的问题统筹规划,作出决策的一门应用科学.”运筹学的另一位创始人定义运筹学是：“管理系统的人为了获得关于系统运行的最优解而必须使用的一种科学方法.”它使用许多数学工具（包括概率统计、数理分析、线性代数等）和逻辑判断方法,来研究系统中人、财、物的组织管理、筹划调度等问题,以期发挥最大效益.
现代运筹学的起源可以追溯到几十年前,在某些组织的管理中最先试用科学手段的时候.可是,现在普遍认为,运筹学的活动是从二次世界大战初期的军事任务开始的.当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动,所以美国及随后美国的军事管理当局都号召大批科学家运用科学手段来处理战略与战术问题,实际上这便是要求他们对种种（军事）经营进行研究,这些科学家小组正是最早的运筹小组.
第二次世界大战期间,“OR”成功地解决了许多重要作战问题,显示了科学的巨大物质威力,为“OR”后来的发展铺平了道路.
当战后的工业恢复繁荣时,由于组织内与日俱增的复杂性和专门化所产生的问题,使人们认识到这些问题基本上与战争中所曾面临的问题类似,只是具有不同的现实环境而已,运筹学就这样潜入工商企业和其它部门,在50年代以后得到了广泛的应用.对于系统配置、聚散、竞争的运用机理深入的研究和应用,形成了比较完备的一套理论,如规划论、排队论、存贮论、决策论等等,由于其理论上的成熟,电子计算机的问世,又大大促进了运筹学的发展,世界上不少国家已成立了致力于该领域及相关活动的专门学会,美国于1952年成立了运筹学会,并出版期刊《运筹学》,世界其它国家也先后创办了运筹学会与期刊,1957年成立了国际运筹学协会.
[编辑本段]运筹学的特点
运筹学的特点是：1.运筹学已被广泛应用于工商企业、军事部门、民政事业等研究组织内的统筹协调问题,故其应用不受行业、部门之限制；2.运筹学既对各种经营进行创造性的科学研究,又涉及到组织的实际管理问题,它具有很强的实践性,最终应能向决策者提供建设性意见,并应收到实效；3.它以整体最优为目标,从系统的观点出发,力图以整个系统最佳的方式来解决该系统各部门之间的利害冲突.对所研究的问题求出最优解,寻求最佳的行动方案,所以它也可看成是一门优化技术,提供的是解决各类问题的优化方法.
[编辑本段]运筹学的研究方法
运筹学的研究方法有：1.从现实生活场合抽出本质的要素来构造数学模型,因而可寻求一个跟决策者的目标有关的解；2.探索求解的结构并导出系统的求解过程；3.从可行方案中寻求系统的最优解法.
[编辑本段]运筹学的具体内容
运筹学的具体内容包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、图论、决策论、对策论、排队论、存储论、可靠性理论等.
规划论
数学规划即上面所说的规划论,是运筹学的一个重要分支,早在1939年苏联的康托洛维奇（H.B.Kahtopob ）和美国的希奇柯克（F.L.Hitchcock）等人就在生产组织管理和制定交通运输方案方面首先研究和应用一线性规划方法.1947年旦茨格等人提出了求解线性规划问题的单纯形方法,为线性规划的理论与计算奠定了基础,特别是电子计算机的出现和日益完善,更使规划论得到迅速的发展,可用电子计算机来处理成千上万个约束条件和变量的大规模线性规划问题,从解决技术问题的最优化,到工业、农业、商业、交通运输业以及决策分析部门都可以发挥作用.从范围来看,小到一个班组的计划安排,大至整个部门,以至国民经济计划的最优化方案分析,它都有用武之地,具有适应性强,应用面广,计算技术比较简便的特点.非线性规划的基础性工作则是在1951年由库恩（H.W.Kuhn）和达克（A.W.Tucker）等人完成的,到了70年代,数学规划无论是在理论上和方法上,还是在应用的深度和广度上都得到了进一步的发展.
数学规划的研究对象是计划管理工作中有关安排和估值的问题,解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案.它可以表示成求函数在满足约束条件下的极大极小值问题.
数学规划和古典的求极值的问题有本质上的不同,古典方法只能处理具有简单表达式,和简单约束条件的情况.而现代的数学规划中的问题目标函数和约束条件都很复杂,而且要求给出某种精确度的数字解答,因此算法的研究特别受到重视.

H. 求C++算法。。。田忌赛马扩展版。

有趣的问题，分析分析了半天，貌似不能用很简单的数学公式计算出来。如果用C语言穷举，还是比较简单的，权当交流。

题目分析：
由于是求概率，可以假定齐王的马永远是按照顺序出的，田忌的马是任意顺序。因此，总共是 N！种可能性。如果田忌需要赢，田忌需要赢 (N+1)/2场，如总共3场，需要赢2场，总共4场，需要赢3场（赢2场是平局）。

按照题目的要求，设定：
齐王的马的次序：Q[N]
田忌的马的次序：T[N]
齐王的马的速度设定为 2n+1, 2(n-1)+1, ..., 1 (0<=n < N)
田忌的马的速度设定为 2n, 2(n-1), ..., 0 (0<=n<N)

穷举法：
1）齐王的马永远是固定的，Q[n] = 2n+1
2）穷举田忌所有的排列方法（穷举的算法网上应该有现成的），对于每一种排列，比较T和Q的大小，统计输赢的情况: T[n] > Q[n]的数目大于(N+1)/2
2）将赢的次数处以N!, 就是概率

数学的方式，分析了半天，没有搞定，不献丑了。

I. 25匹马赛跑，共有5个赛道，最少赛多少次可以找出前三名

7次。理由如下:

1、先分开赛5组（A-E）， 5次， 每组的最后两名肯定会被淘汰，（-10)。

2、5组第一名赛一次，假设A1 > B1 > C1 > D1＞E1，那么 A1肯定是总体第一名。则D，E全部被淘汰（-6） . 现在需要在剩下的里面取2个，那么C2，C3，B3也会被淘汰（-3) 。

3、那么就剩下A2，A3，B1，B2，C1了，再赛一次，取前两名（-3)。

最多7次比赛，前5次总共淘汰10匹，第6次淘汰9匹，第7次淘汰3匹。 总共淘汰22匹。

(9)田忌赛马算法扩展阅读

有关赛马的故事：

齐国的大将田忌，很喜欢赛马，有一回，他和齐威王约定，要进行一场比赛。各自的马都可以分为上，中，下三等。比赛的时候，齐威王总是用自己的上马对田忌的上马，中马对中马，下马对下马。由于齐王每个等级的马都比田忌的马强一些，所以比赛了几次，田忌都失败了。

有一次，田忌又失败了，觉得很扫兴，比赛还没有结束，就垂头丧气地离开赛马场，这时，田忌抬头一看， 人群中有个人，原来是自己的好朋友孙膑。孙膑招呼田忌过来，拍着他的肩膀说： “我刚才看了赛马，威王的马比你的马快不了多少呀。”

孙膑还没有说完，田忌瞪了他一眼： “想不到你也来挖苦我！” 孙膑说：“我不是挖苦你，我是说你再同他赛一次，我有办法准能让你赢了他。” 田忌疑惑地看着孙膑： “你是说另换一匹马来？” 孙膑摇摇头说： “连一匹马也不需要更换。”

田忌毫无信心地说： “那还不是照样得输！”孙膑胸有成竹地说： “你就按照我的安排办事吧。”齐威王屡战屡胜，正在得意洋洋地夸耀自己马匹的时候，看见田忌陪着孙膑迎面走来， 便站起来讥讽地说： “怎么，莫非你还不服气？”

田忌说：“当然不服气，咱们再赛一次！”说着，“哗啦”一声，把一大堆银钱倒在桌子上，作为他下的赌钱。 齐威王一看，心里暗暗好笑，于是吩咐手下，把前几次赢得的银钱全部抬来，另外又加了一千两黄金，也放在桌子上。

齐威王轻蔑地说：“那就开始吧！” 一声锣响，比赛开始了。 孙膑先以下等马对齐威王的上等马，第一局田忌输了。齐威王站起来说： “想不到赫赫有名的孙膑先生，竟然想出这样拙劣的对策。” 孙膑不去理他。接着进行第二场比赛。

孙膑拿上等马对齐威王的中等马，获胜了一局。 齐威王有点慌乱了。 第三局比赛，孙膑拿中等马对齐威王的下等马，又战胜了一局。这下，齐威王目瞪口呆了。 比赛的结果是三局两胜，田忌赢了齐威王。 还是同样的马匹，由于调换一下比赛的出场顺序，就得到转败为胜的结果。

这个故事告诉我们:由于其结合变化了，事物的质也会发生变化。在事物发展变化过程中，构成事物的成分在排列次序上发生变化也会引|起事物的质变。这是量变引起质变的又一种形式。

J. C语言里关于田忌赛马的问题

其实你的算法很简单，就是让渊子的马按照速度按照从小到大排序，取前1/3为从小到大的顺序，然后剩下的2/3按照从大到小排序。
让对手的马按照从大到小排序。
这样你就能保证渊子赢了。