На этом шаге мы рассмотрим пример использования указанной конструкции.
Когда в соответствии с реализуемым в программе алгоритмом приходится делать многовариантный выбор, то применяют конструкцию вида:
if (выражение) {блок} else if (выражение) {блок} else if (выражение) {блок} else if (выражение) {блок} else {блок}
Работает эта конструкция так:
- Последовательно вычисляется выражение в каждой строке.
- Если выражение истинно, то выполняется тело (т. е. блок операторов) и происходит выход из конструкции на выполнение следующего за ней оператора.
- Если выражение ложно, то начинает вычисляться выражение в следующей строке и т. д.
Последняя часть конструкции (else {блок}) не обязательна.
Приведем пример функции поиска заданного элемента в упорядоченном по возрастанию элементов числовом массиве.
Пусть даны массив v[n] и число х. Надо определить, принадлежит ли х массиву. Так как элементы массива предполагаются упорядоченными по возрастанию их значений, то поиск проведем, применяя метод половинного деления (иначе называемый двоичным поиском).
Суть метода такова:
- Рассматривается отрезок, на котором расположены все элементы числового массива. Если массив v[n] имеет размерность n, то отрезок, на котором расположены номера его элементов, это [0, n-1], потому что номер первог элемента массива будет 0, а последнего - (n-1).
- Этот отрезок делится пополам.
- Средняя точка отрезка вычисляется как j = (0 + (n-1))/2.
- В этой средней точке вычисляется значение v[j] и проверяется: значение x больше, меньше или равно v[j]:
- если х < v[j], значит, х находится слева от середины отрезка;
- если х > v[j], то х находится справа от середины отрезка;
- если х = v[j], значит, х принадлежит массиву.
Когда же следует остановиться?
Один вариант останова мы уже видели: когда значение х совпадет с одной из середин отрезка.
А второй - когда отрезок "сожмется" так, что его нижняя граница (левый край) совпадет с верхней (правый край). Это произойдет обязательно, потому что мы станем делить отрезок пополам и в качестве результата брать целую часть от деления, поскольку, как мы видели, ее надо использовать в качестве индекса массива. А индекс массива это величина обязательно целая, т. к. это порядковый номер элемента массива.
Например, массив из трех элементов будет иметь отрезок [0,2]. Делим пополам и получаем (0+2)/2=1 (т. е. имеем два отрезка [0,1] и [1,2]).
Если станем искать в [0,1], то придется находить его середину: (0+1)/2=0 (мы помним, что операция "/" при работе с целыми операндами дробную часть результата отбрасывает и оставляет только целую часть, что нам и требуется для нахождения индекса массива). Видим, что левый конец отрезка (0) совпал с правым (0), т. к. правый конец нового отрезка получился равным нулю. Вот в этот момент деление пополам надо прекратить и завершить программу.
Если в нашем случае получится так, что отрезок сжался в точку, а число х не сравнялось ни с одним элементом массива v[], то надо вывести об этом событии информацию: например, -1. Если обнаружено, что х содержится в массиве v[], то надо вывести номер элемента v[], на котором и произошло совпадение.
Примечание. Значение индекса массива, на котором произошло совпадение, положительно. Если же совпадения не обнаружено, то значение индекса - отрицательно.
Это все необходимо для того, чтобы при обращении к функции поиска вхождения проверить результат поиска: входит ли число х в массив v[] или не входит. Текст программы представлен ниже.
// ElseIf.cpp: главный файл проекта. #include "stdafx.h" #include <stdio.h> //for getchar(),... #include <conio.h> #include <stdlib.h> //for atoi() #include <clocale> //обязательно для функции setlocale() #define eof -1 #define MAXLINE 100 using namespace System; // --- Ввод строки с клавиатуры int getline (char s[], int lim) { int c, i; for(i=0; i<lim-1 && (c=getchar()) != eof && c != '\n'; i++) s[i] = c; s[i]='\0'; i++; //для учета количества return i; } // ---------------------------- int binary(int x, int v[], int n) // ищет в массиве v[n] элемент со значением "х" n - размерность массива { int low, high, mid; low = 0; high = n-1; while(low <= high) { mid = (low + high) / 2; if ( x < v[mid] ) high=mid - 1; else if(x > v[mid]) low=mid + 1; else return mid ; //найдено } //конец while return -1; //не найдено } int main() { setlocale(LC_ALL,"Russian"); //функция setlocale() с аргументами //для корректного вывода кириллицы int v[MAXLINE] = {0,1,2,3,4,5,6,7,8,9}; int c, i, x; char s[MAXLINE]; do { printf("Задайте целое число x >"); getline(s, MAXLINE); x = atoi(s); i = binary (x, v, 10); if(i != -1) printf("Это число есть в массиве\n"); else printf("Этого числа нет в массиве\n"); printf("Продолжить - Enter, выход - Ctrl+z\n"); } while( ( c=getchar() ) != eof ); // Это - конец оператора do...while. Нам требовалось, // чтобы тело while выполнилось хотя бы один раз return 0; }
Рассмотрим работу функции binary().
В переменных low, high, mid размещаются, соответственно, текущие значения: нижней границы отрезка, верхней границы отрезка и его середины.
Если значение числа х находится в левой половине поделенного отрезка, то изменяется отрезок поиска: переменная low остается без изменения, а переменная high сдвигается на середину (поэтому этой переменной присваивается значение середины, в результате чего получается отрезок, являющийся левой половиной предыдущего отрезка).
Если значение числа х находится в правой половине поделенного отрезка, то изменяется отрезок поиска: переменная high остается без изменения, а переменная low сдвигается на середину, в результате чего получается правый отрезок.
Если значение х совпадает со значением v[середина отрезка], то функция вращает переменную mid и процесс поиска прекращается.
Если цикл поиска закончился, это сигнал о том, что просмотрены все элементы и совпадения не найдено. В этом случае будет возвращено отрицательное число.
Рассмотрим работу основной программы. Выражение int v[MAXLINE]={0,1,2,3,4,5,6,7,8,9}; - это инициализация (определение элементов) массива. Для простоты проверки работы функцш поиска мы задали значения элементов, совпадающими с номерами своих элементов. Далее с помощью функции getline() в строку вводится значение х и переводится с помощью функции atoi() в целое число. Затем происходит обращение к функции binary() и проверяется результат ее работы: равно ли возвращенное ею значение -1.
Все эти операторы помещены в блок - тело условной конструкции do...while и выполняются в цикле, пока не будет нажата комбинация клавиш Ctrl+z. Такая структура дает возможность вводить разные значения переменной х. Результат работы программы приведен на рисунке 1.
Рис.1. Результат работы приложения
На следующем шаге мы рассмотрим переключатель switch.
