最新答案（O(log n) 复杂度）
如果我们相信 templatetypedef 和 Aleksi Torhamo 的猜想（更新：本文末尾的证明），则有一个count(n)可计算的封闭形式解决方案O(log n)（或者O(1)如果我们假设对数和位移是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++：
int log(int n){ // Integer logarithm, by counting the number of leading 0
return 31-__builtin_clz(n);
}
int p(int n){ // The largest power of 2 not exceeding n
if(n==0) return 0;
return 1<<log(n);
}
int f(int n){ // The f function calculated using Aleksi Torhamo conjecture
int val0 = p(n-1);
int val1 = val0/2+1;
int val2 = n-val0;
return val1>val2 ? val1 : val2;
}
int count(int n){ // The count, using position k conjectured by templatetypedef
int k = p(n-1)+1;
int count_left = k/2;
int count_right = f(n-k+1);
return count_left + count_right;
}
此代码可以立即正确计算n=100,000,000（甚至n=1e24在 Python 中！）的结果1。
我已经测试了具有各种值的代码n（使用我的O(n)解决方案作为标准，请参阅下面的旧答案部分），它们似乎仍然正确。
此代码依赖于 templatetypedef 和 Aleksi Torhamo 2的两个猜想。有人想证明这些吗？=D（更新 2：证明）
1没有时间，我的意思是几乎立即
2 Aleksi Torhamo 关于f函数的猜想已被经验证明n<=100,000,000
旧答案（O(n) 复杂度）
我可以使用 Python 2.7 以 1.358 秒（在我的 iMac 中）返回n=1,000,000（结果为）的计数。更新：在 C++ 中是 0.198 秒。=)475712n=10,000,000
这是我的想法，它实现了O(n)时间复杂度。
算法
的定义f(n)
定义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高达 的所有值）：n
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)和f(n+1-i)。
因此 的值g(n,i)可以计算为：
g(n,i) = f(i) + f(n+1-i) - 1
计算时遵循这个想法f(n)。
现在，计算最终结果是微不足道的。
的定义g(n)
定义g(n)为在原始问题中寻找的计数。然后我们可以取所有可能的最大值i，即初始位的位置：
g(n) = 最大值i=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值i，即初始位的位置。在每次迭代中，我们调用f(i)and f(n+1-i)。天真的分析会导致O(n * O(f(n)))，但实际上我们在 上使用了 memoization f，所以它比这快得多，因为每个 的值f(i)最多只计算一次。因此，复杂性实际上是由计算 的所有值所需的时间增加的f(n)，O(n + f(n))取而代之的是。
那么初始化的复杂性是f(n)什么？
我们可以假设我们f(n)在计算 之前预先计算了 first的每个值g(n)。请注意，由于递归关系和记忆，生成整个值f(n)需要O(n)时间。下一次调用f(n)将需要O(1)时间。
因此，总体复杂性是O(n+n) = O(n)，正如我的 iMac 中运行时间所证明的n=1,000,000那样n=10,000,000：
> python max_vec_bit.py
输入 n（1 <= n <= 10,000,000；0 停止）：1000000
g(1000000) = 475712，在 1.358 秒内
输入 n（1 <= n <= 10,000,000；0 停止）：0
>
> <重启程序消除记忆效果>
>
> python max_vec_bit.py
输入 n（1 <= n <= 10,000,000；0 停止）：10000000
g(10000000) = 4757120，在 13.484 秒内
输入 n（1 <= n <= 10,000,000；0 停止）：6745231
g(6745231) = 3145729，在 3.072 秒内
输入 n（1 <= n <= 10,000,000；0 停止）：0
并且作为 memoization 的副产品，n在第一次调用 large 后，较小值的计算会快得多n，您也可以在示例运行中看到。并且使用更适合数字运算的语言（例如 C++），您可能会获得显着更快的运行时间
我希望这有帮助。=)
使用 C++ 的代码，用于提高性能
C++ 中的结果大约快 68 倍（通过 测量clock()）：
> ./a.out
输入 n（1 <= n <= 10,000,000；0 停止）：1000000
g(1000000) = 475712，在 0.020 秒内
输入 n（1 <= n <= 10,000,000；0 停止）：0
>
> <重启程序消除记忆效果>
>
> ./a.out
输入 n（1 <= n <= 10,000,000；0 停止）：10000000
g(10000000) = 4757120，在 0.198 秒内
输入 n（1 <= n <= 10,000,000；0 停止）：6745231
g(6745231) = 3145729，在 0.047 秒内
输入 n（1 <= n <= 10,000,000；0 停止）：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);
}
}
证明
请注意，为了保持这个答案（已经很长）简单，我跳过了证明中的一些步骤
Aleksi Torhamo 关于价值的猜想f
对于`n>=1`，证明：
f(2 n +k) = 2 n-1 +1 对于 k=1,2,…,2 n-1 ...(1)
f(2 n +k) = k for k=2 n-1 +1,…,2 n ...(2)
给定 f(0)=f(1)=f(2)=1
上面的结果可以很容易地通过对递归关系的归纳来证明，通过考虑四种情况：
- 案例1：（1）对于偶数
k
- 案例2：（1）对于奇数
k
- 案例3：（2）对于偶数
k
- 案例4：（2）对于奇数
k
假设我们已经证明了 n 的四种情况。现在考虑n+1。
情况1：
f(2 n+1 +2i) = f(2 n +i) + f(2 n +i+1) - 1，对于 i=1,…,2 n-1
= 2 n-1 +1 + 2 n-1 +1 - 1
= 2 n +1
案例二：
f(2 n+1 +2i+1) = 2*f(2 n +i+1) - 1，对于 i=0,…,2 n-1 -1
= 2*(2 n-1 +1) - 1
= 2 n +1
案例3：
f(2 n+1 +2i) = f(2 n +i) + f(2 n +i+1) - 1，对于 i=2 n-1 +1,…,2 n
= i + (i+1) - 1
= 2i
案例4：
f(2 n+1 +2i+1) = 2*f(2 n +i+1) - 1，对于 i=2 n-1 +1,…,2 n -1
= 2*(i+1) - 1
= 2i+1
所以通过归纳，猜想得到证明。
最佳位置的templatetypedef猜想
对于 n>=1 和 k=1,…,2 n，证明 g(2 n +k) = g(2 n +k, 2 n +1)
也就是说，证明将第一位放在第 2 n +1 个位置会给出最大位数。
证据：
首先，我们有
g(2 n +k,2 n +1) = f(2 n +1) + f(k-1) - 1
接下来，通过 f 的公式，我们有以下等式：
f(2 n +1-i) = f(2 n +1)，对于 i=-2 n-1 ,…,-1
f(2 n +1-i) = f(2 n +1)-i，对于 i=1,…,2 n-2 -1
f(2 n +1-i) = f(2 n +1)-2 n-2，对于 i=2 n-2 ,…,2 n-1
还有以下不等式：
f(k-1+i) <= f(k-1), 对于 i=-2 n-1 ,…,-1
f(k-1+i) <= f(k-1)+i , 对于 i=1,…,2 n-2 -1
f(k-1+i) <= f(k-1)+2 n-2，对于 i=2 n-2 ,…,2 n-1
所以我们有：
f(2 n +1-i)+f(k-1+i) <= f(2 n +1)+f(k-1)，对于 i=-2 n-1 ,…,2 n-1
现在，请注意我们有：
g(2 n +k) = 最大值i=1..ceil(2 n-1 +1-k/2) (f(i) + f(2 n +k+1-i) - 1)
<= f(2 n +1) + f(k-1) - 1
= g(2 n +k,2 n +1)
于是猜想得到了证明。