A701a

Задача

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] с [latex]n[/latex] элементами. Получить вектор:
a) [latex]Ab[/latex];

Размерность
матрицы
Матрица Вектор Результирующий
вектор
2
1 2
3 4
1
2
5
11
3
3 2 6
3 2 1
5 3 8
4
5
7
64
29
91
4
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
1
2
3
4
30
70
20
50
 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
5
6
7
8
9
115
290
465
640
815

Алгоритм действия достаточно прост:
Вводим размерность матрицы. Потом в цикле вводим саму матрицу. Вводим вектор. Далее идет сам алгоритм матрично-векторного произведения.

Последовательный алгоритм умножения матрицы на вектор может быть представлен следующим образом. Исходные данные: [latex]A[n][m][/latex] – матрицы размерности [latex]n[/latex]× [latex]m[/latex] . [latex]B[m][/latex] – вектор, состоящий из [latex]m[/latex] элементов. Результат: [latex]rezult[n][/latex] – вектор из [latex]n[/latex] элементов.

 

Матрично-векторное умножение – это последовательность вычисления скалярных произведений. Поскольку каждое вычисление скалярного произведения векторов длины [latex]m[/latex] требует выполнения [latex]m[/latex] операций умножения и [latex]m-1[/latex] операций сложения, его трудоемкость порядка [latex]O(m)[/latex]. Для выполнения матрично-векторного умножения необходимо выполнить [latex]n[/latex] операций вычисления скалярного произведения, таким образом, алгоритм имеет трудоемкость порядка [latex]O(nm)[/latex].

Ниже представлен сам код (C++).

Код на Java:

 

Также, Вы можете воспользоваться ссылкой (C++)/ссылкой (Java) на саму программу.

 

А413б

Задача

Таблица футбольного чемпионата задана квадратной матрицей порядка [latex]n[/latex], в которой все элементы, принадлежащие главной диагонали, равны нулю, а каждый элемент, не принадлежащий главной диагонали, равен  [latex]2[/latex],  [latex]1[/latex]  или  [latex]0[/latex] (числу очков, набранных в игре:  [latex]2[/latex]- выигрыш,  [latex]1[/latex]- ничья,   [latex]0[/latex]- проигрыш).

б) Определить номера команд, прошедших чемпионат без поражений.

Количество команд. Турнирная таблица.

Номера команд, прошедшие турнир без поражений.

Комментарий.
4
0 2 0 1
0 0 1 2
2 1 0 1
1 0 1 0
3 Пройдено.
4
0 1 2 2
1 0 2 2
0 0 0 1
0 0 1 0
1 2 Пройдено.
3
0 2 0
0 0 2
2 0 0
Ни одна из команд не прошла турнир без поражений. Пройдено.
4
0 2 1 1
0 0 1 2
1 1 0 2
1 2 2 0
1 3 4 Пройдено.

От нас требуют определить номера команд, прошедших чемпионат без поражений. Турнирная таблица, которую нам следует проверить, имеет вид матрицы, где строки- это очки набранные командой, а столбцы- сами команды. Всего у нас столько команд, сколько элементов в столбце. Т.к команда  не может играть сама с собой, диагональные элементы равны [latex]0[/latex].

Для начала вводим двумерный массив. Далее, в циклах, проверяем на наличие у команды поражения: для не диагональных элементов ([latex]i\neq j[/latex]), если команда хотя бы один раз проиграла, цикл обрывается и команда в дальнейшей проверке не участвует.

Если ни одна команда не прошла турнир без поражений, то для этого заводим счетчик [latex]k[/latex]. Если [latex]k>0[/latex], то хотя бы одна команда прошла турнир без поражений. Если [latex]k=0[/latex], то ни одна из команд не прошла без поражений.

Ниже представлен сам код (C++).

Код на Java:

 

Также, вы можете воспользоваться ссылкой (C++)/ссылкой (Java) на саму программу.

Ю4.35

Задача

Совместная работа. Известно время [latex]t_{1},t_{2}, \cdots,t_{n}[/latex], за которое некоторую работу может выполнить каждый из [latex]n[/latex] рабочих бригады, работая в одиночку. Сколько времени понадобится бригаде на выполнение этой работы, если они будут работать совместно (и при этом никто из них не «сачкует»)?

Количество рабочих n. Время t каждого рабочего, требуемое для выполнения некоторой работы.  Время совместной работы.
3 2 4 5 1.1
5 2 4 5 1 2 0.4
6 6 6 6 6 6 6 1.0
7 8 6 5 6 6 7 2 0.7

В данной задаче нам нужно найти время, за которое [latex]n[/latex] рабочих выполнят какую-то совместную работу. В задаче не указан  общий объём выполняемой работы, по-этому зададим его как 1. Время совместной работы находят по формуле: [latex]t_{call}=\frac{V}{\frac{V}{t_{1}}+\frac{V}{t_{2}}+\cdots+\frac{V}{t_{n}}}[/latex], где [latex]V[/latex] –  общий объём выполняемой работы, т.е – 1. Т.к в задаче не указана единица измерения времени, будем считать все в часах.

В программе используются два цикла. Первый– для ввода времени каждого рабочего, а второй– для вычисления общей производительности рабочих. Call–callaboration (время совместной работы), sum – общая производительность рабочих.

Ниже представлена сама программа (C++):

Код на Java:

Так же вы можете воспользоваться ссылкой (C++)/ссылкой (Java), для ознакомления с программой.

А165а

Задача

Даны действительные числа [latex]a_{1},a_{2}, \ldots [/latex]. Известно, что [latex]a_{1}>0[/latex] и что среди [latex]a_{2},a_{3}, \ldots[/latex] есть хотя бы одно отрицательное число. Пусть [latex]a_{1},\ldots , a_{n}[/latex] -– члены данной последовательности, предшествующие первому отрицательному члену ([latex]n[/latex] заранее известно). Получить:

a) [latex]a_{1}+a_{2}+ \cdots +a_{n}[/latex];

Элементы последовательности Сумма элементов до отрицательного числа.
3 4 6 -2 3 1 13
2 8 -1 2 3 4 5 10
1 0 5 0 0 -1 0 0 0 6
4.2 3.2 1 -5 1 5 8.4

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

Ниже представленная сама программа (C++).

Код на Java:

 

Так же вы можете воспользоваться ссылкой (C++)/ссылкой (Java), для ознакомления с программой.

Ю3.38

Задача

Численно убедиться в справедливости равенства, для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]\varepsilon[/latex] . Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex]n[/latex] (слагаемых или сомножителей), необходимых для достижения заданной точности.

[latex]\frac{\pi ^{2}}{8}-\frac{\pi }{4}\cdot |x|=\frac{cosx}{1!}+\frac{cos3x}{3^{2}}+\frac{cos5x}{5^{2}}+\cdots+\frac{cos((2n+1)\cdot x) }{(2\cdot n+1)^{2}}+\cdots[/latex],

[latex]|x|<1[/latex].

x E Левая часть (left). Правая часть (right). Разность (right-left). n Комментарий.
0.6 0.000001 0.7624616521 0.7604912379 0.0019704142 3 Пройден.
0.75 0.000035 0.6446519276 0.6290694254 0.0155825022 3 Пройден
0.4 0.00002 0.9195412848 0.9143769743 0.0051643104 5 Пройден
4 0.0001 Некорректно задан аргумент x (|x|<1)Не пройден.
0.4 0 0.9195412848 0.9195412848 0.9195412848 бесконечность Погрешность равна 0, тогда правая часть стремится к левой.Пройден.

Необходимо доказать равенство левой и правой части при заданных [latex]x[/latex] и [latex]\varepsilon[/latex].

Мы высчитываем левую часть [latex]\frac{\pi ^{2}}{8}-\frac{\pi }{4}\cdot |x|[/latex], с заданным аргументом [latex]x[/latex]. Затем в цикле do высчитываем значение правой части [latex]\frac{cosx}{1!}+\frac{cos3x}{3^{2}}+\frac{cos5x}{5^{2}}+\cdots+\frac{cos((2n+1)\cdot x) }{(2\cdot n+1)^{2}}+\cdots[/latex], до тех пор, пока разность правой и левой части не превысит заданную погрешность [latex]\varepsilon[/latex]. После этого программа выводит значение левой и правой части, их разницу и количество итераций для заданной погрешности.

Ниже представлена сама программа (C++).

Код на Java:

 

Так же вы можете воспользоваться ссылкой (C++)/ссылкой (Java), для ознакомления с программой.

Ю3.16

Задача

Сравнить скорость сходимости при вычислении числа [latex]e[/latex] с помощью ряда и бесконечной дроби:

[latex]e=2+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}+…[/latex]; [latex]e=1+\frac{1}{1-\frac{1}{2+\frac{1}{3-\frac{1}{2+\frac{1}{5-…}}}}}[/latex]

У нас дан ряд(row) и бесконечная дробь(inf). Для разложения числа  [latex]e[/latex] в ряд использована функция вычисления факториала. Задаем начальные переменные и вычисляем основание натурального логарифма. При достижении заданной точности [latex]E[/latex] цикл вычислений ряда прекращается, и начинается вычисление по методу цепной дроби с заданным в первой части программы количеством итераций (для корректного сравнения скорости сходимости, количество итераций должно быть одинаково).

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

E

Количество итераций ряда(row)

i

Количество итераций цепной дроби(inf)l Комментарий
0.00001 9 7

Бесконечная дробь быстрее сходится к числу е, чем ряд.

Тест пройден.

0.0000002 11 9

Бесконечная дробь быстрее сходится к числу е, чем ряд.

Тест пройден.

0.00078 7 6

Бесконечная дробь быстрее сходится к числу е, чем ряд.

Тест пройден.

0.0004 7 6

Бесконечная дробь быстрее сходится к числу е, чем ряд.

Тест пройден.

При схождении к числу [latex]e[/latex] с точностью [latex]E[/latex] цепная дробь будет  делать это быстрее, чем ряд.

Ниже представлена сама программа(C++).

Код на Java:

 

Также вы можете воспользоватся ссылкой (C++)/ссылкой (Java), для ознакомления с программой.

А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).

Ю2.12

Задача

Планировка. Можно ли на прямоугольном участке застройки размером a на b метров разместить два дома размером в плане p на q и r на s метров? Дома можно располагать только параллельно  сторонам участка.

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

Илья_задание_01 Илья_задание_04

a b p q r s Ответ
100 150 20 70 25 50 Дома могут быть построены на заданном участке.
20 50 10 60 10 15 Дома не могут быть построены.
50 150 25 150 25 150 Дома могут быть построены на заданном участке.
50 150 50 75 50 75 Дома могут быть построены на заданном участке.
200 300 115 50 110 100 Дома могут быть построены на заданном участке.
2 4 1 3 2 2 Дома не могут быть построены.
2 5 1 3 2 3 Дома не могут быть построены.
2 5 2 2 1 4 Дома не могут быть построены.
3 3 2 2 2 2 Дома не могут быть построены.
2 10 10 1 10 1 Дома могут быть построены на заданном участке при повороте на 90 градусов.
10 2 1 10 1 10 Дома могут быть построены на заданном участке при повороте на 90 градусов.
2 10 1 10 10 1 Дома могут быть построены на заданном участке при повороте дома со сторонами r s на 90 градусов.
10 2 10 1 1 10 Дома могут быть построены на заданном участке при повороте дома со сторонами r s на 90 градусов.
10 2 1 10 10 1 Дома могут быть построены на заданном участке при повороте дома со сторонами p q на 90 градусов.
2 10 10 1 1 10 Дома могут быть построены на заданном участке при повороте дома со сторонами p q на 90 градусов.
2 3 1 1 2 3 Дома не могут быть построены.
2 4 1 1 3 3 Дома не могут быть построены.
2 6 1 3 3 3 Дома не могут быть построены.

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

Всего у нас есть 8 вариантов расположения домов на участке.

Каждый дом можно расположить на участке двумя способами (вертикально или горизонтально). Значит всего четыре различные комбинации их расположения относительно участка. Среди этих четырёх комбинация должна существовать по крайней мере одна в которой дома помещаются. Т.е. либо суммарная ширина домов меньше ширины участка и длина каждого дома меньше его длины, либо суммарная длина домов меньше длины участка и ширина каждого дома меньше ширины участка. Поскольку выполнится должно хоть одно такое условие, то их нужно соединить логическим “или”.

Так же у нас есть 4 различных комбинации размещения домов, в которых один из домов(а может и сразу два) не помещается на участке, но если его развернуть на [latex]90^{\circ}[/latex], то дома успешно разместятся на участке.

Ниже представлен сам код(C++):

Код на Java:

 

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

Ю1.17

ЗАДАЧА

tupougolnyi-treugolnik

Длинна высоты. Треугольник [latex]ABC[/latex] задан длинами своих сторон. Найти длину высоты, опущенной из вершины А.

Экстремальные тесты: сумма двух сторон равна третьей; одна из сторон равна нулю.

Для справки.

Высота в произвольном треугольнике вычисляется по формуле:

[latex]h=2\cdot\frac{\sqrt{(p\cdot(p-a)\cdot(p-c)\cdot(p-b)}}{b}[/latex]

где

[latex]p=\frac{a+b+c}{2}[/latex]

В таблице представлены возможные треугольники: прямоугольный, равнобедренный, равносторонний и с неизвестными углами (произвольный). Также тут указаны условия, при которых треугольник существовать не может.

a

b

c

h

Коментарии

2 3 4 1.94 Тест пройден.
0 4 5 Ошибка в условии.Одна из сторон равна или меньше 0.
3 3 6 Ошибка в условии. Сумма двух сторон равна или меньше третьей стороны.
-4 3 6 Ошибка в условии.Одна из сторон равна или меньше 0.
6 6.5 2.6 2.4 Тест пройден.
4.4 4.4 5 4.11 Тест пройден.
4 4 4 3.46 Тест пройден.

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

Код на С++:

Код на Java:

 

Для выполнения программы и проверки тестов можно воспользоватся следующей ссылкой (C++)/ссылкой(Java).