資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用二分查詢法查詢最大子陣列和的C++程式
二分查詢是一種快速查詢演算法，其執行時間複雜度為Ο(log n)。該查詢演算法基於分治的思想。為了使該演算法正常工作，資料集合必須已排序。
二分查詢透過比較集合中最中間的項來查詢特定項。如果找到匹配項，則返回該項的索引。如果中間項大於該項，則在中間項左側的子陣列中搜索該項。否則，在中間項右側的子陣列中搜索該項。此過程也繼續在子陣列上進行，直到子陣列的大小減小到零。
這是一個使用二分查詢法查詢最大子陣列和的程式。
演算法
Begin Declare an integer function maximum() to find the maximum of two integers. Declare val1, val2 to the integer datatype. Pass them as parameter. Check the maximum between val1 and val2. Return the maximum value. End Begin Declare an integer function MCS() to find the maximum sum sub-array which includes medium of the sub-array. Declare an array array[] and variable l, m, h to the integer datatype. Pass them as parameter. Declare variable s, sum_of_left_part to the integer datatype. Initialize s = 0. Initialize sum_of_left_part = -1. for (int i = m; i >= l; i--) s = s + array[i]. if (s > sum_of_left_part) then sum_of_left_part = s. s = 0 Declare variable sum_of_right_part to the integer datatype. Initialize sum_of_right_part = -1. for (int i = m+1; i <= h; i++) s = s + array[i]. if (s > sum_of_right_part) then sum_of_right_part = s. return sum_of_left_part + sum_of_right_part. End Begin Declare an integer function MaximumSum_of_SubArray(). Declare an array array[] and variable l, h to the integer datatype. Pass them as parameter. Declare m to the integer datatype. if (l == h) then return array[l]. m = (l + h)/2; return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h)). Declare number_of_elements and i to the integer datatype. Print “Enter the number of elements of array: ”. Enter the value of number_of_elements. Declare an array a[number_of_elements] to the integer datatype. for(i = 0; i < n; i++) Print “Enter the element of”. Enter the data element of array. Print “Maximum sum of Sub-Array is: ” . Print the result of MaximumSum_of_SubArray(a, 0, n-1). End.
示例
#include<iostream>
using namespace std;
int maximum(int val1, int val2) // find the maximum of two integers {
return (val1 > val2)? val1:val2;
}
int MCS(int array[], int l, int m, int h) // find the maximum sum sub-array which includes medium of the sub-array. {
int s = 0;
int sum_of_left_part = -1;
for (int i = m; i >= l; i--) {
s = s + array[i];
if (s > sum_of_left_part)
sum_of_left_part = s;
}
s = 0;
int sum_of_right_part = -1;
for (int i = m+1; i <= h; i++) {
s = s + array[i];
if (s > sum_of_right_part)
sum_of_right_part = s;
}
return sum_of_left_part + sum_of_right_part; // Return sum of elements on left and right of medium.
}
int MaximumSum_of_SubArray(int array[], int l, int h) {
int m;
if (l == h)
return array[l];
m = (l + h)/2;
return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h));
}
int main() {
int number_of_elements, i;
cout<<"Enter the number of elements of array: ";
cin>> number_of_elements;
cout<<endl;
int a[number_of_elements];
for(i = 0; i < number_of_elements; i++) {
cout<<"Enter the element of "<<i+1<<": ";
cin>>a[i];
}
cout<<"\nMaximum sum of Sub-Array is: "<<MaximumSum_of_SubArray(a, 0, number_of_elements -1); // Print the maximum sum sub-array.
return 0;
}輸出
Enter the number of elements of array: 5 Enter the element of 1: 12 Enter the element of 2: 45 Enter the element of 3: 56 Enter the element of 4: 48 Enter the element of 5: 75 Maximum sum of Sub-Array is: 236
更新於：2019年7月30日
239 次瀏覽
廣告