8 Организация поиска в упорядоченном массиве

Общие задания:

1. Даны действительные а₁, а₂,…а_n (a₁>a₂>a₃>…>a_n), действительное – b. Осуществить в данной последовательности поиск элемента равного b, и вывести его номер.

2. Даны a₁>a₂>a₃>…>a_n, b – некоторое число. Вставить число b в упорядоченную совокупность а₁, а₂,…а_n.

Индивидуальные задания:

1. Даны натуральные А1,…,А50, m, В1,…,Вm (A1>A2>…>A50). Подсчитать количество тех Bi, 1<=i<=m, для которых нет равных среди А1,…,А50.

2. Составить программу определения задуманного человеком числа от 1 до 1000 с помощью 10 вопросов. Каждый вопрос имеет вид «Верно ли, что задуманное число больше R?». При этом указывается конкретное R. Ответы человека это Д и Н. Применить идею деления пополам.

3. Использовать предложенную в задаче 2 игру. Указать количество вопросов которые при экономном ведении игры будет достаточным для угадывания числа от 1 до 2000, 3000.

4. Доказать, что если n=2^m, то число сравнений с элементами А1,…,Аn в процессе применения алгоритма деления пополам равно m (без учета дополнительные сравнения Ар=b).

5. Доказать, что если 2^m-1<n<=2^m, m>=1, то число сравнений b с элементами А1,…,Аn в процессе применения алгоритма деления пополам равно m (без учета дополнительного сравнения Ар<b). Указание: установить, что при m>1 первое сравнение приводит к поиску среди n элементов, где 2^m-2<n<=2^m-1

6. Воспользовавшись утверждением, сформулированным в предыдущей задаче, вычислить количество сравнений, которое потребуется произвести при n=60, 70, 80, 90 (без учета дополнительного сравнения).Построить график зависимости.

7. Пусть имеется интерполяционная таблица функции, причем шаг таблицы непостоянен. Использовать идею алгоритма поиска места элемента для поиска m такого, что данное х принадлежит отрезку [Xm, Xm+1].

8. Даны целые А1,…, An, b. Если среди чисел А1,…,Аn есть равное b, то оставить А1, …Аn без изменений, в противном случае вставить b в этот массив без нарушения упорядоченности.

9. Изменить алгоритм поиска места элемента, предполагая, что числа А1,…,Аn упорядочены по убыванию.

10. В случае, если среди А1,…,Аn допускаются равные (А1<=A2<=…<=An), то алгоритм поиска места элемента позволяет узнать самое первое из мест, на которое может быть вставлено число b в массив А1,…, Аn без нарушения упорядоченности по убыванию. Изменить алгоритм, чтобы указывалось последнее из этих мест.

11. Даны a1<a2<a₃<…<a_n, b – некоторое число. Вставить число b в упорядоченную совокупность а₁, а₂,…а_n

12. Даны a₁>a₂>a₃>…>a_n, b – некоторое число. Вставить число b в упорядоченную совокупность а₁, а₂,…а_n В случае если среди элементов есть элементы равные b вставку осуществить на самое последнее из мест.

13. Даны a₁ <a₂<a₃<…<a_n, b – некоторое число. Вставить число b в упорядоченную совокупность а₁, а₂,…а_n В случае если среди элементов есть элементы равные b вставку осуществить на самое последнее из мест.

14. Использовать предложенную в задаче 2 игру. Указать количество вопросов которые при экономном ведении игры будет достаточным для угадывания числа от 1 до 4000, 5000.

15. Воспользовавшись утверждением, сформулированным в задаче №5, вычислить количество сравнений, которое потребуется произвести при n=100, 110, 120, 130 (без учета дополнительного сравнения).Построить график зависимости.