换次数}

输出最少交换次数a1+a2+a3+a123；

3、计算一种对换方案

我们从原序列的第一个元素开始，顺序搜索每一个元素。如果f[i]≠M[i]的话，则必须与序列中的某个值为M[i]的元素对换，使第i个元素实现目标状态。那么，如何寻找这个元素呢?为了保证排序过程的有序性，我们顺序搜索f[i+1]?f[n]。寻找过程中遇到的情况无非有两种：

⒈ f[j]≠M[j] (i＋1≤j≤n），但f[j]=M[i]，而f[i]=M[j]。显然，我们将f[i]与f[j]

对换一次后，便可实现i位置和j位置的目标状态； ⒉ f[j]≠M[j]但f[j]=M[i]，而f[i]≠M[j]。在这种情况下继续往后搜索。如果搜索过程中出现某个元素f[k]符合第一种情况(f[k]≠M[k]，f[k]=M[i]，f[i]=M[k]，j

上述过程顺序进行，直到搜索完第n个元素。至此，经一系列对换操作后实现了排序，其对换次数是最少的。

例如，初始序到 2 2 1 3 3 3 2 3 1 目标序列 1 1 2 2 2 3 3 3 3 2 2 1 3 3 3 2 3 1 第一步换f1和f3，使得位置1和3实现目标状态

1 2 2 3 3 3 2 3 1 第二步换f2和f9，使得位置2实现目标状态

1 1 2 3 3 3 2 3 2 第三步换f4和f7，使得位置4和位置7实现目标状态

1 1 2 2 3 3 3 3 2 第四步换f5和f9，使得位置5和9实现目标状态

1 1 2 2 2 3 3 3 3 排序结束。

计算过程如下：

for i：=1 to n do {搜索原序列的第一个元素}

if f[i]<>M[i]then {若i位置非目标状态，则顺序搜索往后的元素}

begin

for j：=i+1 to n do

if (f[j]<>M[j])and(f[j]=M[i]) {若j位置非目标状态，但相同于i位置的目标状态，则记下}

then begin k←j；

if M[j]=f[i] then break； {若第i个元素值为j位置的目标状态，则退出循环}

end；{then}

输出i位置与k位置对换；

f[k]?f[i]； {i位置和k位置的两个元素对换}

end；{then}

【例题廿七】青蛙过河(Frog)

大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。图示如下：

青蛙的站队和移动方法规则如下： 1、 每只青蛙只能站在荷叶、石墩，或者仅比它大一号的青蛙背上（统称为合法的落脚点）； 2、一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点； 3、青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上，允许从河心的石墩和荷叶跳到右岸的石墩D上；

4、青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动； 5、青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回；

6、假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。

7、荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。 8、每一步只能移动一只青蛙，并且移动后需要满足站队规则；

9、在一开始的时候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则6站在比其大一号的青蛙的背上。

10、 青蛙希望最终能够全部移动到D上，并完成站队。 设河心有m片荷叶和n个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从A过到D。

例如，在m=1且 n=1时，河心有一片荷叶（Y1）和一个石墩（S1），此时至多有4只青蛙能够过河（由小到大称为1、2、3、4），过河的一种方法为： 开始 1 2 3 4 A S1 Y1 D Step 1 1 from A to Y1 2 3 4 1 A S1 Y1 D 2 from A to S1 3 4 2 1 A S1 Y1 D 1 from Y1 to S1 3 1 4 2 A S1 Y1 D 3 from A to Y1 1 4 2 3 A S1 Y1 D 4 from A to D 1 2 3 4 A S1 Y1 D Step 2 Step 3 Step 4 Step 5 Step 6 3 from Y1 to D 1 3 2 4 A S1 Y1 D Step 7 1 from S1 to Y1 3 2 1 4 A S1 Y1 D Step 8 2 from S1 to D 2 3 1 4 A S1 Y1 D Step 9 1 from Y1 to D 1 2 3 4 A S1 Y1 D 此例中，当河心有一片荷叶和一个石墩时，4只青蛙能够跳动9步过河。 输入文件

文件仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n（0≤n≤25），第二行为荷叶数m（0≤m≤25）。 输出文件

文件中仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时，最多能够过河的青蛙的只数。 输入输出文件样例 Input．txt 1 1

Output．txt 4

算法分析

按题意，在石墩(包括左岸石墩A和右岸石墩D)上的青蛙个数不限，但必须按编号递减的顺序一个个地往上摞。移动从顶端的青蛙开始，自上而下进行。每片荷叶仅允许承载一只青蛙，m片荷叶起一种“过渡”作用，在同一时刻里最多可使得m+1只青蛙在保持编号顺序不变的前提下，从一个石墩移至另一个石墩。

我们将河心n个石墩按青蛙编号递减的顺序排列，即si上的青蛙编号>si+1上的青蛙编号，s1上的青蛙编号最大，?，sn上的青蛙编号最小。Si-1未尾的青蛙编号与si顶端的青蛙编号相衔接(1≤i≤n-1)。

1、计算河心n个石墩可承载的最大青蛙数

设 f[i]—河心i个石墩上可承载的最大青蛙数(1≤i≤n)。显然 f[0]=0； f[1]=m+1

设河心有两个石墩s1，s2。在m片荷叶y0，?，ym的“过渡”下，首先将左岸石墩A上的m+1只青蛙移至s1；然后将A上的m+1只青蛙移至s2，将s1上的m+1只青蛙移至s2，使得s2上的青蛙数达到m+1+f[1]=2*(m+1)只；最后将A上的m+1只青蛙移至s1。显然f[2]=m+1+f[1]+f[1]=3*(m+1)。

设河心有三个石墩s1，s2，s3。同样，在m片荷叶y1，?，ym的“过渡”下，先按上述顺序摆放s1和s2上的f[2]只青蛙；然后将左岸石墩A上的m+1只青蛙移至s3，将s1上的m+1只青蛙移至s3，将s2上的2*(m+1)只青蛙移至s3，使得s3上的青蛙数达到m+1+f[2]=4*(m+1)；最后按上述顺序从A上取走f[2]只青蛙放到s1和s2上。显然f[3]=m+1+2*f[2]=7*(m+1)。 ????????

依次类推，可引出这样一个结论：河心n个石墩可承载的最多青蛙数

n

f[n]=m+1+2*f[n-1]=(2-1)*(m+1)。