практикумы по языку Питон. Питон. Практикум Загидуллин Наиль Рашитович мбоу сош 2 Оглавление Введение в Питон 4 Команда вывода 4

• Название: Практикум Загидуллин Наиль Рашитович мбоу сош 2 Оглавление Введение в Питон 4 Команда вывода 4
• Анкор: практикумы по языку Питон
• Дата: 07.11.2022
• Размер: 7.93 Mb.
• Имя файла: Питон.docx
• Тип: Практикум; #774704
• страница: 7 из 11

Метод половинного деления (Двоичный или бинарный поиск)

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

Задача1: Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?

n=int(input())

k=0

d=0

while n>1:

d=n%2

n//=2

k+=1

if d==1:

n+=1

print(k)

Задача2.1: Имеется отсортированный список из чисел. Нужно выяснить имеется ли там число n.

Самый тривиальный способ — это перебирать массив (линейный поиск). Но если список большой, то поиск будет не эффективной.

Способ 1

import random

L = 1

R = 20

Mid = 0

n, x = 3, 0

m =[random.randint(1,5) for i in range(20)]

m.sort()

print(m)

while R > L:

Mid = (R+L)//2

if m[Mid] == n:

x = n

print("yes")

break

else:

if n < Mid:

R = Mid - 1

else:

L = Mid + 1

if x == 0:

print("no")

Способ 2

Для двоичного поиска в Питоне можно использовать модуль bisect

Задача 2.2 Имеется отсортированный список из чисел. Нужно вставить в список число, не нарушая сортировку.

import bisect, random

left=1

right=10

m=[]

for i in range(left,right):

m.append(random.randint(1,50))

m.sort()

x=int(input())

k = bisect.bisect_left(m, x)

m.insert(k,x)

print(m)

Решите задачи:


Урок 3.4 Задача3

n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) def find(n,k,a,b): if 0 for i in b: L = 0 R = n-1 while R - L > 1: M = (R + L) // 2 if a[M] < i: L = M else: R = M if i == a[R] or i == a[L]: print('YES') else: print('NO') find(n,k,a,b) Тестирование программы def test1(): n=10 k=5 a=[1,2,3,4,5,6,7,8,9,10] b=[-2,0,4,9,12] find(n,k,a,b) return def test2(): n=2 k=1 a=[1,2] b=[1] find(n,k,a,b) return test1() test2()

1 Решите эту задачу, используя модуль bisect

Урок 3.5

2 Первый нуль. Дан массив, нужно найти позицию первого нуля. Счет с нуля!

[1111111111110111], ответ: 12

3 Первый чётный. Дан массив чисел, первая часть состоит из нечетных чисел, а вторая - из четных. Найти индекс, начиная с которого все числа четные.