百度实习生招聘笔试题:
请编写函数foo(int x, int y, int n)
计算：随机生成x个大小为[1,y]的正整数，它们的和为n的概率是多少？
解 ：用一个数组count[m][k]表示共m次生成随机数,和为k的次数,初始化count[1][1],count[1][2]..count[1][y]=1
对于第i次产生随机数：和为i*min到i*max的和数j的概率(或称 次数)需要更改(这里min=1,max=y)
count[i][j]=count[i-1][j-1]+count[i-1][j-2]..count[i-1][j-y+1]
这里的二维数组可以用两个一维数组交替使用
// foo.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <math.h> using namespace std; double foo(int x, int y, int n) { if (n > x * y || n < x) return 0; double t = pow((double) y, x); if (n == x || n == x * y) return 1 / t; if (x == 1) return (double) 1 / y; int flag = 1; double *p[2]; p[0] = new double[x * y + 1]; p[1] = new double[x * y + 1]; int i; for (i = 1; i <= x * y; i++) { p[0][i] = 0; p[1][i] = 0; } for (i = 1; i <= y; i++) { p[0][i] = 1; } for (i = 2; i <= x; i++) { for (int j = i; j <= i * y; j++) { p[flag][j] = 0; for (int k = 1; k <= y && j - k > 0; k++) p[flag][j] += p[1 - flag][j - k]; } flag = 1 - flag; } //for(i=x;i<=x*y;i++) // printf("%2d: %f\n",i,p[1-flag][i]); double ret = p[1 - flag][n] / t; delete[] p[0]; delete[] p[1]; return ret; } int main(int argc, char* argv[]) { printf("%f\n", foo(9, 6, 23)); return 0; }
参考自:http://zhedahht.blog.163.com/blog/static/254111742009101524946359/
2.设计函数，输入为一个字符串，里边包含中文、英文、数字等字符，编码为GBK。中文字符的编码规则假定为：双字节组成，高字节大于0x80，低字节任意。
a) 用常用语言（c/c++/php/java）编写函数，实现功能为：按顺序提取输入文本中的中文字符，形成新的文本串返回调用者。
b) 如果调用者有时希望得到输入串的全中文内容，有时希望得到英文内容，那么该函数应如何设计。
c) 如果调用者希望获取输入串中包含中文、英文、数字这三种字符中的一种或多种的需求不定时，函数应如何设计。
getChar(s,LETTER|DIGIT|CHINESE)
enum Type{ CHINESE=1, LETTER=2, DIGIT=4 }; static inline bool isLetter(char c){ return c>='a'&&c<='z'||c>='A'&&c<='Z'; } string getChar(const char* str,int type = CHINESE){ int length = strlen(str); char *tmp =(char*)malloc((length+1)*sizeof(char)); string ret; int k = 0; for(int i=0;i<length;i++){ if(type>>0&1){ if((unsigned char)str[i]>0x80){ tmp[k++]=str[i]; tmp[k++]=str[++i]; continue; } } if((type>>1&1)&&isLetter(str[i])){ tmp[k++]=str[i]; continue; } if((type>>2&1)&&isdigit(str[i])){ tmp[k++]=str[i]; continue; } } tmp[k]='\0'; ret.assign(tmp); free(tmp); return ret; }