你說得很有道理

不過你的假設就完全沒有初始條件了，而原題一開始還是有規律的。

另外assign value是不行的。事實上數組裏每個元素應該是一個結構，包括一個整數key和一個value。這裏隻不過簡化成隻有key而已。

我把你的問題變成這樣一個程序問題，你看看合適不合適：
------------------------------------------------
有個長度為n的數組a[n]，初始隨機存儲0,1,...n-1。要求最終a[f(k)]=k，其中f(k)是從0,1,...,n-1的一個一一對應的函數，計算f(k)需要常數時間。
------------------------------------------------
下麵是程序，這裏f(n)可以自己另外定義。根本算法和我前麵說的沒有任何區別。

using System;
using System.Collections.Generic;
using System.Text;

namespace netiq
{
class Program
{
static int numOperations = 0;
const int n = 10;

static int[] GenRandData(int n)
{
Random rand = new Random(0);
int[] data = new int[n];
for (int i = 0; i for (int i = 0; i {
int k = rand.Next(n - i);
int j = data[i]; data[i] = data[k]; data[k] = j;
}
return data;
}

static int f(int k)
{
return (k % 2 > 0) ? ((k - 1) / 2 + n / 2) : k / 2;
}

static string toString(int[] data)
{
string str = data[0].ToString();
for (int i = 1; i {
str += " " + data[i];
}
return str;
}

static void ReOrder(int[] data)
{
for(int k = 0; k {
if (k == data[f(k)]) continue;

int start = data[f(k)];
while(start != k)
{
int temp = data[f(start)];
data[f(start)] = start;
start = temp;
numOperations++;
}
data[f(k)] = k;
}
}


static void Main(string[] args)
{
int[] obj = new int[n];
for (int i = 0; i Console.WriteLine(toString(obj));

int[] data = GenRandData(n);
Console.WriteLine(toString(data));
ReOrder(data);
Console.WriteLine(toString(data));
Console.WriteLine(numOperations);
return;
}
}
}

所有跟帖： 

• 我還是覺得我們在說兩件不同的事 -康MM- ♀ (0 bytes) () 08/06/2009 postreply 17:49:24