Билет №27 Алгоритм бинарного поиска заданного элемента в упорядоченной последовательности.

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

Описание алгоритма

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

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

3. Одна из границ исследуемой последовательности становится равной предыдущему или последующему среднему элементу из п.2.

4. Снова находится средний элемент, теперь уже в «выбранной» половине. Описанный выше алгоритм повторяется уже для данной последовательности.

Билет № 28 Аритмические операции в двоичной системе счисления.

В двоичной системе счисления арифметические операции выполняются по тем же правилам, что и в десятичной системе счисления, т.к. они обе являются позиционными (наряду с восьмеричной, шестнадцатеричной и др.).

Сложение

Сложение одноразрядных двоичных чисел выполняется по следующим правилам:

0 + 0 = 0 0+1=1

1 + 0 = 1 1+1=10

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

Сложим для примера два любых двоичных числа:

1101

+ 101

------

10010

Вычитание

Вычитание одноразрядных двоичных чисел выполняется по следующим правилам:

0 - 0 = 0 0-1=(затем старшего разряда)1

1 - 0 = 1 1-1=0

Пример:

1110

- 101

----

1001

Умножение

Умножение одноразрядных двоичных чисел выполняется по следующим правилам:

0 * 0 = 0 0*1=0

1 * 0 = 0 1*1=1

Пример:

1110

* 10

------

+ 0000

1110

------

11100

Деление

Деление выполняется так же как в десятичной системе счисления:

1110 | 10

|----

10 | 111

----

11

10

----

10

10

----

0

Билет № 29 Перевод чисел из двоичной системы счисления в десятичную и обратно.

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

Например, требуется перевести двоичное число 10110110 в десятичное. В этом числе 8 цифр и 8 разрядов ( разряды считаются, начиная с нулевого, которому соответствует младший бит). В соответствии с уже известным нам правилом представим его в виде суммы степеней с основанием 2:

101101102 = (1·27)+(0·26)+(1·25)+(1·24)+(0·23)+(1·22)+(1·21)+(0·20) = 128+32+16+4+2 = 18210

Из этого примера видно, в частности, что десятичная система счисления более компактно отображает числа - 3 цифры (т.е. бита) вместо 8 цифр в двоичной системе счисления. Для вычислений "вручную" и решения примеров и контрольных заданий вам могут пригодиться таблицы степеней оснований изучаемых систем счисления (2, 8, 10, 16), приведенные в Приложении.