1. 如果用最少的比较次数找出 一个数组的最大和次大的数?
2. 50个黑球50个百球，2个罐，要求你放这100个球在这2个罐，使得别人随机从2个
罐中任意拿一个球是黑球的几率达到最大。
3. 2个人商量好策略，然后一个从52张牌里面随机抽5张，看牌，考虑。。。然后排在
桌上，摊开前4张，第5张面朝下，由第二个人判断第5张牌。 问这个策略。
4.写atoi函数
5.古老的三角形问题：输入3边，看是什么三角形。
1. Brute Force当然可以算出来, 这样找到最大的 需要比较 (n-1)次, 然后在(n-1)个数里面找到最大的
要(n-2)次, 总共比较n-1+n-2 = 2*n-3次
然后可以Divide and Conquer, 如果n个数, 分成2组, 每组的最大,次大都找到了,
M1 M2
N1 N2
那么只要M1和M2比一次, 找出即是最大的数, 然后如果M1大, N1 和 M2再比一次就好了,
所以我们有 T(n) = 2*T(n/2) + 2;
而且因为 T(2) = 1;
T(n) = 1.5*n – 2;
但是还有更好的方法, 发现每次我们分组之后其实只要把最大值比较出来就好, 然后把比较中小的
那个数放入一个group中, 最后我们比较出来之后就找到最大的数了, 然后在那个group中找到最大
的数就是整个线性列的次大数了
这样找到最大的数 T(n) = 2*T(n/2) +1 T(n) = n-1;(这是废话拉,找到最大的数最少也要n-1次)
然后巧妙的是group中只有log(n)个元素, 比较log(n) -1 就好了
所以总共 T(n) = (n-1)+(log(n)-1) = log(n) +n-2;
我们可以证明log(n) < 0.5*n, 所以 T(n) = long(n) + n-2是上述中最好的方法
2. 最好的方法应该是 一个黑球放在A罐, 49个黑球和50个白球放在B罐
3. 老实说没看懂..
4. 这个很直观, char* -> int, 但是需要考虑很多边界条件, 比如输入的字符串里面出现了非法字符
怎么办, 比如输入的是NULL怎么办;
还有一点关键的的是 有可能字符串里面开始阶段有很多/space, /tab(这个都是允许的, 这个比较
容易忘记), 然后有可能有sign符号(“+”或者 “-“)
int atoi(char *p)
{
int index = 0, sign = 1, s =0;
if(!p) exit(1);
while(p[index]==' '||p[index]=='\t')
index++;
if(p[index] == '+')
index++;
else if(p[index] == '-')
{ sign = -1; index++;}
while(p[index]!='\0'&&p[index]<='9'&&p[index]>='0')
s = s*10 + (p[index++]-'0');
if(p[index]!='\0') exit(2); //illegal character examined
else return (sign*s);
}
还有一个值得讨论的问题, 当输入的字符大于int的最大范围(-2^31–2^31-1), 如果每次都要判断
感觉很麻烦,
5. 大概就是把vector求出来, 然后利用 a*b = |a|*|b|*cos(theta);
把角度的余玄算出来,就好了