今天的2道百度面试题
今天下午面了百度，其中两题是这样的，我都没有回答出来。
概率题：一个篮子里装着20个红球和20个蓝球，每次从中取出2球，如果取出的2球颜色是一样的，那么放回红球，取出蓝球；如果取出的2球的颜色是一样的，则都不放回，将2球都取出；不断重复以上步骤。问题：求最后一次取球恰好只取到一个红球的概率。
算法题：给你一个自然数N，求[6,N]之内的所有素数中，两两之和为偶数的那些偶数。（直接枚举的话应该是O(n^3)）。我的解法如下，是直接枚举的。
百度 面试题
/* 百度面试题 */
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define N (20000)
#define M (N/2)
static int primes[M]; /*编译器初始化了0*/
static int sums[M*M]; /*任意两素数之和*/
int my_cmp (const void * a, const void * b);
/* 判断一个数是不是素数，是素数则返回它自己；否则返回0 */
int is_prime (int x){
int i,t;
int ans = 0;
if (x<=1 || 0==x%2){
return ans;
}
t = (int)sqrt (x);
for (i=3;i<=t;i+=2){
if (0 == x%i){
return ans;
}
}
return (ans = x);
}
/* 保存区间的素数到全局数组primes */
void primes_in (int low, int high){
int i=0,j=low;
while (j<=high){
if (is_prime (j)){
primes[i++]=j;
}
j++;
}
}/*数组中的非零元素就是区间中的素数 */
/*求区间中素数的和并打印出来 */
void solve (int left, int right){
int i,j,k;
int t;
primes_in (left,right);
for (t=0; t<M; t++){
if (!primes[t]){
break;
}
}
for (k=0,i=0; i<t; i++){
for (j=i; j<t; j++){
sums[k++]=primes[i]+primes[j];
}
}
/*排序*/
qsort (sums, k, sizeof (int), my_cmp);
/*去重*/
i=0;
for (j=i+1; j<k; j++){
if (sums[j] > sums[i]){
sums[++i] = sums[j];
}
}
/*打印*/
for (j=0;j<=i;j++){
printf ("%d, %d\n", j+1, sums[j]);
}
}
int my_cmp (const void * a, const void * b){
return (*(int *)a - *(int *)b);
}
/* 程序入口 */
int main (){
solve (6,N);
return 0;
}
[解决办法]
第一题的概率是0；因为这个取球的过程表明蓝球的数目永远是偶数，因为是最后一次取球，所以如果只有一个红球，那说明也只有一个蓝球了，而这时不可能的；
第二题就是哥德巴赫猜想，任何一个大于6的偶数都可以表示为两个素数之和，所以直接打印所有的偶数就完了。
[解决办法]
第一题 概率为零
设 A为取出两个同色的球，B为取出一个红一个蓝，C为取出一个红球，D为取出一个篮球
情况一：
每次都发生A事件，则B，C，D的概率都为零。
情况二：
由于蓝球只有20个，所以B事件连续最多发生20次。之后就都是A事件发生。C、D概率为零。
情况三：
由于B事件发生后，必留下红球取走蓝球，所以D事件要发生的话，最后必须剩余3个球，
而只有A事件发生且取出两个都是红球时，红球才会被取走，所以剩余的红球数都是偶数，
那么最后三个球必是2个红球一个篮球，或者三个都是蓝球。所以C事件发生的概率为零。
综合上述三个情况C发生的概率都是零，所以C的概率是零。
[解决办法]
coder的心思猜不起啊，还要写个代码来算一下，人家考的是逻辑，不需要你写代码，如果人家告诉你不是20个，而是200个，2000个，你们是不是也要去写个代码好好算一下呢。
[解决办法]
有意思，各种取球情况下，红球以偶数2为阶梯递减，蓝球以1 或者2为阶梯递减，所以红球不会只剩下一个。