程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> c語言求1+2+...+n的解決方法

c語言求1+2+...+n的解決方法

編輯:C語言基礎知識
題目:求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
{
private:
 static int N;
 static int Sum;
public:
 Temp() {   ++ N;   Sum += N;    }
 static void Reset() {   N = 0;   Sum = 0; }
 static int GetSum() {   return 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;

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