【#程序員考試# #2018年程序員考試面試題精選題#】®無憂考網特別整(zheng)理(li)發布2018年程序員(yuan)考(kao)試(shi)面試(shi)題(ti)精選題(ti)，供考(kao)生參(can)考(kao)及學習(xi)，希望對大家備(bei)考(kao)有所幫助。
-求1+2+...+n
題目(mu)：求(qiu)1+2+…+n，要求(qiu)不能使(shi)用乘除(chu)法、for、while、if、else、switch、case等(deng)關鍵字以(yi)及條件判斷語句(A?B:C)。
分(fen)析(xi)：這(zhe)道(dao)題沒有(you)(you)多少實(shi)際意(yi)義，因為在(zai)軟(ruan)件(jian)開發(fa)中不(bu)會有(you)(you)這(zhe)么(me)變態的(de)限(xian)制。但(dan)這(zhe)道(dao)題卻能有(you)(you)效地(di)考查發(fa)散(san)思(si)維能力(li)，而發(fa)散(san)思(si)維能力(li)能反映出對編程相(xiang)關技術(shu)理解的(de)深刻程度。
通(tong)常(chang)求1+2+…+n除了(le)用(yong)公(gong)式n(n+1)/2之外(wai)，無外(wai)乎循(xun)環和遞(di)歸兩種(zhong)思路。由于已經(jing)明確限制(zhi)for和while的(de)使(shi)用(yong)，循(xun)環已經(jing)不能(neng)再用(yong)了(le)。同樣，遞(di)歸函數(shu)也需要用(yong)if語(yu)句或者條件判斷語(yu)句來判斷是繼續(xu)遞(di)歸下(xia)去還是終止(zhi)遞(di)歸，但(dan)現在題目已經(jing)不允許(xu)使(shi)用(yong)這(zhe)兩種(zhong)語(yu)句了(le)。
我(wo)們(men)仍然圍繞循(xun)環做文章(zhang)。循(xun)環只是讓相同的代(dai)(dai)碼(ma)執行n遍而已，我(wo)們(men)完全(quan)可(ke)以(yi)不用(yong)for和while達到這(zhe)個效果。比如(ru)定(ding)義(yi)一個類，我(wo)們(men)new一含有n個這(zhe)種類型(xing)元(yuan)素的數(shu)組，那么該類的構造(zao)函數(shu)將確(que)定(ding)會被(bei)調(diao)用(yong)n次。我(wo)們(men)可(ke)以(yi)將需要執行的代(dai)(dai)碼(ma)放到構造(zao)函數(shu)里。如(ru)下代(dai)(dai)碼(ma)正是基于這(zhe)個思(si)路：
class Temp
{
public:
Temp() { ++ N; Sum += N; }
static void Reset() { N = 0; Sum = 0; }
static int GetSum() { return Sum; }
private:
static int N;
static int Sum;
};
int Temp::N = 0;
int Temp::Sum = 0;
int solution1_Sum(int n)
{
Temp::Reset();
Temp *a = new Temp[n];
delete []a;
a = 0;
return Temp::GetSum();
}
我(wo)們同(tong)樣(yang)也可以(yi)圍繞遞(di)歸做文章。既然不(bu)(bu)(bu)能判斷是(shi)不(bu)(bu)(bu)是(shi)應該終止遞(di)歸，我(wo)們不(bu)(bu)(bu)妨定義兩(liang)個函(han)(han)數(shu)。一(yi)(yi)個函(han)(han)數(shu)充當(dang)遞(di)歸函(han)(han)數(shu)的(de)(de)角色，另一(yi)(yi)個函(han)(han)數(shu)處理終止遞(di)歸的(de)(de)情況，我(wo)們需要做的(de)(de)就是(shi)在兩(liang)個函(han)(han)數(shu)里二(er)選(xuan)一(yi)(yi)。從二(er)選(xuan)一(yi)(yi)我(wo)們很(hen)自(zi)然的(de)(de)想到布爾變量，比如(ru)ture(1)的(de)(de)時候(hou)調用第(di)一(yi)(yi)個函(han)(han)數(shu)，false(0)的(de)(de)時候(hou)調用第(di)二(er)個函(han)(han)數(shu)。那(nei)現(xian)在的(de)(de)問(wen)題是(shi)如(ru)和把數(shu)值(zhi)變量n轉換成布爾值(zhi)。如(ru)果對n連續做兩(liang)次反運算，即(ji)!!n，那(nei)么(me)非(fei)零的(de)(de)n轉換為(wei)true，0轉換為(wei)false。有了上述分析，我(wo)們再(zai)來看(kan)下(xia)面(mian)的(de)(de)代碼：
class A;
A* Array[2];
class A
{
public:
virtual int Sum (int n) { return 0; }
};
class B: public A
{
public:
virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }
};
int solution2_Sum(int n)
{
A a;
B b;
Array[0] = &a;
Array[1] = &b;
int value = Array[1]->Sum(n);
return value;
}
這種方法是用虛函數來實現函數的選擇。當n不為零時，執行函數B::Sum;當n為0時，執行A::Sum。我們也可以(yi)直(zhi)接用函數指針數組，這樣可能還更直(zhi)接一些：
typedef int (*fun)(int);
int solution3_f1(int i)
{
return 0;
}
int solution3_f2(int i)
{
fun f[2]={solution3_f1, solution3_f2};
return i+f[!!i](i-1);
}
另外我們(men)還可(ke)以讓(rang)編譯器幫我們(men)來完成類似于遞歸的(de)運算，比如(ru)如(ru)下代碼：
template struct solution4_Sum
{
enum Value { N = solution4_Sum::N + n};
};
template <> struct solution4_Sum<1>
{
enum Value { N = 1};
};
solution4_Sum<100>::N就是1+2+...+100的(de)(de)(de)(de)結果。當編(bian)譯(yi)器(qi)(qi)看到(dao)solution4_Sum<100>時，就是為模板(ban)類solution4_Sum以(yi)(yi)參(can)(can)數(shu)100生成該(gai)類型(xing)的(de)(de)(de)(de)代碼(ma)。但(dan)以(yi)(yi)100為參(can)(can)數(shu)的(de)(de)(de)(de)類型(xing)需要得到(dao)以(yi)(yi)99為參(can)(can)數(shu)的(de)(de)(de)(de)類型(xing)，因為solution4_Sum<100>::N=solution4_Sum<99>::N+100。這(zhe)(zhe)個過(guo)程會遞(di)歸(gui)一(yi)直到(dao)參(can)(can)數(shu)為1的(de)(de)(de)(de)類型(xing)，由于該(gai)類型(xing)已經顯式定義，編(bian)譯(yi)器(qi)(qi)無(wu)需生成，遞(di)歸(gui)編(bian)譯(yi)到(dao)此結束。由于這(zhe)(zhe)個過(guo)程是在(zai)編(bian)譯(yi)過(guo)程中完(wan)成的(de)(de)(de)(de)，因此要求(qiu)輸(shu)(shu)入(ru)n必須是在(zai)編(bian)譯(yi)期間就能(neng)確定，不(bu)能(neng)動態輸(shu)(shu)入(ru)。這(zhe)(zhe)是該(gai)方法的(de)(de)(de)(de)缺點(dian)。而且編(bian)譯(yi)器(qi)(qi)對(dui)遞(di)歸(gui)編(bian)譯(yi)代碼(ma)的(de)(de)(de)(de)遞(di)歸(gui)深(shen)度(du)是有限制(zhi)的(de)(de)(de)(de)，也就是要求(qiu)n不(bu)能(neng)太大(da)。
