快速放置puzz钻头的方法

Question

我要解决的是一个难题。在

考虑一个长度为n的二进制向量，它最初都是零。你选择一个向量并将其设置为1。现在，一个进程开始设置从任何1位到$1$的最大距离的位（如果有多个位，则任意选择最远的位）。这种情况会反复发生，因为规则是两个1位不能相邻。当没有足够的空间放置1位时，它终止。目标是放置初始的1位，以便尽可能多的位在终止时被设置为1。在

假设n=2。那么无论我们在哪里设置位，我们最终只设置了一个位。在

对于n=3，如果我们设置第一个位，最后得到101。但是如果我们设置中间位，我们得到010，这不是最优的。在

对于n=4，无论我们设置了哪一个位，我们都会得到两组。在

对于n=5，设置第一个值得到10101，最后设置三个位。在

对于n=7，我们需要设置第三个位，以获得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

Answer 1

最新答案（O（logn）复杂性）

如果我们相信templatetypedef和Aleksi Torhamo的猜想（update：在这篇文章的最后证明），存在一个封闭形式的解count(n)，可以在{}中计算（或者{}，如果我们假设对数和位移位是O(1)）：

Python：

from math import log

def count(n): # The count, using position k conjectured by templatetypedef
    k = p(n-1)+1
    count_left = k/2
    count_right = f(n-k+1)
    return count_left + count_right

def f(n): # The f function calculated using Aleksi Torhamo conjecture
    return max(p(n-1)/2 + 1, n-p(n-1))

def p(n): # The largest power of 2 not exceeding n
    return 1 << int(log(n,2)) if n > 0 else 0

C++：

^{pr2}$

这段代码可以计算n=100,000,000（甚至在Python中是n=1e24）的结果立即正确¹。在

我测试了n的不同值的代码（使用我的O(n)解决方案作为标准，请参见下面的旧答案部分），它们似乎仍然正确。在

这段代码依赖于templatetypedef和Aleksi Torhamo²的两个猜想。 有人想证明吗？=D（更新2：经验证）

¹_{我的意思是几乎立即}
Aleksi Torhamo关于f函数的猜想已被n<=100,000,000的经验证明

---

旧答案（O（n）复杂性）

我可以使用Python2.7在1.358s（在我的iMac中）中返回n=1,000,000（结果是475712）的计数。<>更新> eEM>：C++中的{{CD13}}为0.19s。=）

这是我的想法，它实现了O(n)时间复杂性。在

算法

{cd15}的定义

将f(n)定义为将在长度为n的位向量上设置的位数，假设第一位和最后一位都被设置为（除了n=2，其中只设置了第一位或最后一位）。因此我们知道f(n)的一些值如下：

f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 2
f(5) = 3

请注意，这与我们正在寻找的值不同，因为初始位可能不在第一位或最后一位，正如f(n)计算的那样。例如，我们有f(7)=3而不是4。在

注意，这可以相当有效地计算（摊销O(n)来计算f到{}的所有值），使用递归关系：

f(2n) = f(n)+f(n+1)-1
f(2n+1) = 2*f(n+1)-1

对于n>=5，因为遵循规则的下一个位集将是中间位，除了n=1,2,3,4。然后我们可以将位向量分成两部分，每个部分相互独立，这样我们就可以使用f( floor(n/2) ) + f( ceil(n/2) ) - 1来计算比特集的数目，如下所示：

n=11              n=13
10000100001       1000001000001
<  >            <  ->
 f(6)<  >        f(7) <  ->
      f(6)               f(7)

n=12              n=14
100001000001      10000010000001
<  >            <  ->
 f(6)<  ->       f(7) <   >
      f(7)                f(8)

我们在公式中使用-1，以排除中间位的双计数。在

现在我们准备计算原问题的解。在

g(n,i)的定义

将g(n,i)定义为将在长度为n的位向量上设置的位数，遵循问题中的规则，其中初始位位于i-位（基于1）。注意，通过对称，初始位可以是从第一位到第ceil(n/2)-位的任何位置。对于这些情况，请注意，第一位将设置在第一位和初始位之间的任何位之前，最后一位也是如此。因此，第一分区和第二分区中的比特数分别为f(i)和{}。在

{29>的值可以计算为：

g(n,i) = f(i) + f(n+1-i) - 1

在计算f(n)时遵循这个想法。在

现在，计算最终结果是微不足道的。在

g(n)的定义

将g(n)定义为在原始问题中查找的计数。然后我们可以取所有可能的最大值i，初始位的位置：

g(n) = maxi=1..ceil(n/2)(f(i) + f(n+1-i) - 1)

Python代码：

import time
mem_f = [0,1,1,2,2]
mem_f.extend([-1]*(10**7)) # This will take around 40MB of memory
def f(n):
    global mem_f
    if mem_f[n]>-1:
        return mem_f[n]
    if n%2==1:
        mem_f[n] = 2*f((n+1)/2)-1
        return mem_f[n]
    else:
        half = n/2
        mem_f[n] = f(half)+f(half+1)-1
        return mem_f[n]

def g(n):
    return max(f(i)+f(n+1-i)-1 for i in range(1,(n+1)/2 + 1))

def main():
    while True:
        n = input('Enter n (1 <= n <= 10,000,000; 0 to stop): ')
        if n==0: break
        start_time = time.time()
        print 'g(%d) = %d, in %.3fs' % (n, g(n), time.time()-start_time)

if __name__=='__main__':
    main()

复杂性分析

有趣的是，用上述方法计算g(n)的复杂度是多少？在

我们首先要注意的是，我们迭代n/2的n/2值，即初始位的位置。在每个迭代中，我们称之为f(i)和{}。朴素的分析会导致O(n * O(f(n)))，但实际上我们在{}上使用了记忆，所以它比这个快得多，因为{}的每个值都是根据最多一次。因此，复杂性实际上是通过计算f(n)的所有值所需的时间而增加的，这将是O(n + f(n))。在

那么初始化f(n)的复杂性是什么呢？在

我们可以假设在计算f(n)之前，我们先预计算f(n)的每个值。注意，由于递归关系和记忆，生成f(n)的整个值需要O(n)时间。下一次调用f(n)将花费O(1)时间。在

因此，总的复杂性是O(n+n) = O(n)，这可以从n=1,000,000和n=10,000,000的iMac中的运行时间证明：

> python max_vec_bit.py
Enter n (1 <= n <= 10,000,000; 0 to stop): 1000000
g(1000000) = 475712, in 1.358s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0
>
> <restarted the program to remove the effect of memoization>
>
> python max_vec_bit.py
Enter n (1 <= n <= 10,000,000; 0 to stop): 10000000
g(10000000) = 4757120, in 13.484s
Enter n (1 <= n <= 10,000,000; 0 to stop): 6745231
g(6745231) = 3145729, in 3.072s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0

作为记忆化的一个副产品，n的较小值的计算在第一次调用大型n之后会快得多，正如您在示例运行中看到的那样。而且，如果语言更适合于数字压缩，例如C++，则运行速度可能会大大加快。

我希望这有帮助。=）

使用C++的代码，用于性能改进< /H2><> > C++中的结果约为68倍（用{{CD63}}测量）：

> ./a.out
Enter n (1 <= n <= 10,000,000; 0 to stop): 1000000
g(1000000) = 475712, in 0.020s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0
>
> <restarted the program to remove the effect of memoization>
>
> ./a.out
Enter n (1 <= n <= 10,000,000; 0 to stop): 10000000
g(10000000) = 4757120, in 0.198s
Enter n (1 <= n <= 10,000,000; 0 to stop): 6745231
g(6745231) = 3145729, in 0.047s
Enter n (1 <= n <= 10,000,000; 0 to stop): 0

<> C++中的代码：

#include <cstdio>
#include <cstring>
#include <ctime>

int mem_f[10000001];
int f(int n){
    if(mem_f[n]>-1)
        return mem_f[n];
    if(n%2==1){
        mem_f[n] = 2*f((n+1)/2)-1;
        return mem_f[n];
    } else {
        int half = n/2;
        mem_f[n] = f(half)+f(half+1)-1;
        return mem_f[n];
    }
}

int g(int n){
    int result = 0;
    for(int i=1; i<=(n+1)/2; i++){
        int cnt = f(i)+f(n+1-i)-1;
        result = (cnt > result ? cnt : result);
    }
    return result;
}

int main(){
    memset(mem_f,-1,sizeof(mem_f));
    mem_f[0] = 0;
    mem_f[1] = mem_f[2] = 1;
    mem_f[3] = mem_f[4] = 2;
    clock_t start, end;
    while(true){
        int n;
        printf("Enter n (1 <= n <= 10,000,000; 0 to stop): ");
        scanf("%d",&n);
        if(n==0) break;
        start = clock();
        int result = g(n);
        end = clock();
        printf("g(%d) = %d, in %.3fs\n",n,result,((double)(end-start))/CLOCKS_PER_SEC);
    }
}

---

证据

注意，为了让这个答案（已经很长了）保持简单，我跳过了证明中的一些步骤

关于f值的Aleksi Torhamo猜想

For `n>=1`, prove that:  
f(2n+k) = 2n-1+1 for k=1,2,…,2n-1  ...(1)  
f(2n+k) = k     for k=2n-1+1,…,2n  ...(2)
given f(0)=f(1)=f(2)=1

考虑到上述四种情况下的回归关系，可以很容易地证明：

• 情况1：（1）对于偶数k
• 情况2：（1）对于奇数k
• 情况3：（2）偶数k
• 情况4：（2）奇数k

Suppose we have the four cases proven for n. Now consider n+1.
Case 1:
f(2n+1+2i) = f(2n+i) + f(2n+i+1) - 1, for i=1,…,2n-1
          = 2n-1+1 + 2n-1+1 - 1
          = 2n+1

Case 2:
f(2n+1+2i+1) = 2*f(2n+i+1) - 1, for i=0,…,2n-1-1
            = 2*(2n-1+1) - 1
            = 2n+1

Case 3:
f(2n+1+2i) = f(2n+i) + f(2n+i+1) - 1, for i=2n-1+1,…,2n
          = i + (i+1) - 1
          = 2i

Case 4:
f(2n+1+2i+1) = 2*f(2n+i+1) - 1, for i=2n-1+1,…,2n-1
            = 2*(i+1) - 1
            = 2i+1

因此通过归纳证明了这个猜想。在

templatetypedef在最佳位置的猜想

For n>=1 and k=1,…,2n, prove that g(2n+k) = g(2n+k, 2n+1)
That is, prove that placing the first bit on the 2n+1-th position gives maximum number of bits set.

证明：

First, we have
g(2n+k,2n+1) = f(2n+1) + f(k-1) - 1

Next, by the formula of f, we have the following equalities:
f(2n+1-i) = f(2n+1), for i=-2n-1,…,-1
f(2n+1-i) = f(2n+1)-i, for i=1,…,2n-2-1
f(2n+1-i) = f(2n+1)-2n-2, for i=2n-2,…,2n-1

and also the following inequality:
f(k-1+i) <= f(k-1), for i=-2n-1,…,-1
f(k-1+i) <= f(k-1)+i , for i=1,…,2n-2-1
f(k-1+i) <= f(k-1)+2n-2, for i=2n-2,…,2n-1

and so we have:
f(2n+1-i)+f(k-1+i) <= f(2n+1)+f(k-1), for i=-2n-1,…,2n-1

Now, note that we have:
g(2n+k) = maxi=1..ceil(2n-1+1-k/2)(f(i) + f(2n+k+1-i) - 1)
       <= f(2n+1) + f(k-1) - 1
        = g(2n+k,2n+1)

所以这个猜想被证明了。在

Answer 2

因此，为了打破我通常不公布算法的传统，我没有证据，我想我应该提一下，有一种算法似乎对50000+以内的数字是正确的，并且运行时间为O（logn）。这要归功于Sophia Westwood，我今天和他共事了大约三个小时。这一切都归功于她。从经验上看，它似乎运行得很好，而且比O（n）解决方案快得多。在

关于这个问题结构的一个观察是，如果n足够大（n≥5），那么如果你把1放在任何地方，问题就会分成两个子问题，一个在1的左边，一个在右边。虽然1可能会在不同的时间被放在不同的两半，但最终的布局是一样的，就像你把每一半分开求解，然后把它们组合在一起。在

下一个观察是：假设你有一个大小为2^k+1的数组，在这种情况下，假设你在数组的两边各放一个1。然后：

• 下一个1放在数组的另一边。在
下一个1放在中间。在
• 现在有两个更小的子问题，大小为2^k-1+1。在

重要的一点是，产生的位模式是1和0的交替序列。例如：

• 对于5=4+1，我们得到10101
• 对于9=8+1，我们得到101010101
• 对于17=16+1，我们得到10101010101010101

这很重要的原因是：假设数组中有n个元素，k是2^k+1≤n的最大可能值。如果将1放在位置2^k+1，则数组左侧到该位置的部分将以交替的1和0平铺，它将一个1s的批放入数组中。在

不明显的是，把1位放在那里，对于5万以内的所有数字，似乎会产生一个最佳的解决方案！我已经编写了一个Python脚本来检查这一点（使用一个类似于@justhalf的递归关系），它似乎工作得很好。这个事实如此有用的原因是计算这个指数非常容易。特别是，如果2^k+1≤n，则2^k≤n-1，因此k≤lg（n-1）。选择值⌊lg（n-1）⌋作为k的选择，然后通过计算2^k+1来计算位索引。这个k值可以在O（logn）时间内计算，求幂也可以在O（logn）时间内完成，因此总运行时间为Θ（logn）。在

唯一的问题是我还没有正式证明这是有效的。我只知道，对于我们尝试的前50000个值来说，这是正确的。：-）

希望这有帮助！在

Answer 3

我会附上我所有的。和你的一样，唉，时间基本上是O(n**3)。但至少它避免了递归（等等），所以当你接近一百万时不会爆炸；-）注意，这返回找到的最佳向量，而不是计数；例如

>>> solve(23)
[6, 0, 11, 0, 1, 0, 0, 10, 0, 5, 0, 9, 0, 3, 0, 0, 8, 0, 4, 0, 7, 0, 2]

所以它也显示了选择1位的顺序。获取计数的最简单方法是将结果传递给max()。在

^{pr2}$

或者将函数更改为返回maxsofar，而不是best。在

如果你想计算一百万的数字，你需要的是完全不同的东西。你甚至负担不起二次方时间（更不用说这种方法的立方时间了）。不太可能从更华丽的数据结构中得到如此巨大的改进，我希望它需要对问题的数学有更深入的了解。在

def solve(n):
    maxsofar, best = 1, [1] + [0] * (n-1)
    # by symmetry, no use trying starting points in last half
    # (would be a mirror image).
    for i in xrange((n + 1)//2):
        v = [0] * n
        v[i] = count = 1
        # d21[i] = distance to closest 1 from index i
        d21 = range(i, 0, -1) + range(n-i)
        while 1:
            d, j = max((d, j) for j, d in enumerate(d21))
            if d >= 2:
                count += 1
                v[j] = count
                d21[j] = 0
                k = 1
                while j-k >= 0 and d21[j-k] > k:
                    d21[j-k] = k
                    k += 1
                k = 1
                while j+k < n and d21[j+k] > k:
                    d21[j+k] = k
                    k += 1
            else:
                if count > maxsofar:
                    maxsofar = count
                    best = v[:]
                break
    return best