資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究根據給定的條件，將陣列拆分成相等的部分(C++)
接下來，我們來看個問題。假設給定了一個數組 arr。我們必須檢查陣列是否可以分成兩部分，滿足以下條件：
- 兩個子陣列相減結果相同
- 所有 5 的倍數元素都必須在同組中
- 所有 3 的倍數但不是 5 的倍數的元素都必須在同組中
- 其他所有元素都必須在其他組中。
假設陣列元素為 {1, 4, 3}，那麼可以拆分，因為 {1, 3} 的和與 {4} 的和相同，並且給定的條件也符合這些分組。
演算法
isSplitArray(arr, n, start, left_sum, right_sum) −
Begin if start = n, then return true when left_sum = right_sum, otherwise false if arr[start] is divisible by 5, then add arr[start] with the left_sum else if arr[start] is divisible by 3, then add arr[start] with the right_sum else return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) OR isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]) isSplitArray(arr, n, start + 1, left_sum, right_sum) End
示例
#include <iostream>
using namespace std;
bool isSplitArray(int* arr, int n, int start, int left_sum, int right_sum) {
if (start == n) //when it reaches at the end
return left_sum == right_sum;
if (arr[start] % 5 == 0) //when the element is divisible by 5, add to left sum
left_sum += arr[start];
else if (arr[start] % 3 == 0) //when the element is divisible by 3 but not 5, add to right sum
right_sum += arr[start];
else // otherwise it can be added to any of the sub-arrays
return isSplitArray(arr, n, start + 1, left_sum + arr[start], right_sum) || isSplitArray(arr, n, start + 1, left_sum, right_sum + arr[start]);
// For cases when element is multiple of 3 or 5.
return isSplitArray(arr, n, start + 1, left_sum, right_sum);
}
int main() {
int arr[] = {1, 4, 3};
int n = sizeof(arr)/sizeof(arr[0]);
if(isSplitArray(arr, n, 0, 0, 0)){
cout <<"Can be split";
} else {
cout <<"Can not be split";
}
}輸出
Can be split
更新時間：2019 年 10 月 17 日
730 次檢視
廣告