hiho一下第168周《Biinary Numbers》题目分析

7
1

《Biinary Numbers》题目分析

这道题是一道计数问题。我们一开始就会有一个大概的思路:依次确定每一个二进位是0、1还是2,分别计算3种情况下表示方法的数目。

我们下面介绍2种不同的方法,一种是从最高位到最低位依次计算,另一种是从最低位到最高位依次计算。

假设我们要求N=10的表示方法数,10的二进制表示是(1010)2,我们用f(1010)表示(1010)2在扩展二进制下有多少种表示方法。

如果我们用扩展二进制表示10,那么10的最高位(2^3这一位)有两种可能,一种是0,一种是1。

如果最高位是1,那么剩下3位我们只需要表示(010)2,表示方法一共有f(010)种。

如果最高位是0,那么剩下3位需要表示的数是(010)2再加上第四位(2^3)的1,我们用f(1|010)来表示用三位扩展二进制数表示(1010)2有多少种方法。

对于f(010),我们考虑(010)2的最高位只有0一种可能,所以f(010)=f(10)。

对于f(1|010),我们考虑第三位只可能是1或者2。如果是1,后2位表示方法有f(1|10)种;如果是2,后两位表示方法有f(10)种。

我们可以把上述N=10的计算的递归树的画出来,如下图:

我们写一个递归程序来实现以上的计算过程:

int f(int k, int rest) {  //递归计算f(rest|a[k..0]),其中rest是0/1,a[k..0]是n的二进制表示的后缀
        if(k == 0) {
                if(a[0] == 1 && rest == 1) return 0;
                else return 1;
        }
        int sum = a[k] + 2 * rest;
        if(sum == 3) return f(k-1, 1);
        if(sum == 2 || sum == 1) return f(k-1, 0) + f(k-1, 1);
        return f(k-1, 0);
}
int main()
{
        cin >> n;
        m = 0;
        while(n) {  //a[m-1] .. a[0]是n的二进制表示
                a[m] = n & 1;
                n >>= 1;
                m++;
        }
        cout << f(m-1, 0) << endl;
        return 0;
}

值得一提的是,上述递归算法有很多重复计算,例如橘色、灰色和绿色的函数值。不过它仍然能在时限内通过所有的数据,你能准确计算出上述递归算法的复杂度吗?

我们可以发现,每一层只有2个函数值要求:f(N的二进制表示的后缀)和f(1|N的二进制表示的后缀)。所以我们可以用动态规划来优化上述递归算法,保证每个函数值只被计算一次。复杂度O(logN)。

以上是从最高位向最低位依次确定每一位的值。我们还可以倒过来从最低位向最高位依次确定。可以得到一个更简单的递归算法:

int calc(int n) {
        if (n == 0) return 1;
        if (n % 2 == 0) return calc(n / 2) + calc(n / 2 - 1);
        return calc(n / 2);
}

int main() {
        int n;
        cin >> n;
        cout << calc(n) << endl;
        return 0;
}

具体推导留给大家思考。

最后我们介绍一个研究数列问题的大杀器https://oeis.org。OEIS是一个整数数列百科全书,你可以输入数列的连续若干项,OEIS会告诉你这些项可能是哪个数列的一部分。以及这个数列有什么性质、递归公式、通项公式等等。

比如这周的题目我们可以手算出来N=1~8的值分别是1,2,1,3,2,3,1,4。在OEIS中搜索1,2,1,3,2,3,1,4就可以知道这个数列的信息啦。

4 answer(s)

0

腾讯9.13笔试题目,这个早出一周就好了,233。

  • 其实这题去年就在题库里了~ 查了查数据库9.13前几天还真有同学AC了这题。不知道他有没有参加腾讯的笔试 233

  • 添加评论
  • reply
3

上周腾讯笔试题啊...当时做的时候一不小心点到了下一页...然后就回不去了...OTZ

  • 实在是坑,第一道随机的难度大,直接g

  • 添加评论
  • reply
1

大佬们帮忙解释一下动态规划那个程序啊

  • 分偶数和奇数。 偶数:最后一位只能是0或者2, 是0时,需要计算f(n/2),是2是需要计算f( (n - 2)/2 ) 即 f(n/2 - 1). 所以 if (n % 2 == 0) return calc(n / 2) + calc(n / 2 - 1); 当n是奇数时,最后一位只能是1,即算f(n/2)。

  • thanks

  • 添加评论
  • reply
0

写了个TLE的。。。

#include "iostream"
#include "math.h"
using namespace std;

int f(int x, int i)
{
    if (x>2*(pow(2,i)-1))
        return 0;
    if (x == 0)
        return 1;   

    int sum = 0;
    if (x>=pow(2,i))
        sum += f(x-pow(2,i), i-1);
    sum += f(x-pow(2,i-1), i-1);
    sum += f(x, i-1);

    return sum;
}  

main()
{
    int x,i;
    cin>>x;
    i = 1;
    while (pow(2,i)<=x)
    {
        i = i+1;
    }

   cout<<f(x,i);
}

write answer 切换为英文 切换为中文


转发分享