ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.10.2023
Просмотров: 439
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Решение задач с массивами 83
for (
[ int j = i; \ j > start && ] intArray[j-1] > intArray[j]; j--) {
^ int temp = intArray[j-1];
intArray[j-1] = intArray[j];
intArray[j] = temp;
}
}
Мы начинаем с объявления двух переменных, start
X
и end
Y
, обозначающих индекс первого и последнего элементов массива.
Так код становится более удобным для чтения, а также при необхо- димости может быть легко модифицирован для сортировки только части массива. Внешний цикл выбирает следующую «карту», кото- рая должна быть вставлена в наш все возрастающий отсортирован- ный набор
Z
. Обратите внимание на то, что при инициализации этого цикла счетчику i присваивается значение start + 1. Помни- те, в коде для нахождения наибольшего значения мы инициализи- ровали переменную с наибольшим значением первым элементом массива и начали цикл со второго элемента массива. В этом случае идея та же. Если у нас есть только одно значение (или «карта»), то по определению она «упорядочена», и мы можем начать с рассмо- трения вопроса о том, должно ли второе значение располагаться до или после первого. Внутренний цикл помещает текущее значе- ние в правильную позицию, многократно меняя местами текущее значение с предшествующим ему, пока оно не окажется в нужной позиции. Начальным значением счетчика цикла j является i
[
, и цикл уменьшает это значение на 1, пока не будет достигнут нижний предел массива
\
и не найдется правильная позиция для этого но- вого значения
]
. До тех пор мы будем использовать три инструк- ции присваивания для смещения текущего значения на одну пози- цию в массиве
^
. Другими словами, если бы у вас был набор из 13 игральных карт, из которых четыре крайние левые были уже отсо- ртированы, то вы могли бы поместить пятую карту слева в правиль- ную позицию, последовательно перемещая ее на одну позицию до тех пор, пока ее значение не превысит значение карты, располо- женной слева от нее. Именно это делает внутренний цикл. Внеш- ний цикл делает это для каждой карты, начиная с крайней левой.
Таким образом, к моменту завершения цикла весь массив будет от- сортирован.
В большинстве случаев сортировка вставками — не самый эффек- тивный алгоритм, и, честно говоря, приведенный выше код — даже не самый эффективный способ выполнения такого рода сортиров- ки. Тем не менее он подходит для небольших массивов и достаточ- но прост, чтобы его можно было запомнить, поэтому считайте его ментальным макросом. Вне зависимости от того, какой алгоритм сор тировки вы выберете, у вас должен быть приличный метод код для которого вы можете легко создать самостоятельно. Недостаточ- но иметь доступ к чужому коду для осуществления сортировки, кото- рый вы не вполне понимаете. Вам не следует возиться с машиной, если вы не знаете, как она работает.
84 Глава 3
Вычисление статистических показателей
Последняя операция похожа на поиск в том плане, что перед воз- вратом значения нам нужно просмотреть каждый элемент массива.
Отличие заключается в том, что это значение является не просто одним из элементов массива, а некоторым статистическим пока- зателем, вычисленным на основании всех значений в массиве. На- пример, мы могли бы вычислить среднее арифметическое значе- ние, медиану или статистическую моду, и сделаем это далее в этой главе. Примером вычисления простейшего статистического пока- зателя могло бы быть среднее арифметическое значение оценок учащихся: const int ARRAY_SIZE = 10;
int gradeArray[ARRAY_SIZE] = {87, 76, 100, 97, 64, 83, 88, 92, 74, 95};
double sum = 0;
for (int i = 0; i < ARRAY_SIZE; i++) {
sum += gradeArray[i];
}
double average = sum / ARRAY_SIZE;
В качестве еще одного простого примера рассмотрим проверку данных. Пусть массив значений типа double с именем vendorPayments содержит данные о платежах поставщикам. Действительны только положительные значения, поэтому отрицательные указывают на проблемы целостности данных. В части отчета о проверке мы мо- жем написать цикл для подсчета количества отрицательных значе- ний в массиве:
const int ARRAY_SIZE = 10;
int countNegative = 0;
for (int i = 0; i < ARRAY_SIZE; i++) {
if (vendorPayments[i] < 0) countNegative++;
}
Решение задач с помощью массивов
После того как вы разберетесь с общими операциями, решение за- дач с помощью массивов не будет сильно отличаться от их решения с использованием простых данных, которые разбирались в преды- дущей главе. Рассмотрим один пример и проработаем все его этапы, используя методы из предыдущей главы и любую из часто применяе- мых операций для массивов, которые нам могут понадобиться.
: 9 " #
В статистике мода набора значений представляет собой самое часто встречающееся значение. Напишите код, который обрабатывает массив данных опроса, в ходе кото- рого респонденты отвечали на вопрос с помощью цифры от 1 до 10, чтобы определить моду набора данных. Для нашей цели можно выбрать любую моду, если их окажется несколько.
Решение задач с массивами 85
В этой задаче нам требуется извлечь из массива одно значе- ние. Используя методы поиска аналогии и начав с уже известного, мы можем надеяться на то, что сможем применить вариант поис- ковой техники, с которой познакомились, когда искали наиболь- шее значение в массиве. Принцип работы этого кода заключается в сохранении наибольшего из наблюдаемых до сих пор значений в переменной. Затем код сравнивает каждое последующее значение с этой переменной, заменяя ее при необходимости. В данном слу- чае аналогичный метод заключается в том, что мы будем сохранять наиболее часто встречающееся до сих пор значение в переменной, а затем изменять ее при обнаружении более распространенного значения в массиве. Когда мы проговариваем это словами, кажет- ся, что это может сработать, но когда думаем о реальном коде, то обнаруживаем проблему. Давайте рассмотрим образец массива и константу размера для этой задачи: const int ARRAY_SIZE = 12;
int surveyData[ARRAY_SIZE] = {4, 7, 3, 8, 9, 7, 3, 9, 9, 3, 3, 10};
Модой среди этих данных является значение 3, потому что оно встречается четыре раза, то есть чаще, чем любое другое. Однако если мы обрабатываем этот массив последовательно, как в задаче с нахождением «наибольшего значения», в какой момент мы решаем, что значение 3 является нашей модой? Как мы узнаем, что оно встре- тилось в массиве в четвертый и последний раз? Кажется, что у нас нет никакой возможности выяснить это с помощью одной последо- вательной обработки данных массива.
Итак, обратимся к одному из других наших методов: упрощению задачи. Что, если бы мы упростили себе жизнь, собрав вместе все случаи появления одного и того же значения? Например, что, если бы наш массив с данными результатов опроса выглядел так: int surveyData[ARRAY_SIZE] = {4, 7, 7, 9, 9, 9, 8, 3, 3, 3, 3, 10};
Теперь оба значения 7 собраны вместе, как и значения 9 и 3.
После такой группировки данных кажется возможным последо- вательно обработать массив с целью нахождения моды. Обраба- тывая массив вручную, легко подсчитать количество каждого из значений, поскольку вы просто отсчитываете элементы массива, пока вам не встретится другое значение. Тем не менее преобра- зовать наши мыслительные операции в программные инструкции может быть сложно. Поэтому, прежде чем пытаться написать код для этой упрощенной задачи, давайте напишем некоторый псевдо-
код, представляющий программные инструкции, написанные на языке, который представляет собой нечто среднее между челове- ческим языком и C++. Этот код будет напоминать о том, что мы пытаемся сделать с каждым утверждением, которое нужно напи- сать.
1 ... 6 7 8 9 10 11 12 13 ... 34
86 Глава 3
int mostFrequent =
X?;
int highestFrequency =
X?;
int currentFrequency = 0;
Y for (int i = 0; i < ARRAY_SIZE; i++) {
Z currentFrequency++;
[ if (surveyData[i] IS LAST OCCURRENCE OF A VALUE) {
\ if (currentFrequency > highestFrequency) {
highestFrequency = currentFrequency;
mostFrequent = surveyData[i];
}
] currentFrequency = 0;
}
}
Не существует правильного или неправильного способа написа- ния псевдокода, и если вы собираетесь использовать данную техни- ку, то вам следует выработать свой собственный стиль. Когда я пишу псевдокод, я стараюсь использовать действительный C++ для любой инструкции, в которой я уже уверен, а затем на человеческом языке пишу то, что я все еще обдумываю. В данном случае мы знаем, что нам понадобится переменная (mostFrequent) для хранения наиболее часто встречающегося до сих пор значения, которое после оконча- ния цикла будет являться модой, если все будет сделано правильно.
Нам также нужна переменная для хранения данных о том, насколь- ко часто встречается это значение (highestFrequency), с которой мы можем производить сравнение. Наконец, нам нужна переменная, которую мы можем использовать для подсчета частоты отслежива- емого значения в процессе последовательной обработки массива
(currentFrequency). Мы знаем, что нужно инициализировать наши переменные. Значение currentFrequency логически должно начи- наться с 0, однако в отсутствие другого кода пока неясно, как следу- ет инициализировать остальные переменные. Итак, давайте просто расставим вопросительные знаки
X
в качестве напоминания.
Сам цикл представляет собой уже знакомый нам цикл для обра- ботки массива, поэтому он уже представлен в окончательной фор- ме
Y
. Внутри цикла мы инкрементируем значение переменной, которая подсчитывает количество раз, когда встречается текущее значение
Z
, а затем следует ключевая инструкция. Мы знаем, что нужно проверить, достигли ли мы последнего случая появления определенного значения
[
. Данный псевдокод позволяет пока про- пустить этап выявления логики и набросать остальную часть кода.
Однако если это действительно последний раз, когда встречается данное значение, мы знаем, что нужно делать, поскольку это по- хоже на код для нахождения «наибольшего значения»: нужно выяс- нить, превышает ли частота этого значения частоту значения, ко- торое до сих пор было самым часто встречающимся. Если это так, то данное значение становится новым наиболее часто встречаю- щимся значением
\
. Тогда, поскольку следующее прочитанное зна- чение будет первым случаем появления нового значения, мы сбра- сываем значение счетчика
]
Решение задач с массивами 87
Вернемся к логике инструкции if, которую мы пропустили. Как мы узнаем, что это последний случай появления значения в массиве?
Поскольку значения в массиве сгруппированы, мы знаем, что значе- ние встречается в последний раз, когда следующее значение в масси- ве отличается от него: в терминах C++, когда значения переменных surveyData[i]
и surveyData[i + 1] не равны. Кроме того, послед- нее значение в массиве также представляет собой последний случай появления некоторого значения, даже если следующего значения нет. Мы можем узнать это, проверив, равно ли значение i == ARRAY_
SIZE — 1
, в случае чего это значение в массиве является последним.
Выяснив все это, давайте подумаем о первоначальных значени- ях для наших переменных. Помните, что в случае с кодом для об- работки массива с целью нахождения «наибольшего значения» мы инициализировали переменную «с наибольшим значением, обна- руженным до сих пор» первым значением в массиве. Здесь «наи- более часто встречающееся» значение представлено двумя пере- менными — mostFrequent для самого значения и highestFrequency для количества случаев появления. Было бы хорошо, если бы была возможность инициализировать переменную mostFrequent первым значением в массиве, а переменную highestFrequency — значением счетчика частоты, однако не существует способа определить часто- ту первого значения, пока мы не доберемся до цикла и не начнем подсчет. В этот момент может показаться, что частота первого зна- чения, каким бы она ни была, будет больше нуля. Поэтому, если мы зададим для переменной highestFrequency значение, равное нулю, то по достижению последнего случая появления первого значе- ния, код все равно заменит значения переменных mostFrequent — highestFrequency показателями, соответствующими первому значе- нию. Финальная версия кода выглядит следующим образом: int mostFrequent;
int highestFrequency = 0;
int currentFrequency = 0;
for (int i = 0; i < ARRAY_SIZE; i++) {
currentFrequency++;
X // if (surveyData[i] IS LAST OCCURENCE OF A VALUE)
Y if (i == ARRAY_SIZE — 1 || surveyData[i] != surveyData[i + 1]) {
if (currentFrequency > highestFrequency) {
highestFrequency = currentFrequency;
mostFrequent = surveyData[i];
}
currentFrequency = 0;
}
}
В этой книге мы не будем много говорить о таких чисто стилевых проблемах, как стиль документирования (комментирования), одна- ко, поскольку мы используем псевдокод в данной задаче, я хочу дать вам совет. Я заметил, что строки, написанные мной на «простом ан- глийском языке» в псевдокоде, являются теми строками, которые больше всего выигрывают от комментариев в итоговом коде, и сами