Ю4.3

Задача

Центрирование массива. От каждого из заданных чисел {x}_{1}, {x}_{2}, \ldots, {x}_{m} отнять их среднее арифметическое \overline{x}_{i} = {x}_{i}{x}_{cp}, i = 1, 2, … , m.

\overline{x} = 1/m;
E от m при i = 1 (x_1);
{x}_{i} = {x}_{i}\overline{x}; i = 1, 2, … , m

Результаты разместить на месте исходных данных.

Тесты

Количество элементов в массиве — m Массив Результат
2 2

5

-1,5

1,5

2 2

6

-2

2

7 2

6

-3

5

1

0

0

0.43

4.43

-4.57

3.43

-0.57

-1.57

-1.57

Код

Протестированный код можно увидеть тут.

Решение

Объявляем массив типа double размерностью m. Считываем размерность из первой строки ввода, конвертируем из типа string в тип int; затем считываем элементы массива из второй строки ввода (их конвертируем в double — для точности вычислений). В циклах: находим сумму введенных чисел, затем их среднее арифметическое, затем высчитываем новые значения элементов массива, вычитая от каждого из них среднее арифметическое всего массива. Записываем новые значения поэлементно в исходный массив arr[ ]. Выводим arr[ ].

 

 

Ю 4.17

Постановка задачи

В массиве A(n) найти и напечатать номера (индексы) локальных максимумов, то есть таких a_{i}, что a_{i-1}<x_{i}>a_{i+1}.

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

Количество значений и сами значения

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

Индексы локальных максимумов

Тесты

Количество значений Значения Результат
1 6 2 4 6 1 3 7 5 2
2 7 3 1 6 2 8 5 7 2, 4
3 10 2 5 8 3 5 6 9 7 1 4 2, 6

Решение

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n для хранения размера массива. Далее создаем массив типа double. Для нахождения локальных максимумов x[i] создаем цикл for, в котором при каждой итерации будем проверять, являются ли значения локальными максимумами. Если значение удовлетворяет условие, выводим на экран индекс этого значения. Например, в первом тесте мы вводим количество значений 6, сами значения 2 4 6 1 3 7 5 и нашим результатом оказывается число с индексом 2, т.е. число 6. Так как числа 4 и 1 меньше 6, наше значение будет удовлетворять условие.

Ю4.32

Постановка задачи

Суммы по косой. Просуммировать элементы матрицы A(n,n) по каждой из линий, параллельных главной диагонали. Напечатать полученные суммы.

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

n — размерность матрицы (n\geq 1).
A — квадратная матрица.

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

Суммы элементов матрицы A по каждой из линий, параллельной главной диагонали.

Тесты

Входные данные Выходные данные
Размерность матрицы (n) Матрица A Суммы
1 2 \begin{pmatrix}  3 & 6\\  -7 & -5  \end{pmatrix} -7  -2  6
2 3 \begin{pmatrix}  1 & 2 & 3\\  4 & 5 & 6\\  7 & 8 & 9  \end{pmatrix} 7  12  15  8  3
3 4 \begin{pmatrix}  4 & 1 & -6 & 3\\  2 & 8 & 19 & 7\\  -8 & -11 & 3 & -13\\  0 & 2 & 16 & -9  \end{pmatrix} 0  -6  7  6  7  1  3

Посмотреть работу программы на примере третьего теста можно на сайте ideone.

Решение

Описание решения

Сначала объявляем переменную n — размерность матрицы A — и присваиваем ей значение, которое вводит пользователь. Если (n\geq 1) — продолжаем работу, иначе выводим сообщение об ошибке и завершаем работу программы.

Теперь, зная размерность матрицы, можем инициализировать 2 массива:

  1. Двумерный массив double[][] matrix = new double[n][n]; размерностью (n\times n), который будет содержать в себе значения элементов матрицы A;
  2. Массив double[] sum = new double [2*n - 1]; размерностью (2*n-1) для хранения сумм диагоналей. Такая размерность обусловлена следующей логикой: главная диагональ матрицы размерностью (n\times n) содержит n элементов. Побочная диагональ, находящаяся выше, содержит в себе уже (n-1) элементов и т.д., пока элементов в диагонали больше нуля. Становится ясно, что выше главной диагонали находится (n-1) побочных диагоналей, еще столько же ниже. Прибавляем еще главную диагональ к этому числу и выводим формулу количества диагоналей у матрицы, параллельных главной: 2(n-1)+1=2n-1.

Заполняем с помощью двух циклов for массив matrix из потока ввода, а затем в таких же циклах находим суммы элементов требуемых диагоналей ( sum[(j-i) + (n-1)] += matrix[i][j];).

Известно, что индексы i,j элементов главной диагонали матрицы всегда одинаковы. Аналогично можно заметить, что на побочных диагоналях индекс j отличается от индекса i на число — «расстояние» между главной диагональю и рассматриваемой побочной. К примеру, если рассматривать побочную диагональ, находящуюся выше через одну от главной («расстояние» между ними равно 2), то в таком случае j-i=2.

И если на главной диагонали разность индексов будет равна 0, на диагоналях выше эта разность будет числом положительным, а на диагоналях ниже — отрицательным, то при попытке обращения к элементу массива sum[j-i] мы неизбежно столкнемся с ошибкой, так как индекс массива не может быть числом отрицательным. Значит, чтобы избежать этого, нам надо прибавить к этому индексу некую константу, чтобы самая нижняя диагональ n-1 обладала индексом 0 в массиве sum. Отсюда и формула (j-i+n-1).

A302. Количество различных цифр числа в его десятичной записи

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

Дано натуральное число N. Сколько различных цифр встречается в его десятичной записи?

Тесты

Входные данные: натуральное число N

Выходные данные: количество различных цифр в десятичной записи числа N

Входные данные Выходные данные
1 1234567890 10
2 43352 4
3 10101 2
4 1 1

Код

Код доступен на ideone

Пояснение

Для хранения заданного числа N будем использовать переменную  n  типа long, которая будет проинициализирована значением из стандартного потока ввода, а для хранения результата — переменную differentDigitsCount  типа int, которую проинициализируем числом 0. Переменные объявляются в начале программы. Для определения количества различных цифр будем использовать массив типа int из 10 элементов, где каждый элемент будет соответствовать количеству вхождений одной из цифр в заданное число . Элементы массива инициализируются числом 0 по умолчанию. В цикле поочередно определяется разряд — последний разряд числа, и соответствующий элемент массива инкрементируется, затем это число разделяется на 10, чтобы «отбросить» последний разряд. Результат работы программы — вывод значения переменной  differentDigitsCount, которое получается путем подсчета ненулевых элементов массива в цикле.

 

 

Ю 4.9

Задача

В матрице A(n, m) все ненулевые элементы заменить обратными по величине и противоположными по знаку.

Тесты

      n        m  Входная матрица              Выходная матрица
     1                     3                         3           6   -2    -1                     0    0     4                    11   2    -3         -0.167     0.500      1.000                  0.000     0.000     -0.250                 -0.091    -0.500      0.333
     2                     3                         4       -3    -9    15   12        -31   -8     2     8           -1     2    -6    -8      0.333   0.111    -0.067   -0.083      0.032   0.125    -0.500   -0.125      1.000  -0.500     0.167    0.125
     3                    4                         3             1   1   1                       1   1   1                       1   1   1                       1   1   1            -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000                    -1.000  -1.000   -1.000

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Объявляем и инициализируем переменные n  и m , которые являются размерами нашей матрицы A. Объявляем нашу матрицу и создаем экземпляр с размерами n x m. Далее создаем цикл по i  от 0 до n-1 в котором создаем вложенный цикл по  j  от 0 до m-1, и в нем поэлементно вводим значения матрицы. В следующем цикле снова создаем вложенный, в котором мы проходим по каждому элементу матрицы и проверяем не равен ли он нулю  if(A[i][j] != 0) . Если условие выполняется, то мы заменяем элемент на обратный и меняем знак. В последнем цикле выводим полученную матрицу, элементы которой будут выводится с точностью до трех символов после запятой.

А694а. Многомерные массивы

Условие
Получить квадратную матрицу порядка \begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}

Тесты

n Матрица
3 1 0 0
0 1 0
0 0 1
4 1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
6 1 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 1
Решение

  1. С помощью цикла заполняем главную диагональ единицами.
  2. Приравниваем элементы не равные единице к нулю.
  3. Вывод массива.

Iseone.com

А99. Массивы

Условие
Пусть a_{1}=4, b1=v, an=2bk-1+ak-1. bk=2a^2k-1+bk-1, k=2,3…
Даны действительные u, v, натуральное n. Найти Е от n при k=1 (ak*bk)/(k+1)!

Тесты

N U V Результат Вывод
2 4 3 64 тест пройден
1 4 2 4 тест пройден
2 1 2 4 тест пройден
0 3 1 1 тест пройден
1 2 3 3 тест пройден
Решение
if (M == 0) // массив
return 1; // возвращаем факториал от нуля, это 1
else // Во всех остальных случаях
return M * fact(M — 1); // делаем рекурсию.

Пишем условия и формулы:

sum = a * b / fact(k + 1);
for (k = 2; k <= n; k++) // цикл

Цикл:
t = a;
a = 2*b + a;
b = 2 * t * t + b;
sum = sum + (a * b / fact(k + 1));

Ideone.com

А702а

Дана квадратная матрица порядка n.
Получить вектор Ab, где b-вектор, элементы которого вычисляются по формуле: {b}_{i}={\frac{1}{{i}^{2}+2}}, где i=1,2,\dots,n.

2
1 2
3 4
0.666667 1.66667
Пройдено
2
5 6
7 8
2.66667 3.66667
Пройдено

Исходный код:

Ссылка на Ideone

http://ideone.com/UAvHF4

Ю4.24

  «Нарастающий итог»

Задача:

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

 
Вводимые данные Предполагаемый вывод Комментарий
1 1 1 1 1 1 1 1 2 3 4 5 Тест пройден
1 2 3 4 5 6 7 8 9 1 1 3 6 10 15 21 28 36 Тест пройден
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 Тест пройден

Исходный код:

Описание:

Если действовать в лоб (последовательно менять значения элементов от первого до последнего на сумму предыдущих) можно получить различные геометрические прогрессии и даже, в некоторых случаях, последовательность Фибаначчи(так как мы меняем предшествующие элементы, и, при обычном подходе нет эффективного способа их запоминать). Подумав некоторое время над этой  проблемой, и осознав бесперспективность своих действий, решил зайти с другой стороны. Да, я не могу менять элементы в начале массива, но я могу менять их в конце, т. к. они не влияют на вычисления. Для этого пришлось создать новый цикл, в котором мы находим сумму всех элементов массива кроме последнего, величина которого (массива) уменьшается с каждым шагом. Далее, в главном цикле, мы последовательно присваиваем элементам массива найденные суммы. И уже после цикла присваиваем нулевому элементу значение первого.

Ссылка на Ideone

http://ideone.com/Wj86C6

e-olymp 974. Флойд-1

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

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

В первой строке записано количество вершин графа n (1n100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Алгоритм

(взято с Википедии)

Пусть вершины графа {\displaystyle G=(V,\;E),\;|V|=n} пронумерованы от 1 до  {\displaystyle n} и введено обозначение {\displaystyle d_{ij}^{k}} для длины кратчайшего пути от  {\displaystyle i} до {\displaystyle j}, который кроме самих вершин  {\displaystyle i,\;j} проходит только через вершины {\displaystyle 1\ldots k} . Очевидно, что {\displaystyle d_{ij}^{0}} — длина (вес) ребра {\displaystyle (i,\;j)}, если таковое существует (в противном случае его длина может быть обозначена как {\displaystyle \infty } ).

Существует два варианта значения  {\displaystyle d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n)} d_{ij}^{k},\;k\in \mathbb {(} 1,\;\ldots ,\;n):

Кратчайший путь между {\displaystyle i,\;j} не проходит через вершину  {\displaystyle k}, тогда {\displaystyle d_{ij}^{k}=d_{ij}^{k-1}} Существует более короткий путь между {\displaystyle i,\;j}, проходящий через {\displaystyle k}, тогда он сначала идёт от {\displaystyle i} до  {\displaystyle k} , а потом от  {\displaystyle k} до  {\displaystyle j} . В этом случае, очевидно, {\displaystyle d_{ij}^{k}=d_{ik}^{k-1}+d_{kj}^{k-1}}

Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.

Тогда рекуррентная формула для {\displaystyle d_{ij}^{k}} имеет вид:

{\displaystyle d_{ij}^{0}} — длина ребра  {\displaystyle (i,\;j);} (i,\;j); {\displaystyle d_{ij}^{k}=\min(d_{ij}^{k-1},\;d_{ik}^{k-1}+d_{kj}^{k-1}).}

Алгоритм Флойда-Уоршелла последовательно вычисляет все значения {\displaystyle d_{ij}^{k},} , {\displaystyle \forall i,\;j} для  {\displaystyle k} от 1 до  {\displaystyle n} . Полученные значения  {\displaystyle d_{ij}^{n}} являются длинами кратчайших путей между вершинами . {\displaystyle i,\;j.} .

Код

Условие на e-olymp.com
Решение на e-olymp.com
Код на ideone.com