面试中你不可回避的C、C++的问题(四)

            在IT企业面试中往往会让你手写一段代码,然后讨论,其实一般的代码都不是很难,但是技巧性较强,所以很多同学心中有点犯怵,其实大可不必,在准备面试前自己多写写基本思维的代码,对面试还是有好处的。自己也要找工作,所以将一些比较重要的问题,拿出来更大家一起晒晒,共同进步!

问题一:基本的阶乘-递归问题

基本模式:

#include <stdio.h>

int Factorial(int n)
{
    if(1==n)
        return 1;
    else
        return Factorial(n-1)*n;
    return 0;
}

int main()
{
    int num = Factorial(10);
    printf("%d\n",num);
    return 0;
}
但是往往,阶乘都比较大,所以建议使用这样的方式,这样面试官会知道你是基本还是了解一点程序可能出现的错误,所以不妨将int换成long,这样表示的范围比较大,但是对于大的阶乘貌似就不太好了!

#include <stdio.h>

long Factorial(long n)
{
    if(1==n)
        return 1;
    else
        return Factorial(n-1)*n;
    return 0;
}

int main()
{
    long num = Factorial(10);
    printf("%ld\n",num);
    return 0;
}
其实同学们也可以使用非递归的形式解决这个问题,但是也会有同样的问题,就是会很容易的超出int表示的范围

long Factorial_NR(long n)
{
    long sum = 1;
    while(n>0)
        sum *= n--;
    return sum;
}
其实,这些算法就是最基本的算法,在后续的文章中,我会写一写关于大数的一些基本操作,那个才是在实际工程中需要的真正算法!

问题二:多重循环简化问题

         编程实现,一个射击运动员连开十枪最后恰好打中九十环的可能性?

解答:

        其实,这个问题可以使用多重循环解决问题, 但是如果你这样给面试官写出这个问题的时候,估计你也离这个公司渐行渐远了。我们要好好分析,情况成立的可能条件,和不可能条件,使用剪枝算法可以将一些无用的运算直接删除。

        每一枪可以打0-10换,共11种可能:

        1.当你的现在得分在很少,即使后面每一环都打10环也不可能得到90环,所以这种情况下就直接退出;

        2.如果满足条件且打到最后一次;

        3.让每次都尝试的打中每种可能,这样就可以遍历所有的可能;

看源代码如下:

#include <iostream>

using namespace std;

int sum=0,store[10];

void OutPut()
{
    for(int i=9;i>=0;i--)
        cout << store[i] << " ";
    cout << endl;
    sum++;
}

void Comput(int score,int num)
{
    if(score < 0 || score > (num+1)*10)
        return ;
    if(0==num)
    {
        store[num] = score;
        //OutPut();
        sum++;
        return ;
    }

    for(int i=0;i<11;i++)
    {
        store[num]=i;
        Comput(score-i,num-1);
    }
}

int main()
{
    Comput(90,9);
    cout << "Total Number is: " << sum << endl;
    return 0;
}
       将输出信息全部屏蔽掉,这样可以让执行速度提高很多!

面试中你不可回避的C、C++的问题(四),布布扣,bubuko.com

面试中你不可回避的C、C++的问题(四)

上一篇:[C++] Boost智能指针——boost::shared_ptr(使用及原理分析)


下一篇:python使用锁访问共享变量