面接で避けられないC、C++の質問(四)

IT企業の面接では、コードを手書きで書いて議論することがよくありますが、一般的なコードは難しくありませんが、テクニックが強いので、多くの学生の心の中で少し恐れています.自分も仕事を探さなければならないので、いくつかの重要な問題を出して、もっとみんなで日焼けして、一緒に進歩します!
問題1:基本的な階乗-再帰問題
基本モード:

#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
",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
",num);
    return 0;
}

実は学生たちも非再帰的な形式でこの問題を解決することができますが、同じ問題があります.int表現の範囲を超えやすいということです.

long Factorial_NR(long n)
{
    long sum = 1;
    while(n>0)
        sum *= n--;
    return sum;
}

実は、これらのアルゴリズムは最も基本的なアルゴリズムで、後続の文章の中で、私は大数のいくつかの基本的な操作について書くことができて、それこそ実際の工事の中で必要とする本当のアルゴリズムです!
問題2:多重サイクル簡略化問題
プログラミングは実現して、1人の射撃選手が10発連続して最後にちょうど90環に当たった可能性がありますか?
回答:
実は、この問題は多重ループで問題を解決することができますが、このように面接官にこの問題を書くと、あなたもこの会社から遠ざかると思います.状況が成立する可能性条件と不可能条件をよく分析し,剪断アルゴリズムを用いて不要な演算を直接削除することができる.
1発あたり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;
}

出力情報をすべて遮断することで、実行速度を大幅に向上させることができます.