Конструкция else-if

   
На этом шаге мы рассмотрим пример использования указанной конструкции.

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

  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.



    Вы можете оставить комментарий, или Трекбэк с вашего сайта.

    Оставить комментарий