資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究在C++中透過刪除恰好k個子陣列來最大化陣列大小，使其成為素數陣列
給定任務是從具有N個正元素的給定陣列Arr[]中刪除恰好K個子陣列，使得陣列中所有剩餘元素都是素數，並且剩餘陣列的大小最大。
輸入
Arr[]={4, 3, 3, 4, 3, 4, 3} , K=2輸出
3
解釋 − K=2，這意味著必須刪除2個子陣列。
刪除的子陣列是Arr[0]和Arr[3…5]，留下陣列Arr[]={3,3,3}，其中所有元素都是素數，並且大小最大。
輸入
Arr[]={7, 6, 2, 11, 8, 3, 12}, K=2輸出
3
解釋 − 刪除的子陣列是Arr[1]和Arr[4…6]，剩下的素數陣列是Arr[]={7,2,11}。
下面程式中使用的演算法如下
首先，使用埃拉託斯特尼篩法（透過呼叫sieve()函式）將所有素數儲存到另一個數組prime[]中。
在MaxSize()函式中，從i=0迴圈到i<N，並將所有合數的索引號儲存到int型別的向量vect中。
然後，從i=1迴圈到i<vect.size，計算兩個連續合數之間素數的數量，並將結果儲存到int型別的向量diff中。
然後，使用sort()函式對向量diff進行排序。
現在，從i=1迴圈到i<diff.size()，計算該向量的累加和，這將幫助我們知道需要刪除多少個素數。
使用if語句檢查不可能的情況，即當K=0且沒有合數時。
如果K大於或等於合數的數量，則刪除所有合數，包括多餘的素數，並且這些要刪除的子陣列的大小應為1，以獲得最佳答案。
如果K小於合數的數量，則必須刪除包含合數的子陣列，而素數子陣列不應該屬於此類別。
示例
#include <bits/stdc++.h>
using namespace std;
const int Num = 1e5;
bool prime[Num];
//Sieve of Eratosthenes
void sieve(){
for (int i = 2; i < Num; i++) {
if (!prime[i]){
for (int j = i + i; j < Num; j += i){
prime[j] = 1;
}
}
}
prime[1] = 1;
}
int MaxSize(int* arr, int N, int K){
vector<int> vect, diff;
//Inserting the indices of composite numbers
for (int i = 0; i < N; i++){
if (prime[arr[i]])
vect.push_back(i);
}
/*Computing the number of prime numbers between
two consecutive composite numbers*/
for (int i = 1; i < vect.size(); i++){
diff.push_back(vect[i] - vect[i - 1] - 1);
}
//Sorting the diff vector
sort(diff.begin(), diff.end());
//Computing the prefix sum of diff vector
for (int i = 1; i < diff.size(); i++){
diff[i] += diff[i - 1];
}
//Impossible case
if (K > N || (K == 0 && vect.size())){
return -1;
}
//Deleting sub-arrays of length 1
else if (vect.size() <= K){
return (N - K);
}
/*Finding the number of primes to be deleted
when deleting the sub-arrays*/
else if (vect.size() > K){
int tt = vect.size() - K;
int sum = 0;
sum += diff[tt - 1];
int res = N - (vect.size() + sum);
return res;
}
}
//Main function
int main(){
sieve();
int arr[] = { 7, 2, 3, 4, 3, 6, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout<< MaxSize(arr, N, K);
return 0;
}輸出
如果執行上述程式碼，將得到以下輸出：
6
更新於：2020年8月17日
90 次瀏覽
廣告