Lcm что это такое в математике

Документация

L = lcm( A,B ) возвращает наименьших общих кратных элементов A и B .

Примеры

Наименьшие общие кратные двойного массива и скаляра

A = [5 17; 10 60]; B = 45; L = lcm(A,B)

L = 2×2 45 765 90 180

Наименьшие общие кратные Целых чисел без знака

A = uint16([255 511 15]); B = uint16([15 127 1023]); L = lcm(A,B)

L = 1x3 uint16 row vector 255 64897 5115

Входные параметры

A,B — Входные значения
скаляры, векторы или массивы действительных, положительных целочисленных значений

Входные значения в виде скаляров, векторов или массивов действительных, положительных целочисленных значений. A и B может быть любой числовой тип, и они могут иметь различные типы в рамках определенных ограничений:

Если A или B имеет тип single , затем другой может иметь тип single или double .
Если A или B принадлежит целочисленному классу, затем другой должен принадлежать тому же классу, или это должен быть double скалярное значение.

A и B должен быть одного размера или нужно быть скаляром.

Пример: [20 3 13],[10 6 7]

Пример: int16([100 30 200]),int16([20 15 9])

Пример: int16([100 30 200]),20

Выходные аргументы

L — Наименьшее общее кратное
действительные, положительные целочисленные значения

Наименьшее общее кратное, возвращенное как массив действительных положительных целочисленных значений. L одного размера с A и B , и это имеет тот же тип как A и B . Если A и B имеют различные типы, затем L возвращен как недвойной тип.

Расширенные возможности

Генерация кода C/C++
Генерация кода C и C++ с помощью MATLAB® Coder™.

Основанная на потоке среда
Запустите код в фоновом режиме с помощью MATLAB® backgroundPool или ускорьте код с Parallel Computing Toolbox™ ThreadPool .

Эта функция полностью поддерживает основанные на потоке среды. Для получения дополнительной информации смотрите функции MATLAB Запуска в Основанной на потоке Среде.

Смотрите также

Представлено до R2006a

Открытый пример

У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?

Документация MATLAB

Поддержка

MATLAB Answers
Помощь в установке
Отчеты об ошибках
Требования к продукту
Загрузка программного обеспечения

Условия использования
Патенты
Торговые марки
Список благодарностей

Для просмотра документации необходимо авторизоваться на сайте
Войти
Памятка переводчика

1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.

2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.

3. Сохраняйте структуру оригинального текста — например, не разбивайте одно предложение на два.

4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.

5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.

Математика нужна программистам, или задача, которую мне пришлось решать

Я работаю над WebRTC — фреймворком для аудио-видео конференций (или звонков? проще говоря — real time communication). В этой статье я хочу описать интересную задачу и как она была решена. В задаче, по сути, потребовалось минимизировать lcm нескольких вещественных чисел с дополнительными ограничениями. Пришлось применить совсем чуть чуть теории чисел или хотя бы логики.

Если вам интересна только задача — то можете смело проматывать до секции «Формулировка задачи». Следующая секция объясняет откуда она такая взялась и в чем ее смысл.

Введение

Клиенты могут настроить WebRTC кодировать входящий поток сразу в нескольких разрешениях. Например, это может быть полезно в видео конференциях: каждый клиент посылает на сервер несколько потоков с разным разрешением и битрейтом, а сервер пересылает всем остальным только тот поток, который помещается в пропускную способность до клиента.

Но нельзя просто задать желаемые разрешения, нет — это было бы слишком просто. Дело в том, что источник (например, камера в хроме) может выдавать видео какого угодно разрешения. А еще есть механизм обратной связи и при высокой нагрузке на CPU входящее разрешение снижается. Короче говоря, пользователь задает коэффициенты масштабирования. Потом входящий кадр сжимается в заданное количество раз, кодируется и отправляется по сети получателям.

Проблема в том, что некоторые энкодеры не работают с произвольными изображениями — им обязательно нужны четные размеры. А еще есть всякие оптимизации при кодировании, если соотношение разрешения у разных изображений целое. А главное, если у разных потоков будет разное соотношение сторон то при переключении между ними будет весьма заметный рывок. Поэтому надо, чтобы входящее разрешение нацело делилось на все коэффициенты.

Самый эффективный способ этого добиться, это требовать от источника, чтобы разрешение делилось на некоторое заданное число: alignment . Например, для стандартных коэффициентов и требования четности для энкодера, можно легко попросить у источника alignment=8 . Источник чуть-чуть обрежет изображения. Это приведет к незначительному искажению соотношения сторон у видео, зато сделает переключение между потоками незаметным. В итоге, входящее разрешение, кратное 8 можно спокойно делить в 1, 2 или 4 раза и получать четное разрешение, которое енкодер с радостью закодирует.

Но что делать, если заданы коэффициенты ? Минимальное целое, «делящееся» нацело на все эти коэффициенты — 391. А чтобы результат был четным, нужно вообще взять 782. Согласитесь, это весьма нагло требовать от источника выдавать разрешение, делящееся на 782. Это значит, что даже VGA (640×480) видео уже не послать вообще никак. На практике — максимально допустимое выравнивание, которое мы можем попросить должно быть ограничено, чтобы, во-первых, допускать маленькие разрешения и, во-вторых, не очень сильно искажать соотношение сторон.

Но, раз уж мы уже немного искажаем настройки пользователя, округляя входящее разрешение, то почему бы и не округлить чуть чуть коэффициенты масштабирования? Например, можно было бы взять коэффициенты вместо и получить необходимую делимость в 48 (сильно лучше 782). Если еще больше поменять коэффициенты, то можно получить и меньшее выравнивание.

Формулировка задачи

Или словами: минимизировать искажение коэффициентов и найти какое-то выравнивание А в допустимых пределах, так чтобы это значение делилось нацело на все новые коэффициенты, плюс требование по выравниванию энкодера.

Решение

В задаче и так много неизвестных, так что первая мысль — это зафиксировать хоть что-то. Переменная отлично подходит на эту роль. Она может принимать лишь значений и из предметной области получается что довольно маленькое (эвристически оно было закреплено на значении 16). Поэтому первый шаг — перебрать все возможные значениярешить задачи и выбрать то решение, которое имеет наименьшее значение целевой функции.

Следующее наблюдение — можно оптимизировать все коэффициенты масштабирования независимо друг от друга, соблюдая условие (1), ведь в целевую функцию они входят отдельными слагаемыми. Далее сфокусируемся на i-ом коэффициенте.

Поскольку в условии , то получается, что или. Потому что только рациональные числа можно домножить и поделить на целое и получить в итоге целое.

Можно потребовать, чтобы дробь была неприводимая:

Подставим дробь в (1) и получим откуда следует, что

(запись означает: левая часть делит правую).

Тут немного теории чисел или просто логики. взаимно просто с по условию, но делит правую часть. Значит целиком содержится в оставшемся множителе или , отсюда можно записать

Далее, домножим обе части уравнения (2) на :

Подставим выражение (3) для выше:

Раз левая часть делит правую, то можно переписать уравнение так:

Теперь вспомним выражение для в виде дроби и домножим числитель и знаменатель на и применим (3) и (4):

Добавив к этому условие, что коэффициенты не могут быть меньше 1 (ведь растягивать изображения смысла вообще нет) мы получим:

Таким образом, из условия (1) мы получили (5) и (6), которые говорят, что искомый коэффициент должен быть представим в виде дроби у которой числитель равен , а знаменатель делиться на и не превосходит числитель. При чем любая такая дробь нам подходит. Из (6) следует что таких дробей мало, а значит их все можно перебрать.

А можно и не перебирать. Ведь целевая функция, если рассматривать непрерывнуювыпуклая и имеет минимум, равный 0, в точке . Значит, достаточно рассмотреть 2 ближайших целых значения . Все, что левее левой точки — хуже ее, ведь она сама левее минимума выпуклой функции. Аналогично и с правой точкой. Еще надо аккуратно проверить, что эти точки положительные и удовлетворяют (6).

Итого, получаем такое решение (тут для простоты нет проверок входных данных):

const int kMaxAlignment = 16; // Находит лучшее приближение scale_factor (S_i) при заданном // выравнивании энкодера (d) и результирующем выравнивании источника (A). // Ошибка приближения прибавляется к error_acc. float GetApprox(int encoder_alignment, int requested_alignment, float scale_factor, float *error_acc) < int k = static_cast((requested_alignment + 0.0) / (encoder_alignment * scale_factor)); float best_error = 1e90; float best_approx = 1.0; for (int i = 0; i < 2; i++, k++) < if (k == 0 || k * encoder_alignment >requested_alignment) continue; float approx = (requested_alignment +0.0) / (k * encoder_alignment); float error = (approx - scale_factor) * (approx - scale_factor); if (error < best_error) < best_error = error; best_approx = approx; >> *error_acc += best_error; return best_approx; > // Решает задачу. Возвращает измененные коэффициенты (S'_i) // и результирующее выравнивание (A) в параметре requested_alignment. std::vector CalulateAlignmentAndScaleFactors( int encoder_alignment, std::vector scale_factors, int *requested_alignment) < float best_error = 1e90; int best_alignment = 1; std::vectorbest_factors; std::vector cur_factors; for (int a = 1; a if (cur_error < best_error) < best_error = cur_error; best_factors = cur_factors; best_alignment = a; >> *requested_alignment = best_alignment; return best_factors; >

Заключение

Мне кажется, это хороший пример, когда программисту нужна математика. Без математических рассуждений выше совершенно непонятно, почему этот код находит лучшее решение и откуда он вообще взялся. Без формальной записи задачи вообще непонятно, как к ней подступиться.

Да, без математики еще можно убедить себя, что выданные этим кодом коэффициенты будут подходить под условие задачи (числитель делит вычисленное выравнивание, поэтому все поделиться нацело, а знаменатель дает делимость на необходимое выравнивание для энкодера). Но без цепочки рассуждений (1) => (4),(5) вообще неясно, как этот код находит оптимальное решение.

Наименьшее общее кратное

Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка. Обозначается одним из следующих способов:

Пример: НОК(16, 20) = 80.

Наименьшее общее кратное для нескольких чисел — это наименьшее натуральное число, которое делится на каждое из этих чисел.

Одно из наиболее частых применений НОК — приведение

Свойства [ ]

Коммутативность: lcm ⁡ ( a , b ) = lcm ⁡ ( b , a ) . (a,b)=\operatorname (b,a).>
Ассоциативность: lcm ⁡ ( a , lcm ⁡ ( b , c ) ) = lcm ⁡ ( lcm ⁡ ( a , b ) , c ) . (a,\operatorname (b,c))=\operatorname (\operatorname (a,b),c).>
Связь с наибольшим общим делителем gcd(a,b): lcm ⁡ ( a , b ) = | a ⋅ b | gcd ⁡ ( a , b ) . (a,b)=<\operatorname (a,b)>>.>
В частности, если a и b — взаимно-простые числа , то: lcm ⁡ ( a , b ) = a ⋅ b . (a,b)=a\cdot b.>
lcm ⁡ ( a 1 n , a 2 n , . . . , a k n ) = ( lcm ⁡ ( a 1 , a 2 , . . . , a k ) ) n (a_^,a_^. a_^)=(\operatorname (a_,a_. a_))^> при n ⩾ 0
Наименьшее общее кратное двух целых чисел m и n является делителем всех других общих кратных m и n . Более того, множество общих кратных m, n совпадает с множеством кратных для НОК(m, n).
lcm ⁡ ( 1 , 2 , … , n ) (1,2,\ldots ,n)> могут быть выражены через некоторые теоретико-числовые функции. Так, функция Чебышёва ψ ( x ) = ln ⁡ lcm ⁡ ( 1 , 2 , … , ⌊ x ⌋ ) <\displaystyle \psi (x)=\ln \operatorname (1,2,\ldots ,\lfloor x\rfloor )> . А также:
- lcm ⁡ ( 1 , 2 , … , n ) ⩽ g ( n ( n + 1 ) 2 ) ∼ e n ( n + 1 ) 2 ln ⁡ n ( n + 1 ) 2 (1,2,\ldots ,n)\leqslant g\left(>\right)\sim e^<\sqrt <>\ln >>>> . Это следует из определения и свойств lcm ⁡ ( 1 , 2 , … , n ) ∼ e n + o ( 1 ) (1,2,\ldots ,n)\sim e^> , что следует из Нахождение НОК [ ]
- lcm ⁡ ( a , b , c ) = lcm ⁡ ( lcm ⁡ ( a , b ) , c ) ; (a,b,c)=\operatorname (\operatorname (a,b),c);>
- lcm ⁡ ( a 1 , a 2 , … , a n ) = lcm ⁡ ( lcm ⁡ ( a 1 , a 2 , … , a n − 1 ) , a n ) . (a_,a_,\ldots ,a_)=\operatorname (\operatorname (a_,a_,\ldots ,a_),a_).>
См. также [ ]

Литература [ ]
- Виноградов И. М.Основы теории чисел. М.-Л.: Гос. изд. технико-теоретической литературы, 1952, 180 с.
Перевод «least common multiple» на русский

Those three numbers are all prime, so multiplying them together will give us their least common multiple: 1001.

Все три — простые числа, поэтому, перемножив их, мы получим их наименьшее общее кратное — 1001.
To do this, we simply scale up the number of branches to the least common multiple.
Чтобы это сделать достаточно увеличить число веток до наименьшего общего кратного.
There are special cases of determining the least common multiple.
Существуют частные случаи определения наименьшего общего кратного.
Returns the least common multiple of one or more integers.
Возвращает наименьшее общее кратное для одного или нескольких целых чисел.

One can erase any two distinct integers and write their greatest common divisor and least common multiple instead.

За одну операцию вместо двух чисел, не делящих друг друга, можно написать их наибольший общий делитель и их наименьшее общее кратное.

Students often meet among the her math homework the following formulation: «find the least common multiple of numbers».

Школьники часто встречают среди заданий по математике такую формулировку: «найдите наименьшее общее кратное чисел».

The least common multiple is being used when finding a common denominator for working with fractions.

Наименьшее общее кратное используется при поиске общего знаменателя нескольких дробей.

After I do a couple of these problems you should be able to go to the least common multiple module and do some of them yourselves.

После того как я сделал пару из этих проблем вы сможете перейти на наименьшее общее кратное модуль и сделать некоторые из них сами.

Finding least common multiple: basic concepts
Нахождение наименьшего общего кратного: основные понятия.
This is the least common multiple of the orders of the elements of the group.
Пусть теперь — наименьшее общее кратное порядков всех элементов группы.
The integers in the following ten sets all have a least common multiple of 6
Целые числа следующих десяти множеств все имеют наименьшее общее кратное 6
Let L(n) denote the least common multiple of the numbers 1 through n.
Пусть L(n) обозначает наименьшее общее кратное всех чисел от 1 до n включительно.
The function lcm(a, b) denotes the least common multiple of a and b.
Функция lcm(a, b) обозначает наименьшее общее кратное чисел a и b.
Divisibility: greatest common divisor and least common multiple, Euclid’s algorithm.
Основы теории делимости: наибольший общий делитель, наименьшее общее кратное, алгоритм Евклида.

If you want to find the least common multiple of relatively Prime numbers that do not have the same divisors, their NOC will be equal to their product.

Если необходимо найти наименьшее общее кратное взаимно простых чисел, не имеющих одинаковых делителей, то их НОК будет равняться их произведению.

Find the pairs of natural numbers whose least common multiple is 78 and the greatest common divisor is 13.

Найдите все пары натуральных чисел, наименьшее общее кратное которых равно 78, наибольший общий делитель равен 13

So the brute force method is literally just to write down all the multiples of the two numbers and figure out what the least common multiple they have is.

Таким образом, метод грубой силы буквально записать все кратные из двух чисел и выяснить, что наименьшее общее кратное у них есть.

Because for smaller numbers like 8 or 10 or two and 3, it’s pretty easy to just think about the multiples and figure out the least common multiple.

Потому что для меньших количествах, как 8 или 10 или два, и 3, это довольно легко думать только о кратных и выяснить, наименьшее общее кратное.

If the numbers are large, or need to find the least common multiple of three or more numbers, it is better to use a different method to calculate the NOC.

Если числа большие, или нужно найти наименьшее общее кратное трех и более чисел, то лучше использовать другой способ вычисления НОК.

Возможно неприемлемое содержание

Примеры предназначены только для помощи в переводе искомых слов и выражений в различных контекстах. Мы не выбираем и не утверждаем примеры, и они могут содержать неприемлемые слова или идеи. Пожалуйста, сообщайте нам о примерах, которые, на Ваш взгляд, необходимо исправить или удалить. Грубые или разговорные переводы обычно отмечены красным или оранжевым цветом.

Зарегистрируйтесь, чтобы увидеть больше примеров. Это просто и бесплатно
Ничего не найдено для этого значения.
Предложить пример
Больше примеров Предложить пример

Новое: Reverso для Mac

Переводите текст из любого приложения одним щелчком мыши .

Скачать бесплатно
Перевод голосом, функции оффлайн, синонимы, спряжение, обучающие игры

Результатов: 41 . Точных совпадений: 41 . Затраченное время: 89 мс

Помогаем миллионам людей и компаний общаться более эффективно на всех языках.
Похожие публикации: