急求 田忌赛马 详细题解 freePascal
一、急求 田忌赛马 详细题解 freePascal
type arr=array[1..2000] of longint;
var
tian,qi:arr;
ans:array[1..2000,1..2000] of longint;
i,j,k,n:longint;
procedure qs(left,right:longint;var a:arr);
var
t,mid,l,r:longint;
begin
l:=left;r:=right;mid:=a[(l+r) div 2];
while lmid do inc(l);
while a[r]if lleft then qs(left,r,a); end; function cost(a,b:longint):longint; begin if a>b then exit(200); if a=b then exit(0); if a end; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin readln(n); for i:=1 to n do read(tian[i]); for i:=1 to n do read(qi[i]); qs(1,n,tian); qs(1,n,qi); for i:=1 to n do ans[i,i]:=cost(tian[i],qi[n]); for k:=n-1 downto 1 do for i:=1 to k do begin j:=n-k+i; ans[i,j]:=max(ans[i+1,j]+cost(tian[i],qi[k]),ans[i,j-1]+cost(tian[j],qi[k])); end; writeln(ans[1,n]); end.
二、田忌和齐王赛马是历史上有名的故事，设齐王的三匹马分别为A、B、C，田忌的三匹马分别为a、b、c；三匹马各
（1）齐王的三匹马的所有可能的出场顺序：上中下，上下中，中上下，中下上，下上中，下中上；
（2）只有2113田忌的下等马对齐5261王的上等马，田忌的中等马对齐王的下等马，田忌的上等马对齐王的中等马才可取胜；齐王第一场必出上等马，所以田忌第一场需出下等马；还剩下田忌的上等马和4102中等马，齐王的中等马和下等马．所以此1653题可以看做需两步完成的事件，列表得：
（上，内下） （中，下）
（上，中） （中，中） ∴一共4种情况，第二个田忌安排上等马赢的为（上，中），第二个田忌安排中等马赢的为（中，下），
∴第二个田忌安排上等马或中等马赢的概率都为
1
4 ，所以田忌应安排下等马第一个出场，第二个上等马，容中等马均可．
三、田忌赛马的故事田忌是怎样胜过了齐王，四年级上册数学广角齐王田忌本场胜者
挑换了马的顺序：下等马对上等马，上等马对中等马，中等马对下等马。
典故
齐国使者到大梁来，孙膑以刑徒的身份秘密拜见，劝说齐国使者。齐国使者觉得此人是个奇人，就偷偷地把他载回齐国。齐国将军田忌非常赏识他，并且待如上宾。
田忌经常与齐国众公子赛马，设重金赌注。孙膑发现他们的马脚力都差不多，马分为上、中、下三等，于是对田忌说：“您只管下大赌注，我能让您取胜。”田忌相信并答应了他，与齐王和各位公子用千金来赌注。比赛即将开始，孙膑说：“现在用您的下等马对付他们的上等马，用您的上等马对付他们的中等马，用您的中等马对付他们的下等马。”已经比了三场比赛，田忌一场败而两场胜，最终赢得齐王的千金赌注。于是田忌把孙膑推荐给齐威王。齐威王向他请教了兵法，于是把他当成老师。
