-求1+2+...+n

題目：求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等關鍵字以及條件判斷語句(A?B:C)。

分析：這道題沒有多少實際意義，因為在軟件開發中不會有這么變態的限制。但這道題卻能有效地考查發散思維能力，而發散思維能力能反映出對編程相關技術理解的深刻程度。

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

我們仍然圍繞循環做文章。循環只是讓相同的代碼執行n遍而已，我們完全可以不用for和while達到這個效果。比如定義一個類，我們new一含有n個這種類型元素的數組，那么該類的構造函數將確定會被調用n次。我們可以將需要執行的代碼放到構造函數里。如下代碼正是基于這個思路：

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

}

我們同樣也可以圍繞遞歸做文章。既然不能判斷是不是應該終止遞歸，我們不妨定義兩個函數。一個函數充當遞歸函數的角色，另一個函數處理終止遞歸的情況，我們需要做的就是在兩個函數里二選一。從二選一我們很自然的想到布爾變量，比如ture(1)的時候調用第一個函數，false(0)的時候調用第二個函數。那現在的問題是如和把數值變量n轉換成布爾值。如果對n連續做兩次反運算，即!!n，那么非零的n轉換為true，0轉換為false。有了上述分析，我們再來看下面的代碼：

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。我們也可以直接用函數指針數組，這樣可能還更直接一些：

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

}

另外我們還可以讓編譯器幫我們來完成類似于遞歸的運算，比如如下代碼：

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的結果。當編譯器看到solution4_Sum<100>時，就是為模板類solution4_Sum以參數100生成該類型的代碼。但以100為參數的類型需要得到以99為參數的類型，因為solution4_Sum<100>::N=solution4_Sum<99>::N+100。這個過程會遞歸一直到參數為1的類型，由于該類型已經顯式定義，編譯器無需生成，遞歸編譯到此結束。由于這個過程是在編譯過程中完成的，因此要求輸入n必須是在編譯期間就能確定，不能動態輸入。這是該方法最大的缺點。而且編譯器對遞歸編譯代碼的遞歸深度是有限制的，也就是要求n不能太大。

相關推薦：

計算機軟件水平考試輔導資料

計算機軟件水平考試精品輔導班

（責任編輯：）

共2頁,當前第1頁  第一頁  前一頁  下一頁