华为软件工程笔试
写一个程序, 要求功能:求出用1,2,5这三个数不同个数组合的和为100的组合个数。如:100个1是一个组合,5个1加19个5是一个组合。。。。 请用C++语言写。
答案:最容易想到的算法是:设x是1的个数,y是2的个数,z是5的个数,number是组合数注意到0=x=100,0=y=50,0=z=20,所以可以编程为:number=0;for (x=0; x=100; x++)for (y=0; y=50; y++)for (z=0; z=20; z++)if ((x+2*y+5*z)==100)number++;coutnumberendl;上面这个程序一共要循环100*50*20次,效率实在是太低了事实上,这个题目是一道明显的数学问题,而不是单纯的编程问题。
我的.解法如下:因为x+2y+5z=100所以x+2y=100-5z,且z=20 x=100 y=50所以(x+2y)=100,且(x+5z)是偶数对z作循环,求x的可能值如下:z=0, x=100, 98, 96, ... 0z=1, x=95, 93, ..., 1z=2, x=90, 88, ..., 0z=3, x=85, 83, ..., 1z=4, x=80, 78, ..., 0......z=19, x=5, 3, 1z=20, x=0因此,组合总数为100以内的偶数+95以内的奇数+90以内的偶数+...+5以内的奇数+1,
即为:(51+48)+(46+43)+(41+38)+(36+33)+(31+28)+(26+23)+(21+18)+(16+13)+(11+8)+(6+3)+1某个偶数m以内的偶数个数(包括0)可以表示为m/2+1=(m+2)/2某个奇数m以内的奇数个数也可以表示为(m+2)/2
所以,求总的组合次数可以编程为:number=0;for (int m=0;m=100;m+=5){number+=(m+2)/2;}coutnumberendl;
这个程序,只需要循环21次, 两个变量,就可以得到答案,比上面的那个程序高效了许多倍----只是因为作了一些简单的数学分析这再一次证明了:计算机程序=数据结构+算法,而且算法是程序的灵魂,对任何工程问题,当用软件来实现时,必须选取满足当前的资源限制,用户需求限制,开发时间限制等种种限制条件下的最优算法。而绝不能一拿到手,就立刻用最容易想到的算法编出一个程序了事
-
阿里巴巴二面受打击
阿里巴巴二面受打击距离第一次找工作(09年2月份)已一年多了,少了份稚气、多了份成熟;少了份急切、多了份沉稳;也多了份点点社会经历,但也褪去了学生时代的天真无邪。还记得一月份接待外教老师和她女朋友时,与他女朋友是2年没有见面,她说我更成熟了,我嘴角微笑下没有再说...
-
大连求职生活指南:公交常识
大连的公共交通非常发达,市内有公交线路百余条,其中有全国仅存的有轨电车线路3条。大公交首班车时间为4:00—4:30,末班车时间为22:00-23:50,平时行车间隔3-8分钟,高峰期1-2分钟就有一趟车。按营运方式分,1-99路为公共汽车,1字头为无轨电车,2字头为有轨电车,4字头为...
-
女性面试求职时如何回答敏感问题?
女性在求职面试时,常会碰到一些敏感的问题,总觉得如何回答都不妥,很难让自己和别人都满意。那么,常问的问题有哪些?究竟该如何应对这些让人感到尴尬的问题?女性在求职面试时,常会碰到一些敏感的问题,总觉得如何回答都不妥,很难让自己和别人都满意。那么,常问的问题有哪些...
-
新形势下人力资源培训体系的创新与实施
经济危机下的公司管理要关注以下三个重要问题:第一是要专注公司的战略愿景不动摇。困难时期是企业自我提高甚至快速发展的最好时机,最重要的就是要保持前后目标的一致性----我们要始终做到临危不乱。第二是要调整你公司的经营管理而不是试图调整宏观经济发展的全...