資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢自然數 N 的第 k 小的除數
在這個問題中，我們給定兩個整數值 N 和 k。我們的任務是查詢自然數 N 的第 k 小的除數。
讓我們舉個例子來理解這個問題，
Input : N = 15, k = 3 Output : 5
解釋 -
Factors of 15 are 1, 3, 5, 15 3rd smallest is 5
解決方案方法
解決此問題的一個簡單方法是找到數字的因子並以排序的方式儲存它們，然後列印第 k 個值。
對於排序，我們將迴圈到根號(N) 並檢查 N 是否可被 i 整除。並將 i 和 (N/i) 的值儲存在一個數組中並對其進行排序。從這個排序後的陣列中，列印第 k 個值。
示例
程式說明我們解決方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
int factors[n/2];
int j = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
factors[j] = i;
j++;
if (i != sqrt(n)){
factors[j] = n/i;
j++;
}
}
}
sort(factors, factors + j);
if (k > j)
cout<<"Doesn't Exist";
else
cout<<factors[k-1];
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
}輸出
3-th smallest divisor of the number 16 is 4
另一種方法
解決此問題的另一種方法是使用兩個排序的陣列。
一個儲存值 i，按升序排序。
另一個儲存值 N/i，按降序排序。
我們將從這兩個陣列中的任何一個找到第 k 小的值。如果 k 大於陣列的大小，則它存在於第二個陣列的末尾。
否則它存在於第一個陣列中。
示例
程式說明我們解決方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
int factors1[n/2];
int factors2[n/2];
int f1 = 0,f2 = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
factors1[f1] = i;
f1++;
if (i != sqrt(n)){
factors2[f2] = n/i;
f2++;
}
}
}
if (k > (f1 + f2))
cout<<"Doesn't Exist";
else{
if(k <= f1)
cout<<factors1[f1-1];
else
cout<<factors2[k - f2 - 1];
}
}
int main(){
int N = 16,
k = 3;
cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
findFactorK(N, k);
return 0;
}輸出
3-th smallest divisor of the number 16 is 4
更新於: 2022-01-28
409 次檢視
廣告