我觉得我解释不清楚

来源: 说了就走于 2009-07-30 11:56:00 [档案] [博客] [旧帖] [给我悄悄话] 本文已被阅读：次 (1593 bytes)

回答: 似乎没有那么复杂由说了就走于 2009-07-29 21:45:44

下面是源程序（编译通过）。有3个变量；我认为是O(n)的

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

namespace netiq
{
class Program
{
const int n = 10;

static int f(int k)
{
return (k % 2 > 0) ? ((k - 1) / 2 + n) : k / 2;
}
static int g(int k)
{
return (k < n) ? (k * 2) : ((k - n) * 2 + 1);
}
static string toString(int[] a)
{
string str = a[0].ToString();
for (int i = 1; i < a.Length; i++)
{
str += " " + a[i];
}
return str;
}

static void Main(string[] args)
{
string str;
int[] a = new int[n * 2];
for (int i = 0; i < n * 2; i++) { a[i] = g(i); }

for (int k = 0; k < n * 2; k++) { a[k] = k; } // init
Console.WriteLine(toString(a));

// run algorithm
for (int k = 0; k < n * 2; k++)
{
if (g(k) == a[k]) { continue; }
int i = k, j;
while (f(i) != k)
{
j = a[f(i)];
a[f(i)] = i;
i = j;
}
a[k] = i;
}

Console.WriteLine(toString(a));
return;
}
}
}