之前去面试了一间梦想已久的外商也碰到类似的变形考题
现在碰巧翻到这古文
考题如下:
1. 给定一 1~N 的正整数数字序列
2. 给定三个正整数 A, B, C 其中 A>B>C>0
3. 序列中能被A整除则显示Adorable
4. 序列中能被B以及C整除则显示CUTE
5. 序列中能被A,B,C同时整除显示AdorableCUTE
6. 其余显示原本数字
* 效率越高越佳
我给的方式如下:
UINT n1,n2,n3;
UINT n1x,n2x,n3x;
.....
n1 = n2 = n3 = 0;
n1x = A; n2x = B; n3x = C;
for i=1; i<=n; ++i,already=0
if i-n1 == n1x
print "Adoriable"
already = 1; n1 = i;
if i-n2 == n2x and i-n3 == n3x
print "CUTE"
already = 1;
if i-n2 == n2x
n2 = i;
if i-n3 == n3x
n3 = i;
if !already
print i
跟面试官讲解了我的逻辑概念后，面试官觉得我的逻辑正确。
但被要求给出数学证明就被考倒了(原谅我没办法用数学表示我的想法)。
幸好最后还是offer get.
※ 引述《Domos (没事发发废文)》之铭言：
: 看了andrei alexandrescu的Three Optimization Tips for C++
: 了解到这题的意思
: % (模数运算) 是很贵的
: 如何不用模数运算解掉这题?
: pattern就是每15一个循环
: 必定为 1 2 F 4 B F 7 8 F FB
: 写个loop照上面输出，一次处理15个数字
: 把尾数处理的漂亮就行了
: 另外resize是很贵的
: 回传的vector<string>可以先reserve起来
: string本身因为不长，所以不会有malloc的动作
: to_string的效率不佳
: 追求最佳化可使用andrei提供的算法
: 大guy4酱