資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中求兩個數的倍數之和（小於 N）
在這個問題中，我們給定三個整數 M1、M2 和 N。我們的任務是建立一個程式來找到兩個數的倍數之和（小於 N）。
在這裡，我們將新增所有小於 N 且是 M1 或 M2 的倍數的元素。
讓我們舉個例子來理解這個問題，
輸入
N = 13, M1 = 4, M2 = 6
輸出
20
解釋 - 小於 13 且是 4 和 6 的倍數的數字是 4、6、8、12。
解決這個問題的一個簡單方法是從 1 到 N 迴圈，並新增所有可以被 M1 或 M2 整除的值。
演算法
步驟 1 - sum = 0，i = 0。從 i = 1 迴圈到 N。
步驟 1.1 - 如果 (i%M1 == 0) 或 (i%M2 == 0)，則 sum += i
步驟 2 - 返回 sum。
示例
程式說明了解決方案的工作原理，
#include <iostream<
using namespace std;
int calcMulSum(int N, int M1, int M2){
int sum = 0;
for (int i = 0; i < N; i++)
if (i%M1 == 0 || i%M2 == 0)
sum += i;
return sum;
}
int main(){
int N = 24, M1 = 4, M2 = 7;
cout<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
return 0;
}輸出
The sum of multiples of 4 and 7 below 24 is 102
這不是我們問題的最佳解決方案，因為它需要 O(n) 的時間複雜度。
一個更好的解決方案將是使用數學公式來計算級數的和。
在這裡，我們將使用級數和的公式。最終的和將是 (M1 的倍數 + M2 的倍數 - M1*M2 的倍數)
x 的倍數之和（最多 n 項）由下式給出，
Sum(X) = (n * (1+n) * X)/2
讓我們制定求和公式，
sum = ( ( ((n/M1)*(1+(n/M1))*M1)/2) + ((n/M2)*(1+(n/M2))*M2)/2 ) - ((n/M1*M2)*(1+(n/M1*M2))*M1*M2)/2 ) )
示例
程式說明了解決方案，
#include <iostream>
using namespace std;
int calcMulSum(int N, int M1, int M2){
N--;
return (((N/M1) * (1 + (N/M1)) * M1 / 2) + ((N/M2) * (1 + (N/M2)) * M2 / 2) - ((N/(M1*M2)) * (1 + (N/(M1*M2))) * (M1*M2) / 2));
}
int main(){
int N = 24, M1 = 4, M2 = 7;
cout<<"The sum of multiples of "<<M1<<" and "<<M2<<" below "<<N<<" is "<<calcMulSum(N, M1, M2);
return 0;
}輸出
The sum of multiples of 4 and 7 below 24 is 102
更新於: 2020-08-06
289 次瀏覽
廣告