またはのように、複数の数値の最小公倍数を計算する C++ アルゴリズムはありますlcm(3,6,12)かlcm(5,7,9,12)?
85878 次
16 に答える
50
std::accumulate といくつかのヘルパー関数を使用できます。
#include <iostream>
#include <numeric>
int gcd(int a, int b)
{
for (;;)
{
if (a == 0) return b;
b %= a;
if (b == 0) return a;
a %= b;
}
}
int lcm(int a, int b)
{
int temp = gcd(a, b);
return temp ? (a / temp * b) : 0;
}
int main()
{
int arr[] = { 5, 7, 9, 12 };
int result = std::accumulate(arr, arr + 4, 1, lcm);
std::cout << result << '\n';
}
于 2010-11-19T22:25:50.573 に答える
18
boost は、2 つの数値の lcm を計算するための関数を提供します (こちらを参照)
次に、という事実を使用して
lcm(a,b,c) = lcm(lcm(a,b),c)
複数の数値の lcm も簡単に計算できます
于 2010-11-19T22:17:44.777 に答える
6
このアルゴリズムは C++ に固有のものではありません。私の知る限り、標準ライブラリ関数はありません。
LCM を計算するには、最初にユークリッド アルゴリズムを使用して GCD (最大公約数) を計算します。
http://en.wikipedia.org/wiki/Greatest_common_divisor
通常、GCD アルゴリズムは 2 つのパラメーターに対して指定されますが、...
GCD (a, b, c) = GCD (a, GCD (b, c))
= GCD (b, GCD (a, c))
= GCD (c, GCD (a, b))
= ...
LCM を計算するには、次を使用します...
a * b
LCM (a, b) = ----------
GCD (a, b)
そのロジックは、素因数分解に基づいています。より一般的な形式 (2 つ以上の変数) は...
a b
LCM (a, b, ...) = GCD (a, b, ...) * --------------- * --------------- * ...
GCD (a, b, ...) GCD (a, b, ...)
編集 - 実際、最後のビットが間違っている可能性があると思います。ただし、最初の LCM (2 つのパラメーターの場合) は正しいです。
于 2010-11-19T22:30:00.463 に答える
5
C++ 14でGCCを使用すると、次のコードがうまくいきました。
#include <algorithm>
#include <vector>
std::vector<int> v{4, 6, 10};
auto lcm = std::accumulate(v.begin(), v.end(), 1, [](auto & a, auto & b) {
return abs(a * b) / std::__gcd(a, b);
});
C++17 には、累積で直接使用できるstd::lcm 関数 ( http://en.cppreference.com/w/cpp/numeric/lcm ) があります。
于 2016-12-16T13:37:02.957 に答える
1
標準ライブラリには組み込まれていません。自分でビルドするか、それを行うライブラリを入手する必要があります。Boostには1つあるに違いない...
于 2010-11-19T22:17:23.240 に答える
1
複数の番号に対して gcd を作成しました。
#include <iostream>
using namespace std;
int dbd(int n, int k, int y = 0);
int main()
{
int h = 0, n, s;
cin >> n;
s = dbd(n, h);
cout << s;
}
int dbd(int n, int k, int y){
int d, x, h;
cin >> x;
while(x != y){
if(y == 0){
break;
}
if( x > y){
x = x - y;
}else{
y = y - x;
}
}
d = x;
k++;
if(k != n){
d = dbd(n, k, x);
}
return d;
}
dbd-gcd.
n - 数字の数。
于 2012-12-01T17:55:09.827 に答える
0
/*
Copyright (c) 2011, Louis-Philippe Lessard
All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
unsigned gcd ( unsigned a, unsigned b );
unsigned gcd_arr(unsigned * n, unsigned size);
unsigned lcm(unsigned a, unsigned b);
unsigned lcm_arr(unsigned * n, unsigned size);
int main()
{
unsigned test1[] = {8, 9, 12, 13, 39, 7, 16, 24, 26, 15};
unsigned test2[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
unsigned result;
result = gcd_arr(test1, sizeof(test1) / sizeof(test1[0]));
result = gcd_arr(test2, sizeof(test2) / sizeof(test2[0]));
result = lcm_arr(test1, sizeof(test1) / sizeof(test1[0]));
result = lcm_arr(test2, sizeof(test2) / sizeof(test2[0]));
return result;
}
/**
* Find the greatest common divisor of 2 numbers
* See http://en.wikipedia.org/wiki/Greatest_common_divisor
*
* @param[in] a First number
* @param[in] b Second number
* @return greatest common divisor
*/
unsigned gcd ( unsigned a, unsigned b )
{
unsigned c;
while ( a != 0 )
{
c = a;
a = b%a;
b = c;
}
return b;
}
/**
* Find the least common multiple of 2 numbers
* See http://en.wikipedia.org/wiki/Least_common_multiple
*
* @param[in] a First number
* @param[in] b Second number
* @return least common multiple
*/
unsigned lcm(unsigned a, unsigned b)
{
return (b / gcd(a, b) ) * a;
}
/**
* Find the greatest common divisor of an array of numbers
* See http://en.wikipedia.org/wiki/Greatest_common_divisor
*
* @param[in] n Pointer to an array of number
* @param[in] size Size of the array
* @return greatest common divisor
*/
unsigned gcd_arr(unsigned * n, unsigned size)
{
unsigned last_gcd, i;
if(size < 2) return 0;
last_gcd = gcd(n[0], n[1]);
for(i=2; i < size; i++)
{
last_gcd = gcd(last_gcd, n[i]);
}
return last_gcd;
}
/**
* Find the least common multiple of an array of numbers
* See http://en.wikipedia.org/wiki/Least_common_multiple
*
* @param[in] n Pointer to an array of number
* @param[in] size Size of the array
* @return least common multiple
*/
unsigned lcm_arr(unsigned * n, unsigned size)
{
unsigned last_lcm, i;
if(size < 2) return 0;
last_lcm = lcm(n[0], n[1]);
for(i=2; i < size; i++)
{
last_lcm = lcm(last_lcm, n[i]);
}
return last_lcm;
}
于 2012-11-05T21:10:12.947 に答える
0
同様の問題を検索しているときにこれを見つけたので、思いついたものを 2 つの数値に貢献したいと思いました。
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
cin >> x >> y;
// zero is not a common multiple so error out
if (x * y == 0)
return -1;
int n = min(x, y);
while (max(x, y) % n)
n--;
cout << n << endl;
}
于 2014-09-30T02:26:04.477 に答える
0
#include<iostream>
using namespace std;
int lcm(int, int, int);
int main()
{
int a, b, c, ans;
cout<<"Enter the numbers to find its LCM"<<endl; //NOTE: LCM can be found only for non zero numbers.
cout<<"A = "; cin>>a;
cout<<"B = "; cin>>b;
cout<<"C = "; cin>>c;
ans = lcm(a,b,c);
cout<<"LCM of A B and C is "<<ans;
}
int lcm(int a, int b, int c){
static int i=1;
if(i%a == 0 && i%b == 0 && i%c ==0){ //this can be altered according to the number of parameters required i.e this is for three inputs
return i;
} else {
i++;
lcm(a,b,c);
return i;
}
}
于 2021-04-29T18:02:53.447 に答える
0
上記のコードは、複数の数値の LCM の評価についてのみ説明していますが、乗算を実行しているとき に、データ型ストレージの整数制限をオーバーフローする可能性が非常に高くなります
*コーナーケース:- *
たとえば、評価中に次のような状況に達した場合、 LCM_till_now=1000000000000000 next_number_in_list=99999999999999 および したがって GCD=1 (両者は互いに互いに素であるため)
したがって、操作 (LCM_till_now*next_number_in_list) を実行すると、「unsigned long long int」にも収まりません。
解決策:- 1.Big Integer Class を使用する 2.または、問題が LCM%MOD を要求している場合----------->モジュラー演算のプロパティを適用します。
于 2014-07-05T21:22:39.520 に答える
-1
#include
#include
void main()
{
clrscr();
int x,y,gcd=1;
cout<>x;
cout<>y;
for(int i=1;i<1000;++i)
{
if((x%i==0)&&(y%i==0))
gcd=i;
}
cout<<"\n\n\nGCD :"<
cout<<"\n\n\nLCM :"<<(x*y)/gcd;
getch();
}
于 2011-02-06T03:24:09.260 に答える
-1
このページを見ると、かなり単純なアルゴリズムを使用できることがわかります。:-)
効率的だと言っているわけではありませんが、概念的には複数の数値にスケーリングします。LCM が見つかるまで、元の数値と操作するクローン セットを追跡するためのスペースのみが必要です。
于 2010-11-19T22:28:44.660 に答える
-1
- lcm を計算したい数値の集合をシータとする
- 乗数 i を = 1 とする
- x = シータの最大数とする
- x * i
- theta のすべての要素 j について (x*i)%j=0 の場合、x*i は最小の LCM です。
- そうでない場合は、ループして i を 1 ずつ増やします
于 2013-10-01T06:34:25.690 に答える