07.08.2018 19:33
demsp 22 7600 Источник
По мотивам статьи «Об одной задаче, которую больше не предлагают на собеседовании».

Для начала рассмотрим задачу, которую всё-таки могут предложить на собеседовании.

38. Вычислить сумму ( «Задачи для детей от 5 до 15 лет»)

$\frac{ 1 }{ 1\cdot2 } + \frac{ 1 }{ 2\cdot3 } + \frac{ 1 }{ 3\cdot4 } + ... + \frac{ 1 }{ 99\cdot100 }$


(с ошибкой не более 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 вычислил с ошибкой



Если рассмотреть частичные суммы в обыкновенных дробях, то можно заметить, что сумма ряда равна

$ \frac{ n }{ n + 1 } $



Напомню, что $\lim \frac{ n }{ n+1 } = \frac{ 1 }{ 1+ \frac{1}{n} } = \frac{1}{1}=1 $ при $ n \to \infty $

Во втором томе «Курса дифференциального и интегрального исчисления» (363) рассматривается общий случай

$ \sum \frac{ 1 }{ ( \alpha + n)( \alpha + n +1) } = \frac{ 1 }{ \alpha + 1 } $



Далее, перейдём к основной теме статьи и рассмотрим ещё один пример из задачника.
43. Числа кроликов («Фибоначчи»), образуют последовательность $(a_{1}=1), 1, 3, 5, 8, 13, 21, 34, ..., $ в которой $ a_{n+2} = a_{n+1} + a_{n} $ для всякого $ n = 1, 2, ... $. Найти наибольший общий делитель чисел $ a_{100} $ и $ a_{99} $.

Ответ: Два соседних числа Фибоначчи взаимно просты, т.е. $ \gcd(u_{n+1},u_{n}) = 1 $
(gcd — это greatest common divisor, т.е. НОД).

Доказательство из книги «За страницами учебника математики» [10-11]:
Из равенства $ u_{n+2} = u_{n+1} + u_{n} $ следует, что $ \gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},u_{n})$. Пятясь таким образом назад, придём к $ \gcd(u_{2},u_{1}) = \gcd(1,1) = 1 $, а потому два соседних числа Фибоначчи взаимно просты.

Доказательство того, что $\gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},u_{n})$ в книге не приводится, но по алгоритму Евклида
$\gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},r)$
где $ r $ — остаток от деления $u_{n+2} $ на $ u_{n+1}$

а поскольку для чисел Фибоначчи $ r = u_{n}$
то
$\gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},u_{n})$

Еще один пример из задачника
53. Для последовательности чисел Фибоначчи $a_{n}$ задачи 43 найти предел отношения $ \frac { a_{n+1} }{ a_{n} } $ при стремлении $ n $ к бесконечности:

$ \frac { a_{n+1} }{ a_{n} } = 2, \frac {3}{2}, \frac {5}{3}, \frac {8}{5}, \frac {13}{8},\frac {21}{13}, \frac {34}{21}. $


Ответ: «золотое сечение», $ \frac {\sqrt{5} + 1}{2} \approx 1,618 $.

Рассмотрим отрезки, представляющие собой разности двух соседних членов ряда $ \frac { a_{n+1} }{ a_{n} } $.

Четные члены ряда $ \frac { a_{n+1} }{ a_{n} } $ представляют растущую последовательность $ x_{n} $

$\frac{ 3 }{ 2 }, \frac{ 8 }{ 5 }, \frac{ 21 }{ 13 }, ..., $



Нечетные члены ряда $ \frac { a_{n+1} }{ a_{n} } $ представляют убывающую последовательность $ y_{n} $

$2 , \frac{ 5 }{ 3 }, \frac{ 13 }{ 8 }, ..., $



По лемме о вложенных промежутках (Курс дифференциального и интегрального исчисления, 38)

$ c = \lim x_{n} = \lim y_{n} $


Для нашего ряда в точке $ c $ справедливо равенство $ \frac { a_{n+2} }{ a_{n+1} } = \frac { a_{n+1} }{ a_{n} } $

Произведя замену $ a_{n+2} = a_{n+1} + a_{n} $, получим искомое решение.


www.geogebra.org/geometry






Следующий пример из задачника
54. Вычислить бесконечную цепную дробь

$1+ \frac{1}{2 + \frac{1}{1+ \frac{1}{2+ \frac{1}{1+ \frac{1}{2+...}}}}}$



Задача подобного типа есть в книге «За страницами учебника математики» [10-11]
4. Покажите, что число $\sqrt{1+ \sqrt{1 +\sqrt{1 + ...} } }$ равно числу $\varphi $, задающему золотое сечение.

Рассмотрим варианту $ x_{n} = \sqrt{c+ \sqrt{c +... + \sqrt{c } } } $
Курс дифференциального и интегрального исчисления, 35 (2):
Таким образом $ x_{n+1}$ получается из $ x_{n+1}$ по форуле

$ x_{n+1} = \sqrt{c + x_{n} } $


… По основной теореме, варианта $ x_{n}$ имеет некий конечный предел $ a $. Для определения его перейдём к пределу в равенстве

$ x_{n+1}^{2} = c + x_{n}; $


Мы получим, таким образом, что $ a $ удовлетворяет квадратному уравнению

$ a^{2} = c + a $


Уравнение это имеет корни разных знаков; но интересующий нас предел $ a $ не может быть отрицательным, следовательно, равен именно положительному корню:

$ a = \frac{ \sqrt{4c + 1} + 1}{2} $



Из чего можно сделать вывод, что «золотое сечение» является решением уравнения $ a^{2} = c + a $
при $ c = 1 $.

Далее, рассмотрим варианту $ x_{n+1} = x_{n}(2 - x_{n}) $
Курс дифференциального и интегрального исчисления, 35 (3):
Пусть $ c $ — любое положительное число, и положим $ x_{n} = cy_{n} $. Написанное выше рекуррентное соотношение заменится таким:

$ y_{n+1} = y_{n}(2 - cy_{n}) $


Взяв начальное значение $ y_{0} $ под условием: $ 0< y_{0}<\frac{1}{c} $, получим, что $ y_{n} $, монотонно возрастая, будет стремиться к $ \frac{1}{c} $. По этой схеме на счётных машинах и вычисляется число, обратное $ c $.


Алгоритм вычисления числа, обратного $ c $ на языке Python:
def reciprocal(c,y0,n):
	arr=[]
	for i in range(n):
		arr.append(y0)
		y0=y0*(2-c*y0)
return arr

Функция reciprocal принимает на вход число $ c $, начальное значение $ y_{0} $, количество итераций $ n $ и возвращает массив «приближений» к числу $ \frac{1}{c} $.
$ y_{0} = 0.1 $ при $ c<10 $
$ y_{0} = 0.01 $ при $ 10<c<100 $
$ y_{0} = 0.001 $ при $ 100<c<1000 $
и т.д.
Примеры работы функции reciprocal при различных $ c $

>>> 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 лет», В. И. Арнольд.
«Курс дифференциального и интегрального исчисления», Г. М. Фихтенгольц.
«За страницами учебника математики», Н. Я. Виленкин, Л. П. Шибасов, З. Ф. Шибасова.

Комментарии (22)


  1. akhalat
    08.08.2018 03:20
    #18969483
    +1

    Слово «варианта» — устаревшее, понятное только в контексте самого Фихтенгольца, все же кто изучал теорию предела по другим учебникам знают слово «последовательность», неплохо было бы заменить везде в тексте. Точно также, к слову, Фихтенгольц дальше называет «выпуклую» функцию «вогнутой» и, наоборот, т.е. современное понимание этого термина оказывается обратно противоположным.

    Далее, при перепечатке и сокращении примера 35.2 стало непонятно какая «основная теорема» имеется в виду в тексте. А имеется ввиду теорема о гарантированном существовании предела монотонной и возрастающей последовательности – это важно, т.к. не удостоверившись в существовании предела, предельный переход к числу a делать нельзя – можно получить бессмысленный ответ (примеры есть в том же Фихтенгольце).


    1. youree
      08.08.2018 04:27
      #18969533

      Да, с корнями тоже непонятный огород.
      Пишем просто x = sqrt(1 + sqrt(1 + ..)) и возводим в квадрат.
      Получается: x2 = 1 + x.
      Решаем.
      Основная часть задачи (опущенная в статье) как раз в том, чтобы удостовериться в существовании предела последовательности, то есть возможности написать «x =».


    1. demsp Автор
      08.08.2018 07:55
      #18969857

      Спасибо (кстати, слово «варианта» встречается не только у Фихтенгольца)


      1. akhalat
        08.08.2018 10:56
        #18970661

        Ну может где-то ещё и встречается в текстах времён Фихтенгольца или их переизданий, но сейчас полностью устарело за ненадобностью (о чём пишут, например, в примечаниях от редактора в новых изданиях того же Фихтенгольца).


  1. youree
    08.08.2018 03:45
    #18969503
    +1

    Что-то с 38-й задачей не понял.
    1 / [ n * (n+1) ] = 1/n ? 1/(n+1)
    Если так расписать каждый член суммы, то будет 1/1 ? 1/2 +1/2 ? 1/3 + 1/3 ? 1/4 +… + 1/99 ? 1/100 = 1 ? 1/100 = 0.99
    А… понял: у Вас в условии n от 1 до 99, а в программе — 99, 999, 9999… Но всё равно, надо просто из единицы вычитать 1 / (n + 1).


    1. demsp Автор
      08.08.2018 08:00
      #18969861

      Т. о. можно доказать (по индукции), что сумма ряда равна 1-1/(n+1)=n/(n+1)


  1. da-nie
    08.08.2018 07:08
    #18969739

    Для начала рассмотрим задачу, которую всё-таки могут предложить на собеседовании


    А расчёт обменного интеграла ещё пока не могут предложить на собеседовании? :)


    1. demsp Автор
      08.08.2018 08:05
      #18969871

      Задача не требует каких-то особых знаний из области дифференциального и интегрального исчисления.


      1. da-nie
        08.08.2018 08:11
        #18969879

        А много ли народу решило эту «не требующую особых знаний» задачу? :)


        1. demsp Автор
          08.08.2018 08:32
          #18969939

          Нам на первом курсе похожую задачу задавали на ИТ-курсе.


          1. da-nie
            08.08.2018 08:48
            #18969983

            И что же, все решили? :)


  1. priccroc
    08.08.2018 07:47
    #18969833

    по поводу примера 54. это нормально, что получается 2 ответа: (1 +- sqrt(3))/2? или я ошибся? если коротко, то решал так: x = 1 + 1/(2 + 1/x)


    1. priccroc
      08.08.2018 08:02
      #18969865

      извиняюсь за глупый вопрос. мое решение строится на предположении о том, что эта дробь равна конечному числу. из полученного противоречия ясно, что это не так.


    1. demsp Автор
      08.08.2018 08:25
      #18969923

      Полученный вами ответ говорит о том, что иррациональное число (1+sqrt(3))/2 можно представить в виде приближений данной цепной дроби.


      1. priccroc
        08.08.2018 08:48
        #18969985

        а как же (1 — sqrt(3))/2?


  1. aamonster
    08.08.2018 08:58
    #18970013
    +7

    Решать 38 программой на лиспе вместо 1-2 строчек на листе бумаги? Экий вы, сударь, простофиля.
    (1/1-1/2) + (1/2-1/3) +… + (1/99-1/100), раскрываем скобки, видим ответ. А не лезем в "Курс дифференциального и интегрального исчисления"


    1. da-nie
      08.08.2018 10:15
      #18970403
      +2

      Вы фактически разрушили всю идеологическую ценность статьи. :)


      1. demsp Автор
        08.08.2018 19:41
        #18973885

        :))


        1. da-nie
          08.08.2018 20:56
          #18974117

          На самом деле, это удивительно. :) Вы столько усилий потратили, но… решение было в другой плоскости. Так в общем-то получилось потому, что здесь задача изначально сделана под конкретное решение. И если не догадаться, то решать можно разными способами.


    1. pasetchnik
      09.08.2018 14:57
      #18977293

      А как у вас получилось, что 1/(2*3) = (1/2-1/3)? Ведь 1/5 <> 1/6.
      (простите, конечно, мою безграмотность, если глупость сказал: математика уже порядком подзабылась)


      1. aamonster
        09.08.2018 17:24
        #18977931
        +1

        Приводим к общему знаменателю:
        1/2 — 1/3 = 3/(2*3) — 2/(2*3) = (3-2)/(2*3) = 1/(2*3)
        Ну, на самом деле я просто примерно помнил, что такие дроби (типа 1/(2*3)) раскладываются в разность соседних. Может быть, даже и задачку подобную решал лет 30 назад, что-то в памяти задержалось — во всяком случае, идея привести произведение дробей к их разности пришла сразу, а дальше уже сразу видно, что задача решилась.

        P.S. А насчёт 1/5 — это, думаю, не математика подзабылась, а внимание рассеялось, не удивлюсь, если, пока я писал ответ, вы и сами сообразили (или вспомнили, что знаменатели складывать не надо)


        1. pasetchnik
          09.08.2018 18:15
          #18978215
          +1

          И правда.
          Видимо почаще высыпаться надо (пишу 2*3 а считаю как 2+3)