數值的整數次方

語言: CN / TW / HK

highlight: atom-one-dark

前言

在JavaScript中有一個庫函數(Math.pow())可以對一個數進行次方運算,本文將實現一個類似pow功能的函數,歡迎各位感興趣的開發者閲讀本文。

實現思路

第一眼看到這個問題,有些開發者可能思考幾秒鐘,覺得這很簡單嘛。直接遍歷次方數,將底數與前一次的計算結果相乘即可,直接一把梭🤓,很快就寫完了代碼,如下所示:

typescript /** * 計算一個數的次方 * @param base 底數 * @param exponent 指數 */ public power(base: number, exponent: number): number { let result = 1; for (let i = 1; i <= exponent; i++) { result *= base; } return result; }

細心的開發者可能已經發現了這段代碼的不足之處,上述代碼只考慮了指數是正數的情況,當輸入的指數為小於1的時候上述代碼就計算錯誤了🌝

image-20211114225904657

全面考慮的解法

接下來,我們把指數為負數和0時的情況考慮進去,來捋一下實現思路:

  • 當指數為負數的時候,需要對指數求絕對值,算出次方的結果之後再取倒數
  • 當指數為0時,我們就要考慮兩種情況:
  • 當底數為0且指數為負數時,就會出現對0求倒數,會導致程序運行出錯,需要進行容錯處理,將錯誤信息告知調用者
  • 當底數為0且指數為0時,這在數學上是沒有意義的,此處我們將結果返回0或1都可以

我們將上述思路轉化為代碼,如下所示:

```typescript /* * 計算一個數的次方 * @param base 底數 * @param exponent 指數 / public power(base: number, exponent: number): number | string { // 求出指數對絕對值 const absExponent = Math.abs(exponent); // 程序會出錯 if (base === 0 && exponent < 0) { return "參數錯誤: 0的負次方不能進行計算"; }

// 當底數和指數都為0時,在數學上是沒意義的
if (base === 0 && exponent === 0) {
  return 0;
}

let result = 1;
for (let i = 1; i <= absExponent; i++) {
  result *= base;
}

// 指數小於0, 對計算出的結果求倒數
if (exponent < 0) {
  result = 1 / result;
}
return result;

} ```

我們將各種情況都考慮進去,作為參數傳入上述代碼,觀察下運行結果,如下所示:

image-20211114235913960

最優解

上述解法已經滿足了題目要求,但是並不是最優解法,接下來,我們來看一種更好的解法。

上述代碼中循環計算底數的指數次方代碼可以拆分成一個函數,如下所示:

typescript /** * 求底數的指數次方 * @param base * @param exponent */ private static powerWithExponent(base: number, exponent: number) { let result = 1; for (let i = 1; i <= exponent; i++) { result *= base; } return result; }

拆分後,我們考慮這樣一個場景:

當指數為32時,就需要在上述函數的循環中做31乘法。然而,我們的目標就是求出一個數字的32次方,如果我們已經知道了它的16次方,那麼只要在16次方的基礎上再平方一次就可以了。而16次方是8次方的平方。

以此類推,我們求32次方只需要做5次乘法:

  • 先求平方
  • 在平方的基礎上求4次方
  • 在4次方的基礎上求8次方
  • 在8次方的基礎上求16次方
  • 在16次方的基礎上求32次方

思考到這裏,我們設要求的次方為n,那麼:

  • 當n為偶數時,可以拆分為n/2 * n/2
  • 當n為奇數時,可以拆分為(n-1)/2 * (n-1)/2

乘式兩邊計算出結果後,仍然可以對結果應用上述規則進行計算,直至n為0或1,總結成公式後,如下圖所示:

image-20211115211445909

實現代碼

有了公式後,我們很快就能想到可以用遞歸來解決這個問題,我們來畫一下遞歸棧,如下圖所示:

image-20211115233901255

思路捋清楚後,就可以愉快的進入編碼環節了🤓,完整代碼如下所示:

```typescript export default class IntegerPower { /* * 計算一個數的次方 * @param base 底數 * @param exponent 指數 / public power(base: number, exponent: number): number | string { // 求出指數對絕對值 const absExponent = Math.abs(exponent); // 程序會出錯 if (base === 0 && exponent < 0) { return "參數錯誤: 0的負次方不能進行計算"; }

// 當底數和指數都為0時,在數學上是沒意義的
if (base === 0 && exponent === 0) {
  return 0;
}

// 進行次方運算
let result = this.powerWithExponent(base, absExponent);

// 指數小於0, 對計算出的結果求倒數
if (exponent < 0) {
  result = 1 / result;
}
return result;

}

/* * 求底數的指數次方 * @param base 底數 * @param exponent 指數 / private powerWithExponent(base: number, exponent: number): number { // 遞歸終止條件 if (exponent === 0) { // 非0數的0次方值為1 return 1; } if (exponent === 1) { // 任意數的0次方為其本身 return base; }

// 遞歸對指數/2,計算結果
// 用右移運算符代替除以2運算
let result =
  this.powerWithExponent(base, exponent >> 1) *
  this.powerWithExponent(base, exponent >> 1);

// 指數為奇數時,result就為result乘以底數
if (exponent % 2 === 1) {
  result *= base;
}
return result;

} }

```

上述代碼中,我使用了右移運算符來代替除法運算,這樣可以提升代碼的執行速度。對此不瞭解的開發者請移步我的另一篇文章:二進制中一的個數-右移運算符

對遞歸不熟悉的開發者,請移步:遞歸的理解與實現

編寫測試用例

接下來,我們將各種邊界條件都考慮進去,驗證下上述代碼能否正確執行。

```typescript import IntegerPower from "../IntegerPower.ts";

const powerHandler = new IntegerPower(); const result1 = powerHandler.power(5, 6); const result2 = powerHandler.power(3, -4); const result3 = powerHandler.power(0, 0); const result4 = powerHandler.power(0, 3); const result5 = powerHandler.power(0, -3); console.log(result1); console.log(result2); console.log(result3); console.log(result4); console.log(result5);

```

運行結果如下所示:

image-20211115225812545

項目代碼

文中的示例代碼請移步:

寫在最後

至此,文章就分享完畢了。

我是神奇的程序員,一位前端開發工程師。

如果你對我感興趣,請移步我的個人網站,進一步瞭解。

  • 文中如有錯誤,歡迎在評論區指正,如果這篇文章幫到了你,歡迎點贊和關注😊
  • 本文首發於神奇的程序員公眾號,未經許可禁止轉載💌