23.01 Динамика, метод мат. индукции
Ошибка.
Попробуйте повторить позже
Дана арифметическая прогрессия первый элемент которой равен . Шаг прогрессии равен
. Найдите десятый элемент
последовательности.
n-ый элемент арифметической прогрессии будет равен 2 + (n - 1) * 3.
Тогда десятый элемент будет равен 2 + 9 * 3 = 29.
Ошибка.
Попробуйте повторить позже
Дана последовательность А = 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
Ошибка.
Попробуйте повторить позже
Даны первый и восьмой элементы последовательности A[] = 3, A[
] = 59. Найдите пятнадцатый элемент
последовательности, если известно, что это арифметическая прогрессия.
Это арифметическая прогрессия. Тогда n-ый элемент будет равен 3 + (n - 1) * d, где d - разность арифметической прогрессии.
Восьмой элемент 59 = 3 + 7d. Тогда d = 8.
Пятнадцатый элемент последовательности равен 3 + 14 * 8 = 115.
Ошибка.
Попробуйте повторить позже
Даны первые три элемента последовательности: A[] =
, A[
] =
, A[
] =
.
-ый элемент последовательности
(A[
]) состоит из суммы значений A[
] и A[
]. Найдите с помощью программы
-ый элемент данной
последовательности.
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])
Ошибка.
Попробуйте повторить позже
Найдите девятое число Фибоначии. Числа Фибоначчи это последовательность, в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел.
Посчитаем эти числа вручную:
1: 0
2: 1
3: 1
4: 2
5: 3
6: 5
7: 8
8: 13
9: 21
Ошибка.
Попробуйте повторить позже
Найдите -ую ступень в треугольнике Паскаля и выпишите максимальный элемент получившейся последовательности. 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)
Ошибка.
Попробуйте повторить позже
АР сделал банкомат, который выдает купюры достоинством , и перепоручил написать
жадный алгоритм по выдаче купюр (банкомат должен выдавать как можно меньше купюр). На вход подается число -
целое значение в рублях, программа должна напечатать значения купюр в порядке убывания, которые выдает
выдаст банкомат. В ответ выпишите кол-во 5000 купюр, которые выдаст банкомат, если на вход подать число
.
Пример входных данных:
Ответ для данного пример:
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)
Ошибка.
Попробуйте повторить позже
Докажите, что для всех натуральных n чисел верно равенство:
В качестве ответа запишите 0.
База: для имеем,
.
Переход: Допустим, что для n=k выполняется
Проверим утверждения для :
По предположению про первые k слагаемых, сумма обретёт вид:
Преобразуем:
=
=
Ошибка.
Попробуйте повторить позже
Докажите, что для всех натуральных n чисел верно равенство:
В качестве ответа напишите 0.
База: для имеем,
.
Переход: предположим, что для выполняется
Проверим, что для тоже выполняется:
- надо доказать.
По предположению индукции, первые k слагаемых свернутся в сумму и выражение примет вид:
- мы получили желаемое равенство.
Ошибка.
Попробуйте повторить позже
Докажите, что при любом число
делится на
:
.
В качестве ответа запишите 0.
Проверим для :
, делится на 6.
Переход: допустим для , выполняется равенство:
Тогда проверим для :
Преобразуем:
Поскольку делится на 6 по предположению и у
есть множитель 6, то и сумма делится
на 6.
Ошибка.
Попробуйте повторить позже
Торт разрезали прямолинейными разрезами на несколько кусков. Оказалось, что одна сторона у ножа была грязная. Докажите, что всегда найдется хотя бы один чистый кусок.
В ответ запишите 0.
База: при одном разрезе очевидно, что одна часть будет чистая, другая грязная.
Переход: k разрезов оставляют чистый кусок. Докажем, что k+1 разрез тоже оставят чистый кусок.
На картинке черным нарисованы k распилов, синим отмечен чистый кусок, оставленный после k распилов. Красным нарисованы возможные положения k+1 распила: он может проходить через чистый кусок или не проходить. Если он не проходит через чистый кусок, то чистый кусок всё еще остается чистым. Если же проходит, то одна часть чистого куска всё еще останется чистой.
Ошибка.
Попробуйте повторить позже
Из квадрата клетчатой бумаги размером вырезали одну клетку. Докажите, что полученную фигуру можно
разрезать на уголки из трех клеток.
В качестве ответа запишите 0.
База: для , очевидно, что если квадрата 2×2 убрать одну клетку, получится уголочек из трех клеток.
Переход: возьмём, что квадрат можно разрезать на уголки из трех клеток.
Докажем для : мы получим квадрат, который в четыре раза больше квадрата
, то есть состоит из 4
таких же квадратов.
Если из одного квадрата вырезать одну клетку, по предположению индукции, мы можем разбить его на уголки из 3 клеток. Теперь вырежем из центра квадрата уголок из трех клеток, не используя квадрат, из которого уже убрали клетку. Получается, мы убрали по одной клетке из каждого квадрата, по предположению индукции, мы можем разбить эти маленькие квадраты на уголки. И можно заметить, что мы, как и требуется по условию, убрали только одну одиночную клетку из большого квадрата. Клетки, которые мы убрали из трех квадратов образуют уголок из трех клеток, остальное разобьется по предположению.
Ошибка.
Попробуйте повторить позже
Докажите при помощи математической индукции, что в n-угольнике ровно диагоналей (n > 3). В качестве ответа
запишите 0.
Докажем, для n = 4: . Это верно.
Примем, что для n = k: верно.
Теперь докажем, для n = k+1: .
При добавлении новой вершины в n-угольник мы получаем одну дополнительную диагональ (если поставить её между
веришами и
, то бывшее ребро
станет диагональю) и
диагоналей (соединяя новую вершину со всеми
остальными кроме соседних). Тогда у нас добавляется
диагональ. Что и соответствует равенству
выше.
Ошибка.
Попробуйте повторить позже
Дано равенство . Напишите программу, используя динамический алгоритм, доказывающий
(проверяющий) верность равенства (n < 1000). В качестве ответа запишите 0.
summ = 0
for j in range(1,n+1):
summ += j
if summ == ((n+1)*n)//2:
print("На данном n равенство выполняется!")
else:
print("Ошибка в равенстве!")
break
Ошибка.
Попробуйте повторить позже
Напишите программу, которая рекурсивным методом будет находить кол-во нечетных произведений в последовательности. В ответ запишите кол-во нечетных произведений для последовательности a = [34, 65, 75, -101, 0, 333, 535, 2, 7]
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))
Ошибка.
Попробуйте повторить позже
Напишите программу, которая динамическим алгоритмом будет находить кол-во нечетных произведений в последовательности. В ответ запишите кол-во нечетных произведений для последовательности 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)
Ошибка.
Попробуйте повторить позже
Напишите рекурсивную программу, которая находит n-ый член арифметической прогрессии. В ответ запишите 96-ой
член арифметической прогрессии, в которой , где
- первый элемент прогрессии,
- шаг
прогрессии.
if n == 1:
return a
else:
return arif(a, n - 1, d) + d
print(arif(3, 96, 7))