《转微软的面试试题》word版.doc

转 微软的面试试题日志24)&0xff；return this.FONTMAP.substring(2*(id-1),2*id)；color=#000000 size=4微软的面试试题各位看看这个微软的面试试题的c语言算法对吗?楼主fgq 841103(冯志宏)2006-05-05 06：57：21在C/C+/C语言提问这是csdn的一个帖子：求第1500个只有2,3,5因子的数数是从小到大排列第一个数是1,1=20*30*50要求用C实现,至少要讲清楚算法思路-第1500个数大约要六分钟,确实不行！还不知结果正不正确！859963392！-long result1500；int p2,p3,p5；int i；result0=1；p2=p3=p5=0；for(i=1；i 1500；i+)int min=resultp2*2；int choice=2；if(min resultp3*3)min=resultp3*3；choice=3；if(min resultp5*5)min=resultp5*5；choice=5；result=min；switch(choice)case 2：p2+；break；case 3：p3+；break；case 5：p5+；break；printf(%d,result1500-1)；-mathe的方法确实不错，偶原来也想这样去做，偶还有一个想法，用数学的方法可以笔算出结果，但有点小问题。设s=2x*3y*5z两边取对数有：log(s)=x+K1*y+K2*z K1=log(3),K2=log(5).(以2为底)对s的排序和对log(s)是一样的，设t=log(s)则t=x+K1*y+K2*z问题去求t的第n个数是多少。设L，使得x+K1*y+K2*z=L x=0 y=0 z=0 x,y,z为整数上面规划的整点数就是问题的解。方程x+K1*y+K2*z=L就是三维立体中四面体中的整点数，求一个物体的整点数是有一个公式，不好意思偶忘了这个公式，不知mathe可知否?即使不知四面体的整点数的公式，四面体的整点数和它的体积是很接近的，四面体的体积为1/6*x0*y0*z0=1/6*x03*K1*K2=L可以解得x0，y0，z0，从x0，y0，z0开始来计算第n个点的位置，我想复杂度大概可以低于O(log(n)-我用c+和stl写了个，结果是859963392#include iostream.h#include vector.h#include algorith.h using namespace std；int main()vector unsigned long a2,a3,a5；int t=1,n=1500,i；for(i=1；i 1500；i+)/cout t；a2.push_back(t*2)；a3.push_back(t*3)；a5.push_back(t*5)；/cout a20a30a50endl；if(a20=a30&a20=a50)t=a20；else if(a30=a20&a30=a50)t=a30；else if(a50=a30&a50=a20)t=a50；if(a20=t)a2.erase(a2.begin()；if(a30=t)a3.erase(a3.begin()；if(a50=t)a5.erase(a5.begin()；cout tendl；return 0；我的知识不足，看不明白，但我觉1499个2相乘不就是第1500个吗?还有，这个问题还要解决数据的处理问题，哪种数据类型能存储这么大的数据?问题点数：20、回复次数：212Top回复于2006-05-05 08：21：33得分11499个2相乘不就是第1500个吗?=这个应该不对.哪种数据类型能存储这么大的数据=有必要的话，可以使用巨型数据类型，这个是自己写的一个大数处理函数(或类).Top 2楼cctvnight(异度使者)回复于2006-05-05 08：42：13得分1第一个1第二个2第三个3第四个4第五个5第六个6第七个8第八个9第九个10第九个并不是8个2相乘所以第1500个也就不是1499个2相乘Top 3楼yuanchuang(元创)回复于2006-05-05 08：43：06得分11499个2相乘不就是第1500个吗?-这个肯定不对。哪种数据类型能存储这么大的数据-这个确实比较麻烦Top 4楼niatclock(豆豆雅)回复于2006-05-05 09：48：33得分1MARKTop 5楼tigermoon()回复于2006-05-05 10：08：01得分1呵呵，上面的都不错，但是我认为可以按如下思路编程s=2x*3y*5z我们知道2，3，4(2的平方)，5，所以从第一个数开始他们的大小的循环应该是s*2,s*3,s*4,s*5,所以我们要的第1500个数字是s=2375*3375*4375*5374也就是s=21125*3375*5374我觉得这样应该可以，只是早上起床准备洗脸的时候，想到的，也许不成熟。敬请指正Top 6楼elvai_wind()回复于2006-05-05 11：35：10得分1楼主的理解是不是搞错了，你这道题的计算结果根本不对以下是我对这道题的解法：#include stdio.h#define M1500 void main()long count=1,x=0,y=0,z=0；printf(%5ld：%ldn,count,1.0)；while(count M)while(x+2=y+3&x+2=z+5&count M)x=x+2；if(x！=z&x！=y)count+；printf(%5ld：%ldn,count,x)；while(y+3=z+5&！(x+2 y+3)&count M)y=y+3；if(y！=x&y！=z)count+；printf(%5ld：%ldn,count,y)；if(x+2 z+5&y+3 z+5&count M)z=z+5；if(z！=x&z！=y)count+；printf(%5ld：%ldn,count,z)；printf(time over！n)；/*计算结束，耗时1秒都不到！*/getch()；计算的结果是求第1500个只有2,3,5因子的数：2044 Top 7楼elvai_wind()回复于2006-05-05 11：37：25得分1修正一下！把此行(程序中第6行)：printf(%5ld：%ldn,count,1.0)；改为printf(%5ld：%ldn,count,1)；刚才没看清楚，有个小问题Top 8楼liuguangliang(小刀刘)回复于2006-05-05 15：07：50得分1回复人：elvai_wind()(一级(初级)计算的结果是求第1500个只有2,3,5因子的数：2044 2044=2*2*511；你的不对。Top 9楼Ninstein(www.Ninstein.Com)回复于2006-05-05 16：00：55得分1假设某一符合要求的数为A则A总是满足以下条件：A=2x*3y*5z xy z为非负整数而且我们要的第1500个A是从小到大排列得到的也就是说这里的x yz是有规律的：x增1带来的代价是值A扩大为2倍y增1带来的代价是值A扩大为3倍z增1带来的代价是值A扩大为5倍明显，我们得依次按照x-y-z的顺序来增加才能满足题目的A是从小到大排列这里应该是一个突破口Top 10楼elvai_wind()回复于2006-05-05 19：48：08得分1不好意思！(本题最新解法！)上午没看清楚题目，不好意思，搞错了意思，好了，我重新做了一下，可以求出非常大数目的程序，也是只需要1秒多就算出来了，思想与先的差不多，不过有些不同，希望楼主自己看看，如果需要说明，我可以给予说明。程序代码：#include stdio.h void main()double a1500=1.0；int x3=0；int y3=2,3,5；int count=1；printf(%d count,result：%lfn,count,acount-1)；while(count 1500)register int min；if(ax01.5*ax1)if(ax02.5*ax2)min=0；else min=2；else if(3*ax15*ax2)min=1；else min=2；if(ymin*axminacount-1)acount=ymin*axmin；count+；printf(%d count,result：%lfn,count,acount-1)；xmin+；printf(*n)；printf(%d count,result：%lfn,count,acount-1)；getch()；Top 11楼elvai_wind()回复于2006-05-05 20：15：33得分1不好意思！(本题最新解法！)上午没看清楚题目，不好意思，搞错了意思，好了，我重新做了一下，可以求出非常大数目的程序，也是只需要1秒多就算出来了，思想与先的差不多，不过有些不同，希望楼主自己看看，如果需要说明，我可以给予说明。程序代码：#include stdio.h void main()double a1500=1.0；int x3=0；int y3=2,3,5；int count=1；printf(%d count,result：%lfn,count,acount-1)；while(count 1500)register int min；if(ax01.5*ax1)if(ax02.5*ax2)min=0；else min=2；else if(3*ax15*ax2)min=1；else min=2；if(ymin*axminacount-1)acount=ymin*axmin；count+；printf(%d count,result：%lfn,count,acount-1)；xmin+；printf(*n)；printf(%d count,result：%lfn,count,acount-1)；getch()；Top 12楼ForestDB(冰)回复于2006-05-06 03：32：49得分1偶的，嘻嘻161 859963392 Press any key to continue 161秒左右吧(做了好几次)859963392对不对啊。这是偶的程序：#include stdio.h#include time.h long d235(long i)while(i%2=0)i/=2；while(i%3=0)i/=3；while(i%5=0)i/=5；return i；int main()long i=2；int index=2；time_t start,end；time(&start)；while(index=1500)if(d235(i)=1)index+；i+；elsei+；time(&end)；printf(%dn,end-start)；printf(%dn,i-1)；还请大家指正。Top 13楼ForestDB(冰)回复于2006-05-06 03：48：21得分1本来还想优化下，如下#include stdio.h#include time.h#define INVALID-1 long d235(long i)if(i%7=0)return INVALID；if(i%11=0)return INVALID；while(i%2=0)i/=2；while(i%3=0)i/=3；while(i%5=0)i/=5；return i；int main()long i=2；int index=2；time_t start,end；time(&start)；while(index=1500)if(d235(i)=1)index+；i+；elsei+；time(&end)；printf(%dn,end-start)；printf(%dn,i-1)；结果加上if(i%7=0)return INVALID；174 859963392 Press any key to continue再加上if(i%11=0)return INVALID；200 859963392 Press any key to continue结果越来越大啦，想想也是，虽然每隔7或11或.排除了一些树，但给其他更多的数多加了几条指令，当然变大啦。偶想偶的程序就是思路很简单吧，(嘻嘻，自觉得是个优点)前面有个兄弟提出log什么的，偶觉得思路不错，可惜偶数学没学好啊，不能先将问题从数学角度提出解答，只能让计算机死算了。呵呵。等待数学好的人给出更好更简单的解答(最好看了程序就能明白的，看了些解答，都没太懂思路。)Top 14楼elvai_wind()回复于2006-05-06 09：02：16得分1楼上的兄弟，你的程序100多秒还叫好吗?我的程序1秒，甚至好的机子，一秒都用不了，是最快的程序了，用这种思想还可以改编，由用户自行输入任意个不同的数作为其要求的因子都可以，我的程序才是最优化的，不信，自己拿回去试试。Top 15楼lbaby(春天来了.)回复于2006-05-06 13：50：39得分1 Ninstein(LO几又VE www.Ninstein.Com)()信誉：100 2006-5-5 16：00：56得分：0假设某一符合要求的数为A则A总是满足以下条件：A=2x*3y*5z xy z为非负整数而且我们要的第1500个A是从小到大排列得到的也就是说这里的x yz是有规律的：x增1带来的代价是值A扩大为2倍y增1带来的代价是值A扩大为3倍z增1带来的代价是值A扩大为5倍明显，我们得依次按照x-y-z的顺序来增加才能满足题目的A是从小到大排列这里应该是一个突破口补充一下，x每增加2会比y增加1大，y每增加2会比z增加的数量多，其实是求当x+y+z=1500-3时如何取值才能满足下边的条件：2x与3y和5z的乘积最大(2x与3y和5z三者之间的相互差的距离最小)又知：22 31 23 32取它们的对数值(lg3,lg5,2为底)，可以得出一个x yz之间的关系，从而可以得出这三个数的大致的下界和上界，要找的x yz就在它们之间Top 16楼lbaby(春天来了.)回复于2006-05-06 14：01：03得分1呵呵，又想了一下，下边的数字是错误的：x+y+z=1500-3时如何取值才能满足下边的条件：1500-3可以直接拿1500算的，呵呵，连我自己也不知所云，回家陪老婆逛超市去.Top 17楼panyong0202(永)回复于2006-05-06 15：17：25得分1#include iostream#include string using namespace std；int main()clock_t start_clock_pany,finish_clock_pany；double totaltime_clock_pany；start_clock_pany=clock()；int curr_2,curr_3,curr_5；int res1500；res0=1；curr_2=curr_3=curr_5=0；int i；for(i=1；i 1500；+i)if(rescurr_2*2=rescurr_3*3)&(rescurr_2*2=rescurr_5*5)if(rescurr_2*2=res)+curr_2；-i；continue；res=rescurr_2*2；+curr_2；else if(rescurr_3*3=rescurr_2*2)&(rescurr_3*3=rescurr_5*5)if(rescurr_3*3=res)+curr_3；-i；continue；res=rescurr_3*3；+curr_3；elseif(rescurr_5*5=res)+curr_5；-i；continue；res=rescurr_5*5；+curr_5；cout res1499endl；finish_clock_pany=clock()；totaltime_clock_pany=(double)(finish_clock_pany-start_clock_pany)/CLOCKS_PER_SEC；coutn此程序的运行时间为totaltime_clock_pany秒！endl；return 0；答案是859963392，用时：0.016sTop 18楼yanglight(东丈)回复于2006-05-06 20：57：13得分1请问楼上兄弟所写算法的原理，惭愧，本人未能看懂。望指点！Top 19楼billmo1986(潘安+宋玉)回复于2006-05-06 22：11：13得分1mark好好学习Top 20楼danshuihepan(淡水河畔)回复于2006-05-06 23：19：17得分1不知是不是我没有理解题目的意思，我觉得很简单的！设表带式5x*3y*2z,(初始条件x=y=z=0)稍微分析一下就知道，x,y,z全为0最小，为1；x,y,z全为1时是30，在1到30之间，就是2，3，5的公倍数：2，3，4，5，6，8，9，10，12，15，18，20，24，25，27不包括30就是16个也就是说x,y,z从(a,a,a)变为(a+1,a+1,a+1)时，中间有16个数。那么1500=1693+12也就是说：此时(x,y,z)在(93，93，93)的基础上分析。最终结果为(93，95，94)即593+395+294将以上分析变成程序即可！Top 21楼yuxh(yuxh)回复于2006-05-07 10：44：22得分0#include math.h int get_val(int i,int j,int k)int x；int val=1；for(x=0；x i；x+)val*=2；for(x=0；x j；x+)val*=3；for(x=0；x k；x+)val*=5；return val；void qsort(int*ary,int p,int r)int i,j；int x,t；if(p r)x=ary；i=p；j=r+1；while(ary-jx)；while(i j)t=ary；ary=aryj；aryj=t；while(ary+ix)；while(ary-jx)；qsort(ary,p,j)；qsort(ary,j+1,r)；int main()double max=2147483647.0；int i,j,k,idx=0；int result2000；for(i=0；i=log(max)/log(2)；i+)for(j=0；j=log(max/pow(2,i)/log(3)；j+)for(k=0；k=log(max/pow(2,i)/pow(3,j)/log(5)；k+)resultidx+=get_val(i,j,k)；qsort(result,0,idx-1)；printf(%dn,result1499)；Top 22楼wolfkain()回复于2006-05-07 11：12：00得分0本人在很多地方发过算法，自认为没更好的算法思想，23楼hawk_jane()回复于2006-05-07 11：20：00得分0楼上分析错误从(a,a,a)-(a+1,a+1,a+1)中间的满足要求的数不是常数Top 24楼hawk_jane()回复于2006-05-07 11：22：00得分0我说的是danshuihepan(淡水河畔)的分析阿Top 25楼wolfkain()回复于2006-05-07 11：25：30得分0楼上有一兄弟说说你怎么证明x,y,z从(a,a,a)变为(a+1,a+1,a+1)时，中间有16个数。27-900之间只有16个数?Top 26楼wolfkain()回复于2006-05-07 11：28：32得分0 1-2-3-4-5-6-8-9-10-12-15-16-18-20-24-25-27-30-32-36-40-45-48-50-54-60-64-72-75-80-81-90-96-100-108-120-125-128-135-144-150-160-162-180-192-200-216-225-240-243-250-256-270-288-300-320-324-360-375-384-4 00-405-432-450-480-486-500-512-540-576-600-625-640-648-675-720-729-750-768-800-810-864-900-960-972-1000-1024-1080-1125-1152-1200-1215-1250-1280-1296-1350-1440-1458-1500-1536-Press any key to continueTop 27楼wolfkain()回复于2006-05-07 11：36：24得分0提示：求仅由因子2和3构成的数的一个数集.我们可以认为开始数集中只有2,3；然后用2依次去乘每个数,和3*3比较,小于则插入,大于则先插入3*3,然后插入,再接着用2乘,和3*3*3比较,以后同理,即可得到仅由因子2和3构成的数的有序序列,这样就减小了时间复杂度！Top 28楼cyblueboy83(爱情白痴-电脑迷)回复于2006-05-07 13：46：22得分0帮顶Top 29楼GoodNight2005(GoonNight)回复于2006-05-07 15：37：09得分0帮顶Top 30楼danshuihepan(淡水河畔)回复于2006-05-07 15：46：23得分0证明(a,a,a)-(a+1,a+1,a+1)之间只有16个数：设(a,a,a)对应的数值5a*3a*2a为k很显然，由于存在2 32*2 52*3 2*2*2 3*3 2*5 3*2*2 3*5 2*3*3 2*2*5 3*2*2*2 5*5 3*3*3 2*3*5即在满足条件的数值中，k-30k之间只有这16个值！因而如果编号从0开始，那么1500-1=1693+11也就是3093*21*32*50=3093*18Top 31楼yanglight(东丈)回复于2006-05-07 16：10：04得分0楼上很强，但证明不严密。你只能证明k-30k有16个值而不是只有16个值Top 32楼yanglight(东丈)回复于2006-05-07 16：27：23得分0 panyong0202(永)()信誉：100 2006-5-6 15：17：25得分：0#include iostream#include string using namespace std；int main()clock_t start_clock_pany,finish_clock_pany；double totaltime_clock_pany；start_clock_pany=clock()；int curr_2,curr_3,curr_5；int res1500；res0=1；curr_2=curr_3=curr_5=0；int i；for(i=1；i 1500；+i)if(rescurr_2*2=rescurr_3*3)&(rescurr_2*2=rescurr_5*5)if(rescurr_2*2=res)+curr_2；-i；continue；res=rescurr_2*2；+curr_2；else if(rescurr_3*3=rescurr_2*2)&(rescurr_3*3=rescurr_5*5)if(rescurr_3*3=res)+curr_3；-i；continue；res=rescurr_3*3；+curr_3；elseif(rescurr_5*5=res)+curr_5；-i；continue；res=rescurr_5*5；+curr_5；cout res1499endl；finish_clock_pany=clock()；totaltime_clock_pany=(double)(finish_clock_pany-start_clock_pany)/CLOCKS_PER_SEC；coutn此程序的运行时间为totaltime_clock_pany秒！endl；return 0；答案是859963392，用时：0.016s望此程序作者指教，殷切期盼中。Top 33楼Michaelgs(Michaelgs)回复于2006-05-07 22：59：45得分0一时兴起Answer=859963392 Total：0.000000 seconds/csdn forum c/c+/by Michael 2006-5-7/求第1500个只有2,3,5因子的数,数是从小到大排列,第一个数是1,1=20*30*50#include stdio.h#include stdlib.h#include time.h long number1600；char accFlag=0；long*pf2=0；long*pf3=0；long*pf5=0；int main()int n；long max；long next2,next3,next5；double t1,t2；t1=clock()；number1=1；pf2=pf3=pf5=number+1；next2=2；next3=3；next5=5；for(n=2；n=1500；+n)max=next2；accFlag=1；if(next3 max)max=next3；accFlag=2；else if(next3=max)accFlag|=2；if(next5 max)max=next5；accFlag=4；else if(next5=max)accFlag|=4；numbern=max；if(accFlag&1)+pf2；next2=*pf2*2；if(accFlag&2)+pf3；next3=*pf3*3；if(accFlag&4)+pf5；next5=*pf5*5；t2=clock()；printf(Answer=%ldn,number1500)；printf(Total：%f secondsn,(t2-t1)/CLK_TCK)；return 0；Top 34楼yanglight(东丈)回复于2006-05-08 10：01：30得分0楼上强人，谢谢你的程序！Top 35楼templarzq(原谅我这一生不羁放纵爱自由，也会怕有一天会跌倒)回复于2006-05-08 10：12：05得分0实际是指数增加顺序的问题。指数增加顺序是(2+)，/*从这里开始循环*/(2-，3+)，(3-，2+，2+)，(2-，2-，5+)，(5-，2+，2+)，/跳至(2-,3+)处循环，计算运算步骤即可Top 36楼templarzq(原谅我这一生不羁放纵爱自由，也会怕有一天会跌倒)回复于2006-05-08 10：13：55得分0说明一下，2+是指2的指数加1，2-是指2的指数减1，设置3个变量代表2，3，5的指数，算出第1500个数的2、3、5的指数就ok了Top 37楼yanglight(东丈)回复于2006-05-08 10：35：03得分0