Деякі завдання шкільної математики
За мотивами статті «Про одну задачу, яку більше не пропонують на співбесіді».
Для початку розглянемо задачу, яку все-таки можуть запропонувати на співбесіді.
38. Обчислити суму ( «Завдання для дітей від 5 до 15 років»)
(з помилкою не більше 1% від відповіді)
Алгоритм для обчислення часткових сум ряду мовою Scheme (Lisp) в середовищі drRacket (drRacket дозволяє робити обчислення в звичайних дробах):
#lang racket
(define series_sum
( lambda (n)
(if (= n 0 0
(+ (/ 1 (* n (+ n 1))) (series_sum(- n 1)))
) ) )
(series_sum 10)
(series_sum 100)
(series_sum 1000)
(series_sum 10000)
(series_sum 100000)
(series_sum 1000000)
(define series_sum_1
( lambda (n)
(if (= n 0 0
(+ (/ 1.0 (* n (+ n 1.0))) (series_sum_1(- n 1.0)))
) ) )
(series_sum_1 10)
(series_sum_1 100)
(series_sum_1 1000)
(series_sum_1 10000)
(series_sum_1 100000)
(series_sum_1 1000000)
Два останніх прикладу drRacket обчислив з помилкою
Якщо розглянути часткові суми в звичайних дробах, то можна помітити, що сума ряду дорівнює
Нагадаю, що при
У другому томі «Курсу диференціального та інтегрального числення» (363) розглядається загальний випадок
Далі, перейдемо до основної теми статті розглянемо ще один приклад із задачника.
43. Числа кроликів («Фібоначчі»), утворюють послідовність в якій
для всякого
. Знайти найбільший спільний дільник чисел
і
.
Відповідь: Два сусідніх числа Фібоначчі взаємно прості, тобто
(gcd — це greatest common divisor, тобто НОД).
Доказ з книги «За сторінками підручника математики» [10-11]:
З рівності випливає, що
. Задкуючи таким чином тому, прийдемо до
, а тому два сусідніх числа Фібоначчі взаємно прості.
Доказ того, що в книзі не наводиться, але за алгоритмом Евкліда
де — залишок від ділення
на
а оскільки для чисел Фібоначчі
то
Ще один приклад з задачника
53. Для послідовності чисел Фібоначчі завдання 43 знайти межа відносини
при прагненні
до нескінченності:
Відповідь: «золотий перетин», .
Розглянемо відрізки, що представляють собою різниці двох сусідніх членів ряду .
Парні члени ряду представляють зростаючу послідовність
Непарні члени ряду являють убуваючу послідовність
По лемі про вкладених проміжках (Курс диференціального і інтегрального обчислення, 38)
Для нашого ряду в точці справедливо рівність
Зробивши заміну , отримаємо шукане рішення.
Наступний приклад із задачника
54. Обчислити нескінченну ланцюгову дріб
Завдання подібного типу є в книзі «За сторінками підручника математики» [10-11]
4. Покажіть, що число дорівнює числу
, заданому золотий перетин.
Розглянемо варіанту
Курс диференціального і інтегрального обчислення, 35 (2):
Таким чином виходить із
за форуле
… За основною теоремою, варіанта має якийсь кінцевий межа
. Для визначення його перейдемо до границі у рівності
Ми отримаємо, таким чином, що задовольняє квадратному рівнянню
Це рівняння має корені різних знаків; але нас цікавить межа не може бути негативним, отже, дорівнює саме позитивного корені:
З чого можна зробити висновок, що «золотий перетин» є рішенням рівняння
при .
Далі, розглянемо варіанту
Курс диференціального і інтегрального обчислення, 35 (3):
Нехай — будь-яке позитивне число, і покладемо
. Написане вище рекурентне співвідношення заміниться таким:
Взявши початкове значення під умовою:
, отримаємо, що
, монотонно зростати, буде прагнути до
. За цією схемою на рахункових машинах і обчислюється число, протилежне
.
Алгоритм обчислення числа, оберненого на мові Python:
def reciprocal(c,y0,n):
arr=[]
for i in range(n):
arr.append(y0)
y0=y0*(2-c*y0)
return, arr
Функція reciprocal приймає на вхід число , початкове значення
, кількість ітерацій
і повертає масив «наближення» до числа
.
при
при
при
і т. д.
Приклади роботи функції reciprocal при різних
>>> reciprocal(3,0.1,10)
[0.1,
0.17,
0.2533,
0.31411733000000003,
0.3322255689810133,
0.3333296519077525,
0.3333333332926746,
0.33333333333333337,
0.33333333333333337,
0.33333333333333337]
>>> reciprocal(8,0.1,10)
[0.1,
0.12,
0.1248,
0.12499968,
0.1249999999991808,
0.125,
0.125,
0.125,
0.125,
0.125]
>>> reciprocal(5,0.1,10)
[0.1,
0.15000000000000002,
0.18750000000000003,
0.19921875000000003,
0.19999694824218753,
0.1999999999534339,
0.20000000000000004,
0.19999999999999998,
0.19999999999999998,
0.19999999999999998]
(Т. о. застосування цього алгоритму вимагає обмежень)
На завершення: хотілося б нагадати всім про завдання Багато бітів з нічого з журналу «Квант». Завдання передбачає рішення методом перебору і вже згадувалася на Хабре — ось, ось, ось, ось і ось.
Книги:
«Завдання для дітей від 5 до 15 років», Ст. В. Арнольд.
«Курс диференціального і інтегрального обчислення», Р. М. Фіхтенгольц.
«За сторінками підручника математики», М. Я. Віленкін, Л. П. Шибасов, З. Ф. Шибасова.