Документация
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
Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64
Выходные аргументы
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
- Помощь в установке
- Отчеты об ошибках
- Требования к продукту
- Загрузка программного обеспечения
© 1994-2021 The MathWorks, Inc.
- Условия использования
- Патенты
- Торговые марки
- Список благодарностей
Для просмотра документации необходимо авторизоваться на сайте
Войти
Памятка переводчика
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста — например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.
Документация
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
Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64
Выходные аргументы
L Наименьшее общее кратное
действительные, положительные целочисленные значения
Наименьшее общее кратное, возвращенное как массив действительных положительных целочисленных значений. L одного размера как A и B , и это имеет тот же тип как A и B . Если A и B имеют различные типы, то L возвращен как недвойной тип.
Расширенные возможности
Генерация кода C/C++
Генерация кода C и C++ с помощью MATLAB® Coder™.
Смотрите также
Представлено до R2006a
Документация MATLAB
Поддержка
- MATLAB Answers
- Помощь в установке
- Отчеты об ошибках
- Требования к продукту
- Загрузка программного обеспечения
© 1994-2019 The MathWorks, Inc.
- Условия использования
- Патенты
- Торговые марки
- Список благодарностей
Для просмотра документации необходимо авторизоваться на сайте
Войти
Памятка переводчика
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) вообще неясно, как этот код находит оптимальное решение.
Наименьшее общее кратное
где a и b — это натуральные числа, НОД — наибольший общий делитель.
Решение задачи на языке программирования Python
Из условия задачи ясно, чтобы найти НОК, надо сначала найти НОД. Последний можно вычислить, постепенно находя остаток от деления большего числа из пары на меньшее и присваивая остаток переменной, связанной с большим числом (см. алгоритм Евклида). В какой-то момент значение одной из переменных станет равным 0. Когда это произойдет, другая будет содержать НОД. Если неизвестно, какая именно переменная содержит НОД, то можно просто сложить значения обоих переменных.
В коде ниже используется функция для нахождения НОК, которая принимает два числа и возвращает найденное наименьшее общее кратное.
В основной ветке программы функция вызывается в цикле, который завершается, если то, что было введено, нельзя преобразовать к целому. В этом случае генерируется исключение и поток выполнения переходит к ветке except .
def lcm(a, b): m = a * b while a != 0 and b != 0: if a > b: a %= b else: b %= a return m // (a + b) while 1: try: x = int(input('a = ')) y = int(input('b = ')) print('НОК:', lcm(x, y)) except ValueError: break
a = 14 b = 18 НОК: 126 a = 105 b = 305 НОК: 6405 a = stop
В модуле math языка программирования Python есть функция для нахождения наибольшего общего делителя ( gcd — greatest common devisor). При ее использовании наша функция вычисления наименьшего общего кратного lcm (least common multiple) упрощается.
def lcm(a, b): import math return (a * b) // math.gcd(a, b)
X Скрыть Наверх
Решение задач на Python