資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++程式：查詢第N個可被a或b整除的數
在這個問題中，我們給出三個數字A、B和N。我們的任務是編寫一個C++程式來查詢第N個可被A或B整除的數。
問題描述
第N個可被A或B整除的數。我們將找到第n個數，該數可被數字A或B整除。為此，我們將計算直到第n個可被A或B整除的數。
讓我們來看一個例子來理解這個問題：
輸入
A = 4, B = 3, N = 5
輸出
9
解釋
可被3和4整除的數是：
3, 4, 6, 8, 9, 12, …
第5個數是9。
解決方案
為了找到第n個可被A或B整除的數，我們可以簡單地找到可被A或B整除的數，而該序列中的第n個數就是我們的答案。
示例
#include<iostream>
using namespace std;
int findNTerm(int N, int A, int B) {
int count = 0;
int num = 1;
while( count < N){
if(num%A == 0 || num%B == 0)
count++;
if(count == N)
return num;
num++;
}
return 0;
}
int main(){
int N = 12, A = 3, B = 4;
cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B)<<endl;
}輸出
12th term divisible by 3 or 4 is 24
另一種解決這個問題的方法是使用二分查詢來找到第N個可被A或B整除的元素。我們將使用以下公式找到第N個數：
NTerm = maxNum/A + maxNum/B - maxNum/lcm(A,B)
並根據Nterm的值，我們將檢查是否需要遍歷小於maxNum或大於maxNum的數字。
示例
#include <iostream>
using namespace std;
int findLCM(int a, int b) {
int LCM = a, i = 2;
while(LCM % b != 0) {
LCM = a*i;
i++;
}
return LCM;
}
int findNTerm(int N, int A, int B) {
int start = 1, end = (N*A*B), mid;
int LCM = findLCM(A, B);
while (start < end) {
mid = start + (end - start) / 2;
if ( ((mid/A) + (mid/B) - (mid/LCM)) < N)
start = mid + 1;
else
end = mid;
}
return start;
}
int main() {
int N = 12, A = 3, B = 4;
cout<<N<<"th term divisible by "<<A<<" or "<<B<<" is "<<findNTerm(N, A, B);
}輸出
12th term divisible by 3 or 4 is 24
更新於：2020年10月9日
619 次瀏覽
廣告