Изучаем Python для успешной сдачи ЕГЭ: алгоритмы и код

Наиболее эффективный способ - использовать цикл по всем наборам переменных. Для четырёх переменных (x, y, z, w) функция вычисляется напрямую.

for x in (0,1):
    for y in (0,1):
        for z in (0,1):
            for w in (0,1):
                f = int((x and y) or (not z) and w)
                print(x, y, z, w, f)

решение задач егэ python (решение задач егэ по информатике на python)

Этот код выводит все комбинации и значение функции.

Эффективное решение заключается в переборе чисел в заданном диапазоне и проверке условий с помощью функции перевода в произвольную систему счисления. Пример задачи: найти все числа от 1 до 1000, у которых в троичной записи ровно две цифры 2.

def to_base(n, base):
    digits = []
    while n > 0:
        digits.append(n % base)
        n //= base
    return ''.join(str(d) for d in reversed(digits))

result = []
for num in range(1, 1001):
    trinary = to_base(num, 3)
    if trinary.count('2') == 2:
        result.append(num)
print(result[:10])

задача примеры python (примеры задач по python с решениями)

[5, 6, 7, 14, 15, 16, 19, 20, 21, 23]

Оптимальный способ - организовать цикл, который последовательно заменяет вхождения подстрок до тех пор, пока это возможно. Используется метод replace с ограничением количества замен (count=1).

s = '121212'
while '12' in s:
    s = s.replace('12', '21', 1)
print(s)

212112

Пояснение: цикл продолжается, пока в строке есть подстрока '12'. Каждая замена затрагивает только первое вхождение, что позволяет обрабатывать перекрывающиеся шаблоны.

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

# Граф задан списком смежности (ориентированный ациклический)
graph = {
    1: [2, 3],
    2: [3, 4],
    3: [5],
    4: [5],
    5: []
}
start, end = 1, 5
dp = {v: 0 for v in graph}
dp[start] = 1
# Топологический порядок (известен заранее, можно использовать обход)
order = [1,2,3,4,5]
for v in order:
    for u in graph[v]:
        dp[u] += dp[v]
print(dp[end])

3

Для функций с глубокой рекурсией лучше использовать итеративный подход с запоминанием промежуточных значений (динамическое программирование). Пример: F(n) = n, если n < 3; иначе F(n-1) + 2*F(n-2). Вычислить F(50).

n = 50
f = [0] * (n+1)
f[0] = 0
f[1] = 1  # хотя по условию n<3, начнём с 0 и 1
f[2] = 2
for i in range(3, n+1):
    f[i] = f[i-1] + 2 * f[i-2]
print(f[n])

12297829382473034410

Этот код выполняется за O(n) и не использует рекурсию.

Считываем все числа в список, затем проходим по всем парам с помощью вложенных циклов. Для уменьшения числа операций можно использовать перебор только по индексам i < j, если пары неупорядочены.

with open('data.txt') as f:
    nums = [int(line) for line in f]

count = 0
for i in range(len(nums)):
    for j in range(i+1, len(nums)):
        if (nums[i] + nums[j]) % 8 == 0 and (nums[i] * nums[j]) % 2 != 0:
            count += 1
print(count)