电视调台问题(再增加一问）

lulijie

昨天买了一个液晶电视，在调频道时，我让它先自动调台，调完后，我想按照自己的习惯顺序，把台重新调整，但发现居然不能把某个台随意设置在某个频道，竟然要每个频道都要重新手动调台一次，37个频道重新手动调台，花了我不下一个小时。比如一频道自动调台后是湖南台，而我想一频道设置为中央1台，所以要从原先的湖南台手动向后调了16个台，才把中央1台设置在一频道，而二频道要把西藏台调整为中央2台，又手动调了13个台，等等。
我在痛骂电视产商之余，突然想到了一个问题，无论有线电视经营商预先如何设置各台的频率，我让电视先自动调台，然后再每个频道都手动调台，把各频道调整为自己习惯的顺序，最多需要调整的总台数是多少。（调台时不能从最后一个频率向后调整跳到第一个频率）。比如调一频道，我调了16台，调二频道，我调了13台，把它们都加起来，是否存在最大值。
我把以上问题抽象成等价的以下问题。
从1至37共37个数，按从小到大的顺序排列，得到一个数列A(n)=n，再把这37个数随机打乱，排成一个顺序，得到另一个数列B(n)。     S＝∑|B(i)-A(i)|     (i从1到37)     即A、B两个数列所有  相同位置的差的绝对值  的总和。
求S的最大值。
-----------------------------------------------------------------------------------------------------------------
若数列的总个数为m，求得的S的期望值为S(m)。
那么求证：S(m)=(m^2-1)/3。
例如，m=1,也就是1个数的序列，S(1)=0。
          m=2,也就是2个数的序列，S(2)=1。（就两个值0和2，期望值是1)

[ 本帖最后由 lulijie 于 2009-4-6 20:14 编辑 ]

xiaohua594

线代中的求逆序数？？？

lulijie

平均值（期望值）为456是对的，但概率最高的S是不是就是456呢？

金眼睛

LS高手，答案很好，平均值没有问题。

平均值程序如下，通过精度控制，可以确定平均值为456。
Average=0;
OAverage=1;
N=0;
while abs(OAverage-Average)>eps
    Sum=sum(abs(randperm(37)-(1:37)));
    OAverage=Average;
    Average=(Average*N+Sum)/(N+1);
    N=N+1;
end

[ 本帖最后由 金眼睛 于 2009-4-5 23:12 编辑 ]

zxl0714

S最大应该是684吧
S取456的概率最高

以上为猜测

[ 本帖最后由 zxl0714 于 2009-4-4 23:32 编辑 ]

Cielo

原式展开后必然是正的37个数加上负的37个数，这样只需要让正的为最大的37个、负的为最小的37个就行！

而楼主在5楼给出的23个数的例子很显然满足上述要求，所以最大值很容易求吧

oboe

补充一下，如果从中间分开，左边和右边要交换的话，
那么必定面积是减少的。

又说个跑题话。
我现在已经不调台了，打印了个频道表。
电子表格，节目变了，就再打印一个。
表２是我在用的“广铁有线”
表１有大部分的卫视图标。

oboe

用几何来算。
１到３７是一条X=Y＝３７组成的三角形。
随机数可以以看成一条不连续的折线，
那楼主的题目就是要求那条任意线与斜边所围成的面积，求极值。

直觉上给的极值就是一个“X”形。
也就是一频道要从1上升到37＝３６次，2频道升到36＝３４次。。。
３６+３４+３２+。。。+０+２+。。。+３４+３６

如果随机值是将1升到36＝３５，2频道长到37＝３５和交换的话，
３５+３５++３２+。。。+０+２+。。。+３４+３６
没变。

说明了。
如果在中间频道以前的交换，最大值是不变的。
也就是说，在３７/２＝１８
最大值条件就是：前１８个频道，全要调到１８个频道以后。
后１８个频道要全调到前１８个频道。

bbshanwei

如果是数字电视不是可以设置个人喜好吗？在个人喜好里设置自己的频道排列不是更省力？