Полная версия

Главная arrow Информатика arrow Введение в программирование на языке Visual C#

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Базовые алгоритмы обработки одномерных массивов

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

Из всего многообразия существующих приемов, позволяющих манипулировать с данными, представленными в одномерных массивах, можно выделить следующие:

  • 1. Нахождение количества элементов при заданном условии.
  • 2. Нахождение суммы значений элементов при заданном условии.
  • 3. Нахождение произведения значений элементов при заданном условии.
  • 4. Поиск экстремальных значений элементов массива (поиск максимального и/или минимального значения).
  • 5. Вставка и/или удаление значения элемента массива.
  • 6. Формирование другого массива В из элементов массива А в соответствии с некоторым критерием.
  • 7. Формирование массива в соответствии с определенными правилами.
  • 8. Обмен значений элементов массива.
  • 9. Сортировка (упорядочивание) элементов массива.

Ниже описывается реализация перечисленных алгоритмов обработки одномерных массивов. Первые четыре способа чрезвычайно просты, данные алгоритмы неоднократно рассматривались при решении задач в предыдущих разделах и в настоящее время не требуют комментариев. Однако стоит отметить, что в листингах 90, 91, 92 очередной элемент массива сравнивается с числом 10, однако на практике лучше организовать запрос условия, например, с помощью функции InputBox.

Нахождение количества элементов при заданном условии Листинг 90

namespace WindowsApplicationl {

public partial class Forml : Form {

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

int kol = 0;

textBoxl.Clear();

for (int i = 0; i <= 9; i++)

{

b[i]=a.Next(1,20); //диапазон чисел от 1 до 20 textBoxl.AppendText(b[i] + " "); if (b[i] >= 10)

kol = kol + 1 ;

}

MessageBox.Show("Количество элементов при заданном условии = " + kol.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

}

}

Нахождение суммы значений элементов при заданном условии

Листинг 91

namespace WindowsApplicationl

{

public partial class Forml : Form

{

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

int sum = 0;

textBoxl.Clear();

for (int i — 0; i <— 9; i++)

{

b[i]=a.Next(1,20);

textBoxl.AppendText(b[i] + " ");

if (b[i] >= 10)

sum = sum + b [ i ] ;

}

MessageBox.Show("Сумма значений элементов при заданном условии = " + sum.ToString("п"), "Заголовок окна", MessageBoxButtons.ОК, MessageBoxIcon.Information);

}

}

}

Нахождение произведения значений элементов при заданном условии

Листинг 92

namespace WindowsApplicationl

{

public partial class Forml : Form

{

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

int proizv = 1 ;

textBoxl.Clear();

for (int i = 0; i <= 9; i + + )

{

b[i]=a.Next(1,20);

textBoxl.AppendText(b[i] + " ");

if (b[i] >= 10)

proizv = proizv * b[i] ;

}

MessageBox.Show("Произведение значений элементов при заданном условии = " + proizv.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

}

}

Нахождение экстремальных значений в одномерном массиве

Листинг 93

namespace WindowsApplicationl

{

public partial class Forml : Form

{

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

int max = -32768;

int min = 32767;

textBoxl.Clear();

for (int i = 0; i <= 9; i++)

{

b[i] = a.Next(l, 20); textBoxl.AppendText(b[i] + " "); if (b[i] > max) max = b[i]; if (b[i] < min) min = b[i];

}

MessageBox.Show("Максимальный элемент массива = " + max.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

MessageBox.Show("Минимальный элемент массива = " + min.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

}

}

Вставка значения нового элемента в массив

Прежде чем добавить новый элемент в массив, нужно освободить соответствующее место. Для этого, начиная с конца массива, элементы сдвигаются вправо, т.е. 6-й элемент перемещается на 7-е место, 5-й элемент перемещается на 6-е место и т.д. После этого на освободившееся место с порядковым номером poz занимает значение chislo.

В листинге 94 приведен код процедуры, отвечающий за решение задачи.

Листинг 94

namespace WindowsApplicationl

{

public partial class Forml : Form

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[11];

string chislo_, poz_;

textBoxl.Clear();

textBox2.Clear();

for (int i — 0; i <— 9; i++)

{

b[i] = a.Next(l, 20);

textBoxl.AppendText(b[i] + " ");

}

chislo_ =

Microsoft.VisualBasic.Interaction.InputBox("Введите вставляемый элемент", "Окно ввода данных", 200, 480);

int chislo = Convert.ToIntl6(chislo_);

poz_ = Microsoft.VisualBasic.Interaction.InputBox("Ha какое место в массиве вы хотите вставить элемент?", "Окно ввода данных", 200, 480);

int poz = Convert.ToIntl6(poz_); for (int i — 9; i >— poz; i--)

{

b [ i + 1] - b [ i ] ; b[i] = chislo;

}

for (int i — 0; i < — 10; i++)

textBox2.AppendText(b[i] + " ");

}

}

}

Результат разработанной программы представлен на рис. 112.

Осуществлена вставка числа 50 на девятую позицию массива

Рис. 112. Осуществлена вставка числа 50 на девятую позицию массива

Удаление значения элемента из массива

Для удаления значения элемента массива, стоящего на позиции poz, следует сдвинуть на соседнее место слева все последующие элементы, начиная с poz + 1 и заканчивая п-м.

Самый интересный момент в этой программе — это удаление последнего элемента с 10-й позиции. В этом случае poz + 1 в цикле будет равно 11, и цикл не выполнится ни разу, т.е. оператор b [і — 1] = b [ і ] не выполняется, а за счет

выполнения цикла for (int i = 0; i <= 8; i++) мы избавляемся от последнего элемента в массиве.

В листинге 95 приведен код процедуры, отвечающий за решение задачи.

Листинг 95

namespace WindowsApplicationl

{

public partial class Forml : Form

{

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

string poz_;

textBoxl.Clear();

textBox2.Clear();

for (int i — 0; i <— 9; i++)

{

b[i] = a.Next(l, 20);

textBoxl.AppendText(b[i] + " ");

}

poz_ = Microsoft.VisualBasic.Interaction.InputBox("С какой позиции удаляем элемент ?", "Окно ввода данных", 200, 480);

int poz = Convert.ToIntl6(poz_); for (int i = poz + 1; i <= 9; i++) b[i - 1] - b[i]; for (int i = 0; i <= 8; i++)

textBox2.AppendText(b[i] + " ");

}

}

}

Результат разработанной программы представлен на рисунке 113.

Удален элемент массива с 10-й позиции

Рис. 113. Удален элемент массива с 10-й позиции

Формирование другого массива В из элементов массива А в соответствии с некоторым критерием

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

Комментарий: после формирования одномерного массива с помощью генератора случайных чисел у пользователя запрашивается число. После того как будет 168

выполнена проверка условия: больше или нет (по модулю) очередной элемент массива введенного пользователем числа, — должен формироваться результирующий массив оператором с [n] = b [і]. Для того чтобы был сформирован элемент массива с с индексом 1, т.е. с [1], служит оператор п = 1. Затем значение ячейки п увеличивается на 1 оператором п = п + 1, и в случае истинности проверяемого условия будет формироваться второй элемент массива с, т.е. с [2]. В конце программы предусмотрена проверка на случай, если пользователь не введет нужного числа. В этом случае выводится ответ, что «В массиве нет чисел больше введенного Вами числа», в противном случае с помощью цикла с оператором for выводится результирующий массив.

Разработка алгоритма решения задачи представлена на рис. 114.

Алгоритм решения задачи

Рис. 114. Алгоритм решения задачи

В листинге 96 приведен код процедуры, отвечающий за решение задачи. Листинг 96

namespace WindowsApplicationl {

public partial class Forml : Form {

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

int[] c = new int[10];

string zhach_;

textBoxl.Clear();

textBox2.Clear();

for (int і = 0; і <= 9; i++)

{

b[i] = a.Next(-15, 20);

textBoxl.AppendText(b[i] + " ");

}

zhach_ =

Microsoft.VisualBasic.Interaction.InputBox("Введите значение", "Окно ввода данных", 200, 480);

int znach = Convert.Tolntl?(zhach_);

int n = 1 ; //Исходное значение ячейки n приравнивается единице

for (int i — 0; i <— 9; i++) //Организуется цикл для перебора элементов одномерного массива

if (Math.Abs(b[i]) > znach)

{

c[n] = b[i] ; //Формирование элементов результирующего массива в случае истинности проверяемого условия

n = n + 1 ; //Увеличение счетчика на единицу для формирования очередного элемента массива

}

if (n == 1) //Проверка на случай, если в ячейке п осталась предварительно занесенная единица, и счетчик не увеличивал своего значения

MessageBox.Show("В массиве нет чисел больше введенного Вами числа", "Заголовок окна", MessageBoxButtons.ОК,

MessageBoxIcon.Information);

else

for (int і = 1; і <= n-1; i++)

textBox2.AppendText(c[i] + " ");

}

}

}

Результат разработанной программы представлен на рис. 115.

Результирующий массив содержит элементы, которые больше по модулю введенного числа 5

Рис. 115. Результирующий массив содержит элементы, которые больше по модулю введенного числа 5

Формирование массива в соответствии с определенными правилами

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

от некоторых условии.

Задача. Сформируйте одномерный массив из 10 элементов по следующему правилу:

если / < 5

-, в противном случае

i

В листинге 97 приведен код процедуры, отвечающий за решение задачи.

Листинг 97

namespace WindowsApplicationl {

public partial class Forml : Form {

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

doublet] b = new double[ll];

textBoxl.Clear();

for (int i = 1; i <= 10; i++)

{

if (i < 5)

b[i] = (i * i * i - 4) / (i + 1);

else

b [i] = (i * i - 36) / i textBoxl.Text = textBoxl.Text +

System.String.Format("{0:f2}", b[i]) + " ";

}

}

}

}

Результат разработанной программы представлен на рис. 116.

Одномерный массив, сформированный по определенному правилу

Рис. 116. Одномерный массив, сформированный по определенному правилу

Обмен значений элементов массива

Задача. В одномерном массиве из 10 целых чисел найдите максимальный и минимальный элемент, а также осуществите их обмен.

Комментарий: методы сортировки элементов одномерного массива, которые будут рассмотрены позднее, потребуют вспомогательный алгоритм обмена элементов одномерного массива.

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

12 3 56 4 8 34 23 87 29 20

Минимальный элемент в массиве = 3 с порядковым номером 2, т.е. А[2], а максимальный элемент в массиве = 87 с порядковым номером 7, т.е. А[7]. Возьмем третью ячейку — п. Первым действием (1) будет перемещение в нее найденного минимального числа. Вторым действием (2) на освободившееся место перемещаем максимальное число. И, наконец, третьим действием (3) минимальное число из ячейки п помещается на то место в массиве, где только что находилось максимальное число. В программе эти действия можно было бы описать операторами:

п = а[2]; а [2] = а[7]; а [7] = п;

Но поскольку заранее неизвестно, какой элемент в массиве будет минимальный, а какой максимальный и каковы будут их номера, то такую последовательность операторов заменяем на следующую:

п - а[пошшт]; а[поттт] - а[поттах]; а[поттах] = п

Разработка алгоритма решения задачи представлена на рис. 117.

Алгоритм решения задачи

Рис. 117. Алгоритм решения задачи

В листинге 98 приведен код процедуры, отвечающий за решение задачи.

Листинг 98

namespace WindowsApplicationl

{

public partial class Forml : Form

{

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[11];

textBoxl.Clear();

textBox2.Clear();

for (int i = 1; i <= 10; i++)

{

b[i] = a.Next(l, 50);

textBoxl.AppendText(b[i] + " ");

}

int nommin = 1 ; //Считаем, что номер минимального элемента в массиве равен 1

int nommax = 1 ; //Считаем, что номер максимального элемента в массиве равен 1

int min = 32767 ; int max = -32768 ;

for (int i = 1; i <= 10; i++) //Организуется цикл для перебора элементов одномерного массива

{

if (b[i] < min) //Поиск минимального элемента в

массиве

{

массиве

}

min = b[i] ; nommin = і ;

if (b[і] > max)

{

//Нахождение его номера

//Поиск максимального элемента в

//Нахождение его номера

max = b[і] nommax = і

}

}

//Обмен элементов массива

int nl = b[nommin] ; b[nommin] = b[nommax] ; b[nommax] = nl ;

MessageBox.Show("Минимальное число = " + min.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

MessageBox.Show("Максимальное число = " + max.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

for (int і = 1; і <= 10; i++)

textBox2.AppendText(b[і] + " ");

}

Результат разработанной программы представлен на рис. 118.

Минимальный элемент в исходном массиве 3 обменен с максимальным элементом 49

Рис. 118. Минимальный элемент в исходном массиве 3 обменен с максимальным элементом 49

7.2. Упорядочивание одномерных массивов

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

Наиболее часто применяются следующие способы упорядочивания массивов.

Упорядочивание по возрастанию. Каждый следующий элемент в массиве должен быть больше предыдущего.

Упорядочивание по убыванию. Каждый следующий элемент в массиве должен быть меньше предыдущего.

Упорядочивание по неубыванию. Каждый последующий элемент в массиве должен быть больше или равен предыдущему.

Упорядочивание по невозрастанию. Каждый последующий элемент в массиве должен быть меньше или равен предыдущему.

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

Упорядочивание методом прямого выбора

Задача. Упорядочите элементы одномерного массива произвольных чисел по возрастанию их значений.

Комментарий: алгоритм упорядочивания массива по возрастанию методом прямого выбора может быть представлен следующим образом:

  • 1. Просмотреть массив от первого элемента, найти минимальный элемент и поместить его на место первого элемента, а первый — на место минимального.
  • 2. Просмотреть массив от второго элемента, найти минимальный элемент и поместить его на место второго элемента, а второй — на место минимального.
  • 3. Данный процесс осуществлять до предпоследнего элемента.

Разработка алгоритма решения задачи представлена на рис. 119.

Алгоритм решения задачи

Рис. 119. Алгоритм решения задачи

В листинге 99 приведен код процедуры, отвечающий за решение задачи. Листинг 99

namespace WindowsApplicationl {

public partial class Forml : Form {

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

int bufer;

textBoxl.Clear();

textBox2.Clear();

for (int i — 0; i <— 9; i++)

{

b[i] = a.Next(1, 90);

textBoxl.AppendText(b[i] + " ");

}

до

//Поиск минимального элемента в части массива от а [0]

а [9]

for (int i = 0; i <= 8; i++) //Организуется цикл для перебора элементов одномерного массива

{

int min = i;

for (int j = i + 1; j <= 9; j++) if (b[j] < b[min]) min = j;

//Поменяем местами a [min] и a [i]

bufer = b[i];

b[i] = b[min];

b[min] = bufer;

for (int k = 0; k <= 9; k++)

textBox2.AppendText(b[k] + " ");

}

}

}

}

Результат разработанной программы представлен на рис. 120.

Упорядочивание массива методом прямого выбора

Рис. 120. Упорядочивание массива методом прямого выбора.

Упорядочивание элементов методом обмена (метод «пузырька»)

Задача. Упорядочите элементы одномерного массива произвольных чисел по возрастанию их значений.

Например: исходный массив представлен числами: 7 3 5 4 2, тогда после его обработки он будет выглядеть так: 2 3 4 5 7.

Комментарий: в основе алгоритма лежит обмен соседних элементов массива. Каждый элемент массива, начиная с первого, сравнивается со следующим, и если он больше следующего, то элементы меняются местами. Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением — к концу массива (тонут). Поэтому данный метод сортировки часто называют методом «пузырька».

Этот процесс повторяется столько раз, сколько элементов в массиве, минус единица.

Упорядочивание массива достигается, если после выполнения очередного цикла проверки соседних элементов ни один элемент не был обменен с соседним, следовательно, массив упорядочен.

Разработка алгоритма решения задачи представлена на рис. 121.

Алгоритм решения задачи

Рис. 121. Алгоритм решения задачи

В листинге 100 приведен код процедуры, отвечающий за решение задачи.

Листинг 100

namespace WindowsApplicationl {

public partial class Forml : Form {

риЬІіс Рогті()

{

ІпіЬіаІігеСотропег^ ();

}

private void ЬиІ:1:оп1_С1іск (оЬ^ есЬ эепзЗег, EventArgs е)

{

Ііапсіот а = new Даг^от () ; іпЬ[] Ь = new іп^ІО]; іпЬ Ьи?ег; textBoxl.Сіеаг(); textBox2.Сіеаг();

?ог (ігЛ і = 0; і <= 9; і++) {

Ь[і] = а.ЫехЬ(1, 90);

textBoxl .АррепсІТехЬ (Ь [ і ] + "М;");

}

?ог (ігД; і — 0; і <— 8; і++)

{

?ог (іп± j = і + 1; ] <= 9; j++) і? (Ь [і] > Ь[? ] )

{

Ьи?ег = Ь[і]; b[j] - Ь[і] ;

Ь[і] = Ьи?ег;

?ог (іпЬ к = 0; к <= 9; к++)

textBox2.AppendText(Ь[к] + "Ь");

}

}

}

}

Результат разработанной программы представлен на рис. 122.

Я Метод "пузырька

Исходный массив

18

42

57

60

22

76

85

78

55

75

Результирующий МЗССИЕ

18

22

57

60

42

76

85

78

55

75

18

22

42

60

57

76

85

78

55

75

18

22

42

57

60

76

85

78

55

75

18

22

42

57

55

76

85

78

60

75

18

22

42

57

55

60

85

78

76

75

18

22

42

57

55

60

78

85

76

75

18

22

42

57

55

60

76

85

78

75

18

22

42

57

55

60

75

85

78

76

18

22

42

57

55

60

75

78

85

76

18

22

42

57

55

60

75

76

85

78

18

22

42

57

55

60

75

76

78

85

Ок

Рис. 122. Упорядочивание массива «методом пузырька»

Алгоритм упорядочивания элементов по убыванию

Задача. Упорядочите элементы одномерного массива произвольных чисел по убыванию их значений.

Например: исходный массив представлен числами: 14 2 19 1 17, тогда

после его обработки он будет выглядеть так: 19 17 14 2 1.

Комментарий: словесный алгоритм работы программы можно выстроить так:

  • 1. Сформировать исходный массив.
  • 2. Организовав внешний цикл, взять элемент массива с номером 1 и считать его максимальным.
  • 3. Организовав внутренний цикл, последовательно искать среди оставшихся элементов массива такой элемент, который был бы больше того, который считается максимальным.
  • 4. Если найден такой элемент, то осуществить перестановку.
  • 5. Взять следующий по порядку элемент массива и считать его максимальным.
  • 6. Процедуру с поиском в цикле максимального элемента и обмен элементов повторить.

Разработка алгоритма решения задачи представлена на рис. 123.

Алгоритм решения задачи

Рис. 123. Алгоритм решения задачи

В листинге 101 приведен код процедуры, отвечающий за решение задачи.

Листинг 101

namespace WindowsApplicationl {

public partial class Forml : Form {

public Forml()

{

InitializeComponent();

}

private void buttonl_Click(object sender, EventArgs e)

{

Random a = new Random();

int[] b = new int[10];

textBoxl.Clear();

textBox2.Clear();

for (int i = 0; i <= 9; i++)

{

b[i] = a.Next(l, 90);

textBoxl.AppendText(b[i] + " ");

}

for (int i = 0; i <= 8; i++) //Организуется цикл для перебора элементов одномерного массива

{

int max = b[i]; //Максимальным считается первый

элемент массива

for (int j = i + 1; j <= 9; j++) if (b[j] > max)

{

b[i] = b[j] ; //Происходит обмен элементов

массива

b[j] = max ; max = b[i] ;

}

}

for (int i = 0; i <= 9; i++)

textBoxl.AppendText(b[i] + " ");

}

}

}

Результат разработанной программы представлен на рис. 124.

ш

Упорядочивание одномерного массива по убыванию

і Исходньй массив

18 24 49

83

6

38

30

23

80

76

Результирукщий маССИЕ

83 80 7G

49

38

30

24

23

18

6

с

Ok I

Рис. 124. Упорядочивание элементов массива по убыванию значений

 
<<   СОДЕРЖАНИЕ   >>