三星面试题

medie2005

呵呵,还是我自己灌水洗澡吧.

已知：
a[ 0 ] = 0;
a[ 1 ] = 1;
...
...
a[ 2*i ]  =  a[ i ];
a[ 2*i+1 ]  =  a[  i  ] + a[ i+1 ];

问题：
给定任意一个i（0 <i <2000000)
求a[ 0 ]到a[ i ]之间的最大值，以及其下标。

是在csdn上看到的(http://topic.csdn.net/u/20081023 ... c-41553a66fc4c.html)看能不能找到对数阶的算法.

无心人

我怎么感觉 a[ i ] 象i的二进制表示中的1的数量阿

无心人

a[0] = 0
a[1] = 1
a[2] = a[1] = 1
a[3] = a[1] + a[2] = 1 + 1 = 2
a[4] = a[2] = a[1] = 1
a[5] = a[2] + a[3] = 3
a[6] = a[3] = 2
a[7] = a[3] + a[4] = 3
a[8] = 1
a[9] = a[4] + a[5] = 4
...
还不是那么简单

无心人

显然
2 * i + 1的拆分
i和i + 1
要保证i的二进制表示要足够复杂

medie2005

$[(a[2n+1]),(a[2n])]=[(1,1),(0,1)]*[(a[n+1]),(a[n])]$
$[(a[2n+2]),(a[2n+1])]=[(1,0),(1,1)]*[(a[n+1]),(a[n])]$
记$U=[(1,0),(1,1)],V=[(1,1),(0,1)]$.

[ 本帖最后由 medie2005 于 2008-10-28 14:01 编辑 ]

mathe

挺有意思.
将n用二进制表示,对于每个比特位1,改成$U'=V$,对于每个比特位0,改为$V'=U$
这样我们得到一个矩阵的乘积表达式,然后取乘积矩阵右上角元素就可以了.

mathe

现在结论就简单了,由于对于矩阵乘法有:
$[(a,b),(c,d)][(1,1),(0,1)]=[(a,a+b),(c,c+d)]$
$[(a,b),(c,d)][(1,0),(1,1)]=[(a+b,b),(c+d,d)]$
如果a,b,c,d都非负,我们知道上面乘积过程每次添加矩阵V结果不会差于添加U的结果.
所以我们知道所有k位数中比特位全是1的那个数肯定能够取到最大值$V^k$的右上角的值即k.
同样,所有前缀都相同的数字中,后面不同部分全为1的数据可以取到最大值.
所以假设我们要计算100以前取得最大结果的数据.由于100二进制表示是7位数$(1100100)_b$
我们首先需要计算$a[2^6-1]=6$,
其次我们我们还需要计算$a[(1011111)_b],[1100011)_b],a[(1100100)_b]$
取它们几个中间的最大值就可以了.所有其它数据都可以根据前面的共同前缀原则同这4个数之一有公共前缀

mathe

上面分析错误了.我们首先根据上面结论可以知道a(2n+1)>a(2n).而2n+1的最终取值是n对应的矩阵上面两个数字之和.所以我们可以想办法找到数字对应的矩阵上面两个数字这和最大的数字.
由于对于矩阵$[(a,b),(c,d)]$,在a>b的时候,右乘矩阵V得到矩阵上面两个数字和更大(2a+b>2b+a),而a<b的时候,右乘U得到矩阵两个数字和更加大.所以我们可以知道二进制表示各位为0,1交替的数值比相同位数的其它数有更大的取值.但是这个规则对于总位数偶数位的数不可行.而对于总位数位偶数的数字,我们知道次高位取1和0得到的前两位构成的矩阵的上面两个数字和是相同的,所以丢与总位数是偶数的数据,我们总可以先重复一个数字1,然后在0和1交替就可以了.
通过这个方法,我们可以非常容易计算出二进制k位数中取值最大的数.
不过上面的过程还没有解决那些具有部分相同前缀的二进制数中取值最大的问题,不过也不难解决了,
对于那些余下部分通过01交替正好末尾是1的数据,显然这个数值已经最大;不然,我们可以分别分析这个数据后面在添加一个0和1两种情况.
再次以100作为例子
首先,所有6位数中取值最大的应该是$(110101)_b$
然后在看所有$(10*****)_b$形式的数,这个数据如果01交替添加末尾会是1,所以取最大结果的数为$(1010101)_b$,然后再次查看以$(11000**)_b$形式的数,这个数据如果01交替添加末尾会是0,所以需要分别分析
$(110001*)_b$和$(110000*)_b$两种形式的数.
这个方法总时间复杂度不会超过$O(log^2(n))$

medie2005

f( 0 )==0     : 0
f( 1 )==1     : 1
f( 2 )==1     : 10
f( 3 )==2     : 11
f( 4 )==1     : 100
f( 5 )==3     : 101
f( 6 )==2     : 110
f( 7 )==3     : 111
f( 8 )==1     : 000
f( 9 )==4     : 1001
f( 10 )==3     : 1010
f( 11 )==5     : 1011
f( 12 )==2     : 1100
f( 13 )==5     : 1101
f( 14 )==3     : 1110
f( 15 )==4     : 1111
f( 16 )==1     : 10000
f( 17 )==5     : 10001
f( 18 )==4     : 10010
f( 19 )==7     : 10011
f( 20 )==3     : 10100
f( 21 )==8     : 10101
f( 22 )==5     : 10110
f( 23 )==7     : 10111
f( 24 )==2     : 11000
f( 25 )==7     : 11001
f( 26 )==5     : 11010
f( 27 )==8     : 11011
f( 28 )==3     : 11100
f( 29 )==7     : 11101
f( 30 )==4     : 11110
f( 31 )==5     : 11111
f( 32 )==1     : 100000
f( 33 )==6     : 100001
f( 34 )==5     : 100010
f( 35 )==9     : 100011
f( 36 )==4     : 100100
f( 37 )==11     : 100101
f( 38 )==7     : 100110
f( 39 )==10     : 100111
f( 40 )==3     : 101000
f( 41 )==11     : 101001
f( 42 )==8     : 101010
f( 43 )==13     : 101011
f( 44 )==5     : 101100
f( 45 )==12     : 101101
f( 46 )==7     : 101110
f( 47 )==9     : 101111
f( 48 )==2     : 110000
f( 49 )==9     : 110001
f( 50 )==7     : 110010
f( 51 )==12     : 110011
f( 52 )==5     : 110100
f( 53 )==13     : 110101
f( 54 )==8     : 110110
f( 55 )==11     : 110111
f( 56 )==3     : 111000
f( 57 )==10     : 111001
f( 58 )==7     : 111010
f( 59 )==11     : 111011
f( 60 )==4     : 111100
f( 61 )==9     : 111101
f( 62 )==5     : 111110
f( 63 )==6     : 111111
f( 64 )==1     : 000000
f( 65 )==7     : 1000001
f( 66 )==6     : 1000010
f( 67 )==11     : 1000011
f( 68 )==5     : 1000100
f( 69 )==14     : 1000101
f( 70 )==9     : 1000110
f( 71 )==13     : 1000111
f( 72 )==4     : 1001000
f( 73 )==15     : 1001001
f( 74 )==11     : 1001010
f( 75 )==18     : 1001011
f( 76 )==7     : 1001100
f( 77 )==17     : 1001101
f( 78 )==10     : 1001110
f( 79 )==13     : 1001111
f( 80 )==3     : 1010000
f( 81 )==14     : 1010001
f( 82 )==11     : 1010010
f( 83 )==19     : 1010011
f( 84 )==8     : 1010100
f( 85 )==21     : 1010101   // biggest
f( 86 )==13     : 1010110
f( 87 )==18     : 1010111
f( 88 )==5     : 1011000
f( 89 )==17     : 1011001
f( 90 )==12     : 1011010
f( 91 )==19     : 1011011
f( 92 )==7     : 1011100
f( 93 )==16     : 1011101
f( 94 )==9     : 1011110
f( 95 )==11     : 1011111
f( 96 )==2     : 1100000
f( 97 )==11     : 1100001
f( 98 )==9     : 1100010
f( 99 )==16     : 1100011
f( 100 )==7     : 1100100

mathe

是的,我前面的错误已经发现了
而对于n=100的算法还可以改进,由于我们发现7位二进制数取值最大的数$(1010101)_b$已经小于100了,不需要分析了,直接可以得出它最大.