http://zhedahht.blog.163.com/blog/static/2541117420072915131422/題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關(guān)鍵字以及條件判斷語(yǔ)句（A?B:C）。

分析：這道題沒(méi)有多少實(shí)際意義，因?yàn)樵谲浖_發(fā)中不會(huì)有這么變態(tài)的限制。但這道題卻能有效地考查發(fā)散思維能力，而發(fā)散思維能力能反映出對(duì)編程相關(guān)技術(shù)理解的深刻程度。

通常求1+2+…+n除了用公式n(n+1)/2之外，無(wú)外乎循環(huán)和遞歸兩種思路。由于已經(jīng)明確限制for和while的使用，循環(huán)已經(jīng)不能再用了。同樣，遞歸函數(shù)也需要用if語(yǔ)句或者條件判斷語(yǔ)句來(lái)判斷是繼續(xù)遞歸下去還是終止遞歸，但現(xiàn)在題目已經(jīng)不允許使用這兩種語(yǔ)句了。

我們?nèi)匀粐@循環(huán)做文章。循環(huán)只是讓相同的代碼執(zhí)行n遍而已，我們完全可以不用for和while達(dá)到這個(gè)效果。比如定義一個(gè)類，我們new一含有n個(gè)這種類型元素的數(shù)組，那么該類的構(gòu)造函數(shù)將確定會(huì)被調(diào)用n次。我們可以將需要執(zhí)行的代碼放到構(gòu)造函數(shù)里。如下代碼正是基于這個(gè)思路：

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();
}

我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應(yīng)該終止遞歸，我們不妨定義兩個(gè)函數(shù)。一個(gè)函數(shù)充當(dāng)遞歸函數(shù)的角色，另一個(gè)函數(shù)處理終止遞歸的情況，我們需要做的就是在兩個(gè)函數(shù)里二選一。從二選一我們很自然的想到布爾變量，比如ture（1）的時(shí)候調(diào)用第一個(gè)函數(shù)，false（0）的時(shí)候調(diào)用第二個(gè)函數(shù)。那現(xiàn)在的問(wèn)題是如和把數(shù)值變量n轉(zhuǎn)換成布爾值。如果對(duì)n連續(xù)做兩次反運(yùn)算，即!!n，那么非零的n轉(zhuǎn)換為true，0轉(zhuǎn)換為false。有了上述分析，我們?cè)賮?lái)看下面的代碼：

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;
}

這種方法是用虛函數(shù)來(lái)實(shí)現(xiàn)函數(shù)的選擇。當(dāng)n不為零時(shí)，執(zhí)行函數(shù)B::Sum；當(dāng)n為0時(shí)，執(zhí)行A::Sum。我們也可以直接用函數(shù)指針數(shù)組，這樣可能還更直接一些：

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);
}

另外我們還可以讓編譯器幫我們來(lái)完成類似于遞歸的運(yùn)算，比如如下代碼：

template <int n> struct solution4_Sum
{
      enum Value { N = solution4_Sum<n - 1>::N + n};
};

template <> struct solution4_Sum<1>
{
      enum Value { N = 1};
};

solution4_Sum<100>::N就是1+2+...+100的結(jié)果。當(dāng)編譯器看到solution4_Sum<100>時(shí)，就是為模板類solution4_Sum以參數(shù)100生成該類型的代碼。但以100為參數(shù)的類型需要得到以99為參數(shù)的類型，因?yàn)?/span>solution4_Sum<100>::N=solution4_Sum<99>::N+100。這個(gè)過(guò)程會(huì)遞歸一直到參數(shù)為1的類型，由于該類型已經(jīng)顯式定義，編譯器無(wú)需生成，遞歸編譯到此結(jié)束。由于這個(gè)過(guò)程是在編譯過(guò)程中完成的，因此要求輸入n必須是在編譯期間就能確定，不能動(dòng)態(tài)輸入。這是該方法最大的缺點(diǎn)。而且編譯器對(duì)遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。

大家還有更多、更巧妙的思路嗎？歡迎討論^_^

博主何海濤對(duì)本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請(qǐng)注明出處http://zhedahht.blog.163.com/。整理出版物請(qǐng)和作者聯(lián)系。對(duì)解題思路有任何建議，歡迎在評(píng)論中告知，或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht與我討論。謝謝。
from：
http://zhedahht.blog.163.com/blog/static/2541117420072915131422/