今天的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;
}
