Cum a face tu calcula cel mai mic multiplu comun a mai multor numere?
Până acum am'am fost doar posibilitatea de a calcula între două numere. Dar nu au nici o idee cum să-l extindă pentru a calcula 3 sau mai multe numere.
Până în prezent acest lucru este cum am făcut-o
LCM = num1 * num2 / gcd ( num1 , num2 )
Cu gcd este funcția pentru a calcula cel mai mare divizor comun pentru numerele. Folosind algoritmul euclidian
Dar nu pot't dau seama cum de a calcula pentru 3 sau mai multe numere.
În Python (modificat primes.py):
def gcd(a, b):
"""Return greatest common divisor using Euclid's Algorithm."""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""Return lowest common multiple."""
return a * b // gcd(a, b)
def lcmm(*args):
"""Return lcm of args."""
return reduce(lcm, args)
Utilizare:
>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560
reduce()
lucreaza ceva de genul care:
>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)
Aici's o ECMA-stil de punere în aplicare:
function gcd(a, b){
// Euclidean algorithm
var t;
while (b != 0){
t = b;
b = a % b;
a = t;
}
return a;
}
function lcm(a, b){
return (a * b / gcd(a, b));
}
function lcmm(args){
// Recursively iterate through pairs of arguments
// i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))
if(args.length == 2){
return lcm(args[0], args[1]);
} else {
var arg0 = args[0];
args.shift();
return lcm(arg0, lcmm(args));
}
}
Mi-ar merge cu aceasta (C#):
static long LCM(long[] numbers)
{
return numbers.Aggregate(lcm);
}
static long lcm(long a, long b)
{
return Math.Abs(a * b) / GCD(a, b);
}
static long GCD(long a, long b)
{
return b == 0 ? a : GCD(b, a % b);
}
Doar unele precizări, pentru că la prima vedere nu't cusături atât de clar de ce acest cod este de a face:
Agregate este o metoda de Extindere Linq, astfel încât să cant uitați să adăugați folosind Sistemul.Linq la referințe.
Agregate devine o acumulare de funcție, astfel încât să putem face uz de proprietate lcm(a,b,c) = cmmmc(a,lcm(b,c)) peste o IEnumerable. [Mai multe pe Agregat][1]
GCD calcul face uz de algoritmul Euclidian.
lcm de calcul utilizează Abs(a*b)/cmmdc(a,b) , se referă la Reducere de cel mai mare divizor comun.
Sper că acest lucru ajută,
[1]: https://msdn.microsoft.com/en-us/library/vstudio/bb548651(v=vs. 100).aspx
M-am gândit la asta în Haskell:
lcm' :: Integral a => a -> a -> a
lcm' a b = a`div`(gcd a b) * b
lcm :: Integral a => [a] -> a
lcm (n:ns) = foldr lcm' n ns
Chiar mi-am luat timp pentru a scrie propria mea `gcd funcția, doar pentru a găsi în Preludiul! O mulțime de învățare pentru mine ziua de azi :D
Unele cod Python care nu't nevoie de o funcție pentru gcd:
from sys import argv
def lcm(x,y):
tmp=x
while (tmp%y)!=0:
tmp+=x
return tmp
def lcmm(*args):
return reduce(lcm,args)
args=map(int,argv[1:])
print lcmm(*args)
Aici's ceea ce pare în terminal:
$ python lcm.py 10 15 17
510
Aici este un Python-o linie (nu de numărare importurilor) pentru a reveni la LCM de numere întregi de la 1 la 20 inclusiv:
Piton de 3,5+ importuri:
from functools import reduce
from math import gcd
Python 2.7 importurilor:
from fractions import gcd
Comune logica:
lcm = reduce(lambda x,y: x*y//gcd(x, y), range(1, 21))
Rețineți că, în ambele Python 2 și Python 3, operator de prioritate normele care prevăd că *
și //
operatorii au aceeași prioritate, și astfel încât acestea se aplică de la stânga la dreapta. Ca atare, x*y//z
înseamnă (x*y)//z "și nu" x*(y//z)
. Cei doi produc de obicei rezultate diferite. Acest lucru s-ar't au contat la fel de mult pentru float divizie dar nu pentru podea divizia.
Aici este o C# portul de Virgil Disgr4ce's implementarea:
public class MathUtils
{
/// <summary>
/// Calculates the least common multiple of 2+ numbers.
/// </summary>
/// <remarks>
/// Uses recursion based on lcm(a,b,c) = lcm(a,lcm(b,c)).
/// Ported from http://stackoverflow.com/a/2641293/420175.
/// </remarks>
public static Int64 LCM(IList<Int64> numbers)
{
if (numbers.Count < 2)
throw new ArgumentException("you must pass two or more numbers");
return LCM(numbers, 0);
}
public static Int64 LCM(params Int64[] numbers)
{
return LCM((IList<Int64>)numbers);
}
private static Int64 LCM(IList<Int64> numbers, int i)
{
// Recursively iterate through pairs of arguments
// i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))
if (i + 2 == numbers.Count)
{
return LCM(numbers[i], numbers[i+1]);
}
else
{
return LCM(numbers[i], LCM(numbers, i+1));
}
}
public static Int64 LCM(Int64 a, Int64 b)
{
return (a * b / GCD(a, b));
}
/// <summary>
/// Finds the greatest common denominator for 2 numbers.
/// </summary>
/// <remarks>
/// Also from http://stackoverflow.com/a/2641293/420175.
/// </remarks>
public static Int64 GCD(Int64 a, Int64 b)
{
// Euclidean algorithm
Int64 t;
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
}'
Funcția de a găsi lcm de orice listă de numere:
def function(l):
s = 1
for i in l:
s = lcm(i, s)
return s
Folosind LINQ ai putea scrie:
static int LCM(int[] numbers)
{
return numbers.Aggregate(LCM);
}
static int LCM(int a, int b)
{
return a * b / GCD(a, b);
}
Ar trebui să adaug folosind Sistemul.Linq;
și nu't uitați să se ocupe de excepții ...
Aici este în Rapid.
// Euclid's algorithm for finding the greatest common divisor
func gcd(_ a: Int, _ b: Int) -> Int {
let r = a % b
if r != 0 {
return gcd(b, r)
} else {
return b
}
}
// Returns the least common multiple of two numbers.
func lcm(_ m: Int, _ n: Int) -> Int {
return m / gcd(m, n) * n
}
// Returns the least common multiple of multiple numbers.
func lcmm(_ numbers: [Int]) -> Int {
return numbers.reduce(1) { lcm($0, $1) }
}
În R, putem folosi funcții mGCD(x) și mLCM(x) din pachet numere, pentru a calcula cel mai mare divizor comun și cel mai mic multiplu comun pentru toate numerele din întreg vector x împreună:
library(numbers)
mGCD(c(4, 8, 12, 16, 20))
[1] 4
mLCM(c(8,9,21))
[1] 504
# Sequences
mLCM(1:20)
[1] 232792560
Aici este PHP punerea în aplicare:
// https://stackoverflow.com/q/12412782/1066234
function math_gcd($a,$b)
{
$a = abs($a);
$b = abs($b);
if($a < $b)
{
list($b,$a) = array($a,$b);
}
if($b == 0)
{
return $a;
}
$r = $a % $b;
while($r > 0)
{
$a = $b;
$b = $r;
$r = $a % $b;
}
return $b;
}
function math_lcm($a, $b)
{
return ($a * $b / math_gcd($a, $b));
}
// https://stackoverflow.com/a/2641293/1066234
function math_lcmm($args)
{
// Recursively iterate through pairs of arguments
// i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))
if(count($args) == 2)
{
return math_lcm($args[0], $args[1]);
}
else
{
$arg0 = $args[0];
array_shift($args);
return math_lcm($arg0, math_lcmm($args));
}
}
// fraction bonus
function math_fraction_simplify($num, $den)
{
$g = math_gcd($num, $den);
return array($num/$g, $den/$g);
}
var_dump( math_lcmm( array(4, 7) ) ); // 28
var_dump( math_lcmm( array(5, 25) ) ); // 25
var_dump( math_lcmm( array(3, 4, 12, 36) ) ); // 36
var_dump( math_lcmm( array(3, 4, 7, 12, 36) ) ); // 252
Du-te la credite @T3db0t cu răspunsul de mai sus (ECMA-cod de stil).
poti face un alt mod - Să fie n numere.Ia o pereche de numere consecutive și de a salva sale lcm într-o altă matrice. Face acest lucru la prima iterație program de lucru n/2 iterații.Apoi următorul ridica pereche incepand de la 0 ca (0,1) , (2,3) și așa mai departe.Calcula LCM și magazin într-o altă matrice. Faceți acest lucru până când sunteți plecat cu o matrice. (nu este posibil să se găsească lcm dacă n este impar)
Doar pentru distracție, un shell (aproape orice shell) punerea în aplicare:
#!/bin/sh
gcd() { # Calculate $1 % $2 until $2 becomes zero.
until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done
echo "$1"
}
lcm() { echo "$(( $1 / $(gcd "$1" "$2") * $2 ))"; }
while [ $# -gt 1 ]; do
t="$(lcm "$1" "$2")"
shift 2
set -- "$t" "$@"
done
echo "$1"
încercați să-l cu:
$ ./script 2 3 4 5 6
pentru a obține
60
Cea mai mare intrare și rezultatul ar trebui să fie mai mică decât (2^63)-1
sau coajă de matematica se va încheia.
ES6 stil
function gcd(...numbers) {
return numbers.reduce((a, b) => b === 0 ? a : gcd(b, a % b));
}
function lcm(...numbers) {
return numbers.reduce((a, b) => Math.abs(a * b) / gcd(a, b));
}
Și Scala versiune:
def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
def gcd(nums: Iterable[Int]): Int = nums.reduce(gcd)
def lcm(a: Int, b: Int): Int = if (a == 0 || b == 0) 0 else a * b / gcd(a, b)
def lcm(nums: Iterable[Int]): Int = nums.reduce(lcm)
am fost în căutarea pentru gcd și lcm de elementele de matrice și a găsit o soluție bună în link-ul următor.
https://www.hackerrank.com/challenges/between-two-sets/forum
care include următoarele cod. Algoritmul pentru gcd folosește Algoritmul Euclidian a explicat bine in link-ul de mai jos.
private static int gcd(int a, int b) {
while (b > 0) {
int temp = b;
b = a % b; // % is remainder
a = temp;
}
return a;
}
private static int gcd(int[] input) {
int result = input[0];
for (int i = 1; i < input.length; i++) {
result = gcd(result, input[i]);
}
return result;
}
private static int lcm(int a, int b) {
return a * (b / gcd(a, b));
}
private static int lcm(int[] input) {
int result = input[0];
for (int i = 1; i < input.length; i++) {
result = lcm(result, input[i]);
}
return result;
}
GCD are nevoie de un pic de corecție pentru numere negative:
def gcd(x,y):
while y:
if y<0:
x,y=-x,-y
x,y=y,x % y
return x
def gcdl(*list):
return reduce(gcd, *list)
def lcm(x,y):
return x*y / gcd(x,y)
def lcml(*list):
return reduce(lcm, *list)