数学研发论坛

 找回密码
 欢迎注册
查看: 422|回复: 2

[原创] 和二进制有关的面试题

[复制链接]
发表于 2018-2-9 01:14:07 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
最近在准备工作面试, 看了不少有趣的数学题。再来分享一道。
考虑这样一个函数:
$f : N \to N$, $f(n)$为$n$的二进制表示中$11$出现的次数,
比如: $(11)_{10} = (1011)_2$一共出现了$1$次 $11$. 于是$f(11) = 1$.
再比如:$(15)_{10} = (1111)_2$一共出现了$3$次 $11$. 于是$f(15) = 3$.

问:
$f(64)$=?
$\sum_{i = 0}^64 f(i)$ = ?
$\sum_{i = 0}^96 f(i)$ = ?
更一般的
$\sum_{i = 0}^{2^n} f(i)$ = ?
$\sum_{i = 0}^{2^n + 2^{n-1}} f(i)$ = ?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-9 02:01:56 | 显示全部楼层
临睡前瞄一眼
数列递归公式——数列通项公式——数列和公式
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-2-9 11:50:54 | 显示全部楼层
这个不能算算法题,是纯粹的数学题。属于计数问题,可以直接求出公式解。
由于显然$f(2^n)=0$,所以我们首先需要计算\(\sum_{i=0}^{2^n-1}f(i)\)
我们把这$2^n$个数都看成n比特二进制数进行运算并不影响结果,
这$2^n$个数中第h和第h+1比特都是1的数有$2^{n-2}$个,所以马上有
\(\sum_{i=0}^{2^n-1}f(i)=(n-1)2^{n-2}\)

\(\sum_{i=2^n}^{2^n+2^{n-1}-1}f(i)\)中,类似前面算法可以先得出后面n-2个相邻比特贡献了$(n-2)2^{n-3}$
而最高两比特贡献了$2^{n-2}$,所以结果应该是\(\sum_{i=2^n}^{2^n+2^{n-1}-1}f(i)=n2^{n-3}\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-8-21 13:59 , Processed in 0.046857 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表