G***n
发帖数: 877 | 1 数出从0到N用二进制表示的所有数的1的个数.算法复杂度要求log(N),可以用
recurrence.
比如0到4,一共有有0+1+1+2+1=5 | w***g
发帖数: 5958 | 2 假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
1或63.
举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
这样就可以递归了
f(N, k) {
if (k == 0) return N;
b = N >> k; // 最高为是0或者1
N' = N - b * (1 << k);
return b * (k * (1 << k-1) // 整的
+ N' + 1) + f(N', k-1); // 零的 // hatemaths指出错误，已改正
}
一共递归k次，k=log N, 所以复杂度为O(log N).
【在 G***n 的大作中提到】
: 数出从0到N用二进制表示的所有数的1的个数.算法复杂度要求log(N),可以用
: recurrence.
: 比如0到4,一共有有0+1+1+2+1=5
| P********e
发帖数: 2610 | 3 better than 0(logN), contest的解法。
假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
1或63.
举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
这样就可以递归了
f(N, k) {
if (k == 0) return N;
b = N >> k; // 最高为是0或者1
N' = N - b * (1 << k);
return b * k * (1 << k) // 整的
+ N' + 1 + f(N', k-1); // 零的
}
【在 w***g 的大作中提到】
: 假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
: 1或63.
: 举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
: 先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
: 以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
: 然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
: ，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
: 这样就可以递归了
: f(N, k) {
: if (k == 0) return N;
| j*a
发帖数: 14423 | 4 说得很清楚，好。
成3
是1
【在 w***g 的大作中提到】
: 假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
: 1或63.
: 举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
: 先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
: 以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
: 然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
: ，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
: 这样就可以递归了
: f(N, k) {
: if (k == 0) return N;
| G***n
发帖数: 877 | | h*******s
发帖数: 8454 | 6 很简洁的伪代码
但是最后返回语句似乎应该是
return b * (k * (1 << k-1) // 整的
+ N' + 1) + f(N', k-1); // 零的
成3
是1
【在 w***g 的大作中提到】
: 假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
: 1或63.
: 举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
: 先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
: 以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
: 然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
: ，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
: 这样就可以递归了
: f(N, k) {
: if (k == 0) return N;
| t****t
发帖数: 6806 | 7 how is this "better" than O(logN)?
成3
是1
【在 P********e 的大作中提到】
: better than 0(logN), contest的解法。
:
: 假设你所要的函数为 f(N, k)， k为最高位1的位置-1，不知道的话就按数据类型设成3
: 1或63.
: 举个例子吧。用二进制表示 N = 1011001 (共7位), 求f(N, k=6).
: 先数整的，从000000 数到 111111 (六个1)。这些数里面出现了所有可能的01组合，所
: 以1的个数为 k * 2^k / 2 (每个数k=6位，一共有2^k个数，其中一半是1).
: 然后数1000000到1011001。另N' = N - (1 << k) = 11001。所有这些数的第一位都是1
: ，所以有N' + 1个1, 再加上从0数到N'出现的1的个数f(N',k-1)
: 这样就可以递归了
| w***g
发帖数: 5958 | 8 你是对的，我那个代码错了
【在 h*******s 的大作中提到】
: 很简洁的伪代码
: 但是最后返回语句似乎应该是
: return b * (k * (1 << k-1) // 整的
: + N' + 1) + f(N', k-1); // 零的
:
: 成3
: 是1
| P********e
发帖数: 2610 | 9 题目要求O(logN),这个解法以k递归，当然比logN好了
【在 t****t 的大作中提到】
: how is this "better" than O(logN)?
:
: 成3
: 是1
| t****t
发帖数: 6806 | 10 isn't k~=logN?
【在 P********e 的大作中提到】
: 题目要求O(logN),这个解法以k递归，当然比logN好了
| P********e
发帖数: 2610 | 11 so? this solution is still better.
【在 t****t 的大作中提到】
: isn't k~=logN?
| t****t
发帖数: 6806 | 12 k~=logN, then O(k)=O(logN)...
你这也好意思号称是学过算法的, 不懂没关系, 不懂还要出来卖弄就没品了.
【在 P********e 的大作中提到】
: so? this solution is still better.
| P********e
发帖数: 2610 | 13 我就知道回你帖肯定会后悔.你就钻你的牛角尖吧.
【在 t****t 的大作中提到】
: k~=logN, then O(k)=O(logN)...
: 你这也好意思号称是学过算法的, 不懂没关系, 不懂还要出来卖弄就没品了.
|
|
