三星面试题

medie2005

呵呵,还是我自己灌水洗澡吧. 已知： a[ 0 ] = 0; a[ 1 ] = 1; ... ... a[ 2*i ] = a[ i ]; a[ 2*i+1 ] = a[ i ] + a[ i+1 ]; 问题： 给定任意一个i（0 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

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了,不需要分析了,直接可以得出它最大.