資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中找到使陣列作為互素陣列的最小插入
在本部分中，我們將看到另一個有趣的問題。假設我們有一個 N 元素的陣列。我們必須找到使該陣列成為互素陣列的最小交點數量。在互素陣列中，任意兩個連續元素的最大公約數為 1。我們還必須列印陣列。
假設我們有元素 {5, 10, 20}。這不是互素陣列。現在，透過在 5、10 和 10、20 之間插入 1，它將成為互素陣列。因此，陣列將如下所示：{5, 1, 10, 1, 20}
演算法
makeCoPrime(arr, n): begin count := 0 for i in range 1 to n, do if gcd of arr[i] and arr[i – 1] is not 1, then increase count by 1 done display count value display the first element of arr for i in range 1 to n, do if gcd of arr[i] and arr[i – 1] is not 1, then display 1 display element arr[i] done end
範例
#include <iostream>
#include <algorithm>
using namespace std;
int makeCoPrime(int arr[], int n){
int count = 0;
for(int i = 1; i<n; i++){
if(__gcd(arr[i], arr[i - 1]) != i){
count++;
}
}
cout << "Number of intersection points: " << count << endl;
cout << arr[0] << " ";
for(int i = 1; i<n; i++){
if(__gcd(arr[i], arr[i - 1]) != i){
cout << 1 << " ";
}
cout << arr[i] << " ";
}
}
int main() {
int A[] = {2, 7, 28};
int n = sizeof(A)/sizeof(A[0]);
makeCoPrime(A, n);
}輸出
Number of intersection points: 1 2 7 1 28
更新於: 2019 年 9 月 25 日
135 次檢視
廣告