No. 1≫ No.2 ≫No. 3
nn)/
2010/06/10 14:51
そうですね．求められているのは，必要十分条件でした．
十分条件はマージソートを考えれば出てきます．
N 枚のコインを順位づけるために要する最大の比較回数を n = f(N) と書けば，
f(1) = 0 として，
N が偶数のとき，f(N) = 2 f(N/2) + N - 1
N が奇数のとき，f(N) = f((N+1)/2) + f((N-1)/2) + N -1
です．具体的には，
N: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
n: 1, 3, 5, 8,11,14,17,21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69
で，m = [log_2 N!] との間に必要十分条件があるはずです．
ちゃんと考えていませんが，この n が必要十分条件かもしれません．←本当にちゃんと考えてませんね．
十分条件はマージソートを考えれば出てきます．
N 枚のコインを順位づけるために要する最大の比較回数を n = f(N) と書けば，
f(1) = 0 として，
N が偶数のとき，f(N) = 2 f(N/2) + N - 1
N が奇数のとき，f(N) = f((N+1)/2) + f((N-1)/2) + N -1
です．具体的には，
N: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
n: 1, 3, 5, 8,11,14,17,21, 25, 29, 33, 37, 41, 45, 49, 54, 59, 64, 69
で，m = [log_2 N!] との間に必要十分条件があるはずです．
ちゃんと考えていませんが，この n が必要十分条件かもしれません．←本当にちゃんと考えてませんね．