0%

车厢重组carry

[问题描述]:

在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢,如果将桥旋转180度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后,火车站决定将这一工作自动化,其中一项重要的工作是编一个程序,输入初始的车厢顺序,计算最少用多少步就能将车厢排序。

[输入]:

输入文件有两行数据,第一行是车厢总数N(不大于10000),第二行是N个不同的数表示初始的车厢顺序。

2012-1-17 星期二

初看这题,还有点像冒泡排序,因为这就是不断交换排列;但又有点不同,这是因为这一题只能相邻的两个数进行交换。刚想时想用集合进行控制,但无奈,集合不分先后顺序,只能用数组。

很快,我就想出了一个思路。简单说:①就是找一个最大数,把它与相邻的数进行交换,直到到了数组最后一个,然后排除掉(并不是删掉,之手漠视他,可以用一个变量,控制数组长度)再重复一步骤,直到排序完毕(即控制数组长度变量为0)

1
2
3
4
A.  找最大数
B. For i:=最大数的位置+1 to la(控制数组长度变量) do
Begin inc(time(次数变量)); 交换a[i]与a[i-1] end;
La:=la-1;

程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var
a:array[1..10000] of integer;
n,la,time,i,max:longint;

begin
readln(n);
for i:=1 to n do read(a[i]);//输入

la:=n;
while la>0 do
begin
max:=1;
for i:=1 to la do
if a[i]>=a[max] then max:=i;//找最大数

for i:=max+1 to la do
begin
inc(time);
a[i]:=a[i]+a[i-1];
a[i-1]:=a[i]-a[i-1];
a[i]:=a[i]-a[i-1];//交换
end;

la:=la-1;
end;

writeln(time);
end.
Thank you so much.