Обработка матриц Обработка матриц по строкам Дана матрица А[M,N]. Определить номер первой ее строки, в которой сумма четных элементов совпадает с суммой нечетных. Начало Ввод размеров матрицы M и N Ввод элементов матрицы А[M,N] Флаг = нет Для i от 0 До M CуммаЧетных = 0 CуммаНечетных = 0 Для j от 0 До N Если– четный, То CуммаЧетных = CуммаЧетных + A[i,j] Иначе CуммаНечетных = CуммаНечетных + A[i,j] Все-Если Все-Для-j Если CуммаЧетных = CуммаНечетных, То Флаг = Да Прервать Цикл Все-Если Все-Для-i Если Флаг = Нет, То Печать «Такой строки в матрице нет» Иначе Печать «Суммы совпадают в строке» + i Все-Если Конец 2.2. Обработка матриц по столбцам Дана матрица А[M,N]. Поменять местами столбцы этой матрицы, которые имеют максимальное и минимальное произведение отрицательных элементов. Начало Ввод размеров матрицы M и N Ввод элементов матрицы А[M,N] МинПроизв = МаксимальноеЧисло МаксПроизв = МинимальноеЧисло СтолбМин = -1 СтолбМакс = -1 Для j от 0 До N Произведение = 1 Для i от 0 До M Если A[i,j] < 0, То Произведение = Произведение * A[i,j] Все-Если Все-Для-i Если Произведение < МинПроизв, То МинПроизв = Произведение СтолбМакс = j Все-Если Если Произведение > МаксПроизв, То МаксПроизв = Произведение СтолбМин = j Все-Если Все-Для-j Если СтолбМакс = -1 И СтолбМин = -1, То Печать «Отрицательных элементов в матрице нет» Иначе Если СтолбМакс = СтолбМин, То Печать «Отрицательные элементы только в одном столбце» Иначе Для i от 0 До M Х = A[i, СтолбМакс] A[i, СтолбМакс] = A[i, СтолбМин] A[i, СтолбМин] = Х Все-Для-i Печать матрицы А[M,N] Все-Если Конец 2.3. Обработка квадратных матриц Дана матрица А[N, N]. Заменить все нечетные элементы этой матрицы, лежащие ниже главной диагонали, на произведение четных элементов, расположенных выше главной диагонали. Начало Ввод размера матрицы N Ввод элементов матрицы А[N,N] Произведение = 1 Флаг = Нет Для i от 0 До N Для j от 0 До N Если i < j И A[i,j] - четный, То Произведение = Произведение * A[i,j] Флаг = Да Все-Если Все-Для-j Все-Для-i Если Флаг = Нет, То Печать «Четных выше диагонали в матрице нет» Выход Из Программы Все-Если Флаг = Нет Для i от 0 До M Для j от 0 До N Если A[i,j] - нечетный, То A[i,j] = Произведение Флаг = Да Все-Если Все-Для-j Все-Для-i Если Флаг = Нет, То Печать «Нечетных ниже диагонали в матрице нет» Иначе Печать матрицы А[M,N] Все-Если Конец 3. Указания к работе Разработать и отладить программу, в которой реализовать алгоритм обработки двумерного массива в соответствии с заданием. При необходимости (если алгоритм обработки при этом упрощается) разрешается использовать вспомогательные массивы. Для задания исходных данных целесообразно использовать ввод с клавиатуры, так как размерность исходной матрицы невелика. К тому же использование генератора случайных чисел затрудняет проверку всех возможных вариантов, которые необходимо протестировать при испытании работоспособности программы. 4. Варианты индивидуальных заданий
(Сложность 1) 1. Дана матрица А[m,n]. Определить сумму минимальных элементов строк этой матрицы. 2. Дана матрица А[m,n]. Определить произведение максимальных элементов столбцов этой матрицы. 3. Дана матрица А[m,n]. Определить номер первого столбца этой матрицы, не содержащего четных элементов. 4. Дана матрица А[m,n]. Определить номер последней строки этой матрицы, содержащей хотя бы один ноль. 5. Дана матрица А[m,n]. Найти произведение четных элементов каждой строки и определить номер строки, где это произведение минимально. 6. Дана матрица А[m,n]. Определить номер первой строки, не содержащей ни одного положительного элемента. 7. Дана матрица А[m,n]. Определить количество строк, не содержащих ни одного нечетного элемента. 8. Дана целочисленная прямоугольная матрица. Определить количество столбцов, не содержащих ни одного нулевого элемента. 9. Дана целочисленная прямоугольная матрица. Определить количество нулевых элементов, являющихся единственными в своей строке и столбце. 10. Дана матрица А[m,n]. Определить количество строк, имеющих четную сумму элементов, но нечетное их произведение.
(Сложность 2) 11. Дана матрица А[m,n]. Поменять местами максимальный и минимальный элемент каждой строки. 12. Дана матрица А[m,n]. Сформировать массив В размером [m], поместив туда количество чётных элементов каждой строки матрицы. 13. Дана матрица А[m,n]. Найти первый столбец, сумма элементов которого равна сумме элементов первой строки. 14. Дана прямоугольная матрица. Найти сумму элементов в тех строках, которые содержат хотя бы один отрицательный элемент. 15. Для заданной матрицы размером М на М найти такое число k, что k-я строка матрицы совпадает с k-м столбцом. 16. Дана прямоугольная матрица. Найти произведение элементов в тех столбцах, которые не содержат нулей. 17. Дана целочисленная матрица. Определить произведение элементов в тех строках, которые не содержат отрицательных элементов. 18. Напишите программу, которая вводит матрицу и вычисляет сумму ее элементов в столбцах, где количество положительных и отрицательных элементов одинаково. 19. Ввести матрицу А[m,n]. Элементы тех строк, которые образуют возрастающую последовательность, уменьшить на 1, а тех, которые образуют убывающую последовательность, увеличить на 1. 20. Дана целочисленная прямоугольная матрица. Определить максимальное из чисел, встречающихся в заданной матрице более одного раза.
(Сложность 3) 21. Ввести матрицу А[m,n]. Поменять местами столбцы с минимальным и максимальным количеством нулей. 22. Ввести матрицу А[m,n]. Поменять местами строки, в которых находятся первый и последний четный элементы. 23. Дана матрица А размером m×n, найти такой столбец, в котором сумма нечётных элементов максимальна, и изменить порядок элементов в нём на обратный. 24. Дана матрица n×n элементов. Найти сумму всех нечётных элементов выше главной диагонали и заменить этой суммой все чётные элементы ниже главной диагонали. 25. Ввести матрицу А[m,n]. Поменять местами соседние столбцы с одинаковым количеством отрицательных элементов. 26. Ввести матрицу А[m,n]. Заменить максимальный и минимальный элементы каждого столбца на сумму элементов, расположенных между ними. 27. Ввести матрицу А[m,n]. Заменить строки, в которых количество положительных и отрицательных элементов совпадают, строкой, где находится максимальный элемент матрицы. 28. Ввести матрицу А[m,n]. Заменить столбцы, имеющие четное количество отрицательных элементов, столбцом, где находится минимальный элемент матрицы. 29. Дана матрица n×n элементов. Если количество нечётных элементов выше главной диагонали четное, то заменить все эти элементы максимальным элементом главной диагонали, а если нечетное – то минимальным ее элементом. 30. Дана матрица n×n элементов. Найти сумму всех нечётных элементов выше главной диагонали и заменить этой суммой все чётные элементы ниже главной диагонали.
(Сложность 4) 31. Дана матрица А[m,n]. Если сумма её чётных элементов больше суммы нечётных, то переставить первую и последнюю строки. Иначе переставить первый и последний столбцы. 32. Осуществить циклический сдвиг элементов матрицы размерности m×n вправо на k элементов таким образом: элементы каждой строки сдвигаются вправо, выходящие за пределы строки переносятся в начало следующей строки, элементы последней строки – в первую строку. 33. Дана матрица А[m,n], выполнить циклический сдвиг вправо на одну позицию элементов каждой строки, находящихся между минимальным и максимальным элементом этой строки. 34. Дана матрица А[n,n], упорядочить по возрастанию элементы главной диагонали. 35. Напишите программу, которая находит первое положительное число матрицы и меняет местами строку, в которой находится это число с последней строкой матрицы. 36. Дана матрица А[m,n], выполнить перенос максимального элемента каждого столбца в первую строку этого же столбца, сдвинув элементы, находившиеся выше него на один вниз. 37. Дана матрица А[m,n], выполнить циклический сдвиг всех ее столбцов, начиная со второго, так, чтобы максимальный элемент каждого столбца оказался в той же строке, что и максимальный элемент первого столбца. 38. Дана матрица А[m,n]. Поменять местами каждые две рядом расположенные строки, если максимальные элементы в них имеют одинаковую четность. 39. Дана матрица А[m,n]. Если минимальный элемент строки матрицы четный, выполнить циклический сдвиг этой строки вправо, чтобы этот элемент оказался в последнем столбце. Иначе выполнить циклический сдвиг строки влево, чтобы этот элемент оказался в первом столбце. 40. Дана матрица А[m,n]. Найти и напечатать значения всех седловых точек этой матрицы. (Седловой точкой называется элемент, имеющий минимальное значение в своей строке, но максимальный в своем столбце.)
(Сложность 5) 41. Дана целочисленная прямоугольная матрица. Определить номер строки, в которой находится самая длинная последовательность одинаковых элементов. 42. Дана целочисленная прямоугольная матрица. Поменять местами первую и последнюю строки матрицы, которые содержат одинаковые элементы. 43. Дана целочисленная прямоугольная матрица. Поменять местами первый и последний столбцы матрицы, которые не содержат одинаковых элементов. 44. Дана целочисленная прямоугольная матрица. Определить номер строки матрицы, которая содержит максимальное количество одинаковых элементов. 45. Дана матрица А[m,n]. Расположить строки этой матрицы в порядке убывания их максимальных элементов. 46. Дана матрица А[m,n]. Поменять местами строки этой матрицы, которые содержат максимальное и минимальное количество одинаковых элементов. 47. Дана матрица А[n,n]. Выполнить циклический сдвиг каждой строки так, чтобы ее минимальный элемент оказался на побочной диагонали. Направление сдвига выбрать от позиции минимального элемента к элементу побочной диагонали этой строки. 48. Дана матрица А[m,n]. Создать из неё матрицу B[m-1,n-1], элементы которой равны максимальному из элементов матрицы А, находящихся левее соответствующего столбца и выше соответствующей строки (элемент B[0,0] положить равным 0). 49. Дана матрица А[n,n]. Поменять местами столбцы, содержащие минимальный и максимальный элементы главной диагонали этой матрицы. 50. Дана матрица А[n,n]. Поменять местами строки, содержащие минимальные элементы главной и побочной диагоналей.
(Сложность 6) 51. Дана матрица А[m,n]. Удалить из неё те столбцы, в которых суммы чётных и нечётных элементов совпадают. 52. Дана матрица А[m,n].Удалить из этой матрицы все строки, которые состоят из тех же чисел, что и первая строка (несмотря на количество и порядок элементов). 53. Дана матрица А[m,n].Удалить из неё строку, содержащую максимальный чётный элемент. 54. Дана матрица А[m,n].Удалить из неё столбец, содержащий максимальное число чётных элементов. 55. Дана матрица А[m,n]. Удалить все строки, в которых число четных элементов больше числа нечетных. 56. Дана матрица А[m,n], элементы которой не равны нулю. Удалить столбец этой матрицы, который содержит минимальный по абсолютной величине элемент этой матрицы. 57. Дана матрица А[m,n]. Создать из неё матрицу B[m-1,n-1] путём удаления строки и столбца, содержащих максимальный элемент этой матрицы. 58. Составить программу, удаляющую из матрицы А[m,n] столбцы, в которых чётных элементов больше, чем нечётных. 59. Ввести матрицу А[m,n]. Удалить из неё все столбцы, в которых сумма чётных элементов будет больше суммы нечётных элементов последней строки. 60. Дана матрица А[m,n]. Создать из неё матрицу B[m-1,n], удалив в каждом столбце максимальный нечетный элемент.
(Сложность 7) 61. Дана матрица А[m,n] и массив B[m]. Удалить из матрицы те столбцы, которые содержат те же самые четные элементы, что и массив B и в таком же количестве. 62. Дана матрица А[m,n] и массив B[m]. Вставить после каждого столбца, содержащего четное количество элементов массива B столбец, содержащий элементы этого массива, при каждой вставке циклически сдвигая их на один элемент вниз. 63. Дана матрица А[m,n] и массив B[n]. Сформировать матрицу С[к,n] из тех строк матрицы А, все элементы которых имеются в массиве B, но ни один из них не стоит на том же месте. Строки, добавленные в матрицу С, из матрицы А удалить. 64. Дана матрица А1[m1,n1] и матрица А2[m2,n2], причем m1 > m2 и n1 > n2. Найти в матрице А1 все подматрицы, элементы которых совпадают с элементами матрицы А2. 65. Дана матрица А[m,n] и массив B[m*n]. Отсортировать элементы каждой строки матрицы по возрастанию, после чего выполнить слияние их в массив B так, чтобы его элементы также оказались упорядоченными по возрастанию. Алгоритмов сортировки для массива В не применять. 66. Дана матрица А[n,n]. Выполнить ее «поворот» на К*90°, где К – заданное целое число. 67. Дана матрица А1[m,n] и матрица А2[m,n], получить матрицу B[m,n], элементы которой равны разнице максимального элемента в соответствующей строке матрицы А1 и минимального элемента соответствующего столбца матрицы А2. 68. Дана матрица А1[m,n] и матрица А2[n,k], получить матрицу B[m,k], элементы которой равны сумме произведений элементов соответствующей строки матрицы А1 и соответствующего столбца матрицы А2. 69. Дана матрица А[m,n]. Вставить в каждой строке матрицы сразу после максимального элемента этой строки разность между ее максимальным и минимальным элементами, удалив в этой строке минимальный элемент. 70. Дана матрица А[m,n]. Заменить максимальный элемент каждого столбца суммой минимальных элементов предшествующего и последующего столбцов. Для первого столбца предшествующим считать последний, а для последнего следующим считать первый.
(Сложность 8) 71. Дана матрица А[m,n]. Поменять на обратный порядок элементов в строках, находящихся между строк, дающих максимальное скалярное произведение. 72. Дана матрица А[n,n]. Найти диагональ, параллельную главной диагонали этой матрицы, элементы которой имеют максимальное произведение, и сдвинуть элементы этой диагонали на К позиций вниз и вправо. 73. Дана матрица А[n,n]. Поменять местами элементы тех пар диагоналей, параллельных главной и имеющих одинаковую длину, которые имеют четное количество нечетных элементов. 74. Дана матрица А[n,n]. Определить, на какой из диагоналей, параллельных главной, элементы имеют максимальное произведение. 75. Дана матрица А[2*n,2*n], состоящая из четырех подматриц размером n*n. Поменять в этой матрице местами две любых указанных подматрицы. 76. Дана матрица А[2*n,2*n], состоящая из четырех подматриц размером n*n. Определить, имеются ли в этой матрице совпадающие по значениям элементов подматрицы. 77. Дана матрица А[n,n]. Определить, какая из четырех треугольных подматриц этой матрицы имеет максимальное произведение минимального четного на максимальный нечетный элемент. Элементы главной и побочной диагоналей не учитывать. 78. Дана матрица А[n,n], содержащая результаты игр футбольного чемпионата. Считая, что за победу в матче присуждается три очка, за ничью – одно, за поражение – ноль очков, распечатать команды в порядке занятых ими мест (по сумме полученных очков), начиная с первого. При равенстве количества очков у команд победитель определяется по количеству забитых и пропущенных мячей. При равенстве этого показателя преимущество получает победитель в личной встрече. При ничейном результате в личной встрече рассматриваются результаты встреч с другими командами (сверху вниз). 79. Разработать программу для составления решетки для шифрования. Решеткой называется матрица А[N,N] элементы которой равны 0 или 1. Количество единиц в этой матрице равно N*N/4, а расположены они таким образом, что после трех последовательных поворотов на 90° «покрывают» всю матрицу. 80. Дано целое число N. Получить матрицу А[n,n], состоящую из чисел от 1 до N*N, расположенных по спирали.
(Сложность 9) - Литературу (при необходимости) найти самостоятельно! 81. Дана матрица А[n,n]. Вычислить ее определитель путем разложения по первой строке. 82. Дана матрица А[n,n]. Путем эквивалентных преобразований привести ее к верхнему треугольному виду. 83. Разработать программу для моделирования процесса игры «Реверси», если задана последовательность ходов обоих игроков. Поверять корректность ходов, определить момент окончания игры и победителя. 84. Разработать программу для моделирования процесса игры в шашки, если задана последовательность ходов обоих игроков. Поверять корректность ходов, определить момент окончания игры и победителя. 85. Разработать программу для моделирования процесса игры в шахматы, если задана последовательность ходов обоих игроков. Поверять корректность ходов, определить момент окончания игры и победителя. 86. Разработать программу для моделирования процесса игры «Жизнь» (другое название этой же игры – «Эволюция»). 87. Расписание авиарейсов между N городами задано с помощью вещественной матрицы А[N,N], элемент которой А[K,L] равен нулю, если прямого рейса между городами K и L не существует, иначе он равен времени вылета рейса из города K в город L. Время в полете для каждого рейса хранится в аналогично организованной матрице B[N,N]. Найти все маршруты для перелета из заданного города C в заданный город D (циклические маршруты не учитывать) и выбрать из них минимальный по времени с учетом ожидания в городах пересадки с рейса на рейс. 88. Задана матрица А[N,N] родственных отношений для N человек, элемент которой А[K,L] равен нулю, если прямого родства не существует, единице – если K приходится L мужем (женой), двойке – родителем, тройке – сыном, четверке – дочерью. Ввести матрицу А, проверить ее на непротиворечивость и для заданного K найти и напечатать всех его кузин и кузенов (двоюродных сестер и братьев). Указание: имена родственников удобно хранить в массиве типа string. 89. Дана символьная строка из М символов и матрица А[N,N] (М <= N*N), элементы которой равны 0 или 1. используя эту матрицу как «решетку» для шифрования, зашифровать, а затем расшифровать исходную строку. 90. Проверить, является ли система линейных уравнений AX = B совместной.
(Сложность 10) – Литературу найти самостоятельно! 91. Решить систему линейных уравнений AX = B методом Гаусса. 92. Дана матрица А[m,n]. Выполнить разложение этой матрицы на три: нижнюю треугольную, верхнюю треугольную и перестановочную (NVP-разложение). 93. Предложить алгоритм и программу для составления магических квадратов размера N на N. 94. Предложить алгоритм и программу для составления судоку. 95. Предложить алгоритм и программу для решения судоку. 96. Разработать программу для игры «Реверси», реализующую выигрышную стратегию для компьютера. 97. По заданной матрице координат установочных мест и связности элементов электрической схемы между собой определить оптимальное размещение элементов по заданным местам по критерию минимальной длины соединений. 98. Предложить модель кубика Рубика с использованием двумерных или трехмерных массивов (по выбору). Считая исходное положение кубика упорядоченным (кубик собран) ввести последовательность ходов (поворотов его граней) и напечатать полученное состояние кубика. 99. Задана матрица, представляющая собой дискретное рабочее поле односторонней печатной платы. Положительными числами заданы номера цепей, подлежащих трассировке, отрицательными (например, -1) – области, запрещенные для трассировки. Выполнить трассировку заданных цепей волновым алгоритмом. 100. Задано две матрицы одинакового размера, представляющие собой дискретное рабочее поле двусторонней печатной платы. Положительными числами заданы номера цепей, подлежащих трассировке, отрицательными (например, -1) – области, запрещенные для трассировки. Выполнить трассировку заданных цепей лучевым алгоритмом.
5. Оформление отчета В отчет включить: • Тему и цель работы; • Задание на выполнение (конкретный вариант индивидуального задания); • Алгоритм программы в виде псевдокода. Части алгоритма, выполняющие законченные этапы общего алгоритма, целесообразно оформить в виде подалгоритмов; • Текст программы с комментариями; • Результаты выполнения программы (для нескольких размеров исходной матрицы и для различных ситуаций наличия или отсутствия решения в зависимости от исходных данных):
На повестке дня: 13. Дана матрица А[m,n]. Найти первый столбец, сумма элементов которого равна сумме элементов первой строки. 11. Дана матрица А[m,n]. Поменять местами максимальный и минимальный элемент каждой строки. В каждом из нас спит гений, но с каждым днем все крепче и крепче. ^_^
1. Цель работы Приобретение и закрепление навыков работы с одномерными массивами. 2. Теоретический материал Сортировка пузырьком Расположим массив сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом, второй по величине элемент поднимается на правильную позицию... Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
Алгоритм сортировки «пузырьком» представлен ниже:
i-цикл от 0 до size с шагом 1 j-цикл от size-1 до i с шагом -1 если a[j-1] > a[j], то x = a[j-1] a[j-1] = a[j] a[j] = x все если все j-цикл все i-цикл
Среднее число сравнений и обменов имеют квадратичный порядок роста: O(n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Сортировка выбором Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м. На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.
Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Алгоритм сортировки выбором представлен ниже: i-цикл от 0 до size с шагом 1 k = i x = a[i] j-цикл от i + 1 до size с шагом 1 если a[j] < x, то k = j x = a[j] все если все j-цикл a[k] = a[i] a[i] = x все i-цикл
Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций: n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = O(n2)
Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов. Алгоритм не использует дополнительной памяти: все операции происходят "на месте".
Сортировка вставками Сортировка простыми вставками в чем-то похожа на вышеизложенные методы. Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале «вырастает» отсортированная последовательность... Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться (см. название метода) все новые элементы. Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте (вставка завершена), либо они меняются местами и процесс повторяется.
Таким образом, в процессе вставки мы «просеиваем» элемент x к началу массива, останавливаясь в случае, когда 1. Найден элемент, меньший x 2. Достигнуто начало последовательности. Алгоритм сортировки вставками представлен ниже: i-цикл от 0 до size с шагом 1 x = a[i]
j-цикл от i-1 пока (j >= 0 И a[j] > x) с шагом -1 a[j+1] = a[j] все j-цикл
a[j+1] = x все i-цикл
Аналогично сортировке выбором, среднее, а также худшее число сравнений и пересылок оцениваются как O(n2), дополнительная память при этом не используется. Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Сортировка подсчетом Данный метод сортировки требует использования вспомогательного массива, по размеру совпадающего с исходным. В этот массив помещаются отсортированные элементы. Суть метода заключается в том, что на каждом шаге подсчитывается, в какую позицию результирующего массива надо записать очередной элемент исходного массива. Выглядит это так: Для i = 0 До N-1 k = 0 Для j = 0 До N-1 Если A(i) > A(j) Или A(i) = A(j) И j < i, То k = k +1 Все-Если Все-Для-j B(k) = A(i) Все-Для-i Вычисление номера позиции, куда нужно поместить очередной элемент, реализуется, исходя из следующих соображений. Слева от B(k) должны стоять элементы, меньшие или равные B(k). Значит, число k складывается из количества элементов меньших A(i) и, возможно, некоторого числа элементов, равных A(i). Условимся, что из равных мы будем учитывать только те элементы, которые в исходном массиве стоят левее A(i). Сортировка слиянием Этот метод сортирует массив последовательным слиянием пар уже отсортированных подмассивов, поэтому его и назвали сортировкой слиянием. Поскольку данный метод имеет повышенную (по сравнению с уже рассмотренными) сложность, то алгоритм данного метода предлагается найти в литературе и реализовать самостоятельно. Линейный поиск в массиве Линейным поиском называется обычный просмотр всего массива на предмет нахождения отдельного элемента, отвечающего заданному условию. Линейный поиск – простейшая разновидность алгоритмов поиска данных. Например, если нам требуется найти число 5 в массиве из 15 элементов, то мы начинаем поиск с элемента с номером 0 и последовательно проверяем каждый элемент на равенство числу 5. Если совпадение найдено – необходимо запомнить номер элемента и завершить цикл поиска. Ввиду простоты алгоритма его псевдокод и реализация не приводятся и предлагаются для самостоятельной работы. Двоичный поиск в массиве Если у нас есть массив, содержащий упорядоченную последовательность данных, то очень эффективен двоичный поиск. Переменные lowerBound и upperBound содержат, соответственно, левую и правую границы отрезка массива, где находится нужный нам элемент. Мы начинаем всегда с исследования среднего элемента отрезка. Если искомое значение меньше среднего элемента, мы переходим к поиску в верхней половине отрезка, где все элементы меньше только что проверенного. Другими словами, значением upperBound становится (M – 1) и на следующей итерации мы работаем с половиной массива. Таким образом, в результате каждой проверки мы вдвое сужаем область поиска. Так, в нашем примере, после первой итерации область поиска – всего лишь три элемента, после второй остается всего лишь один элемент. Таким образом, если длина массива равна 6, нам достаточно трех итераций, чтобы найти нужное число. Двоичный поиск - очень мощный метод. Если, например, длина массива равна 1023, после первого сравнения область сужается до 511 элементов, а после второй - до 255. Легко посчитать, что для поиска в массиве из 1023 элементов достаточно 10 сравнений. Алгоритм двоичного поиска приведен ниже: lowerBound = 0 upperBound = size
Повторять бесконечно M = (lowerBound + upperBound) / 2
Если K < A[M], то upperBound = M – 1 Иначе Если K > A[M], то lowerBound = M + 1 Иначе Сообщить «Элемент найден, его индекс: », M Выход из цикла Все если
Если lowerBound > upperBound, то Сообщить «Элемент не найден» Выход из цикла Все если Все повторять
В описанном выше алгоритме приняты следующие условия: 1. size – размер массива 2. K – число, которое нужно найти 3. М – индекс найденного элемента. Инициализация массива случайными числами Для выполнения лабораторной работы №3 придется пользоваться массивами большого размера. Размеры массивов в данной работе могут достигать 15 тысяч элементов, что не позволяет реализовать ввод данных с клавиатуры. Для решения этой задачи предлагается использовать инициализацию массива случайными числами. Для работы с генератором случайных чисел необходимо создать объект стандартного класса Random: Random Rnd = new Random(); Инициализация массива выполняется с помощью метода Next класса Random и может выглядеть следующим образом: int maxValue = 100; int[] a = new int[1000]; for (int i = 0; i < 1000; i++) a[i] = Rnd.Next(0, maxValue); // Случайное число от 0 до 100 Измерение времени работы программы В задании на лабораторную работу требуется измерить время работы программы. Для этого удобно воспользоваться стандартным классом Environment, который содержит свойство TickCount, в котором содержится время (в миллисекундах), прошедшее с момента загрузки операционной системы. Чтобы определить время работы какого-либо фрагмента кода, необходимо выполнить два замера времени (до и после этого фрагмента), а потом вычислить разность полученных значений. Для перевода результата в секунды можно разделить его на 1000. Вот как может выглядеть текст функции Main(), в котором производится замер времени работы фрагмента кода: static void Main(string[] args) { // Здесь выполняется инициализация данных (ввод массивов и проч.) int t1 = Environment.TickCount; // Здесь выполняется основная работа программы (например, // сортировка массива и поиск данных. int t2 = Environment.TickCount; // Печать затраченного времени на экране Console.WriteLine("Продолжительность работы: " + (t2 - t1) / 1000.0); // Печать полученного массива } 3. Указание к работе Разработать и отладить программу, в которой реализовать алгоритмы сортировки и поиска в соответствии с заданием. Определить время работы программы. Для выполнения задания необходимо использовать два одномерных массива целых чисел А[M] и В[N] (М и N – произвольные целые числа, не превышающие 214). Инициализируйте исходные массивы данными, после чего отсортируйте массивы с использованием алгоритма, указанного в вашем задании. Создайте одномерный массив С, который содержит элементы, отвечающие условию задания, в одном экземпляре (без повторений). Сравните время работы программы при следующих размерах исходных массивов: 100, 1000, 5000, 10000, 15000 элементов. Указание: Вспомогательные массивы использовать запрещается, если в алгоритме сортировки не оговорено обратное.
4. Варианты индивидуальных заданий Задание Сложность Алгоритм сортировки Алгоритм поиска 1. элементы, присутствующие в обоих массивах А и В 1 Пузырьком Линейный 2. элементы, которые есть только в массиве А или только в массиве В 1 Пузырьком Линейный 3. элементы, которые присутствуют в массиве А, но отсутствуют в массиве В 1 Пузырьком Линейный 4. элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах 1 Пузырьком Линейный 5. элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В 1 Пузырьком Линейный 6. элементы, которые присутствуют в нескольких экземплярах либо только в массиве A, либо только в массиве В 1 Пузырьком Линейный 7. элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) 1 Пузырьком Линейный 8. элементы массива А, повторяющиеся в массиве В несколько раз 1 Пузырьком Линейный 9. элементы присутствующие в обоих массивах А и В в одном экземпляре 1 Пузырьком Линейный 10. элементы, присутствующие в одном экземпляре либо только в массиве А, либо только в массиве В 1 Пузырьком Линейный 11. повторяющиеся элементы массива А, которые есть в массиве В 1 Пузырьком Линейный 12. повторяющиеся элементы массива В, которые есть в массиве А только в одном экземпляре 1 Пузырьком Линейный 13. неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах 1 Пузырьком Линейный 14. элементы массива А в одном экземпляре, которые присутствуют в массиве В в нескольких экземплярах 1 Пузырьком Линейный 15. повторяющиеся элементы массива А, которых нет в массиве В 1 Пузырьком Линейный 16. элементы, присутствующие в обоих массивах А и В 2 Выбором Линейный 17. элементы, которые есть только в массиве А или только в массиве В 2 Выбором Линейный 18. элементы, которые присутствуют в массиве А, но отсутствуют в массиве В 2 Выбором Линейный 19. элементы, которые присутствуют в обоих массивах А и В в нескольких экземплярах 2 Выбором Линейный 20. элементы, которые присутствуют в нескольких экземплярах в массиве А, но отсутствуют в массиве В 2 Выбором Линейный
На повестке: 13. неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах 1 Пузырьком Линейный
Да Володя на шарпе конечна. Для начала опишу рабочий метод создания и сортировки для третьей лабы:
Code
using System; using System.Collections.Generic; using System.Text; namespace Lab3 { class Program { static void Main(string[] args) {
Console.Write("Введите размер массива N: "); //Выдаем запрос на ввод размера массива int N = Convert.ToInt32(Console.ReadLine()); //Заносим размер массива в переменную N
Random Rnd = new Random(); // создаем генератор случайных чисел int[] a = new int[N]; // создаем массив А int[] c = new int[N]; // создаем массив с int[] b = new int[N]; // создаем массив b int kol; // счетчик количества неповторяющихся элементов bool found; // создаем флаг поиска double t1 = Environment.TickCount; // отсчёт до начала операций
for (int i = 0; i < N; i++) //цикл заполнения { a[i] = Rnd.Next(0, N); //запоняем массив А случайными числами
}
for (int i = 0; i < N; i++) //цикл заполнения b[i] = Rnd.Next(0, N); //запоняем массив Б случайными числами
Console.WriteLine("Массив А без сортировки: "); for (int i = 0; i < N; i++) //Вывод массива A без сортировки { Console.Write(a[i] + " "); //Вывод массива А без сортировки
}
Console.WriteLine("\n" + "Массив Б без сортировки: "); for (int i = 0; i < N; i++) //Вывод массива Б без сортировки { Console.Write(b[i] + " "); //Вывод массива Б без сортировки }
//Сортировка Пузырьком массива А for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { if (a[j - 1] > a[j]) { int x = a[j - 1]; a[j - 1] = a[j]; a[j] = x;
}
} } //Сортировка Пузырьком массива Б for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { if (b[j - 1] > b[j]) { int x = b[j - 1]; b[j - 1] = b[j]; b[j] = x;
}
} } Console.WriteLine("\n" + "Массив А После сортировки: "); for (int i = 0; i < N; i++) //Вывод массива А после сортировки { Console.Write(a[i] + " "); //Выв } Console.WriteLine("\n" + "Массив Б После сортировки: "); for (int i = 0; i < N; i++) //Вывод массива Б после сортировки {
Console.Write(b[i] + " "); //Вывод массива Б после сортировки
namespace lab4 { class Program { static void Main(string[] args) {
Console.Write("Введите n: "); //Выдаем запрос на ввод количества строк int n = Convert.ToInt32(Console.ReadLine()); //Заносим количество строк в n
Console.Write("Введите m: "); //Выдаем запрос на ввод количества столбцов int m = Convert.ToInt32(Console.ReadLine()); //Заносим количество столбцов в m
double[,] msv = new double[n, m]; //создаем двумерный массив
//Заполняем массив for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Console.Write("msv[{0}, {1}] = ", i, j); msv[i, j] = Convert.ToDouble(Console.ReadLine()); } }
//Выводим мартицу Console.WriteLine("Введенная матрица:"); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Console.Write("{0} ", msv[i, j]);
Супер система рандом3М выбрала задание: 13. неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах 1 Пузырьком Линейный В каждом из нас спит гений, но с каждым днем все крепче и крепче. ^_^
так пойду покурю, Кстати сеня маку-сан звонил,грит винду менять будет вскоре. Ему чел сказал что в максимальной семерке есть уже ВСЕ необходимые проги от аимпа до фотоша, а казя ему сказал что можно полностью переразметить винты снеся файловую разметку и потом ничего не потеряется из данных...
13. неповторяющиеся элементы массива А, которые присутствуют в массиве В в нескольких экземплярах 1 Пузырьком Линейный
Code
using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace ConsoleApplication1 { class Program {
static void Main(string[] args) { Console.Write("Введите размер массива N: "); //Выдаем запрос на ввод размера массива int N = Convert.ToInt32(Console.ReadLine()); //Заносим размер массива в переменную N
Random Rnd = new Random(); // создаем генератор случайных чисел int[] a = new int[N]; // создаем массив А int[] c = new int[N]; // создаем массив с int[] b = new int[N]; // создаем массив b int kol; // счетчик количества неповторяющихся элементов bool found; // создаем флаг поиска double t1 = Environment.TickCount; // отсчёт до начала операций
for (int i = 0; i < N; i++) //цикл заполнения { a[i] = Rnd.Next(0, N); //запоняем массив А случайными числами
}
for (int i = 0; i < N; i++) //цикл заполнения b[i] = Rnd.Next(0, N); //запоняем массив Б случайными числами
Console.WriteLine("Массив А без сортировки: "); for (int i = 0; i < N; i++) //Вывод массива A без сортировки { Console.Write(a[i] + " "); //Вывод массива А без сортировки
}
Console.WriteLine("\n" + "Массив Б без сортировки: "); for (int i = 0; i < N; i++) //Вывод массива Б без сортировки { Console.Write(b[i] + " "); //Вывод массива Б без сортировки }
//Сортировка Пузырьком массива А for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { if (a[j - 1] > a[j]) { int x = a[j - 1]; a[j - 1] = a[j]; a[j] = x;
}
} } //Сортировка Пузырьком массива Б for (int i = 0; i < N; i++) { for (int j = 1; j < N; j++) { if (b[j - 1] > b[j]) { int x = b[j - 1]; b[j - 1] = b[j]; b[j] = x;
}
} } Console.WriteLine("\n" + "Массив А После сортировки: "); for (int i = 0; i < N; i++) //Вывод массива А после сортировки { Console.Write(a[i] + " ");
} Console.WriteLine("\n" + "Массив Б После сортировки: "); for (int i = 0; i < N; i++) //Вывод массива Б после сортировки {
Console.Write(b[i] + " "); //Вывод массива Б после сортировки
}
//Линейный поиск kol = 0; for (int i = 0; i < N; i++) {
c[kol] = a[i]; found = false; for (int j = 0; j < N; j++) if (c[kol] == a[j] && i != j) // выполняем проверку условия found = true; if (!found) { found = false; for (int y = 0; y < N; y++) { if (c[kol] == b[y] && found) { kol++;break; } if (c[kol] == b[y]) found = true; } }
}
Console.WriteLine("\n" + "По условию: "); for (int z = 0; z <kol; z++) { Console.Write(c[z] + " ");
} double t2 = Environment.TickCount; // время конца работы Console.Write ("\n" + "Продолжительность работы упорядочивания и "); Console.WriteLine("поиска: " + (t2 - t1) + " миллисекунд");
Console.ReadKey(); }
В каждом из нас спит гений, но с каждым днем все крепче и крепче. ^_^
ЗАДАНИЕ - 13. Дана матрица А[m,n]. Найти первый столбец, сумма элементов которого равна сумме элементов первой строки.
Code
using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace lab4 // Выполнил студент ВМКСС Днепровский Александр { class Program { static void Main(string[] args) {
Console.Write("Введите n: "); //Выдаем запрос на ввод количества строк int n = Convert.ToInt32(Console.ReadLine()); //Заносим количество строк в n
Console.Write("Введите m: "); //Выдаем запрос на ввод количества столбцов int m = Convert.ToInt32(Console.ReadLine()); //Заносим количество столбцов в m
int[,] msv = new int[n, m]; //создаем двумерный массив
//Заполняем массив for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Console.Write("msv[{0}, {1}] = ", i, j); msv[i, j] = Convert.ToInt32(Console.ReadLine()); } }
//Выводим мартицу Console.WriteLine("Введенная матрица:"); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Console.Write("{0} ", msv[i, j]);
} Console.WriteLine(); }
// int summstr = 0;
for (int i = 0; i < n; i++) { int summstb = 0; int summstr = 0; int summone = 0; int k = 0; for (int j = 0; j < m; j++) { //summstr = summstr + msv[i,j]; //Ищем сумму summstb = summstb + msv[j, n]; //Ищем произведение summone = summone + msv[0, i];
if (summstb == msv[0,i]) // проверяем четность суммы и нечетность произведенния k = msv[j,i]; //подсчет количества строк
} if (k != 0) Console.Write("\n" + "В матрице по условию " + k); else //Вывод сообщения при отсутствии нужных строк Console.Write("\n" + "Нет такого столбца");
/* ЗАДАНИЕ - 13. Дана матрица А[m,n]. Найти первый столбец, сумма элементов которого равна сумме элементов первой строки. */
Code
using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace lab4 // Выполнил студент ВМКСС Авельев Владимир { class Program { static void Main(string[] args) { Console.Write("Введите количество строк n: "); //Выдаем запрос на ввод количества строк int n = Convert.ToInt32(Console.ReadLine()); //Заносим количество строк в n
Console.Write("Введите количество столбцов m: "); //Выдаем запрос на ввод количества столбцов int m = Convert.ToInt32(Console.ReadLine()); //Заносим количество столбцов в m
int[,] msv = new int[n, m]; //создаем двумерный массив
//Заполняем массив for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Console.Write("msv[{0}, {1}] = ", i+1, j+1); msv[i, j] = Convert.ToInt32(Console.ReadLine()); } }
//Выводим мартицу Console.WriteLine("Введенная матрица:"); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) Console.Write("{0} ", msv[i, j]); Console.WriteLine(); }
int summstbt = 0; int summstr1 = 0; int CyKa=0; for (int i = 0; i < m; i++) summstr1 += msv[0, i]; //Ищем сумму первой строки!!! for (int i = 0; i < m; i++, summstbt = 0) { for (int j = 0; j < n; j++) summstbt += msv[j, i]; if (summstbt == summstr1) { CyKa = i + 1; break; } }
if(CyKa!=0) Console.Write("\n" + "В матрице по условию столбец " + CyKa); else //Вывод сообщения при отсутствии нужных строк Console.Write("\n" + "Нет такого столбца"); Console.ReadKey(); // Ожидаем нажатие клавиши для завершения }
}
}
В каждом из нас спит гений, но с каждым днем все крепче и крепче. ^_^
уха ха мне кажется имя не чего не поменяет, лень это хорошо но не в таком виде. Лень хороша когда тебе необходимо что то сделать, плюс старания, порождают гениальные творения. Я так же хотел нах снести свой сайт а после одумался, осознав что проще улучшить свой сайт (путь лентяя))) например добавить контента или новых идей. В каждом из нас спит гений, но с каждым днем все крепче и крепче. ^_^
задача надо пройти синусоидально по двумерной матрице от начала и до конца (песочные часы или бантик) массив(является квадратом) m[N,N] N-может быть четным или нечетным В каждом из нас спит гений, но с каждым днем все крепче и крепче. ^_^
Владимир Авельев Разработать и отладить программу, в которой реализовать алгоритмы сортировки и поиска в соответствии с заданием. Определить время работы программы. Для выполнения задания необходимо использовать два одномерных массива целых чисел А[M] и В[N] (М и N – произвольные целые числа, не превышающие 214). Инициализируйте исходные массивы данными, после чего отсортируйте массивы с использованием алгоритма, указанного в вашем задании. Создайте одномерный массив С, который содержит элементы, отвечающие условию задания, в одном экземпляре (без повторений). Сравните время работы программы при следующих размерах исходных массивов: 100, 1000, 5000, 10000, 15000 элементов. Указание: Вспомогательные массивы использовать запрещается, если в алгоритме сортировки не оговорено обратное. * Элементы, которые присутствуют в нескольких экземплярах либо в массиве А, либо в массиве В (либо в обоих массивах) 1 Пузырьком Линейный сегодня в 14:13|Редактировать|Удалить Online
Владимир Авельев сортировка пузырьком, линейный поиск сегодня в 14:14|Редактировать|Удалить Online
Владимир Авельев я тут код на си++ без компилятора накалякал хз может есть ошибки но суть я думаю я передал, нада на шарпе а мне влом его ставить сегодня в 14:17|Редактировать|Удалить Online
Владимир Авельев int M,N,p; int А[M],В[N]; p=(M int C[p] int n=0;
запуск таймера
// Здесь выполняется инициализация данных (ввод массивов и проч.) int t1 = Environment.TickCount; // Здесь выполняется основная работа программы (например, // сортировка массива и поиск данных.
заполнение массива int[] a = new int[M]; for (int i = 0; i < M; i++) a[i] = Rnd.Next(0, 100); // Случайное число от 0 до 100
линейный поиск в массивах for(int i=0;i for(int j=0;j if(A[i]==B[j]) C[n++]=A[i];
линейный поиск в массиве B[N] (для A[M]такаяже) bool ok=1; for(int i=1;i if(B[i]==B[i-1]) { for(int j=0;j if(C[j]==B[i]){ok=0;break;} if(ok)C[n++]=B[i]; }
остановка таймера
int t2 = Environment.TickCount; // Печать затраченного времени на экране Console.WriteLine("Продолжительность работы: " + (t2 - t1) / 1000.0); // Печать полученного массива сегодня в 14:17|Редактировать|Удалить Online
Владимир Авельев вот еще задача Дана матрица А[m,n]. Определить количество строк, не содержащих ни одного нечетного элемента. сегодня в 14:20|Редактировать|Удалить Online
Владимир Авельев a[m,n] int count; for(int ok=1,i=0;i { for(int j=0;j if(a[i,j]<0)ok=0; if(ok)count++; } сегодня в 14:21|Редактировать|Удалить
Александр Днепровский Номер варианта в студию, не забывай, я их по винтовой БД сканерну сегодня в 14:21|Это спам|Ответить Online
Владимир Авельев и еще задача SameCount(s, n) 1 Подсчет количества слов в строке, начинающихся и заканчивающихся на одну и ту же букву сегодня в 14:22|Редактировать|Удалить Online
Владимир Авельев хз на сишарп может и с той функцией как то можно мне влом шарп ставить я на си тебенапишу примитив тут нет проверки на доп. символы типа ?%№"№;%:? и тп тут тока на пробел кароче текст тока из слов и пробелов int count; char c; string text;
хз должно работать сегодня в 14:22|Редактировать|Удалить Online
Владимир Авельев нах тебе номер я ж задачи написал а так №7 сегодня в 14:23|Редактировать|Удалить Online
Владимир Авельев 1. Даны первый член и знаменатель геометрической прогрессии, написать рекурсивную функцию для суммы n первых членов прогрессии. блиииииин я тока щя понял задачу, щя код поделаю, тока узнаю что такое геометрическая прогрессия))) сегодня в 14:25|Редактировать|Удалить Online
Владимир Авельев что такое геом. прогрессия я терь знаю приступаю к разработке кода сегодня в 14:31|Редактировать|Удалить Online
Владимир Авельев хз без компилятора могу и наделать ошибки
int p;//pervij; int m;//mnojitel; int c;//count;
int sum(int ch/*chislo*/) { for(;c>0;c--) { p=p*m; return sum(ch) } return p; } В каждом из нас спит гений, но с каждым днем все крепче и крепче. ^_^
Дана прямоугольная матрица B(n,m)n,m>=2. Написать функцию, возвращающую указатель на верхний левый угол подматрицы размером 2*2, имеющей наибольший определитель, и значение определителя.
Добавлено (17 Май 2012, 18:51) --------------------------------------------- можете помочь?
