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

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

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


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

Метод бинарного поиска

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

Словесный алгоритм работы такого метода следующий:

  • - Сравнить образец со средним (по номеру) элементом массива, если образец равен среднему элементу, то задача решена.
  • - Если образец больше среднего элемента, то искомый элемент расположен выше среднего элемента (между элементами с номерами Sred+1 и verh), и за новое значение niz принимается Sred+1, а значение verh не меняется.
  • - Если образец меньше среднего элемента, то искомый элемент расположен ниже среднего элемента (между элементами с номерами niz и Sred-1), и за новое значение verh принимается Sred-1, а значение niz не меняется.
  • - После того как определена часть массива, в которой может находиться искомый элемент, по формуле (verh — niz) / 2 + niz вычисляется новое значение Sred и поиск продолжается.
  • - Алгоритм заканчивает работу, если искомый элемент найден или перед выполнением очередного цикла обнаруживается, что значение niz больше, чем verh.

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

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

Листинг 102

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();

//-----1 этап-------Ввод массива

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

{

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

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

}

//-----2 этап-------Упорядочивание элементов массива с

использованием метода прямого выбора

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] и а [i] bufer = b[i]; b[i] = b[min]; b[min] = bufer;

}

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

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

//---3 этап-----Применение метода бинарного поиска

int niz = 0 ; int verh = 9; int n = 0 ; bool found = true ; string obr_ =

Microsoft.VisualBasic.Interaction.InputBox("Введите образец для поиска", "Окно ввода данных", 120, 240);

int obr = Convert.ToIntl6(obr_); int sred;

do //Выполнять тело цикла

{

sred = ((verh - niz) / 2) + niz; n = n + 1 ; if (b[sred] == obr) found = false;

else

if (obr < b[sred]) verh = sred - 1;

else

niz = sred + 1;

}

while ((niz <= verh) && (found)); if (found)

{

MessageBox.Show("Образец в массиве не найден", "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information)

}

else {

MessageBox.Show("С образцом совпадает элемент= sred.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

MessageBox.Show("Сравнений = " + n.ToString("n" "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information)

}

}

}

}

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

Алгоритм метода бинарного поиска

Рис. 125. Алгоритм метода бинарного поиска

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

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

30 7 50 30

57 69 28 20 25 40

Результирующий МЭССИ В

7 20 25 28

30 30 40 50 57 69

I Ок 1

Рис. 126. Метод бинарного поиска. В качестве образца для поиска было введено число 50

С образцом совпал элемент массива под номером 7

Рис. 127. С образцом совпал элемент массива под номером 7

Количество сравнений

Рис. 128. Количество сравнений

Примеры решения задач

Задача 1. В одномерном массиве произвольных чисел вычислите произведение отрицательных элементов, имеющих нечетные индексы.

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

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

Листинг 103

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;

int proizv = 1;

textBoxl.Clear();

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

{

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

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

if (i % 2 == 1) //Перебор элементов с нечетными

индексами

if (b [i] < 0)

{

proizv = proizv * b[i]; //Нахождение произведения отрицательных элементов

kol = kol + 1; //Подсчет количества

отрицательных элементов

}

}

if (kol != 0)

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

else

MessageBox.Show("В массиве нет отрицательных чисел с нечетными индексами ", "Заголовок окна", MessageBoxButtons.ОК, MessageBoxIcon.Information);

}

}

}

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

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

Задача 2. В одномерном массиве произвольных чисел вычислите среднее арифметическое значение квадратов положительных элементов.

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

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

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

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

Листинг 104

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;

int sum = 0;

textBoxl.Clear();

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

{

b[i]=a.Next(-40,12);

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

if (b[i] > 0)

{

sum = sum + b[i] * b[i] ;

kol = kol + 1 ;

}

}

if (kol == 0) //Если счетчик не изменил своего начального значения, тогда выводится ответ

MessageBox.Show("Положительных чисел в массиве нет", "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

else

{

double sr = sum / kol;

MessageBox.Show("Среднее арифметическое = " + sr.ToString("n"), "Заголовок окна", MessageBoxButtons.OK, MessageBoxIcon.Information);

}

}

}

}

Задача 3. Выведите элементы произвольного одномерного массива в обратном порядке.

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

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

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

Комментарий: по сравнению с предыдущими программами данная задача реализована, по сути, в одном операторе, а именно с[10 - i] = b[i];, выполняемом в цикле. Поскольку параметр цикла примет последовательные значения от 0 до 9 посредством организации цикла for (int i = 0; i <= 9; i++), то подставив значения параметра в оператор с[10 - i] = b[i];, мы получим с[10 - 0] = Ь[0] , т.е. элемент массива с[10] заменяется на значение элемента Ь[0], затем, выполнив оператор с[10 - 1] = Ь[1] элемент массива с [9] заменится на значение элемента Ь[1] и т.д. Таким образом, элементы массива выстраиваются в обратном порядке.

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

Листинг 105

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[11];

textBoxl.Clear();

textBox2.Clear();

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

{

b[i] = a.Next(10, 40);

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

}

for (int i = 0; i <= 9; i++) c[10 - i] - b[i]; for (int i = 1; i <= 10; i++)

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

}

}

}

Задача 4. В одномерном массиве произвольных чисел определите число инверсий. Инверсией называется пара элементов, в которой большее число расположено слева от меньшего. Например, дан одномерный массив:

24 35 29 44 8 22 4

Стрелками показано количество инверсий.

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

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

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

Комментарий: организовав цикл от 0 до 8, мы сравниваем каждый элемент последовательности с предыдущим и определяем, не больше ли он того. Нет смысла

организовывать цикл от 0 до 9, потому что, выполнив проверку b[i] > b[i + 1], мы десятый элемент последовательности будем сравнивать с одиннадцатым, а такого не существует. В случае истинности проверяемого условия увеличиваем счетчик на единицу оператором inv = inv + 1 и выводим ответ.

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

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 inv = 0;

textBoxl.Clear();

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

{

b[i] = a.Next(10, 40);

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

}

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

if (b[i] > b[i + 1]) //Сравниваются два соседних элемента массива

inv = inv +1; //В случае истинности проверяемого условия счетчик увеличивается на единицу

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

}

}

}

Контрольные вопросы к главе

  • 1. Что называется циклическим алгоритмом?
  • 2. Как записывается цикл с оператором for в блок-схемах?
  • 3. Как записывается цикл с оператором for в программах?
  • 4. Как работает цикл с оператором for?
  • 5. С какой целью применяют одномерные массивы в программах?
  • 6. Каким образом объявляются одномерные массивы в программах?
  • 7. Каким образом осуществляется доступ к каждому элементу одномерного массива при его обработке?
  • 8. Каким образом осуществить вывод одномерного массива на экран?
  • 9. Нарисуйте базовые алгоритмы обработки одномерных массивов.
  • 10. Поясните, каким образом осуществляется обмен значений элементов массива.
  • 11. Назовите основные способы упорядочивания массивов.
  • 12. Расскажите алгоритм упорядочивания одномерного массива по возрастанию 190

методом прямого перебора.

  • 13. Расскажите алгоритм упорядочивания элементов одномерного массива методом обмена (метод «пузырька»).
  • 14. Расскажите алгоритм упорядочивания элементов одномерного массива произвольных чисел по убыванию их значений.
  • 15. Расскажите алгоритм упорядочивания элементов одномерного массива методом бинарного поиска.

Задачи для самостоятельного решения

  • 1. Запишите положительные элементы массива А подряд в массив В. Определите количество положительных элементов. Найдите произведение элементов массива В.
  • 2. В одномерном массиве произвольных чисел А [10] вычислите произведение отрицательных элементов, имеющих нечетные индексы.
  • 3. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Выведите на экран компьютера созданный массив и сформируйте другой массив, элементы которого по модулю больше некоторого значения С. Число элементов массива, значение С вводятся с клавиатуры.
  • 4. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 30. Выведите на экран компьютера созданный массив и сформируйте из него два массива: массив четных чисел Ь и массив нечетных чисел с. Число элементов массива вводится с клавиатуры.
  • 5. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 80. Выведите на экран компьютера созданный массив и найдите максимальный и минимальный элементы, а также осуществите их обмен. Число элементов массива вводится с клавиатуры.
  • 6. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Выведите на экран компьютера созданный массив и определите число инверсий. Инверсией называется пара элементов, в которой большее число расположено слева от меньшего. Число элементов массива вводится с клавиатуры.
  • 7. Определите среднее арифметическое элементов одномерного массива произвольных чисел А[10], удовлетворяющих условию АЬз(А[1])>С. Значение С вводится с клавиатуры.
  • 8. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Выведите на экран компьютера созданный массив и вычислите произведение четных и нечетных чисел. Число элементов массива вводится с клавиатуры.
  • 9. Разработайте программу, заполняющую массив случайными целыми числами, находящимися в интервале от 1 до 50. Определите максимальный и минимальный элементы среди положительных нечетных элементов целочисленного массива произвольных чисел А[10].
  • 10. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от -20 до 40. Выведите на экран компьютера созданный массив и в данном массиве положительные элементы уменьшите вдвое, а отрицательные замените на значения их индексов. Число элементов массива вводится с клавиатуры.
  • 11. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 40. Определите, сколько процентов от всего количества элементов массива составляют нечетные элементы. Число элементов массива вводится с клавиатуры.
  • 12. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Выведите на экран компьютера созданный массив и упорядочите элементы данного одномерного массива по возрастанию их значений. Число элементов массива вводится с клавиатуры.
  • 13. Из одномерного массива произвольных чисел А[ 10] сформируйте другой массив таким образом, чтобы вначале шли отрицательные элементы исходного массива, затем положительные и, наконец, нулевые.
  • 14. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 30. Выведите на экран компьютера созданный массив и найдите максимальный элемент, его номер и поменяйте местами максимальный и первый элемент массива. Число элементов массива вводится с клавиатуры.
  • 15. Разработайте программу, которая включает заданное число Э в массив А[ 10], упорядоченный по возрастанию, с сохранением упорядоченности.
  • 16. Удалите из массива А, состоящего из п элементов, первые четыре нулевых элемента.
  • 17. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от -30 до 50. Выведите на экран компьютера созданный массив и определите, есть ли в нем серии элементов, состоящих из знакочередующихся чисел. Если есть, то выведите на экран количество таких серий. Число элементов массива вводится с клавиатуры.
  • 18. Разработайте программу, которая выводит на экран два одномерных массива А[ 10], содержащих диаметры и веса шин. Следует отобрать две шины, диаметры которых отличаются не более, чем на О см, а вес — не более, чем на У грамм.
  • 19. Из одномерного массива произвольных чисел А[ 10] сформируйте два массива, содержащих номера положительных и отрицательных элементов.
  • 20. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от -20 до 40. Выведите на экран компьютера созданный массив и вычислите среднее арифметическое значение квадратов положительных элементов. Число элементов массива вводится с клавиатуры.
  • 21. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Произведите обмен соседних элементов, стоящих на четных местах, с элементами, стоящими на нечетных местах. Число элементов массива вводится с клавиатуры.
  • 22. Разработайте программу, заполняющую массив из п элементов случайными вещественными числами, находящимися в интервале от 1 до 30. Все элементы массива с четными номерами, предшествующие первому по порядку элементу с наибольшим значением, домножите на него. Число элементов массива вводится с клавиатуры.
  • 23. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от -15 до 20. Выведите на экран компьютера созданный массив и найдите наибольший элемент из отрицательных. Число элементов массива вводится с клавиатуры.
  • 24. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Выведите на экран компьютера созданный массив и найдите количество тех элементов, значения которых находятся в диапазоне от А до В. Число элементов массива, значения А и В вводятся с клавиатуры.
  • 25. Пользователь вводит с клавиатуры элементы одномерного массива А[п]. Определите, является ли заданная последовательность чисел а], а2, ... , ам монотонно убывающей. Число элементов массива вводится с клавиатуры.
  • 26. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 30. Замените нулями элементы между максимальным и минимальным значениями, кроме них самих. Число элементов массива вводится с клавиатуры.
  • 27. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 20. Требуется найти индекс последнего по счету в массиве отрицательного элемента.
  • 28. Разработайте программу, которая определяет, имеется ли в заданном целочисленном массиве А[10] хотя бы одна пара совпадающих по значению чисел.
  • 29. Разработайте программу, которая выводит на экран два одномерных массива А[10], содержащих массивы ростов игроков двух команд (в см), и определяет, имеется ли в данных командах игроки одинакового роста.
  • 30. Разработайте программу, заполняющую массив из п элементов случайными целыми числами, находящимися в интервале от 1 до 50. Выведите на экран компьютера созданный массив и найдите максимальный и минимальный элементы, вычислите их разность. Число элементов массива вводится с клавиатуры.
 
<<   СОДЕРЖАНИЕ   >>