LecturesCMC/PythonIntro2017/Homework_YieldFrom

Ввести последовательность четвёрок целых чисел вида (s, d, m, n), (…), …. Для каждой четвёрки составить целочисленную последовательность {a_i}: a₀=s, a_i+1=a_i/d+m, если a_i делится на d и a_i+1=a_i+n в противном случае. Последовательность заканчивается на i-м элементе, если i+1-й будет ему равен, в противном случае (цикл из нескольких значений или неограниченный рост) последовательность считается бесконечной. Если последовательность, полученная из очередной четвёрки, заканчивается, начинается последовательность, полученная из следующей четвёрки. Ввести k и вывести k-й член этой общей последовательности или "NO", если в ней меньше k элементов. См. далее разбор решения.

(4,2,5,3),(3,5,8,1),(5,3,8,2),(3,4,2,6)
30

• Первая четвёрка породит конечную последовательность '4 7 10 (10)'
• Вторая четвёрка породит конечную последовательность '3 4 5 9 10 (10)'
• Третья четвёрка породит бесконечную последовательность '5 7 9 11 13 15 (13 15)'

• Что породит четвёртая четвёрка, мы не узнаем

Итого, 3 элемента в первой, 5 — во второй и остальные 22 — в третьей последовательности. На чётном месте стоит 13, это и есть ответ

13

Решение

Сначала напишем просто цикл который выводит все члены последовательности, получаемой из четвёрки s, d, m, n:

   1 prev, curr = None, s
   2 while prev!=curr:
   3     print(curr)
   4     prev, curr = curr, (curr+n) if curr%d else (curr//d+m)

Нет ничего легче превратить этот код в (потенциально бесконечный) генератор, который будет вычислять последовательность поэлементно:

   1 def divadd(s, d, m, n):
   2     prev, curr = None, s
   3     while prev!=curr:
   4         yield curr
   5         prev, curr = curr, (curr+n) if curr%d else (curr//d+m)

«Склеить» несколько итераторов в один можно по-разному — с помощью соответствующего метода в модуле itertools или ручным проходом в цикле (fours — это наша последовательность четвёрок):

   1 …
   2 for s, d, m, n in fours:
   3     for e in divadd(s, d, m, n):
   4         print(e)
   5 …

Правда, мы снова упираемся в то, что нам нужны не все элементы, а k-й. Значит, нужно из этих циклов делать генератор. А для генераторов есть способ и покрасивее! Можно написать yield from другой_генератор, что будет означать ровно то же самое:

   1 def catseq(fours):
   2     for four in fours:
   3         yield from divadd(*four)

И всё!

Осталось дождаться k-го элемента. Счётчик последовательности, как это полагается в Python, получим с помощью enumerate():

   1 for i,e in enumerate(catseq(fours)):
   2     if i == k:
   3         print(e)
   4 else:
   5     print("NO")

`

Возможно, вы не поверите, но это всё решение (осталось только fours ввести).

CategoryHomework