微软试题合集 微软面试题

发信人: kaiser (晴耕雨读), 信区: VC 标 题: 微软面试题之数字谜题 发信站: 交大晨光 (2002年03月29日08:49:32 星期五), 站内信件 ◎ 模范版主 微软面试题之数字谜题 设有两个自然数m,n，2〈=m<=99。 S先生知道这两数的和s，P先生知道这两数的积p。他 们两人进行了如下的对话： S：我知道你不知道这两个数是什么，但我也不知道。 P：现在我知道这两个数了。 S：现在我也知道这两个数了。 由这些条件，试确定m，n。 因为S知道两数之和，却由此推断P不知道两个数，所以说两数之和s一定不能拆分成两个 素数的和，即m,n不可能都是素数，且m,n中不会有大于50的素数，否则的话m*n可以唯一 分解，P知道了m,n的积就一定可以知道m,n了。 P从S的言语中能够判断出的信息是： 1。m,n不会全是素数； 2。m,n中不会有大于50的素数； 3。m,n之和不能拆成两个素数的和； 4。因为S自己也不知道这两个数是什么，所以这两个数的和一定小于99+98，否则S就可 以知道这两个数是什么了。 满足以上条件的 s=m+n有以下的可能： 11 17 23 27 29 35 37 41 47 196 然后P根据自己掌握的p=m*n立即算出m,n，这说明p=m*n是具有以下性质的特殊数字： 根据这个特殊的p,当s取上面的那些值的时候，只有一种s的取值使得方程 m+n=s, m*n=p 在[2,99]内有唯一的整数解。 根据这个性质计算出的p有以下的情况（不妨设m<=n）： p = 18, s= 11, m = 2, n = 9 p = 24, s= 11, m = 3, n = 8 p = 28, s= 11, m = 4, n = 7 p = 50, s= 27, m = 2, n = 25 p = 52, s= 17, m = 4, n = 13 p = 54, s= 29, m = 2, n = 27 p = 76, s= 23, m = 4, n = 19 p = 92, s= 27, m = 4, n = 23 p = 96, s= 35, m = 3, n = 32 p = 100, s= 29, m = 4, n = 25 p = 110, s= 27, m = 5, n = 22 p = 112, s= 23, m = 7, n = 16 p = 114, s= 41, m = 3, n = 38 p = 124, s= 35, m = 4, n = 31 p = 130, s= 23, m = 10, n = 13 p = 138, s= 29, m = 6, n = 23 p = 140, s= 27, m = 7, n = 20 p = 148, s= 41, m = 4, n = 37 p = 150, s= 35, m = 5, n = 30 p = 152, s= 27, m = 8, n = 19 p = 154, s= 29, m = 7, n = 22 p = 160, s= 37, m = 5, n = 32 p = 162, s= 27, m = 9, n = 18 p = 168, s= 29, m = 8, n = 21 p = 170, s= 27, m = 10, n = 17 p = 172, s= 47, m = 4, n = 43 p = 174, s= 35, m = 6, n = 29 p = 176, s= 27, m = 11, n = 16 p = 182, s= 27, m = 13, n = 14 p = 186, s= 37, m = 6, n = 31 p = 190, s= 29, m = 10, n = 19 p = 196, s= 35, m = 7, n = 28 p = 198, s= 29, m = 11, n = 18 p = 204, s= 29, m = 12, n = 17 p = 208, s= 29, m = 13, n = 16 p = 216, s= 35, m = 8, n = 27 p = 232, s= 37, m = 8, n = 29 p = 234, s= 35, m = 9, n = 26 p = 238, s= 41, m = 7, n = 34 p = 246, s= 47, m = 6, n = 41 p = 250, s= 35, m = 10, n = 25 p = 252, s= 37, m = 9, n = 28 p = 270, s= 37, m = 10, n = 27 p = 276, s= 35, m = 12, n = 23 p = 280, s= 47, m = 7, n = 40 p = 288, s= 41, m = 9, n = 32 p = 294, s= 35, m = 14, n = 21 p = 304, s= 35, m = 16, n = 19 p = 306, s= 35, m = 17, n = 18 p = 310, s= 41, m = 10, n = 31 p = 322, s= 37, m = 14, n = 23 p = 336, s= 37, m = 16, n = 21 p = 340, s= 37, m = 17, n = 20 p = 348, s= 41, m = 12, n = 29 p = 364, s= 41, m = 13, n = 28 p = 370, s= 47, m = 10, n = 37 p = 378, s= 41, m = 14, n = 27 p = 390, s= 41, m = 15, n = 26 p = 396, s= 47, m = 11, n = 36 p = 400, s= 41, m = 16, n = 25 p = 408, s= 41, m = 17, n = 24 p = 414, s= 41, m = 18, n = 23 p = 418, s= 41, m = 19, n = 22 p = 442, s= 47, m = 13, n = 34 p = 462, s= 47, m = 14, n = 33 p = 480, s= 47, m = 15, n = 32 p = 496, s= 47, m = 16, n = 31 p = 510, s= 47, m = 17, n = 30 p = 522, s= 47, m = 18, n = 29 p = 532, s= 47, m = 19, n = 28 p = 540, s= 47, m = 20, n = 27 p = 546, s= 47, m = 21, n = 26 p = 550, s= 47, m = 22, n = 25 p = 552, s= 47, m = 23, n = 24 p = 9604, s= 196, m = 98, n = 98 最后P说出自己已经知道m,n以后，S也说自己知道了m,n，这说明S根据自己手中的两数之 和可以推断出唯一的m,n来。 因此还要去除上面的情况中重复用到s的情况，得到下面的情况： p = 52, s = 17, m = 4, n = 13 p = 9604, s = 196, m = 98, n = 98 如果规定了m<>n，则最后的解答就是 m=4 , n=13 下面是程序： #include <iostream.h> #include <fstream.h> #include <string.h> const int MAX_N = 99; const char* OUTPUT_FILE = "result.txt"; int s[MAX_N*2]; int p[MAX_N*MAX_N]; int prim[MAX_N]; int primCounter =0; ofstream fout( OUTPUT_FILE ); // 计算素数 void calPrim() { bool used[MAX_N]; int i, p=2; bool found = true; prim[primCounter++] = 2; memset( used, false, sizeof( used ) ); while( found ) { for( i = p; i < MAX_N; i++ ) if( i % p == 0 ) used[i] = true; found = false; for( i = p; i < MAX_N; i++ ) if( ! used[i] ) { p = i; prim[primCounter++] = p; found = true; break; } } } // 根据条件1过滤 void useCon_1() { int i,j; memset(s, 0, sizeof(s)); for( i = 0; i < 4; i++ ) s[i] =-1; calPrim(); // S可以肯定P不知道这两个数是什么 for( i = 0; i < primCounter; i++ ) for( j = i; j < primCounter; j++ ) { if( prim[i] + prim[j] < MAX_N * 2 ) s[ prim[i] + prim[j] ] = -1; } for( i = 0; i < primCounter; i++ ) if( prim[i] > MAX_N / 2 ) break; for( i--; i < primCounter; i++ ) for( j = 2; j < MAX_N; j++ ) s[ prim[i] + j ] = -1; // 因为S自己也不知道这两个数是什么 for( i = 98 + 99; i < MAX_N + MAX_N; i++ ) s[i] = -1; fout << "满足S第一句话的两数之和" << endl; for( i = 0; i < MAX_N * 2; i++ ) if( s[i] == 0 ) fout << i << endl; } // 根据条件2过滤 void useCon_2() { int i, m, n; memset( p, 0, sizeof( p ) ); for( m = 2; m < MAX_N; m++ ) for( n = 2; n < MAX_N; n++ ) { if( s[m+n] >= 0 ) { p[m*n]++; } } fout << "满足P第一句话的两数之积:" << endl; for( i = 0; i < MAX_N * MAX_N; i++ ) if( p[i] == 1 || p[i] == 2 ) { for( m = 2; m < MAX_N; m++ ) for( n = m; n < MAX_N; n++ ) if( m * n == i && s[m + n] >= 0 ) { fout << "p = " << i << ", s= " << m + n << ", m = " << m << ", n = " << n << endl; s[m+n]++; } } } void useCon_3() { int i, m, n; fout << "满足S第二句话的结果:" << endl; for( i = 0; i < MAX_N * MAX_N; i++ ) if( p[i] == 1 || p[i] == 2 ) { for( m = 2; m < MAX_N; m++ ) for( n = m; n < MAX_N; n++ ) if( m * n == i && s[m + n] == 1 ) { fout << "p = " << i << ", s = " << m + n << ", m = " << m << ", n = " << n << endl; } } } void main() { useCon_1(); useCon_2(); useCon_3(); } 对该文的评论 starfish (2002-3-21 11:11:02) 设有两个自然数m,n，2〈=m<=99。 S先生知道这两数的和s，P先生知道这两数的积p。他 们两人进行了如下的对话： S：我知道你不知道这两个数是什么，但我也不知道。 P：现在我知道这两个数了。 S：现在我也知道这两个数了。 由这些条件，试确定m，n。 因为S知道两数之和，却由此推断P不知道两个数，所以说两数之和s一定不能拆分成两个 素数的和，即m,n不可能都是素数，且m,n中不会有大于50的素数，否则的话m*n可以唯一 分解，P知道了m,n的积就一定可以知道m,n了。 P从S的言语中能够判断出的信息是： 1。m,n不会全是素数； 2。m,n中不会有大于50的素数； 3。m,n之和不能拆成两个素数的和； 4。因为S自己也不知道这两个数是什么，所以这两个数的和一定小于99+98，否则S就可 以知道这两个数是什么了。 满足以上条件的 s=m+n有以下的可能： 11 17 23 27 29 35 37 41 47 196 然后P根据自己掌握的p=m*n立即算出m,n，这说明p=m*n是具有以下性质的特殊数字： 根据这个特殊的p,当s取上面的那些值的时候，只有一种s的取值使得方程 m+n=s, m*n=p 在[2,99]内有唯一的整数解。 根据这个性质计算出的p有以下的情况（不妨设m<=n）： p = 18, s= 11, m = 2, n = 9 p = 24, s= 11, m = 3, n = 8 p = 28, s= 11, m = 4, n = 7 p = 50, s= 27, m = 2, n = 25 p = 52, s= 17, m = 4, n = 13 p = 54, s= 29, m = 2, n = 27 p = 76, s= 23, m = 4, n = 19 p = 92, s= 27, m = 4, n = 23 p = 96, s= 35, m = 3, n = 32 p = 100, s= 29, m = 4, n = 25 p = 110, s= 27, m = 5, n = 22 p = 112, s= 23, m = 7, n = 16 p = 114, s= 41, m = 3, n = 38 p = 124, s= 35, m = 4, n = 31 p = 130, s= 23, m = 10, n = 13 p = 138, s= 29, m = 6, n = 23 p = 140, s= 27, m = 7, n = 20 p = 148, s= 41, m