e-olymp 446. Ровные делители

Задача

Натуральное число $m$ называется ровным делителем числа $n$, если частное и остаток от деления $n$ на $m$ равны. По заданному натуральному числу $n$ найти количество его ровных делителей.

Входные данные

Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.

Выходные данные

Выведите искомое количество ровных делителей числа $n$.

Тесты

Входные данные Выходные данные
5 1
20 2
200 6
653 1
5982 4

Код программы

Решение

Для решения этой задачи сперва введем переменную q, в которой будем хранить количество ровных делителей числа $n$. Затем запустим цикл, который будет проверять каждое из чисел от $1$ до $n$ включительно, является ли оно ровным делителем. Если условие выполняется, то увеличиваем значение, хранящееся в q на единицу. После цикла выведем искомое на экран.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

e-olymp 58. Биллиард

Задача


Биллиард представляет собой прямоугольник размерами $M \times N$, где $M$ и $N$ — натуральные числа. Из верхней левой лузы вылетает шар под углом $45^{\circ}$ к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

Входные данные

Во входной строке два числа $M$ и $N$, $1 ≤ M, N ≤ 2000000000$. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. $M$ — горизонтальная сторона биллиарда, $N$ — вертикальная сторона биллиарда.

Выходные данные

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные Выходные данные
2 1 1 2
5 6 9 4
12 33 13 2
156 156 0 3
654 236 443 4

Код программы

Решение

Чтобы решить эту задачу, необходимо найти НОД значений $M$ и $N$ из условия. Для этого, сперва нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали во $2$ строке. Далее, в $8$ строке, введем перемененную g и присвоим ей значение НОД для $M$ и $N$. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

e-olymp 1482. Умножение матриц

Задача

Пусть даны две прямоугольные матрицы $A$ и $B$ размерности $m \times n$ и $n \times q$ соответственно:
$$A = \begin{bmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \ldots & a_{mn} \end{bmatrix} \; , \; B = \begin{bmatrix} b_{11} & b_{12} & \ldots & b_{1q} \\ b_{21} & b_{22} & \ldots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{n1} & b_{n2} & \ldots & b_{nq} \end{bmatrix} .$$
Тогда матрица $C$ размерностью $m \times q$ называется их произведением:
$$C = \begin{bmatrix} c_{11} & c_{12} & \ldots & c_{1q} \\ c_{21} & c_{22} & \ldots & c_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \ldots & c_{mq} \end{bmatrix} ,$$
где: $$c_{i,j} = \sum_{r=1}^{n} a_{i,r}b_{r,j} \; \left(i = 1, 2, \ldots m; j = 1, 2, \ldots q\right).$$
Операция умножения двух матриц выполнима только в том случае, если число столбцов в первом сомножителе равно числу строк во втором; в этом случае говорят, что форма матриц согласована.

Задано две матрицы $A$ и $B$. Найти их произведение.

Входные данные

В первой строке задано $2$ натуральных числа $n_a$ и $m_a$ – размерность матрицы $A$. В последующих $n_a$ строках задано по $m_a$ чисел – элементы $a_{ij}$ матрицы $A$. В $\left(n_a + 2\right)$-й строке задано $2$ натуральных числа $n_b$ и $m_b$ – размерность матрицы $B$. В последующих $n_b$ строках задано по $m_b$ чисел – элементы $b_{ij}$ матрицы $B$. Размерность матриц не превышает $100 \times 100$, все элементы матриц целые числа, не превышающие по модулю $100$.

Выходные данные

В первой строке вывести размерность итоговой матрицы $C$: $n_с$ и $m_c$. В последующих $n_с$ строках вывести через пробел по $m_c$ чисел – соответствующие элементы $c_{ij}$ матрицы $C$. Если умножать матрицы нельзя — в первой и единственной строке вывести число $\; -1$.

Тесты

Входные данные Выходные данные
2 3
1 3 4
5 -2 3
3 3
1 3 2
2 1 3
0 -1 1
2 3
7 2 15
1 10 7
3 3
1 5 3
2 6 1
7 -1 -3
3 2
3 6
-1 1
3 1
3 2
7 14
3 19
13 38
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
4 4
1 0 0 0
0 1 0 0
0 0 1 0
4 4
4 8 -18 16
3 7 14 -42
2 1 1 7
4 9 5 -2
3 3
5 7 -1
8 9 3
0 -6 17
2 3
7 -15 1
8 8 2
-1
2 3
57 -49 31
89 11 -37
3 1
19
-19
0
2 1
2014
1482

Код программы

 

Решение

Для начала, считываем данные матрицы $A$ из входного потока и записываем их в двумерный динамический массив. Далее, получив данные о размерности второй матрицы, мы можем определить, выполнима ли операция умножения, и если нет, то прервать выполнение программы. Если операция умножения данных матриц выполнима, то считываем и записываем данные второй матрицы, после чего, по приведённой выше формуле вычисляем произведение матриц $C = A \times B.$ Наконец, выводим полученную матрицу $C.$

Ссылки

Условие задачи на e-olymp
Код задачи на ideone
Умножение матриц на Wikipedia

e-olymp 2860. Сумма чисел на промежутке

Задача

Найти сумму целых чисел на промежутке от $a$ до $b$.

Входные данные

Два целых числа $a$ и $b$, по модулю не превышающих $10^9$.

Выходные данные

Сумма целых чисел на промежутке от $a$ до $b$.

Тесты

Входные данные Выходные данные
2 5 14
249 318 19845
23 69 2162
124 200 12474
478 653 99528

Код программы

Решение

Для того, что бы найти ответ, нам необходимо знание формул прогрессии, так как решением данной задачи является сумма $n$ первых членов арифметической прогрессии. Вычислить её можно по формуле $\displaystyle S_n = \frac{a_1 + a_n}{2} \cdot n$, где $a_1$ — это a из входного потока, а $a_n$ — это b. Тем не менее, мы все ещё не можем применить вышеприведенную формулу, так как нам неизвестно $n$. Выведем же его из формулы $n$-ого члена арифметической прогрессии: $a_n = a_1 + d \cdot (n-1)$, где $d$ — это разность арифметической прогрессии, которая по условию (хоть и негласно) равна единице. Зная это, из последней формулы выведем, что $n = a_n-a_1 + 1$. Теперь же, когда мы знаем все необходимые значения, остается только подсчитать сумму арифметической прогрессии по ранее данной формуле и подать результат на выход.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

e-olymp 112. Торт

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

Сколько времени потребуется толстякам, чтобы съесть весь праздничный торт вместе?

Входные данные

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $10000$.

Выходные данные

Вывести время в часах, за которое толстяки вместе могут съесть торт. Результат округлить до двух десятичных знаков.

TESTS

$t_1$

$t_2$

$t_3$

$t$

3 3 3 1.00
4 67 50 3.51
228.22 8 2.28 1.76
1577 157.7 15.77 14.21

C ветвлением:

Без ветвления:

 

Решение с ветвлением

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t_1}-\frac{t}{t_2}-\frac{t}{t_3}=0;$
$\frac{t}{t_1}+\frac{t}{t_2}+\frac{t}{t_3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t\left(t_1t_2+t_2t_3+t_1t_3\right)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Решение без ветвления

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $\left(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}\right)$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков. Для этого воспользуемся функцией setprecision() и её аргументом fixed

Ссылки

Условие задачи e-olymp
Код решения

A 325. Простые делители числа

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные выходные данные
2 2
7 7
50 2 5 5
169 13 13
583 11 53
2368 2 2 2 2 2 2 37
73890 2 3 3 5 821
885066 2 3 7 13 1621
6943960340 2 2 5 97 1787 2003

Код программы

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

KM208(a). Наибольшая разность чисел последовательности

Задача

Известно, что разность между наибольшим и наименьшим из вещественных чисел [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_{10}[/latex] равна [latex]1[/latex]. Какой наибольшей может быть разность между наибольшим и наименьшим из [latex]10[/latex] чисел [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_{10}}{10}[/latex]?

Каков будет ответ, если чисел не [latex]10[/latex], а [latex]n[/latex]?

Входные данные

Количество элементов последовательности [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_n[/latex].

Выходные данные

Наибольшая разность наибольшего и наименьшего элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n} {n}[/latex].

Тесты

Входные данные Выходные данные
2 0.5
4 0.75
6 0.833333
8 0.875

Код программы

Решение задачи

Выведем формулу сразу для [latex]n[/latex] чисел. Сделаем несколько предварительных замечаний.

Обозначим через [latex]y_k[/latex] число [latex]\frac{x_1+x_2+ \ldots+x_k}{k}[/latex], где [latex]k=1, 2, 3, \ldots, n[/latex]. Если прибавить ко всем [latex]x_i[/latex] некоторое число [latex]a[/latex], то вместо чисел [latex]y_i[/latex] мы получим числа [latex]y_i+a[/latex]. Максимальные разности для чисел [latex]y_i[/latex] и для [latex]y_i+a[/latex] совпадают. Поэтому от набора [latex]f\{x_i\}[/latex] с помощью подходящего выбора [latex]a[/latex] можно перейти к такому набору [latex]f\{x_i’\}[/latex], что все [latex]x_i’\le0[/latex], наименьшие [latex]x_i[/latex] равны нулю, а наибольшие — единице. В дальнейшем мы будем рассматривать только такие наборы. Аналогично, если заменить числа [latex]x_i[/latex] на [latex]1-x_i[/latex], то [latex]y_i[/latex] заменятся на [latex]1-y_i[/latex]. Следовательно, от набора [latex]f\{x_i\}[/latex] можно перейти к набору [latex]f\{1-x_i\}[/latex]: максимальные разности между числами [latex]y_i[/latex] и числами [latex]1-y_i[/latex] одинаковы.

Решим задачу. Пусть [latex]y_k[/latex] — наименьшее, а [latex]y_t[/latex] — наибольшее из чисел [latex]f\{y_i\}[/latex].

Если [latex]k<l[/latex], то [latex]y_l-y_k=\frac{k y_k}{l}+\frac{x_{k+1}+\ldots+x_l}{l}-y_k[/latex][latex]=\frac{x_{k+1}+\ldots+x_l}{l}-\frac{l-k}{l} y_k[/latex][latex]\le\frac{x_{k+1}+\ldots+x_l}{l}\le\frac{l-k}{l}\le1-\frac{k}{l}\le1-\frac{1}{n}[/latex]

Если же [latex]k>l[/latex], то [latex]y_l-y_k=\frac{k-l}{k} y_l-\frac{y_{l+1}+\ldots+y_k}{k}\le1-\frac{l}{k}\le1-\frac{1}{n}[/latex].

Из вышесказанного следует, что максимальная разность не больше [latex]1-\frac{1}{n}[/latex]. Набор с такой разностью можно легко указать: [latex]x_1=0[/latex], [latex]x_2=x_3=\ldots=x_n=1[/latex].

Л. Г. Лиманов
Научно-популярный журнал «Квант», 1974 год, №3, страницы 38-39.

Итог:
Формула, которую необходимо использовать для решения этой задачи, это [latex]D=1-\frac{1}{n}[/latex], где D — наибольшая разность элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n}{n}[/latex], а [latex]n[/latex] — их количество.

Ссылки

КМ26

Задача

Задача из журнала «Квант» №6 1970 г.
Предположим, что в каждом номере нашего журнала в задачнике «Кванта» будет пять задач по математике. Обозначим через [latex]f(x, y) [/latex] номер первой из задач [latex]x[/latex]-го номера журнала за [latex]y[/latex]-й год (например, [latex]f (6.1970)=26)[/latex]. Напишите общую формулу для[latex]f(x, y) [/latex]для всех [latex] x , y (1 \le x \le 12 , y \ge 1970) [/latex] .
Решите уравнение [latex]f(x, y)=y [/latex] .

Тесты

Входные данные Выходные данные
[latex]x [/latex] [latex]y [/latex] [latex]f(x, y) [/latex]
6 1970 26
12 1970 56
7 1998 1711
9 2016 2801

Код

Решение задачи

При прочтении условия данной задачи, становится ясно что речь идёт о арифметической последовательности с первым элементом [latex]a_1 = 1 [/latex] и разностью данной последовательности [latex]d = 5 [/latex]. Таким образом для нахождения номера первой задачи из [latex]x [/latex]-го номера за [latex] y [/latex]-ый год требуется формула для нахождения [latex]n[/latex]-го члена прогрессии [latex]a_n=a_1+d(n-1) [/latex]. Но для этого случая нужно вывести [latex]n[/latex] что мы сделаем сложив номер выпуска [latex]x [/latex] и разницу [latex]y-1970[/latex] помноженную на [latex]60[/latex] (что является количеством задач опубликованных за год). Зная всё вышеперечисленное выводим общую формулу [latex]f(x, y) = 1 + 5\*(x-1)+60\*(y-1970)[/latex] . В последствии формула была изменена, что позволило избавиться от лишних действий и слегка сократить формулу. Вид этой формулы: [latex]f(x, y) = 5\*x-4+60\*(y-1970)[/latex] .

Ссылки

Условие задачи.
ideone

Ю11.16

Задача:
Для заданной матрицы [latex]A(n, n)[/latex] найти обратную [latex]A^{-1}[/latex], используя итерационную формулу:
[latex]A_{k}^{-1} = A_{k-1}^{-1}(2E-A A_{k}^{-1}),[/latex]
где [latex]E[/latex] — единичная матрица, [latex]A_{0}^{-1} = E[/latex]. Итерационный процесс заканчивается, если для заданной погрешности [latex]\varepsilon[/latex] справедливо:
[latex]\left| det(A A_{k}^{-1})-1 \right| \le \varepsilon[/latex]

Анализ задачи:
Прежде чем приступать к решению средствами языка C++, я создал прототип в системе компьютерной алгебры Wolfram Mathematica, с которым планировал сверяться при тестировании программы. Тем не менее, внимательный анализ показал, что с таким выбором начального приближения процесс уже на пятом шаге в значительной мере расходится даже для матриц размера 2*2. После уточнения условий и анализа дополнительного материала, посвященного методу Ньютона-Шульца, исходное приближение было изменено (по результатам исследования «An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications», Victor Pan, Robert Schreiber, стр. 8):
[latex]A_{0}^{-1} =\frac { A }{ \left\| A \right\|_{1} \left\| A \right\| _{\infty } }[/latex], где [latex]{ \left\| A \right\| }_{ 1 }=\max _{ i }{ \sum _{ j=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } } [/latex], [latex]{ \left\| A \right\| }_{ \infty }=\max _{ j }{ \sum _{ i=0 }^{ n-1 }{ \left| { a }_{ ij } \right| } }[/latex].
Эффективность предложенного подхода иллюстрируют результаты работы прототипа:
процесс сходится
Следовательно, из пространства задачи можно переместиться в пространство решения и составить алгоритм реализации предложенного метода на языке C++.

Тесты:

[latex]n[/latex] [latex]A[/latex] [latex]A^{-1}[/latex] Результат
3 1 2 3
5 5 7
11 13 7
-0.964771 0.430661 -0.017183
0.723533 -0.447973 0.137884
0.172358 0.155200 -0.086211
Пройден
2 1 2
2 1
-0.333067 0.666400
0.666400 -0.333067
Пройден
5 1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
Пройден
3 1 2 3
4 5 6
7 8 9
Матрица вырождена Пройден

Программный код:

Программа доступна для тестирования по ссылке: http://ideone.com/7YphoX.

Алгоритм решения
При решении данной задачи оправдывает себя подход «разделяй и властвуй»: вычисление обратной матрицы подразумевает промежуточные этапы, корректной реализации которых следует уделить особое внимание. Наверняка стоило бы написать класс matrix и реализовать перегрузку операций, но задачу можно решить и без применения объектно-ориентированных средств, пусть от этого решение и потеряет в изящности.
Можно выделить следующие подзадачи:

  1. Инициализация динамического двухмерного массива и передача его в функцию.
  2. Вычисление определителя матрицы (с применением метода Гаусса).
  3. Вычисление нормы матрицы.
  4. Транспонирование матрицы.
  5. Умножение матрицы на скаляр.
  6. Матричное умножение матриц.
  7. Сложение двух матриц.
  8. Непосредственно итерационный процесс Ньютона-Шульца

Ниже приведено пояснение к подходу к реализации некоторых подзадач:

  • Выделение памяти для хранения массива происходит не на этапе запуска программы, после компиляции. Для инициализации использован конструктор new
  • Вычисление определителя можно разбить на два последовательных шага:
    1. Приведение матрицы к верхнетреугольному виду (методом Гаусса).
    2. Вычисление определителя как произведения элементов главной диагонали.
    3. Если матрица вырождена, то дальнейшие вычисления не производятся.

  • Нормы матрицы вычисляются как максимальные значения суммы элементов по столбцам и строкам соответственно.
  • При транспонировании обмениваются местами элементы, симметричные главной диагонали.
  • При умножении матрицы на скаляр каждый элемент матрицы умножается на соответствующее вещественное число.
  • При перемножении двух квадратных матриц используется промежуточный массив для хранения результата вычислений.
  • Сложение двух матриц аналогично попарному сложению элементов, расположенных на соответствующих позициях.
  • Максимально допустимая погрешность для метода Ньютона-Шульца [latex]\varepsilon = 0.001[/latex]. Программа использует локальный массив для хранения [latex]A_{k}^{-1}[/latex], инициализация которого происходит в теле цикла.

Технические детали реализации:
При выполнении подзадач часто приходится использовать локальные массивы, так что для очистки выделенной под них памяти создана отдельная функция clear().

Ю11.12

Задача:
Интерполяционный многочлен Лагранжа. Значения функции [latex]y=f\left(x\right)[/latex] заданы таблично в массиве [latex]Y\left(x\right)[/latex] при соответствующих значениях аргумента в упорядоченном массиве [latex]X\left(x\right)[/latex]. Найти значение функции в произвольной точке [latex]x[/latex] по формуле Лагранжа:
[latex]y={L}_{n}\left(x\right)=\sum _{i=1}^{n}{{y}_{i}\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}}[/latex]

Вводимые значения:

X: -1 0 1 2
Y: 1 2 3 -1

Код программы:

Код программы на Java:

 

Идея решения:
Использование отдельной функции, которой надо передать 3 параметра: значение аргумента, массив исходных значений аргумента и массив исходных значений функции при соответствующих аргументах. Эта функция возвращает значение многочлена Лагранжа при подстановки вместо [latex]x[/latex] конкретного значения.

В функции был использован внешний цикл for для вычисления суммы в формуле и внутренний цикл for для вычисления произведения [latex]\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}[/latex].

В программе мы разбиваем отрезок [-3, 3] на 101 отдельную точку и вычисляем значение полинома Лагранжа для каждой из этих точек. Выводим на экран.

График:ГрафикПолиномаЛагранжа

Комментарии: Точки выбраны специально. Мне просто захотелось увидеть, как выглядит график функции, которую мы разбирали на паре (кстати по той же самой теме =) ). График сделан в xls. Векторы выбраны по причине ограниченности массива.

Ю3.39

Задача: Численно убедиться в справедливости равенства [latex]\frac{1}{4}\ln{\frac{1+x}{1-x}}+\frac{1}{2}\arctan{x}=\quad x+\frac{{x}^{5}}{5}+\dots+\frac{{x}^{4n+1}}{4n+1}+\dots[/latex], для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]e[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex]n[/latex] слагаемых, необходимых, для достижения заданной точности. Интервал для этой задачи: [latex]-1<x<1[/latex].

Ввод Вывод
[latex]x[/latex] Погрешность Output Комментарий
-0.99 1e-4 148 Пройден
0.99 1e-4 148 Пройден
0.99 1e-14 685 Пройден
0.7 1e-10 14 Пройден
-0.3 1e-13 6 Пройден
0.001 1e-13 1 Пройден

Идея решения: Используем цикл for, в условие которого ставим проверку на превышение погрешности суммы. Левую часть выражения вычисляем и записываем в переменную [latex]curr[/latex]. Сумму (то что стоит в правой части выражения) объявим как [latex]sum[/latex], и инициализируем значением [latex]x[/latex] (Это делается для того, чтобы во время работы цикла не вычислялось одно лишнее слагаемое).

Каждую итерацию цикла инкрементируем счетчик [latex]count[/latex]. Переменную [latex]y[/latex], которая соответствует i-тому слагаемому суммы, увеличивают до значения следующего слагаемого и прибавляют к сумме. Далее проверяем разность частичной суммы и заданного значения [latex]curr[/latex]. Если эта разность будет удовлетворять нашей точности, то число [latex]count[/latex] и будет количеством слагаемых в правой части.

Замечание: После цикла значение [latex]count[/latex] вновь инкрементируется, это сделано по следующей причине: сумма изначально содержала в себе первое слагаемое. Если сумма бы изначально содержала в себе 0, то нам пришлось бы вычислять лишнее слагаемое.

Ideone

Ю3.17

Задача: Сколько сомножителей надо взять в произведении: [latex]\prod_{k=1}^{\infty}{(1+\frac{{(-1)}^{k}}{2k+1})}=\frac{\sqrt{2}}{2}[/latex], чтобы равенство выполнялось до шестой значащей цифры, то есть с погрешностью не более [latex]{10}^{-6}[/latex]

Идея решения: Используем цикл for, в качестве [latex]k[/latex] в формуле используем переменную [latex]count[/latex] в программе. Переменную, которая будет соответствовать произведению, назовем [latex]mul[/latex] (сокращенно от multiplication) и присвоим ей значение 1 как нейтральный элемент для операции умножения. Каждую итерацию цикла проверяем разность [latex]mul-curr[/latex], где [latex]curr=\frac{\sqrt{2}}{2}[/latex], на превышение погрешности [latex]{10}^{-6}[/latex].

Если разность больше точности, умножаем [latex]mul[/latex] на выражение под знаком произведения и увеличиваем [latex]count[/latex] на единицу.

Если разность меньше точности, число [latex]count[/latex] и будет количеством сомножителей в произведении.

Число сомножителей оказалось достаточно большим — 88390. Ideone

А52

Задача. Даны действительный числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex], [latex]d[/latex], [latex]s[/latex], [latex]t[/latex], [latex]u[/latex]([latex]s[/latex] и [latex]t[/latex] одновременно не равны нулю). Известно, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] не лежат на прямой [latex]l[/latex], заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] заданной уравнением [latex]sx+ty+u=0[/latex]. Прямая [latex]l[/latex] разбивает координатную плоскость на две полуплоскости. Выяснить, верно ли, что точки [latex](a, b)[/latex] и [latex](c, d)[/latex] принадлежат разным полуплоскостям.

В этой задаче надо воспользоваться тем, что две точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на прямой, определяемой уравнением [latex]sx + ty + u = 0[/latex], принадлежат одной полуплоскости, если [latex]sa + tb + u[/latex] и [latex]sc + td + u[/latex] – числа одного знака. Справедлив и более общий факт: если уравнение [latex]F(x, y) = 0[/latex] определяет прямую или кривую, разбивающую координатную плоскость на две части, то точки [latex](a, b)[/latex] и [latex](c, d)[/latex], не лежащие на этой линии, принадлежат одной и той же части плоскости, если [latex]F(a, b)[/latex] и [latex]F(c, d)[/latex]– числа одного знака.

a b c d s t u Ответ
5 -4 2 9 6 -3 7  Обе точки принадлежат разным полуплоскостям.
-5 -4 -6 -3 2 7 -1 Обе точки принадлежат одной полуплоскости.
 -5 -4 -6 -3 0 0 -1  Условие некорректно:s и t не должны одновременно равняются нулю.
 4 7 2 1 -4 3  -5  Одна, либо обе из точек лежат на прямой, соответственно не принадлежат ни одной из полуплоскостей.

В программу вводятся исходные данные, среди которых координаты точек [latex](a, b)[/latex] и [latex](c, d)[/latex]. Если набор значений будет таким, что выполнится уравнение прямой [latex]sx+ty+u=0[/latex], (где xa и d. А yb и d), то это значит, что одни из точек (или сразу две) принадлежат прямой и следовательно не принадлежат ни одной из полуплоскостей. Если результаты уравнений [latex](s*a)+(t*b)+u[/latex] и [latex](s*c)+(t*d)+u[/latex]- числа одного знака, то точки лежат в одной полуплоскости. Если же эти числа разного знака, то обе точки принадлежат разным полуплоскостям.

Код на C++:

Код на Java:

 

С программой можно ознакомится тут (C++)/тут (Java).

Ю1.9

Кубическое уравнение. Заданы три корня кубического уравнения : [latex]x_{1},x_{2},x_{3}[/latex] . Найти коэффициенты этого уравнения.

[latex] x_{1}[/latex] [latex] x_{2}[/latex] [latex] x_{3}[/latex] Результат [latex]b[/latex] Результат [latex] c[/latex] Результат [latex] d[/latex] Комментарий:
 1  2  3  -6.00  11.00  -6.00 Тест пройден
0.5  6  0.78  -7.28 8.07  -2.34 Тест пройден
-1  -2  -2.25  5.25 8.75  4.50 Тест пройден
 -0.24 -1 2.24  -1.00 -2.54  -0,54 Тест пройден

 

 

Дано кубическое уравнение типа [latex](x — x_{1})(x-x_{2})(x-x_{3})=0[/latex]. После недолгих преобразований я получаю такое выражение:

[latex]x^{3}-(x_{1}+x_{2}+x_{3})x^{2}+(x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{1})x-x_{1}x_{2}x_{3}=0[/latex].

Потом присваиваю трём переменным выражения для коэффициентов:

[latex]\begin{cases} & \ x_{1}+x_{2}+x_{3}=-b \\ & \ x_{1}*x_{2}+x_{2}*x_{3}+x_{1}*x_{3}= c \\ & \ x_{1}*x_{2}*x_{3}=-d \end{cases}[/latex]

где [latex]b[/latex] — коэффициент при [latex]x^{2}[/latex], [latex] c[/latex] — при [latex]x[/latex], а [latex] d[/latex] — свободный коэффициент.

 В итоге, все решение задачи свернулось в 3 этапа:

  1. Ввод переменных.
  2. Вычисление коэффициентов.
  3. Вывод результата.

Результат выводится с точностью до двух знаков после запятой.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.

Код на языке Java:

 

Ю1.5

Задача: в такси одновременно сели три пассажира. Когда вышел первый пассажир, на счетчике было [latex]p_{1}[/latex] рублей; когда вышел второй — [latex]p_{2}[/latex] рублей. Сколько должен был заплатить каждый пассажир, если по окончании поездки счетчик показал [latex]p_{3}[/latex] рублей? Плата за посадку составляет [latex]p_{0}[/latex] рублей.

Ввод Вывод
 [latex]p_{0}[/latex]  [latex]p_{1}[/latex]  [latex]p_{2}[/latex]  [latex]p_{3}[/latex] [latex]op_{1}[/latex]  [latex]op_{2}[/latex] [latex]op_{3}[/latex] Комментарий
 0  0  0  0  0.00  0.00  0.00  Пройден
 6  1  2  3  2.33  2.83  3.83  Пройден
 7  2 5  16  3.00  4.50  15.50  Пройден
 1  1  1  1  0,67  0,67  0,67  Пройден
 150  1138  2590  5788  429.33  1155.33  4353.33  Пройден
 3  0  0  6  1.00  1.00  7.00  Пройден

[latex]p_{0}[/latex],  [latex]p_{1}[/latex],  [latex]p_{2}[/latex],  [latex]p_{3}[/latex] — целые числа, хоть и определены как double, всё равно это целые числа. У таксиста просто такой счетчик.

Идея решение: Первый участок проехали трое и расходы делятся на троих ([latex]\frac { { p }_{ 1 } }{ 3 }[/latex]). Второй участок – двое, значит за него двое платят поровну ([latex]\frac{{p}_{2}-{p}_{1}}{2}[/latex]). Последний участок проехал один, ему за него и платить ([latex]{p}_{3}-{p}_{2}[/latex]). Оплатой за поездку для каждого является сумма стоимости каждого пути до его остановки.