Ю 4.33

Решённую задачу на C++ можно просмотреть здесь

Задача
Для заданной матрицы [latex] A(m,n) [/latex] найти её норму: [latex] \left \| A \right \|_{1} = \max\limits_{i=1,m} \sum\limits_{k=1}^{n} \left | a_{ik} \right |[/latex].

Входные данные
$m$ и $n$ — размеры матрицы, $x$ — временная переменная для хранения следующего значения из входного потока

Выходные данные
$norm$ — норма матрицы

Тесты

Матрица Построчные суммы Вывод
[latex] \begin{pmatrix} 1 & -3 & 2 & 4 & 0 \\ -3 & -7.5 & 2.3 & -3.1 & 2.8 \\ 3.4 & -4.5 & 0 & 0 & 2 \\ 3.2 & 4.7 & 2.8 & -3.1 & -4.3 \end{pmatrix} [/latex] [latex] \begin{matrix} 10 \\ 18.7 \\ 14.4 \\ 18.1 \end{matrix}[/latex] 18.7

Код

Решение
Нам понадобятся два цикла: во внешнем будем искать максимум, пробегая по всем строкам матрицы; во внутреннем будем для фиксированной строки вычислять сумму абсолютных величин её элементов. Если эта сумма превосходит текущую максимальную, обновляем последнюю. Поскольку все наши суммы будут неотрицательными числами, изначально присвоим переменной max значение 0.

Ю4.35

Ссылка на оригинальную статью.

Условие:

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

Тесты

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

Решение:

В программе используются два цикла. Первый– для ввода времени каждого рабочего, а второй– для вычисления общей производительности рабочих. Call–callaboration (время совместной работы), sum – общая производительность рабочих.В данной задаче нам нужно найти время, за которое [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. Т.к в задаче не указана единица измерения времени, будем считать все в часах.

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

 

 

Ю 4.24

Ссылка оригинальную статью

Ссылка Try Haxe!

 

Условие задачи:

В массиве $А(n)$ каждый элемент, кроме первого, заменить суммой всех предыдущих элементов.

Тесты:

Ввод Вывод
1 1 1 1 1 1 1 1 2 3 4 5
3 5 2 9 0 4 65 156 1 3 3 8 10 19 19 23 88 244
2 -7 3 8 -4 5 -2 4 2 2 2 -5 -2 6 2 7 5 9

Код:

Ход решения:

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

e-olymp 138. Банкомат

Ссылка на условие задания: e-olymp.

Условие

В банкомате имеются в достаточном количестве купюры номиналом $10$, $20$, $50$, $100$, $200$, $500$. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в $n$ гривен или вывести $-1$, если указанную сумму выдать нельзя.

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

Одно число $n$ ([latex]1 \leq n \leq 1000000[/latex]).

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

Наименьшее количество купюр, которыми можно выдать $n$ гривен.

Тесты

Входные данные Выходные данные
Сумма Количество купюр
130 3
999 -1
7360 18
440 4
3 -1

Код.

Решение.

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

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

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Для проверки этого условия, до начала выполнения жадного алгоритма, выполняется проверка. Если указанная сумма делится на 10 без остатка, то функция начинает выполнение алгоритма, если же нет, то возвращает $-1$.

Ссылка на решение задачи на сайте Try Haxe!

А409

Задача.

Дана действительная квадратная матрица порядка [latex]9[/latex]. Вычислить сумму тех из её элементов, расположенных на главной диагонали и выше неё, которые превосходят по величине все элементы, расположенные ниже главной диагонали. Если на главной диагонали и выше неё нету элементов с указанным свойством, то ответом должно служить сообщение об этом.

Решение.

  1. Находим наибольший из нижних элементов (элементы, расположенные ниже главной диагонали).
  2. Сравниваем каждый элемент верхнего множества (элементы, расположенные выше главной диагонали и на самой диагонали) с наибольшим элементом ( bottomMax ) из всех нижних элементов и если это число больше, то прибавляем это число к переменной totalSumm.

Код:

Ссылка на решение задачи.

Cсылка на условие задачи.