11_класс_19_метод_перебора_инфоурок

1.

РАЗРАБОТКА И ПРОГРАММНАЯ
РЕАЛИЗАЦИЯ АЛГОРИТМОВ
РЕШЕНИЯ ЗАДАЧ МЕТОДОМ
ПЕРЕБОРА

2.

ЯЗЫК ПРОГРАММИРОВАНИЯ – ЭТО ФОРМАЛЬНЫЙ
ЯЗЫК, ПРЕДНАЗНАЧЕННЫЙ ДЛЯ ЗАПИСИ АЛГОРИТМОВ,
ИСПОЛНИТЕЛЕМ КОТОРЫХ БУДЕТ КОМПЬЮТЕР
Алгоритм
• Это описание последовательности
действий исполнителя над исходными
данными, приводящих к результату
Исполнитель
• Это некоторый объект (человек, животное,
машина), способный выполнять набор
команд

3.

Тип данных — это характеристика данных,
которая определяет, какие значения могут
принимать данные, какие операции можно над
ними выполнять и как они хранятся в памяти
компьютера
В языке Python существует несколько встроенных типов
данных:
• Числовые типы: int (целые числа), float (вещественные
числа)
• Логический тип: bool (булевы значения True и False)
• Последовательности: str (строки), list (списки), tuple
(кортежи), range (диапазоны)
• Множества: set (множества), frozenset (неизменяемые
множества)

4.

МЕТОД ПОЛНОГО ПЕРЕБОРА (BRUTE FORCE) — ЭТО
ПОДХОД, ПРИ КОТОРОМ ПРОГРАММА ПРОВЕРЯЕТ ВСЕ
ВОЗМОЖНЫЕ ВАРИАНТЫ ДЛЯ НАХОЖДЕНИЯ РЕШЕНИЯ
ЗАДАЧИ.
Используется
• когда количество вариантов относительно
невелико, для точного нахождения оптимального
решения, в задачах малого масштаба
Сильные и слабые стороны
• гарантированно находит оптимальное решение и
прост в написании, но его сложность O(n!)
экспоненциальная, поэтому не используется в
больших данных

5.

ДЛЯ ПЕРЕБОРА ИСПОЛЬЗУЕТСЯ ЦИКЛ С ПЕРЕМЕННОЙ,
КОТОРАЯ ПОСЛЕДОВАТЕЛЬНО ПРИНИМАЕТ ВСЕ
ЗНАЧЕНИЯ ИЗ РАССМАТРИВАЕМОГО МНОЖЕСТВА
1.
2.
for i in range(n):
# i — переменная цикла
print(i)
# перебирает 0, 1, 2, ..., n-1
1.
2.
for i in [1, 2, 3]: # i — переменная цикла
print(i)
# перебирает 1, 2, 3
1.
2.
3.
for x in range(3):
for y in range(3): # x и y — переменные циклов
print(x, y)
# перебирает все пары (0,0), (0,1), ...

6.

ЗАДАЧА 1
• Найти все числа от 1 до 100, кратные 7
Решение
1.
for i in range(1, 101):
2.
if i % 7 == 0:
3.
print(i)

7.

ЗАДАЧА 2
• Найти сумму чисел от 1 до 50, которые делятся на 5
Решение
1.
s=0
2.
for i in range(1, 51):
3.
if i % 5 == 0:
4.
s += i
5.
print("Сумма:", s)

8.

ЗАДАЧА 3
• найти все пары чисел (a, b), где
a + b = 10, a и b — целые от 0 до 10
Решение
1.
for a in range(11):
2.
for b in range(11):
3.
if a + b == 10:
4.
print(a, b)

9.

ЗАДАЧА 4
• найти наибольшее число, делящееся на 9 и меньшее 100
Решение
1.
max_number = 0
2.
for i in range(1, 100):
3.
if i % 9 == 0:
4.
max_number = i
5.
print(max_number)

10.

ДОМАШНЕЕ ЗАДАНИЕ
Задача 1: Найдите количество трёхзначных чисел,
которые делятся на 7 или на 11, но не делятся на 3.