計算給定陣列區域性極值的C++程式碼

---

極值是指最小值或最大值。換句話說，它是一個數字或元素，它大於或小於其兩個相鄰值。

假設我們有一個包含n個元素的陣列A。該陣列A[i]中的一個元素被稱為區域性最小值，當且僅當它嚴格小於其兩個相鄰元素。如果它嚴格大於其相鄰元素，則它將是區域性最大值。對於A[0]和A[n-1]，由於只有一個鄰居，它們既不是最大值也不是最小值。我們必須找到給定陣列中區域性極值的個數。

對於給定的一組數字，第一個和最後一個數字永遠不可能是極值。在給定的陣列中，我們可以使用各種C++技術找到這樣的區域性極值。

輸入輸出場景

考慮陣列中的一組N個元素。然後，我們可以計算陣列中存在的區域性極值的總數。

Input: numbers = 12, 16, 4
Output: 1
Input: numbers = 10, 16, 12, 5, 23, 40
Output: 2

使用for迴圈

在這種方法中，我們將使用一個for迴圈，該迴圈將從給定陣列的第二個元素迭代到倒數第二個元素。這是因為第一個和最後一個元素永遠不可能是極值。在迴圈中，我們將使用if語句檢查每個元素是否大於或小於其兩個相鄰元素。如果任一條件為真，則num變數遞增一。

示例

#include <iostream>
using namespace std;
int numberOfExtrema(int x[], int N){
   int num = 0;
   // Iterate the loop from the second
   // element to the second last element
   for(int i = 1; i < N-1; i++){
      if(x[i] > x[i-1] && x[i] > x[i+1]){
         num++;
      }
      if(x[i] < x[i-1] && x[i] < x[i+1]){
         num++;
      }
   }
   return num;
}
int main() {
   int x[] = {10, 16, 12, 5, 23, 40};
   int N = sizeof(x) / sizeof(x[0]);
   std::cout << "Number of local extrema in the array: " << numberOfExtrema(x, N);
   return 0;
}

輸出

Number of local extrema in the array: 2

使用C++標準模板庫

我們可以使用STL（標準模板庫）演算法的最大值和最小值運算。std::max()和std::min()是預定義函式，分別用於返回陣列指定範圍內的最大和最小元素。

語法

std::max_element(first, last)
std::min_element(first, last)

其中，

• first是範圍開始元素的位置。

• last是範圍結束元素的位置。

如果我們想找到區域性極值，我們需要一次考慮三個元素（當前元素及其兩個相鄰元素）。因此，我們的範圍包含三個元素。因此，我們在大括號內指定這三個元素。

std::max({element 1, element 2, element 3});

這裡，我們從給定陣列的第二個元素迭代到倒數第二個元素。我們找到x[i - 1]、x[i]、x[i + 1]中的最大和最小元素。如果當前元素等於兩者中的任何一個，則num遞增一。

示例

讓我們來看一個例子：

#include <iostream>
#include <algorithm>
using namespace std;
int numberOfExtrema(int x[], int N){
   int num = 0;
   // Iterate the loop from the second
   // Element to the second last element
   for (int i = 1; i < N - 1; i++) {
      int max_element = std::max({x[i - 1], x[i], x[i + 1]});
      int min_element = std::min({x[i - 1], x[i], x[i + 1]});
      if (x[i] == max_element || x[i] == min_element) {
         num++;
      }
   }
   return num;
}
int main() {
   int x[] = {10, 16, 12, 5, 23, 40};
   int N = sizeof(x) / sizeof(x[0]);
   std::cout << "Number of local extrema in the array: " << numberOfExtrema(x,N);
   return 0;
}

輸出

Number of local extrema in the array: 2

使用遞迴

在這裡，我們將使用遞迴來解決我們的問題。我們將陣列劃分為更小的子陣列，並在其中找到中心值。然後，我們檢查中心元素是否大於或小於其兩個相鄰元素。

如果滿足任一條件，則num變數遞增一。由於遞迴函式自身呼叫，所有結果都將組合以給出最終輸出。

示例

#include <iostream>
int recursion(int x[], int left, int right) {
   // If subarray contains 2 or less elements
   if (right - left <= 1) {
      return 0;
   }
   int center = left + (right - left) / 2;
   int num = 0;
   if ((x[center] > x[center - 1] && x[center] > x[center + 1]) ||
   (x[center] < x[center - 1] && x[center] < x[center + 1])) {
      num++;
   }
   num += recursion(x, left, center);
   num += recursion(x, center, right);
   return num;
}
int numberOfExtrema(int x[], int N) {
   return recursion(x, 0, N - 1);
}
int main() {
   int x[] = {10, 16, 12, 5, 23, 40};
   int N = sizeof(x) / sizeof(x[0]);
   std::cout << "Number of local extrema in the array: " << numberOfExtrema(x, N) << std::endl;
   return 0;
}

輸出

Number of local extrema in the array: 2

結論

在本文中，我們討論了在陣列中查詢區域性極值的幾種不同方法。在第一種方法中，我們學習了簡單的迭代方法，其中涉及使用for迴圈。在第二種方法中，我們使用了std::max()和std::min()函式。在第三種方法中，我們討論了遞迴方法，該方法對於較大的陣列很有用。