Среда программирования: Java
Название работы: Изучение Java (строки, матрицы, простые и целые числа, бинпоиск и сортировки)
Вид работы: Лабораторная работа
Тематика работы: Алгоритмы, Математика, Работа с текстом, Структуры, Прочие
Объем программы: 8 (по десятибалльной шкале)
Уровень сложности: 8 (по десятибалльной шкале)
Разработчик (автор):
Программист сайта kursovik.com
(письмо автору)
Данная работа написана ЧЕЛОВЕКОМ без использования ИИ
Ключевые слова: Строки, функции, выравнивание строк, добавление слева, добавление справа, матрица, случайные числа, транспонированная матрица, массив, состязания, простые числа, целые числа, бинпоиск, сортировка
Функции программы:
Задание 8.1.
1. Напишите функцию myStrlen – аналог библиотечной функции strlen .
Заготовка:
int myStrlen(char* a);
2. Напишите функцию myStrcpy – аналог библиотечной функции strcpy .
Заготовка:
void myStrcpy(char* a, char* b);
3. Напишите функцию myStrcat – аналог библиотечной функции strcat .
Заготовка:
void myStrcat(char* a, char* b);
4. Напишите функцию myStrcmp – аналог библиотечной функции strcmp .
Заготовка:
int myStrcmp(char* a, char* b);
Например,
i = myStrcmp("abc", "after"); //вернет отрицательное значение
5. Напишите функцию для удаления всех пустых пробелов после окончания
строки.
Заготовка:
void trimRight(char* a);
6. Напишите функцию для удаления всех пустых пробелов перед началом
строки.
Заготовка:
void trimLeft(char* a);
7. Напишите функцию для добавления дополнительных пробелов после
окончания строки, чтобы длина строки стала равна n. Если строка уже из
n или больше символов, то изменять строку не нужно.
Заготовка:
void padRight(char* a, int n);
8. Напишите функцию для добавления дополнительных пробелов перед
началом строки, чтобы длина строки стала равна n. Если строка уже из n
или больше символов, то изменять строку не нужно. Заготовка:
void padLeft(char* a, int n);
9. Напишите функцию «выравнивания» по центру строки, добавляя слева и
справа необходимое количество пробелов. Если строка уже из n или
больше символов, то изменять строку не нужно. Если количество
пробелов нечетно – дополнительный пробел необходимо добавить
справа. Заготовка:
void center(char* a, int n);
10. Напишите функцию count, которая подсчитывает, сколько раз символ c
встретился в строке a. Заготовка:
int count(char* a, char c);
11. Напишите функцию , count, которая подсчитывает, сколько раз символы
из строки b встретились в строке a (суммарное количество вхождений
каждого из уникальных символов). Заготовка:
int count(char* a, char* b);
Например,
i = count("abracadabra", "bax");
вернет значение 7.
12. Напишите функцию deleteChar, которая удаляет все вхождения символа
c в строке a. Заготовка:
void deleteChar(char* a, char c);
Задание 8.2.
1. Создать матрицу из случайных чисел и вывести построчно с форматным выводом,
выделив 3 символа на каждый столбец и пробел в качестве разделителя.
Например:
44 31 15
11 221 78
2. Осуществить транспонирование случайной матрицы (создать новую матрицу -
транспонированную из предыдущей).
3. (A) Дано число n. Создайте массив int A[n][n], и заполните его по следующему
правилу:
Числа на диагонали, идущей из правого верхнего в левый нижний угол равны 1.
Числа, стоящие выше этой диагонали, равны 0.
Числа, стоящие ниже этой диагонали, равны 2.
Полученный массив выведите на экран. Числа разделяйте одним пробелом. Пример
Вход Выход
4 0 0 0 1
0 0 1 2
0 1 2 2
1 2 2 2
2. (B) Дано число n и квадратный массив int A[n][n]. Проверьте, является ли массив
симметричным относительно главной диагонали. Программа должна выводить
слово yes для симметричного массива и слово no для несимметричного. Пример
Вход Выход
3 yes
0 1 2
1 2 3
2 3 4
Указание. Для элемента A[j] симметричным ему является элемент A[j].
3. (C) Состязания-1. В метании молота состязается n спортсменов. Каждый из них
сделал m бросков. Победителем считается тот спортсмен, у которого сумма
результатов по всем броскам максимальна.
Если перенумеровать спортсменов числами от 0 до n-1, а попытки каждого из
них – от 0 до m-1, то на вход программа получает массив int A[n][m],
состоящий из неотрицательных чисел. Программа должна определить
максимальную сумму чисел в одной строке и вывести на экран эту сумму и номер
строки, для которой достигается эта сумма. Если таких строк несколько, то
выводится номер наименьшей из них. Пример для n=4 спортсменов и m=3
попыток:
Вход Выход
4 3 19
5 6 7 1
6 6 7
7 6 6
4 3 5
Не забудьте, что нумерация строк (спортсменов) начинается с 0.
4. (D) Состязания - 2. Победителем соревнований объявляется тот спортсмен, у
которого максимален наилучший результат по всем броскам. Таким образом,
программа должна найти значение максимального элемента в данном массиве, а
также его индексы (то есть номер спортсмена и номер попытки). Программа
выводит значение максимального элемента, затем номер строки и номер столбца, в
котором он встречается. Пример
Вход Выход
4 3 5
1 4 2 1 0
5 2 5
5 1 4
1 2 4
Если в массиве несколько максимальных элементов, то нужно вывести
минимальный номер строки, в которой встречается такой элемент, а если в этой
строке таких элементов несколько, то нужно вывести минимальный номер столбца.
Не забудьте, что все строки и столбцы нумеруются с 0.
5. (E) Состязания - 3. Будем считать, что побеждает спортсмен, у которого
максимален наилучший бросок. Если таких несколько, то из них побеждает тот, у
которого наилучшая сумма результатов по всем попыткам. Если и таких несколько,
победителем считается спортсмен с минимальным номеров. Определите номер
победителя соревнований.
Вход Выход
4 3 2
8 8 8
5 9 3
9 4 7
6 6 2
6. (F) Состязания - 4. Будем считать, что победитель определяется по лучшему
результату. Определите количество участников состязаний, которые разделили
первое место, то есть определите количество строк в массиве, которые содержат
значение, равное наибольшему.
Вход Выход
4 3 2
1 2 3
4 5 6
6 2 5
2 3 4
7. (G) Состязания - 5. Решите предыдущую задачу, но на экран выведите еще и
номера спортсменов, разделивших первое место. Сначала программа выводит
количество спортсменов, показавших наилучший результат, затем – их номера в
порядке возрастания.
Вход Выход
4 3 2
1 2 3 1 2
4 5 6
6 2 5
2 3 4
8. Даны числа n и m. Создайте массив A[n][m] и заполните его спиралью по
часовой стрелке, начиная с элемента [0][0], как показано в примере.
Вход
4 10
Выход
0 1 3 6 10 14 18 22 26 30
2 4 7 11 15 19 23 27 31 34
5 8 12 16 20 24 28 32 35 37
9 13 17 21 25 29 33 36 38 39
9. Создайте матрицу A[2*N+1]x[2*N+1], заполненную по спирали от центра по
часовой стрелке, начиная с 0.
Например, N=2:
20 21 22 23 24
19 6 7 8 9
18 5 0 1 10
17 4 3 2 11
16 15 14 13 12
10. Для случайной матрицы осуществить ее абсолютную сортировку
(от [0][0] к [n-1][n-1]).
11. Отсортировать столбцы матрицы по результату среднего арифметического
элементов.
12. Создать матрицу NxN, заполненную случайными числами, но чтобы около 25%
элементов матрицы были = 0.
Расположение нулей должно быть случайным. Подсчитать количество нулей.
Например, для N=4:
1 0 5 7
2 7 0 4
0 3 8 2
4 6 1 0
13. Создать одномерный массив, который содержит последовательную запись
элементов матрицы NxM. Обеспечить интерфейс работы с данным массивом как с
матрицей:
а) вывод в виде матрицы NxM;
б) изменение элемента с координатами x, y;
в) вычисление суммы по строкам, по столбцам.
Например, матрица 2x3 из 1й задачи будет храниться в виде массива из 6
элементов:
{44, 31, 15, 11, 221, 78}, т.е. каждую новую строку матрицы мы записываем
последовательно в массив.
“Матричные” координаты 5-го элемента массива со значением 221 будут [1][1].
Задание 9.
Простые и целые числа:
1. http://acm.timus.ru/problem.aspx?space=1&num=1086&locale=ru – Криптография.
2. http://acm.timus.ru/problem.aspx?space=1&num=1607 – Такси.
3. http://acm.timus.ru/problem.aspx?space=1&num=1787 – Поворот на МЕГУ.
Возведение в степень:
4. http://codeforces.com/problemset/problem/227/C - Отсеки летающей тарелки.
5. http://acm.timus.ru/problem.aspx?space=1&num=1110&locale=ru – Степень.
Сортировки:
6. http://acm.timus.ru/problem.aspx?space=1&num=1880&locale=ru – Собственные
числа Psych up.
7. http://codeforces.com/problemset/problem/339/A - Математика спешит на помощь.
8. http://codeforces.com/problemset/problem/160/A - Близнецы.
Бинарный поиск:
9. http://acm.timus.ru/problem.aspx?space=1&num=1021&locale=ru – Таинство суммы.
10. http://codeforces.com/problemset/problem/492/B - Ваня и фонари.
11. http://codeforces.com/problemset/problem/474/B - Черви.
Стек и очередь:
12. http://acm.timus.ru/problem.aspx?space=1&num=1795&locale=ru - Мужья в магазине.
Задание 10.1 – динамика, стек и очереди
Динамика:
1. Замощение доминошками доски 3xn (см. пример 1.3).
2. http://acm.timus.ru/problem.aspx?space=1&num=1225 – Флаги.
3. http://acm.timus.ru/problem.aspx?space=1&num=1009 – К-ичные числа.
4. http://acm.timus.ru/problem.aspx?num=1087&locale=ru – Время собирать камни
5. http://acm.timus.ru/problem.aspx?num=1296 – Гиперпереход.
6. http://acm.timus.ru/problem.aspx?num=1119 – Метро.
Стек:
7. http://informatics.mccme.ru/mod/statements/view.php?id=207 – Простой стек.
8. http://informatics.mccme.ru/mod/statements/view3.php?id=207&chapterid=55 – Стек с
защитой от ошибок.
9. http://informatics.mccme.ru/mod/statements/view3.php?id=207&chapterid=56 – Стек
неограниченного размера
10. http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=634 – Скобки.
11. http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=636 – Скобки 2.
12. http://informatics.mccme.ru/mod/statements/view3.php?id=206&chapterid=52 –
Постфиксная запись.
13. http://informatics.mccme.ru/mod/statements/view3.php?id=206&chapterid=53 –
Контейнеры.
Очередь и дек:
14. http://informatics.mccme.ru/mod/statements/view3.php?id=207&chapterid=57 – Простая очередь.
15. http://informatics.mccme.ru/mod/statements/view3.php?id=207&chapterid=58 – Очередь с защитой от ошибок.
16. http://informatics.mccme.ru/mod/statements/view3.php?id=207&chapterid=59 – Очередь неограниченного размера.
17. http://informatics.mccme.ru/mod/statements/view3.php?id=207&chapterid=62 – Дек неограниченного размера.
18. http://informatics.mccme.ru/mod/statements/view3.php?id=206&chapterid=50 – Игра в пьяницу
Задача 10.2 – бинпоиск и сортировки
Бинарный поиск:
1. http://informatics.mccme.ru/mod/statements/view3.php?id=192&chapterid=2 –
Приближенный двоичный поиск
2. http://informatics.mccme.ru/mod/statements/view3.php?id=192&chapterid=3 – Сложность
двоичного поиска.
3. http://informatics.mccme.ru/mod/statements/view3.php?id=192&chapterid=4 – Двоичный поиск.
4. http://informatics.mccme.ru/mod/statements/view3.php?id=192&chapterid=111728 – Левый и правый двоичный поиск.
Бинарный поиск по ответу:
5. http://informatics.mccme.ru/mod/statements/view3.php?id=1966&chapterid=1923 –
Дипломы.
6. http://informatics.mccme.ru/mod/statements/view3.php?id=1966&chapterid=894 - Черепаха.
7. http://informatics.mccme.ru/mod/statements/view3.php?id=1966&chapterid=1620 –
Субботник.
8. http://informatics.mccme.ru/mod/statements/view3.php?id=1966&chapterid=414 – Эльфы и
олени.
9. http://informatics.mccme.ru/mod/statements/view3.php?id=1966&chapterid=1 – Коровы в стойла.
10. http://informatics.mccme.ru/mod/statements/view3.php?id=1966&chapterid=490 – Очень легкая задача.
Сортировки (для закрепления реализации алгоритмов quicksort и merge sort):
11. http://informatics.mccme.ru/mod/statements/view3.php?id=1129&chapterid=766 –
реализовать через сортировку слиянием. Проверить, что сортировка за квадрат O(n2) не пройдет.
12. http://informatics.mccme.ru/mod/statements/view3.php?id=1121&chapterid=1442 –
Объединение последовательностей (реализовать через сортировку слиянием).
13. http://informatics.mccme.ru/mod/statements/view3.php?id=1121&chapterid=767 – Похожие массивы. Реализовать через quicksort, проверить реализацию с помощью метода sort() для вектора.
Для тех, кто захочет вернуться к этой теме вот еще пара задач на очереди, сортировку и бинпоиск:
Без упражнений:
1. http://codeforces.com/contest/559/problem/B - Эквивалентные строки.
2. http://acm.timus.ru/problem.aspx?num=1047 – Простые вычисления.
3. http://acm.timus.ru/problem.aspx?num=1582 – Букмекеры.
4. http://informatics.mccme.ru/mod/statements/view3.php?id=206&chapterid=49 – Списки по классам.
5. http://informatics.mccme.ru/mod/statements/view3.php?id=206&chapterid=112984 – Гоблины и шаманы.
Задачи на векторы – можно попрактиковать здесь (упражнения 6.3 из 6й лабы):
http://informatics.mccme.ru/mod/statements/view3.php?id=4818
Описание (отчет): Нет, но можно заказать его написание
101640027-URL|
Стоимость ИСХОДНОГО ТЕКСТА программы составляет 2500 руб РФ Продажа каждой работы строго учитывается, у каждой работы есть своя история продаж. |