次のように解決するコードを書いているパズルがあります。
最初はすべてゼロである長さ n のバイナリ ベクトルを考えます。ベクトルのビットを選択し、それを 1 に設定します。ここで、任意の 1 ビットから $1$ までの距離が最大のビットを設定するプロセスが開始されます (複数ある場合は、最も遠いビットの任意の選択)。これは、2 つの 1 ビットが隣り合ってはならないというルールで繰り返し発生します。1 ビットを配置するスペースがなくなると終了します。目標は、終了時にできるだけ多くのビットが 1 に設定されるように、最初の 1 ビットを配置することです。
n = 2 とします。この場合、ビットを設定する場所はどこでも、正確に 1 つのビットが設定されます。
n = 3 の場合、最初のビットを設定すると、最終的に 101 になります。しかし、中間ビットを設定すると、最適ではない 010 が得られます。
n = 4 の場合、どちらのビットを設定しても、最終的には 2 セットになります。
n = 5 の場合、最初に設定すると 10101 になり、最後に 3 ビットが設定されます。
n = 7 の場合、3 番目のビットを設定して 1010101 を取得する必要があるようです。
最適な値を見つけるためのコードを書きましたが、大きな n にうまくスケーリングしません。私のコードは n = 1000 あたりで遅くなり始めますが、n が 100 万あたりの問題を解決したいと考えています。
#!/usr/bin/python
from __future__ import division
from math import *
def findloc(v):
count = 0
maxcount = 0
id = -1
for i in xrange(n):
if (v[i] == 0):
count += 1
if (v[i] == 1):
if (count > maxcount):
maxcount = count
id = i
count = 0
#Deal with vector ending in 0s
if (2*count >= maxcount and count >= v.index(1) and count >1):
return n-1
#Deal with vector starting in 0s
if (2*v.index(1) >= maxcount and v.index(1) > 1):
return 0
if (maxcount <=2):
return -1
return id-int(ceil(maxcount/2))
def addbits(v):
id = findloc(v)
if (id == -1):
return v
v[id] = 1
return addbits(v)
#Set vector length
n=21
max = 0
for i in xrange(n):
v = [0]*n
v[i] = 1
v = addbits(v)
score = sum([1 for j in xrange(n) if v[j] ==1])
# print i, sum([1 for j in xrange(n) if v[j] ==1]), v
if (score > max):
max = score
print max