資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學在 C++ 中尋找一個排列，使得 gcd(p[i], i) > 1 的索引個數恰好為 K
假設我們有兩個整數 N 和 K。我們必須找到一個來自範圍 [1 到 N] 的整數排列，使得 gcd(P[i], i) > 1 的索引（1 為基索引）個數恰好為 K。因此，如果 N = 4 且 K = 3，則輸出將為 [1, 2, 3, 4]，因為 gcd(1, 1) = 1，gcd(2, 2) = 2，gcd(3, 3) = 3，gcd(4, 4) = 4。
如果仔細觀察，我們可以發現 gcd(i, i+1) = 1，gcd(1, i) = 1 且 gcd(i, i) = i。由於任何數與 1 的最大公約數始終為 1，因此 K 幾乎可以為 N – 1。考慮排列 P[i] = i。其中 gcd(P[i], i) > 1 的索引個數將為 N – 1。如果我們交換兩個連續的元素（不包括 1），則此類索引的計數將恰好減少 2，而與 1 交換則會減少 1。
示例
#include<iostream>
using namespace std;
void findPermutation(int n, int k) {
if (k >= n || (n % 2 == 0 && k == 0)) {
cout << -1;
return;
}
int P[n + 1];
for (int i = 1; i <= n; i++)
P[i] = i;
int count = n - 1;
for (int i = 2; i < n; i+=2) {
if (count - 1 > k) {
swap(P[i], P[i + 1]);
count -= 2;
} else if (count - 1 == k) {
swap(P[1], P[i]);
count--;
} else
break;
}
for (int i = 1; i <= n; i++)
cout << P[i] << " ";
}
int main() {
int n = 5, k = 3;
cout << "Permutation is: ";
findPermutation(n, k);
}輸出
Permutation is: 2 1 3 4 5
更新於：2019年12月18日
瀏覽量：180
廣告