Хабиб Изадха , Рашид Бехзадидуст - Решение трудных и увлекательных задач на Python

не выполняются,
вернуть None.
'''
if dx1 == dx2 == 0:
ty = (sy2 - sy1) / (dy1 - dy2)
if int(ty) == ty and ty > 0:
t = int(ty)
else:
t = None
return t
'''
3:
Если векторы движения определяют смещение вдоль
оси x и (dy1 == dy2 == 0),
позицию x точки встречи:

7.4. Когда две лягушки встретятся в одном квадрате  227

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

Если tx недробное число
и положительное,
то вернуть tx.
Иначе, если предыдущие условия не выполняются,
вернуть None.
'''
if dy1 == dy2 == 0:
tx = (sx2 - sx1) / (dx1 - dx2)
if int(tx) == tx and tx > 0:
t = int(tx)
else:
t = None
return t
'''
4:
Если dx1 != dx2 (не равны):
1: Если dy1 != dy2, то вычисляются tx и ty.
1.2: Если tx и ty равны и имеют
недробные положительные значения,
то вернуть tx, иначе вернуть None.
2: Если dy1 = dy2, то вычисляется tx.
2.1: Если tx недробное и положительное число,
то вернуть tx,
иначе вернуть None.
'''
if dx1 != dx2:
if dy1 != dy2:
tx = (sx2 - sx1) / (dx1 - dx2)
ty = (sy2 - sy1) / (dy1 - dy2)
if tx == ty and int(tx) == tx and tx > 0:
t=int(tx)
else:
t = None
return t
elif dy1 == dy2:
tx = (sx2 - sx1) / (dx1 - dx2)
if int(tx) == tx and tx > 0 and sy1 == sy2:
t = int(tx)
else:
t = None
return t

228

110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

 Глава 7. Разные задачи

'''
5:
Если dx1 == dx2 (равны)
1: Если dy1 != dy2, то вычислить ty.
1.1: Если ty недробное и
положительное число, то
вернуть tx, иначе
вернуть None.
2: Если dy1 == dy2, то вернуть None.
'''
if dx1 == dx2:
if dy1 != dy2:
ty = (sy2 - sy1) / (dy1 - dy2)
if int(ty) == ty and ty > 0 and sx1 == sx2:
t = int(ty)
else:
t = None
return t
elif dy1 == dy2:
t=None
return t
return t

7.5. Определение позиции числа
в массиве Витхофа
Массив Витхофа – это двумерная таблица, которая характеризуется первой
строкой, содержащей последовательность Фибоначчи (1, 2, 3, 5, …). Массив
можно определить следующим образом: пусть pr обозначает предыдущую
строку, cr обозначает текущую строку, а a и b – первый и второй элементы pr соответственно. Первый элемент следующей строки (исключая первую строку) определяется как наименьшее число, которое не встречается
ни в одной из предыдущих строк, и обозначается как c. Второй элемент
следующей строки определяется на основе следующих двух условий:
1) если c – a = 2, то значение второго элемента равно b + 3;
2) если c – a ≠ 2, то значение второго элемента равно b + 5.

b + 3
x=
b + 5

если c – a == 2 (равно 2)
если c – a != 2 (не равно 2)

.

(7.1)

7.5. Определение позиции числа в массиве Витхофа    229

Значение каждого следующего элемента определяется подобно числам
в последовательности Фибоначчи – как сумма двух предыдущих элементов. Например, пусть x1, x2 и x3 обозначают первую, вторую и третью строки массива Витхоффа.
х1 = 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
х2 = 4, 7, 11, 18, 29, 47, 76, 123, 199,
х3 = 6, 10, 16, 26, 42, 68, 110, 178, 288.
Согласно правилам, первый элемент x2 равен 4 – наименьшему числу, которого нет в x1. Чтобы определить второй элемент в x2, используем
a = 1 и b = 2 из x1 и c = 4 из x2. Вычисляем c – a: 4–1 = 3. Поскольку 3 ≠ 2,
используем формулу b + 5 и получаем 7 – значение для второго элемента
в x2. После получения первых двух элементов в x2 мы можем продолжить
эту последовательность, используя алгоритм Фибоначчи. Например, третий элемент получается сложением 7 и 4 – двух предыдущих элементов,
в результате получается 11. Используя аналогичный подход, можно получить x3 из x2. Цель этой задачи – найти позицию (индекс) заданного числа n в виде кортежа (строка, столбец). Ваша задача: написать функцию, которая принимает положительное целое число n и возвращает его позицию
в виде кортежа (строка, столбец) в массиве Витхофа.
В табл. 7.5 показаны ожидаемые результаты для некоторых входных
данных.
Таблица 7.5. Некоторые ожидаемые результаты для задачи
поиска позиции числа в массиве Витхофа
n

Ожидаемый результат

1042

(8, 8)

13

(0, 5)

127

(48, 0)

20022

(4726, 1)

Алгоритм
Пусть n – заданное искомое число. Алгоритм начинается с инициализации переменных и множеств. Затем он перебирает максимально допустимое количество столбцов (n + 1) и генерирует два числа в текущей строке
на основе меньшего и большего чисел из предыдущей строки. Меньшее
число выбирается в качестве отправной точки, и алгоритм выполняет итерации до тех пор, пока не будет найдено непосещенное число. Затем на основе формулы 7.1 вычисляется следующее число. Далее алгоритм проверяет, присутствует ли искомое число в текущей --">