Динамика, метод мат. индукции —Каталог задач по ЕГЭ - Информатика

Тема 23. Линейные программы и ветвление

23.01 Динамика, метод мат. индукции

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела линейные программы и ветвление

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#20414

Напишите рекурсивную программу, которая находит n-ый член арифметической прогрессии. В ответ запишите 96-ой член арифметической прогрессии, в которой $a1 = 3,d = 7$ , где $a1$ - первый элемент прогрессии, $d$ - шаг прогрессии.

Показать ответ и решение

def arif(a,n,d):
    if n == 1:
        return a
    else:
        return arif(a, n - 1, d) + d
print(arif(3, 96, 7))

Ответ: 668

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#20413

Напишите программу, которая динамическим алгоритмом будет находить кол-во нечетных произведений в последовательности. В ответ запишите кол-во нечетных произведений для последовательности a = [100, 33, 46, -5, 6, 70, 803, 225, -45, 36]

Показать ответ и решение

    a = [100,33,46,-5,6,70,803,225,-45,36]
    ans = 0
    odd = 0
    for x in a:
        if x%2 == 1:
            ans += odd
            odd += 1
    print(ans)

Ответ: 10

Ошибка.
Попробуйте повторить позже

Задача 3#20412

Напишите программу, которая рекурсивным методом будет находить кол-во нечетных произведений в последовательности. В ответ запишите кол-во нечетных произведений для последовательности a = [34, 65, 75, -101, 0, 333, 535, 2, 7]

Показать ответ и решение

    def f(a,t):
        if t == -1:
            return 0
        else:
            if a[t]%2 == 0:
                return f(a,t-1)
            else:
                return odd(a,t-1)+f(a,t-1)
    def odd(a,t):
        if t == -1:
            return 0
        else:
            if a[t]%2 == 1:
                return odd(a,t-1)+1
            else:
                return odd(a,t-1)
    a = [100,33,46,-5,6,70,803,225,-45,36]
    print(f(a,len(a)-1))

Ответ: 15

Ошибка.
Попробуйте повторить позже

Задача 4#20411

Дано равенство $(n+1)n 1+ 2+ 3+ ...+ n = --2---$ . Напишите программу, используя динамический алгоритм, доказывающий (проверяющий) верность равенства (n < 1000). В качестве ответа запишите 0.

Показать ответ и решение

    for n in range(1000):
        summ = 0
        for j in range(1,n+1):
            summ += j
        if summ == ((n+1)*n)//2:
            print("На данном n равенство выполняется!")
        else:
            print("Ошибка в равенстве!")
            break

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 5#20410

Докажите при помощи математической индукции, что в n-угольнике ровно $2 n-−23n$ диагоналей (n > 3). В качестве ответа запишите 0.

Показать ответ и решение

Докажем, для n = 4: $2 4-−32∗4= 2$ . Это верно.

Примем, что для n = k: $k2−23k-$ верно.

Теперь докажем, для n = k+1: $(k+1)2−3(k+1) = k2+2k+1−3k−3-= k2−-k−-2= k2−3k+ (k − 1) 2 2 2 2$ .

При добавлении новой вершины в n-угольник мы получаем одну дополнительную диагональ (если поставить её между веришами $A$ и $B$ , то бывшее ребро $AB$ станет диагональю) и $k − 2$ диагоналей (соединяя новую вершину со всеми остальными кроме соседних). Тогда у нас добавляется $1+ k − 2 = k − 1$ диагональ. Что и соответствует равенству выше.

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 6#20272

Из квадрата клетчатой бумаги размером $2n × 2n$ вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на уголки из трех клеток.

В качестве ответа запишите 0.

Показать ответ и решение

База: для $n = 1$ , очевидно, что если квадрата 2×2 убрать одну клетку, получится уголочек из трех клеток.

Переход: возьмём, что квадрат $2k × 2k$ можно разрезать на уголки из трех клеток.

Докажем для $2k+1 × 2k+1$ : мы получим квадрат, который в четыре раза больше квадрата $2k × 2k$ , то есть состоит из 4 таких же квадратов.

Если из одного квадрата вырезать одну клетку, по предположению индукции, мы можем разбить его на уголки из 3 клеток. Теперь вырежем из центра квадрата уголок из трех клеток, не используя квадрат, из которого уже убрали клетку. Получается, мы убрали по одной клетке из каждого квадрата, по предположению индукции, мы можем разбить эти маленькие квадраты на уголки. И можно заметить, что мы, как и требуется по условию, убрали только одну одиночную клетку из большого квадрата. Клетки, которые мы убрали из трех квадратов образуют уголок из трех клеток, остальное разобьется по предположению.

Ответ: 0

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#20271

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

В ответ запишите 0.

Показать ответ и решение

База: при одном разрезе очевидно, что одна часть будет чистая, другая грязная.

Переход: k разрезов оставляют чистый кусок. Докажем, что k+1 разрез тоже оставят чистый кусок.

На картинке черным нарисованы k распилов, синим отмечен чистый кусок, оставленный после k распилов. Красным нарисованы возможные положения k+1 распила: он может проходить через чистый кусок или не проходить. Если он не проходит через чистый кусок, то чистый кусок всё еще остается чистым. Если же проходит, то одна часть чистого куска всё еще останется чистой.

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 8#20270

Докажите, что при любом $n$ число $an$ делится на $b$ :

$an = 2n3 + 3n2 + 7n,$ $b = 6$ .

В качестве ответа запишите 0.

Показать ответ и решение

Проверим для $n = 1$ :

$a1 = 2+ 3+ 7 = 12$ , делится на 6.

Переход: допустим для $n = k$ , выполняется равенство:

$ak = 2k3 + 3k2 + 7k$

Тогда проверим для $n = k + 1$ :

$ak+1 = 2(k + 1)3 +3(k + 1)2 +7(k +1)$

Преобразуем:

$ak+1 = 2(k + 1)3 +3(k + 1)2 +7(k +1) =$

$= 2(k3 + 3k2 + 3k+ 1)+ 3(k2 + 2k+ 1)+ 7(k +1) =$

$= 2k3 + 6k2 + 6k+ 2 + 3k2 + 6k+ 3 +7k + 7 = (2k3 + 3k2 + 7k) +6k2 + 6k+ 6k+ 12 =$

$3 2 2 = (2k + 3k + 7k)+ 6(k + k+ 2)$

Поскольку $(2k3 + 3k2 + 7k)$ делится на 6 по предположению и у $6(k2 + k+ 2)$ есть множитель 6, то и сумма делится на 6.

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 9#20269

Докажите, что для всех натуральных n чисел верно равенство:

$m + (m + 1)+ (m + 2)+ ...+ (m + n) = (2m-+-n)(n-+-1) 2$

В качестве ответа напишите 0.

Показать ответ и решение

База: для $n = 1$ имеем, $(2m + 1)(1+ 1) m + (m + 1) =-------2------= 2m + 1$ .

Переход: предположим, что для $n = k$ выполняется

$(2m-+-k)(k-+1)- m + (m + 1)+ (m + 2)+ ...+ (m + k) = 2$

Проверим, что для $n = k+ 1$ тоже выполняется:

$(2m-+-k+-1)(k-+-2) m + (m + 1)+ (m + 2)+ ...+ (m + k) +(m + k + 1) = 2$ - надо доказать.

По предположению индукции, первые k слагаемых свернутся в сумму и выражение примет вид:

$(2m + k)(k+ 1) (2m +k )(k+ 1)+ (2m + 2k +2) -------2------+ (m + k+ 1) = -------------2--------------=$

$= 2mk-+-k2 +-4m-+-3k+-2-= (2mk-+-k)+-(4m-+-2)+-(k2 +-2k)= 2 2$

$k(2m + 1)+ 2(2m + 1)+ k(k +2) (k+ 2)(2m + 1)+ k(k + 2) = -----------------------------= -----------------------= 2 2$

$(k+-2)(2m-+-1-+-k) = 2$ - мы получили желаемое равенство.

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 10#20268

Докажите, что для всех натуральных n чисел верно равенство:

$2 2 13 + 23 + 33 + ...+n3 = n-(n+-1) 4$

В качестве ответа запишите 0.

Показать ответ и решение

База: для $n = 1$ имеем, $12 ∗(1 +1)2 13 = ----4------$ .

Переход: Допустим, что для n=k выполняется $3 3 3 3 k2(k + 1)2 1 + 2 + 3 + ...+ k = ---4-----$

Проверим утверждения для $n = k+ 1$ :

$(k+ 1)2(k + 2)2 13 + 23 + 33 + ...+(k + 1)3 =------------- 4$

По предположению про первые k слагаемых, сумма обретёт вид:

$2 2 2 2 k-(k+-1)- +(k + 1)3 = (k+-1)-(k-+-2)- 4 4$

Преобразуем:

$2 2 2 2 3 2 2 k-(k+-1)- +(k + 1)3 = k-(k+-1)-+-4(k-+-1)-= (k-+-1)-(k-+-4(k+-1)) 4 4 4$ =

= $(k + 1)2(k+ 2)2 -------------- 4$

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 11#11537

АР сделал банкомат, который выдает купюры достоинством $1,2,5,10,50,100,500,1000,5000$ , и перепоручил написать жадный алгоритм по выдаче купюр (банкомат должен выдавать как можно меньше купюр). На вход подается число - целое значение в рублях, программа должна напечатать значения купюр в порядке убывания, которые выдает выдаст банкомат. В ответ выпишите кол-во 5000 купюр, которые выдаст банкомат, если на вход подать число $123456789$ .

Пример входных данных: $5350$

Ответ для данного пример: $1$

Показать ответ и решение

n = 123456789
k5000 = 0
k1000 = 0
k500 = 0
k100 = 0
k50 = 0
k10 = 0
k5 = 0
k2 = 0
k1 = 0
while n != 0:
    if n >= 5000:
        n -= 5000
        k5000 += 1
        continue
    if n >= 1000:
        n -= 1000
        k1000 += 1
        continue
    if n >= 500:
        n -= 500
        k500 += 1
        continue
    if n >= 100:
        n -= 100
        k100 += 1
        continue
    if n >= 50:
        n -= 50
        k50 += 1
        continue
    if n >= 10:
        n -= 10
        k10 += 1
        continue
    if n >= 5:
        n -= 5
        k5 += 1
        continue
                                                                                                     
                                                                                                     
    if n >= 2:
        n -= 2
        k2 += 1
        continue
    if n >= 1:
        n -= 1
        k1 += 1
        continue
print(k1, k2, k5, k10, k50, k100, k500, k1000, k5000)

Ответ: 24691

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#11530

Найдите $15$ -ую ступень в треугольнике Паскаля и выпишите максимальный элемент получившейся последовательности. 1 ступень треугольника Паскаля - 1.

Показать ответ и решение

def PrintPasTriangle(rows):
    row = [1]
    for i in range(rows):
        print(row)
        row = [sum(x) for x in zip([0]+row, row+[0])]

PrintPasTriangle(15)

Ответ: 3432

Ошибка.
Попробуйте повторить позже

Задача 13#11505

Найдите девятое число Фибоначии. Числа Фибоначчи это последовательность, в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел.

Показать ответ и решение

Посчитаем эти числа вручную:

1: 0

2: 1

3: 1

4: 2

5: 3

6: 5

7: 8

8: 13

9: 21

Ответ: 21

Ошибка.
Попробуйте повторить позже

Задача 14#11503

Даны первые три элемента последовательности: A[ $1$ ] = $1$ , A[ $2$ ] = $4$ , A[ $3$ ] = $6$ . $i$ -ый элемент последовательности (A[ $i$ ]) состоит из суммы значений A[ $i − 1$ ] и A[ $i− 3$ ]. Найдите с помощью программы $31$ -ый элемент данной последовательности.

Показать ответ и решение

a = [0] * 32
a[1] = 1
a[2] = 4
a[3] = 6
for i in range(4, 32):
a[i] = a[i - 1] + a[i - 3]
print(a[31])

Ответ: 232422

Ошибка.
Попробуйте повторить позже

Задача 15#11502

Даны первый и восьмой элементы последовательности A[ $1$ ] = 3, A[ $8$ ] = 59. Найдите пятнадцатый элемент последовательности, если известно, что это арифметическая прогрессия.

Показать ответ и решение

Это арифметическая прогрессия. Тогда n-ый элемент будет равен 3 + (n - 1) * d, где d - разность арифметической прогрессии.

Восьмой элемент 59 = 3 + 7d. Тогда d = 8.

Пятнадцатый элемент последовательности равен 3 + 14 * 8 = 115.

Ответ: 115

Ошибка.
Попробуйте повторить позже

Задача 16#11499

Дана последовательность А = 2,5,11,23,47,95. Найти шаг прогрессии данной последовательности.

Запишите следующий элемент через предыдущий используя переменную i. Например для последовательности 1, 2, 4 ответом будет i * 2. Пробелы между переменными/числами и знаками сохранять.

Показать ответ и решение

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

Варианты правильных ответов:

i * 2 + 1
2 * i + 1
1 + i * 2
1 + 2 * i

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 17#11496

Дана арифметическая прогрессия первый элемент которой равен $2$ . Шаг прогрессии равен $3$ . Найдите десятый элемент последовательности.

Показать ответ и решение

n-ый элемент арифметической прогрессии будет равен 2 + (n - 1) * 3.

Тогда десятый элемент будет равен 2 + 9 * 3 = 29.

Ответ: 29

Предыдущий раздел

Следующий раздел