Нахождение неизвестных множителя, делимого или делителя

В данный момент вы не можете посмотреть или раздать видеоурок ученикам

Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.

Получите невероятные возможности

1. Откройте доступ ко всем видеоурокам комплекта. 2. Раздавайте видеоуроки в личные кабинеты ученикам. 3. Смотрите статистику просмотра видеоуроков учениками.

Нет, спасибо

Получить доступ

Нахождение неизвестного множителя

Посмотрим на два уравнения: x·2=20 и 3·x=12. В обоих нам известно значение произведения и один из множителей, необходимо найти второй. Для этого нам надо воспользоваться другим правилом.

Определение 4

Для нахождения неизвестного множителя нужно выполнить деление произведения на известный множитель.

Данное правило базируется на смысле, который является обратным смыслу умножения. Между умножением и делением есть следующая связь: a·b=c при a и b, не равных , c: a=b, c: b=c и наоборот.

Пример 4

Вычислим неизвестный множитель в первом уравнении, разделив известное частное 20 на известный множитель 2. Проводим деление натуральных чисел и получаем 10. Запишем последовательность равенств: x·2=20x=20:2x=10. Подставляем десятку в исходное равенство и получаем, что 2·10=20. Значение неизвестного множителя было выполнено правильно.

Уточним, что в случае, если один из множителей нулевой, данное правило применять нельзя. Так, уравнение x·=11 с его помощью решить мы не можем. Эта запись не имеет смысла, поскольку для решения надо разделить 11 на , а деление на нуль не определено. Подробнее о подобных случаях мы рассказали в статье, посвященной линейным уравнениям.

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

Видео

Расширенный алгоритм Евклида*

Очень важным для математики свойством наибольшего общего делителя является следующий факт:

Для любых целых \(a, b\) найдутся такие целые \(x, y\), что \(ax + by = d\), где \(d = \gcd(a, b)\).

Из этого следует, что существует решение в целых числах, например, у таких уравнений: * \(8x + 6y = 2\) * \(4x — 5y = 1\) * \(116x + 44y = 4\) * \(3x + 11y = -1\)

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

Рассмотрим один шаг алгоритма Евклида, преобразующий пару \((a, b)\) в пару \((b, a \operatorname{\%} b)\). Обозначим \(r = a \operatorname{\%} b\), то есть запишем деление с остатком в виде \(a = bq + r\).

Предположим, что у нас есть решение данного уравнения для чисел \(b\) и \(r\) (их наибольший общий делитель, как известно, тоже равен \(d\)): \[bx_0 + ry_0 = d\]

Теперь сделаем в этом выражении замену \(r = a — bq\):

\[bx_0 + ry_0 = bx_0 + (a — bq)y_0 = ay_0 + b(x_0 — qy_0)\]

Tаким образом, можно взять \(x = y_0\), а \(y = (x_0 — qy_0) = (x_0 — (a \operatorname{/} b)y_0)\) (здесь \(/\) обозначает целочисленное деление).

В конце алгоритма Евклида мы всегда получаем пару \((d, 0)\). Для нее решение требуемого уравнения легко подбирается — \(d * 1 + 0 * 0 = d\). Теперь, используя вышесказанное, мы можем идти обратно, при вычислении заменяя пару \((x, y)\) (решение для чисел \(b\) и \(a \operatorname{\%} b\)) на пару \((y, x — (a / b)y)\) (решение для чисел \(a\) и \(b\)).

Это удобно реализовывать рекурсивно:

Но также полезно и посмотреть, как будет работать расширенный алгоритм Евклида и на каком-нибудь конкретном примере. Пусть мы, например, хотим найти целочисленное решение такого уравнения: \[116x + 44y = 4\] \[(2\times44+28)x + 44y = 4\] \[44(2x+y) + 28x = 4\] \[44x_0 + 28y_0 = 4\] Следовательно, \[x = y_0, y = x_0 — 2y_0\] Будем повторять такой шаг несколько раз, получим такие уравнения: \[116x + 44y = 4\] \[44x_0 + 28y_0 = 4, x = y_0, y = x_0 — 2y_0\] \[28x_1 + 16y_1 = 4, x_0 = y_1, y_0 = x_1 — y_1\] \[16x_2 + 12y_2 = 4, x_1 = y_2, y_1 = x_2 — y_2\] \[12x_3 + 4y_3 = 4, x_2 = y_3, y_2 = x_3 — y_3\] \[4x_4 + 0y_4 = 4, x_3 = y_4, y_3 = x_4 — 3 y_4\] А теперь свернем обратно: \[x_4 = 1, y_4 = 0\] \[x_3 = 0, y_3 =1\] \[x_2 = 1, y_2 =-1\] \[x_1 = -1, y_1 =2\] \[x_0 = 2, y_0 =-3\] \[x = -3, y =8\]

Действительно, \(116\times(-3) + 44\times8 = 4\)

Решето Эратосфена

Часто нужно не проверять на простоту одно число, а найти все простые числа до \(N\). В этом случае наивный алгоритм будет работать за \(O(N\sqrt N)\), так как нужно проверить на простоту каждое число от 1 до \(N\).

Но древний грек Эратосфен предложил делать так:

Запишем ряд чисел от 1 до \(N\) и будем вычеркивать числа: * делящиеся на 2, кроме самого числа 2 * затем деляющиеся на 3, кроме самого числа 3 * затем на 5, затем на 7, и так далее и все остальные простые до n. Таким образом, все незачеркнутые числа будут простыми — «решето» оставит только их.

Красивая визуализация

Задание

Найдите этим способом на бумажке все простые числа до 50, потом проверьте с программой:

У этого алгоритма можно сразу заметить несколько ускорений.

Во-первых, число \(i\) имеет смысл перебирать только до корня из \(N\), потому что при зачеркивании составных чисел, делящихся на простое \(i > \sqrt N\), мы ничего не зачеркнем. Почему? Пусть существует составное \(M \leq N\), которое делится на %i%, и мы его не зачеркнули. Но тогда \(i > \sqrt N \geq \sqrt M\), а значит по ранее нами доказанному утверждению \(M\) должно делиться и на простое число, которое меньше корня. Но это значит, что мы его уже вычеркнули.

Во-вторых, по этой же самое причине \(j\) имеет смысл перебирать только начиная с \(i^2\). Зачем вычеркивать \(2i\), \(3i\), \(4i\), …, \((i-1)i\), если они все уже вычеркнуты, так как мы уже вычеркивали всё, что делится на \(2\), \(3\), \(4\), …, \((i-1)\).

Асимптотика

Такой код будет работать за \(O(N \log \log N)\) по причинам, которые мы пока не хотим объяснять формально.

Гармонический ряд

Научимся оценивать асимптотику величины \(1 + \frac{1}{2} + \ldots + \frac{1}{N}\), которая нередко встречается в задачах, где фигурирует делимость.

Возьмем \(N\) равное \(2^i — 1\) и запишем нашу сумму следующим образом: \[\left(\frac{1}{1}\right) + \left(\frac{1}{2} + \frac{1}{3}\right) + \left(\frac{1}{4} + \ldots + \frac{1}{7}\right) + \ldots + \left(\frac{1}{2^{i — 1}} + \ldots + \frac{1}{2^i — 1}\right)\]

Каждое из этих слагаемых имеет вид \[\frac{1}{2^j} + \ldots + \frac{1}{2^{j + 1} — 1} \le \frac{1}{2^j} + \ldots + \frac{1}{2^j} = 2^j \frac{1}{2^j} = 1\]

Таким образом, наша сумма не превосходит \(1 + 1 + \ldots + 1 = i \le 2\log_2(2^i — 1)\). Тем самым, взяв любое \(N\) и дополнив до степени двойки, мы получили асимптотику \(O(\log N)\).

Оценку снизу можно получить аналогичным образом, оценив каждое такое слагаемое снизу значением \(\frac{1}{2}\).

Попытка объяснения асимптотики** (для старших классов)

Мы знаем, что гармонический ряд \(1 + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{N}\) это примерно \(\log N\), а значит \[N + \frac{N}{2} + \frac{N}{3} + \ldots + \frac{N}{N} \sim N \log N\]

А что такое асимптотика решета Эратосфена? Мы как раз ровно \(\frac{N}{p}\) раз зачеркиваем числа делящиеся на простое число \(p\). Если бы все числа были простыми, то мы бы как раз получили \(N \log N\) из формули выше. Но у нас будут не все слагаемые оттуда, только с простым \(p\), поэтому посмотрим чуть более точно.

Известно, что простых чисел до \(N\) примерно \(\frac{N}{\log N}\), а значит допустим, что k-ое простое число примерно равно \(k ln k\). Тогда

\[\sum_{\substack{2 \leq p \leq N \\ \text{p is prime}}} \frac{N}{p} \sim \frac{1}{2} + \sum_{k = 2}^{\frac{N}{\ln N}} \frac{N}{k \ln k} \sim \int_{2}^{\frac{N}{\ln N}} \frac{N}{k \ln k} dk =N(\ln\ln\frac{N}{\ln N} — \ln\ln 2) \sim N(\ln\ln N — \ln\ln\ln N) \sim N \ln\ln N\]

Но вообще-то решето можно сделать и линейным.

Последовательное применение правил

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

Пример 7

У нас есть уравнение вида 3·x+1=7. Вычисляем неизвестное слагаемое 3·x, отняв от 7 единицу. Получим в итоге 3·x=7−1, потом 3·x=6. Это уравнение решить очень просто: делим 6 на 3 и получаем корень исходного уравнения. Вот краткая запись решения еще одного уравнения (2·x−7):3−5=2: (2·x−7):3−5=2,(2·x−7):3=2+5,(2·x−7):3=7,2·x−7=7·3,2·x−7=21,2·x=21+7,2·x=28,x=28:2,x=14.

Всё ещё сложно? Наши эксперты помогут разобраться Все услуги

Теги

Популярные:

Последние:

Adblock
detector