{"id":328076,"date":"2022-01-16T09:00:08","date_gmt":"2022-01-16T09:00:08","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=328076"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=328076","title":{"rendered":"<span>\u0424\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u0431\u0435\u0437 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u0438<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u041a\u0440\u0430\u0441\u0438\u0432\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u0440\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c &#8212; \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438. \u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0435\u0435 \u043d\u0435\u043f\u0440\u0438\u0433\u043e\u0434\u043d\u043e\u0439 \u0434\u043b\u044f \u0442\u043e\u0447\u043d\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. \u042d\u0442\u043e \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432\u043f\u043e\u043b\u043d\u0435 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c. \u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0441\u043f\u043e\u0441\u043e\u0431, \u043a\u0430\u043a \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u0437\u043b\u043e\u0432\u0440\u0435\u0434\u043d\u043e\u0433\u043e \u043a\u043e\u0440\u043d\u044f \u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0411\u0438\u043d\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u043d\u043e\u0439 \u0434\u043b\u044f \u0442\u043e\u0447\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439.<\/p>\n<details class=\"spoiler\">\n<summary>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e? \u0427\u0438\u0442\u0430\u0439\u0442\u0435 \u0434\u0430\u043b\u044c\u0448\u0435<\/summary>\n<div class=\"spoiler__content\">\n<p>\u041a\u0430\u043a \u0445\u043e\u0440\u043e\u0448\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u2013 \u044d\u0442\u043e \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u043f\u0435\u0440\u0432\u044b\u0435 \u0434\u0432\u0430 \u0447\u043b\u0435\u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0432\u043d\u044b \u0435\u0434\u0438\u043d\u0438\u0446\u0435, \u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0440\u0430\u0432\u0435\u043d \u0441\u0443\u043c\u043c\u0435 \u0434\u0432\u0443\u0445 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445. \u0417\u0430 500 \u043b\u0435\u0442, \u043f\u0440\u043e\u0448\u0435\u0434\u0448\u0438\u0445 \u0441 \u043c\u043e\u043c\u0435\u043d\u0442\u0430 \u0432\u0432\u043e\u0434\u0430 \u044d\u0442\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043e\u0431\u0438\u0445\u043e\u0434, \u043e\u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u0437\u0443\u0447\u0435\u043d\u0430. \u041e\u0442\u043a\u0440\u044b\u0442\u043e \u043c\u043d\u043e\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0435\u0439\u0448\u0438\u0445 \u0444\u043e\u0440\u043c\u0443\u043b \u0441 \u0443\u0447\u0430\u0441\u0442\u0438\u0435\u043c \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. \u041d\u043e \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u201c\u043d\u0435\u043f\u0440\u0435\u0445\u043e\u0434\u044f\u0449\u0438\u0445\u201d \u0443\u0447\u0435\u0431\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043e \u043c\u043d\u043e\u0433\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432: \u043e\u0442 \u043f\u0440\u044f\u043c\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u043d\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0435:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"{F}_{n}={F}_{n-1}+{F}_{n-2}\" alt=\"{F}_{n}={F}_{n-1}+{F}_{n-2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/18f\/3bd\/ee1\/18f3bdee1b76e1ca4377a8a4eb26e135.svg\" width=\"152\" height=\"21\"\/><\/p>\n<p>\u0434\u043e \u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430, \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0433\u043e, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u043a\u043d\u0438\u0433\u0435 \u0414.\u041a\u043d\u0443\u0442\u0430 [1]. \u00a0\u0411\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 (\u043a\u0440\u043e\u043c\u0435 \u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u041a\u043d\u0443\u0442\u0430) \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u044b\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443 Fn \u0432 \u043b\u0443\u0447\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0437\u0430\u00a0 \u0432\u0440\u0435\u043c\u044f O(n). \u041c\u0430\u0442\u0440\u0438\u0447\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u041a\u043d\u0443\u0442\u0430 (\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0439 \u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c) \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f [2].<\/p>\n<p>\u041e\u0441\u043e\u0431\u043d\u044f\u043a\u043e\u043c \u0432 \u044d\u0442\u043e\u043c \u0440\u044f\u0434\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 (\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430\u044f \u0435\u0449\u0435 \u041c\u0443\u0430\u0432\u0440\u0443) \u0438\u043c\u0435\u044e\u0449\u0430\u044f \u0432\u0438\u0434:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"F_n=(((1+\u221a5)\/2)^n-((1-\u221a5)\/2))^n)\/(\u221a5)\" alt=\"F_n=(((1+\u221a5)\/2)^n-((1-\u221a5)\/2))^n)\/(\u221a5)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/973\/2fe\/62c\/9732fe62c3eae92414bdf08b78e06ea2.svg\" width=\"381\" height=\"23\"\/><\/p>\n<p>\u042d\u0442\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043f\u0440\u0438\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439, \u043e\u0434\u043d\u0430\u043a\u043e \u043e\u043d\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u0440\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0440\u0438 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f\u0445 \u043c\u044b \u0432\u044b\u043d\u0443\u0436\u0434\u0435\u043d\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0432 \u0444\u043e\u0440\u043c\u0435 \u0447\u0438\u0441\u043b\u0430 \u0441 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u043e\u0439 (\u0442.\u0435. \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u0443\u044e \u043d\u0435\u043f\u0435\u0440\u0438\u043e\u0434\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0434\u0440\u043e\u0431\u044c \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439). <\/p>\n<p>\u0421\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0435 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u0442\u043e\u0447\u043d\u044b\u043c\u0438; \u0432 \u043d\u0438\u0445 \u0432\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f. \u041c\u043d\u0435 \u043e\u0434\u043d\u0430\u0436\u0434\u044b \u043f\u043e\u043f\u0430\u043b\u0430\u0441\u044c \u043d\u0430 \u0433\u043b\u0430\u0437\u0430 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f [3] \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0430\u0441\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u043b\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438 \u0441\u0432\u0435\u0440\u0445\u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e\u0441\u0442\u0438 (\u0441 \u0442\u0435\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0443\u0436\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0443\u043c\u0435\u0441\u0442\u0438\u043b\u043e\u0441\u044c \u0432 \u043c\u0430\u043d\u0442\u0438\u0441\u0441\u0443).<\/p>\n<p>\u041c\u044b \u043f\u043e\u0439\u0434\u0435\u043c \u0441\u043e\u0432\u0441\u0435\u043c \u0434\u0440\u0443\u0433\u0438\u043c \u043f\u0443\u0442\u0435\u043c!<\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0447\u0438\u0441\u0435\u043b \u0432\u0438\u0434\u0430:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x=a+\u221a5*b\" alt=\"x=a+\u221a5*b\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/224\/489\/b7f\/224489b7f65e375b75790419f639d415.svg\" width=\"123\" height=\"22\"\/><\/p>\n<p>\u043f\u0440\u0438 \u0446\u0435\u043b\u044b\u0445 a \u0438 b. \u041b\u0435\u0433\u043a\u043e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u044d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u043e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b\u221a5)+(c+d\u221a5)=((a+c)+(b+d) \u221a5)\" alt=\"(a+b\u221a5)+(c+d\u221a5)=((a+c)+(b+d) \u221a5)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/527\/8e2\/bd7\/5278e2bd7b005c97bc0d49d98294d0d2.svg\" width=\"393\" height=\"23\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b\u221a5)(c+d\u221a5)=((ac+5bd)+(ad+bc) \u221a5)\" alt=\"(a+b\u221a5)(c+d\u221a5)=((ac+5bd)+(ad+bc) \u221a5)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/662\/fcf\/87b\/662fcf87bcab6a15588472babb75a5b7.svg\" width=\"416\" height=\"23\"\/><\/p>\n<p>\u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0443\u0442 \u043a\u043e\u043c\u043c\u0443\u0442\u0430\u0442\u0438\u0432\u043d\u044b\u043c\u0438, \u0447\u0442\u043e \u0442\u043e\u0436\u0435 \u043b\u0435\u0433\u043a\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043d\u043e\u043b\u044c \u0438 \u0435\u0434\u0438\u043d\u0438\u0446\u0430 \u0445\u043e\u0440\u043e\u0448\u043e &#171;\u0432\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0442\u0441\u044f&#187; \u0432 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"1\u2261(1+\u221a5*0)\" alt=\"1\u2261(1+\u221a5*0)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d15\/4c0\/945\/d154c09451c5e34083fafbecc188a3e8.svg\" width=\"137\" height=\"23\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"0\u2261(0+ \u221a5*0)\" alt=\"0\u2261(0+ \u221a5*0)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/080\/ca5\/99e\/080ca599e12e702b60132a07ff555574.svg\" width=\"137\" height=\"23\"\/><\/p>\n<p>\u0412\u043f\u043e\u043b\u043d\u0435 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u0438 \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b\u221a5)-(c+d\u221a5)=((a-c)+(b-d) \u221a5)\" alt=\"(a+b\u221a5)-(c+d\u221a5)=((a-c)+(b-d) \u221a5)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eaf\/3c9\/e01\/eaf3c9e016b4b745941dcad9349fdb83.svg\" width=\"393\" height=\"23\"\/><\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 (\u0440\u0430\u0437\u0443\u043c\u0435\u0435\u0442\u0441\u044f, \u043b\u0438\u0448\u044c \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \u043e\u0442\u043b\u0438\u0447\u0435\u043d \u043e\u0442 \u043d\u0443\u043b\u044f). \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b\\sqrt{5})x=(c+d\\sqrt{5})\" alt=\"(a+b\\sqrt{5})x=(c+d\\sqrt{5})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d75\/005\/a21\/d75005a216476fbf2a534e30d7f7c5c1.svg\" width=\"202\" height=\"24\"\/><\/p>\n<p>\u041f\u0443\u0441\u0442\u044c <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"x=e+f\\sqrt{5}\" alt=\"x=e+f\\sqrt{5}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2b6\/14e\/24a\/2b614e24ac2784b36c4121beac70be82.svg\" width=\"106\" height=\"23\"\/><\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0435 \u0440\u0430\u0432\u0435\u0441\u0442\u0432\u043e \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b\\sqrt{5})(e+f\\sqrt{5})=(c+d\\sqrt{5})\" alt=\"(a+b\\sqrt{5})(e+f\\sqrt{5})=(c+d\\sqrt{5})\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/dda\/7b3\/8b5\/dda7b38b50565d859422694e04b2f0c5.svg\" width=\"275\" height=\"24\"\/><\/p>\n<p>\u0420\u0430\u0441\u043a\u0440\u044b\u0432\u0430\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043b\u0435\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430, \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 e \u0438 f:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a+b\\sqrt{5})(e+f\\sqrt{5})=(ae+5bf)+(af+be)\\sqrt{5}\" alt=\"(a+b\\sqrt{5})(e+f\\sqrt{5})=(ae+5bf)+(af+be)\\sqrt{5}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/162\/d1a\/315\/162d1a315fc951a5e6fd783bb2dea513.svg\" width=\"405\" height=\"24\"\/><\/p>\n<p>\u041e\u0442\u0441\u044e\u0434\u0430:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\left.\\begin{matrix} ae+5bf &amp; = &amp; c\\\\  be+af &amp; = &amp; d  \\end{matrix}\\right\\}\" alt=\"\\left.\\begin{matrix} ae+5bf &amp; = &amp; c\\\\  be+af &amp; = &amp; d  \\end{matrix}\\right\\}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ba6\/aa2\/619\/ba6aa26190233305a53706a356655342.svg\" width=\"156\" height=\"50\"\/><\/p>\n<p>\u0413\u043b\u0430\u0432\u043d\u044b\u0439 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \u044d\u0442\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0440\u0430\u0432\u0435\u043d:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\begin{vmatrix} a &amp; 5b\\\\  b &amp; a \\end{vmatrix} = {a}^{2}-5{b}^{2}\" alt=\"\\begin{vmatrix} a &amp; 5b\\\\  b &amp; a \\end{vmatrix} = {a}^{2}-5{b}^{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4d5\/fac\/b6a\/4d5facb6a2e6851261c07f89844e0405.svg\" width=\"159\" height=\"49\"\/><\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 a \u0438 b \u0437\u0434\u0435\u0441\u044c \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044f \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u0442\u043b\u0438\u0447\u043d\u043e \u043e\u0442 \u043d\u0443\u043b\u044f, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0438\u043c\u0435\u0435\u0442 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e. \u0412\u043f\u0440\u043e\u0447\u0435\u043c, \u043c\u044b \u0443\u0432\u043b\u0435\u043a\u043b\u0438\u0441\u044c. \u0414\u0435\u043b\u0435\u043d\u0438\u0435 \u043d\u0430\u043c \u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f.<\/p>\n<p>\u041c\u044b \u043f\u0440\u0438\u0448\u043b\u0438 \u043a \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0441 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u043a\u043e\u043b\u044c\u0446\u043e [4].<\/p>\n<p><strong>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c &#8212; \u0441\u0430\u043c\u043e\u0435 \u0433\u043b\u0430\u0432\u043d\u043e\u0435! \u0417\u0430\u0447\u0435\u043c \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438?<\/strong>  \u041d\u0438\u043a\u0442\u043e \u043d\u0435 \u043c\u0435\u0448\u0430\u0435\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443 \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u0440 (a,b), \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435 \u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c\u0438:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a,b)+(c,d)=((a+c),(b+d))\" alt=\"(a,b)+(c,d)=((a+c),(b+d))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6f2\/83d\/4e6\/6f283d4e614178cf471ec836119f755d.svg\" width=\"271\" height=\"22\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a,b)-(c,d)=((a-c),(b-d))\" alt=\"(a,b)-(c,d)=((a-c),(b-d))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ba3\/626\/ac8\/ba3626ac81a6c076df1f2b4e7918aa32.svg\" width=\"271\" height=\"22\"\/><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"(a,b)*(c,d)=((ac+5bd),(ad+bc))\" alt=\"(a,b)*(c,d)=((ac+5bd),(ad+bc))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b3\/d39\/eb5\/3b3d39eb568e637d60596b77bf052ccb.svg\" width=\"312\" height=\"22\"\/><\/p>\n<p><strong>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u043e\u0436\u043d\u043e \u201c\u0431\u043b\u0430\u0433\u043e\u043f\u043e\u043b\u0443\u0447\u043d\u043e \u0437\u0430\u0431\u044b\u0442\u044c\u201d \u043f\u0440\u043e \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438\u00a0 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u044f\u043c\u043e\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u0411\u0438\u043d\u0435.<\/strong> \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0446\u0435\u043b\u044b\u043c (\u0438 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438 \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u043b\u0441\u044f), \u043d\u0443\u0436\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c \u0434\u0440\u043e\u0431\u0438 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0411\u0438\u043d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u043b \u0441\u043e\u0431\u043e\u0439 \u0447\u0438\u0441\u043b\u043e \u0432\u0438\u0434\u0430:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"0+r\\sqrt{5}\" alt=\"0+r\\sqrt{5}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/325\/4f6\/bfa\/3254f6bfabf7659f453d6f5a6c5e4663.svg\" width=\"68\" height=\"23\"\/><\/p>\n<p>\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u044b \u043e\u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0438\u043c \u0441 &#171;\u043e\u0431\u044b\u0447\u043d\u044b\u043c&#187; \u0447\u0438\u0441\u043b\u043e\u043c <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"r\\sqrt{5}\" alt=\"r\\sqrt{5}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c12\/efe\/589\/c12efe589a85848aeade6f0810b4abf8.svg\" width=\"34\" height=\"23\"\/><\/p>\n<p>\u0414\u0435\u043b\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e &#171;\u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e&#187; \u0438\u0440\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438 \u0438 \u0434\u0430\u0441\u0442 \u043d\u0430\u043c \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u0446\u0435\u043b\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0447\u0442\u043e \u0432 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c (\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443 \u043f\u0430\u0440) \u0434\u0432\u0430 \u0431\u0438\u043d\u043e\u043c\u0430:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"A=(1+\u221a5)^n\/2^n\" alt=\"A=(1+\u221a5)^n\/2^n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a8f\/c9c\/faa\/a8fc9cfaa9ef70f94aa113a16fb0cd3b.svg\" width=\"154\" height=\"23\"\/><\/p>\n<p>\u0438 <\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"B=(1-\u221a5)^n\/2^n\" alt=\"B=(1-\u221a5)^n\/2^n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/aa6\/185\/e64\/aa6185e6448452407f193a31c396ab60.svg\" width=\"154\" height=\"23\"\/><\/p>\n<p>\u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435. \u041d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0442\u0440\u0443\u0434\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043f\u043e\u0434\u0445\u043e\u0434 \u043d\u0430 \u043b\u044e\u0431\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u041c\u044b \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u044d\u0442\u043e \u043d\u0430 \u041f\u0438\u0442\u043e\u043d\u0435 (\u043f\u0440\u0438\u0432\u043b\u0435\u043a\u0430\u0435\u0442 \u043d\u0435\u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u0430\u044f \u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e\u0441\u0442\u044c \u0446\u0435\u043b\u044b\u0445 \u0432 \u044d\u0442\u043e\u043c \u044f\u0437\u044b\u043a\u0435).<\/p>\n<pre><code class=\"python\">def prod_pairs(a,b):     return (a[0]*b[0]+5*a[1]*b[1],a[0]*b[1]+a[1]*b[0]) def sub_pairs(a,b):     return (a[0]-b[0],a[1]-b[1]) def pow_pair(a,n):     c=a     for _ in range(n-1):         c=prod_pairs(c,a)     return c def fib_bine(n):     x1=pow_pair((1,1),n)     x2=pow_pair((1,-1),n)     z=sub_pairs(x1,x2)     return z[1]\/\/(2**n) <\/code><\/pre>\n<p>\u041a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438 \u0438\u0437\u043b\u0438\u0448\u043d\u0438 &#8212; \u0432\u0441\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e. \u0421\u0440\u0430\u0437\u0443 \u0436\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432\u043e\u043f\u0440\u043e\u0441, \u0430 \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u043a\u043e\u0434? \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e &#171;\u0443\u0437\u043a\u0438\u043c \u043c\u0435\u0441\u0442\u043e\u043c&#187; \u0437\u0434\u0435\u0441\u044c \u044f\u0432\u043b\u044f\u0442\u0441\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u0430\u0440\u044b \u0432 \u0446\u0435\u043b\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0414\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u043f\u0440\u0438\u0435\u043c &#8212; \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c (\u044d\u0442\u0438\u043c \u0436\u0435 \u043f\u0440\u0438\u0435\u043c\u043e\u043c \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0441\u044f \u0438 \u0430\u0432\u0442\u043e\u0440 [2]). \u0418\u0434\u0435\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f x<sup>n<\/sup> \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430 x -> x<sup>2<\/sup> -> x<sup>4<\/sup> ->\u2026->x<sup>2k<\/sup> \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 2<sup>k<\/sup>&lt;=n, \u0430 \u0437\u0430\u0442\u0435\u043c \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f x<sup>(n-2k)<\/sup>.   <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u043f\u0430\u0440\u044b \u0432 \u0446\u0435\u043b\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c:<\/p>\n<pre><code class=\"python\">def pow_pair(a,n): if (n==1):     return a c=copy(a) k=1 while k*2&lt;=n:     if k&lt;=n:        c=prod_pairs(c,c)        k=k*2     p=n-k     if p>=1:        tmp=pow_pair(a,p)        return prod_pairs(tmp,c)     else:        return c <\/code><\/pre>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u0435\u043c\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0437\u0430 \u0432\u0440\u0435\u043c\u044f, \u0431\u043b\u0438\u0437\u043a\u043e\u0435 \u043a \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u0411\u0438\u043d\u0435 \u0438 \u0431\u0435\u0437 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438 \u0441 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u043e\u0439. \u0414\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u0441 \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438, \u043d\u0430\u043f\u0438\u0441\u0430\u043d \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u043a\u043e\u0434:<\/p>\n<pre><code class=\"python\">def fib_ite(n):     c,p=0,1     for _ in range(n):         c,p=c+p,c     return c <\/code><\/pre>\n<p>\u0418 \u0447\u0442\u043e \u0436\u0435? \u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u0443\u044e \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443 \u043a\u043e\u0434\u0430 fib_ite, \u0444\u0443\u043d\u043a\u0446\u0438\u044f fib_bine \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043b\u0443\u0447\u0448\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b. \u0422\u0430\u043a, \u043d\u0430 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u0435 \u0430\u0432\u0442\u043e\u0440\u0430 \u0447\u0435\u0442\u044b\u0440\u0435\u0445\u0441\u043e\u0442\u0442\u044b\u0441\u044f\u0447\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u043f\u043e \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0437\u0430 2 \u0441\u0435\u043a, \u0430 \u043f\u0440\u044f\u043c\u044b\u043c\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u2013 \u0437\u0430 27 \u0441\u0435\u043a.   \u041d\u0430 \u043f\u0440\u0438\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u0440\u0430\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0442\u0435\u0441\u0442\u043e\u0432:<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"\/img\/image-loader.svg\" alt=\"\" title=\"\" height=\"423\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0b0\/f51\/af4\/0b0f51af4b03252200bf169aa7b080a4.png\" data-width=\"573\"\/><figcaption><\/figcaption><\/figure>\n<p>\u041f\u043e \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u0441\u0438 \u043e\u0442\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u043e\u043c\u0435\u0440 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u043f\u043e \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u2013 \u0432\u0440\u0435\u043c\u044f \u0432 \u0441\u0435\u043a\u0443\u043d\u0434\u0430\u0445. <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u0432\u043f\u043e\u043b\u043d\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u043d\u0430 \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u0438 \u0442\u043e\u0447\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438.<\/p>\n<p>\u0421\u043f\u0430\u0441\u0438\u0431\u043e, \u0447\u0442\u043e \u0434\u043e\u0447\u0438\u0442\u0430\u043b\u0438 \u0434\u043e \u043a\u043e\u043d\u0446\u0430, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0438\u0441\u043a\u0440\u0435\u043d\u043d\u0435\u0435 \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0430\u0432\u0442\u043e\u0440\u0430\u043c, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u0441\u0441\u044b\u043b\u0430\u043b\u0441\u044f \u0432 \u044d\u0442\u043e\u0439 \u0437\u0430\u043c\u0435\u0442\u043a\u0435:<\/p>\n<p><strong>1.\u00a0<\/strong>\u0414.\u041a\u043d\u0443\u0442 \u0418\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0430 \u042d\u0412\u041c, \u0442.1, \u041e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u2013 \u041c: \u0412\u0438\u043b\u044c\u044f\u043c\u0441, &#8212; 2017. &#8212; 720 C.<\/p>\n<p><strong>2.\u00a0<\/strong>N-\u0435 \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0437\u0430 O(log N) <a href=\"https:\/\/habr.com\/ru\/post\/148336\/\" rel=\"noopener noreferrer nofollow\">https:\/\/habr.com\/ru\/post\/148336\/<\/a> <\/p>\n<p><strong>3.\u00a0<\/strong>\u0420\u0430\u0441\u0447\u0435\u0442 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/skillfactory\/blog\/555914\/\" rel=\"noopener noreferrer nofollow\">https:\/\/habr.com\/ru\/company\/skillfactory\/blog\/555914\/<\/a> <\/p>\n<p><strong>4.\u00a0<\/strong>\u0421.\u041b\u0435\u043d\u0433 \u0410\u043b\u0433\u0435\u0431\u0440\u0430. \u041c.: \u041d\u0430\u0443\u043a\u0430, &#8212; 1965. &#8212; 431 C.<\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"v-portal\" style=\"display:none;\"><\/div>\n<\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/645829\/\"> https:\/\/habr.com\/ru\/post\/645829\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u041a\u0440\u0430\u0441\u0438\u0432\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u0434\u043b\u044f \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u0440\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c &#8212; \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u044b\u0439 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438. \u042d\u0442\u043e \u0434\u0435\u043b\u0430\u0435\u0442 \u0435\u0435 \u043d\u0435\u043f\u0440\u0438\u0433\u043e\u0434\u043d\u043e\u0439 \u0434\u043b\u044f \u0442\u043e\u0447\u043d\u043e\u0433\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. \u042d\u0442\u043e \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432\u043f\u043e\u043b\u043d\u0435 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c. \u041f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u0441\u043f\u043e\u0441\u043e\u0431, \u043a\u0430\u043a \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u0437\u043b\u043e\u0432\u0440\u0435\u0434\u043d\u043e\u0433\u043e \u043a\u043e\u0440\u043d\u044f \u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0443 \u0411\u0438\u043d\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u043d\u043e\u0439 \u0434\u043b\u044f \u0442\u043e\u0447\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439.<\/p>\n<details class=\"spoiler\">\n<summary>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e? \u0427\u0438\u0442\u0430\u0439\u0442\u0435 \u0434\u0430\u043b\u044c\u0448\u0435<\/summary>\n<div class=\"spoiler__content\">\n<p>\u041a\u0430\u043a \u0445\u043e\u0440\u043e\u0448\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u2013 \u044d\u0442\u043e \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c, \u043f\u0435\u0440\u0432\u044b\u0435 \u0434\u0432\u0430 \u0447\u043b\u0435\u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0432\u043d\u044b \u0435\u0434\u0438\u043d\u0438\u0446\u0435, \u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0440\u0430\u0432\u0435\u043d \u0441\u0443\u043c\u043c\u0435 \u0434\u0432\u0443\u0445 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445. \u0417\u0430 500 \u043b\u0435\u0442, \u043f\u0440\u043e\u0448\u0435\u0434\u0448\u0438\u0445 \u0441 \u043c\u043e\u043c\u0435\u043d\u0442\u0430 \u0432\u0432\u043e\u0434\u0430 \u044d\u0442\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043e\u0431\u0438\u0445\u043e\u0434, \u043e\u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u0437\u0443\u0447\u0435\u043d\u0430. \u041e\u0442\u043a\u0440\u044b\u0442\u043e \u043c\u043d\u043e\u0433\u043e \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0435\u0439\u0448\u0438\u0445 \u0444\u043e\u0440\u043c\u0443\u043b \u0441 \u0443\u0447\u0430\u0441\u0442\u0438\u0435\u043c \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. \u041d\u043e \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u201c\u043d\u0435\u043f\u0440\u0435\u0445\u043e\u0434\u044f\u0449\u0438\u0445\u201d \u0443\u0447\u0435\u0431\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u043e \u043c\u043d\u043e\u0433\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u0432: \u043e\u0442 \u043f\u0440\u044f\u043c\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u043d\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0435:<\/p>\n<p>\u0434\u043e \u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430, \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0433\u043e, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u043a\u043d\u0438\u0433\u0435 \u0414.\u041a\u043d\u0443\u0442\u0430 [1]. \u00a0\u0411\u043e\u043b\u044c\u0448\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u044d\u0442\u0438\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 (\u043a\u0440\u043e\u043c\u0435 \u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u041a\u043d\u0443\u0442\u0430) \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u044b \u043d\u0430 \u0440\u0435\u043a\u0443\u0440\u0440\u0435\u043d\u0442\u043d\u044b\u0445 \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443 Fn \u0432 \u043b\u0443\u0447\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0437\u0430\u00a0 \u0432\u0440\u0435\u043c\u044f O(n). \u041c\u0430\u0442\u0440\u0438\u0447\u043d\u044b\u0439 \u043c\u0435\u0442\u043e\u0434 \u041a\u043d\u0443\u0442\u0430 (\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0439 \u043c\u0430\u0442\u0440\u0438\u0447\u043d\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c) \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0437\u0430 \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0432\u0440\u0435\u043c\u044f [2].<\/p>\n<p>\u041e\u0441\u043e\u0431\u043d\u044f\u043a\u043e\u043c \u0432 \u044d\u0442\u043e\u043c \u0440\u044f\u0434\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u0442\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 (\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0430\u044f \u0435\u0449\u0435 \u041c\u0443\u0430\u0432\u0440\u0443) \u0438\u043c\u0435\u044e\u0449\u0430\u044f \u0432\u0438\u0434:<\/p>\n<p>\u042d\u0442\u0430 \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043d\u0430 \u043f\u0435\u0440\u0432\u044b\u0439 \u0432\u0437\u0433\u043b\u044f\u0434 \u043f\u0440\u0438\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439, \u043e\u0434\u043d\u0430\u043a\u043e \u043e\u043d\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u0440\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043f\u0440\u0438 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f\u0445 \u043c\u044b \u0432\u044b\u043d\u0443\u0436\u0434\u0435\u043d\u044b \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0442\u044c \u0432 \u0444\u043e\u0440\u043c\u0435 \u0447\u0438\u0441\u043b\u0430 \u0441 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u043e\u0439 (\u0442.\u0435. \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u0443\u044e \u043d\u0435\u043f\u0435\u0440\u0438\u043e\u0434\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0434\u0440\u043e\u0431\u044c \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439). <\/p>\n<p>\u0421\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0435 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043d\u0435 \u0431\u0443\u0434\u0443\u0442 \u0442\u043e\u0447\u043d\u044b\u043c\u0438; \u0432 \u043d\u0438\u0445 \u0432\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043f\u043e\u0433\u0440\u0435\u0448\u043d\u043e\u0441\u0442\u044c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f. \u041c\u043d\u0435 \u043e\u0434\u043d\u0430\u0436\u0434\u044b \u043f\u043e\u043f\u0430\u043b\u0430\u0441\u044c \u043d\u0430 \u0433\u043b\u0430\u0437\u0430 \u043f\u0443\u0431\u043b\u0438\u043a\u0430\u0446\u0438\u044f [3] \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0430\u0441\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u043e\u0447\u0435\u043d\u044c \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u043b\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438 \u0441\u0432\u0435\u0440\u0445\u0432\u044b\u0441\u043e\u043a\u043e\u0439 \u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e\u0441\u0442\u0438 (\u0441 \u0442\u0435\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0443\u0436\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u043f\u043e\u043b\u043d\u043e\u0441\u0442\u044c\u044e \u0443\u043c\u0435\u0441\u0442\u0438\u043b\u043e\u0441\u044c \u0432 \u043c\u0430\u043d\u0442\u0438\u0441\u0441\u0443).<\/p>\n<p>\u041c\u044b \u043f\u043e\u0439\u0434\u0435\u043c \u0441\u043e\u0432\u0441\u0435\u043c \u0434\u0440\u0443\u0433\u0438\u043c \u043f\u0443\u0442\u0435\u043c!<\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430, \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0447\u0438\u0441\u0435\u043b \u0432\u0438\u0434\u0430:<\/p>\n<p>\u043f\u0440\u0438 \u0446\u0435\u043b\u044b\u0445 a \u0438 b. \u041b\u0435\u0433\u043a\u043e \u0443\u0431\u0435\u0434\u0438\u0442\u044c\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u044d\u0442\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0430\u043b\u0433\u0435\u0431\u0440\u0430\u0438\u0447\u0435\u0441\u043a\u0438 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u043e \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f:<\/p>\n<p>\u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0438 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0443\u0442 \u043a\u043e\u043c\u043c\u0443\u0442\u0430\u0442\u0438\u0432\u043d\u044b\u043c\u0438, \u0447\u0442\u043e \u0442\u043e\u0436\u0435 \u043b\u0435\u0433\u043a\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u043d\u043e\u043b\u044c \u0438 \u0435\u0434\u0438\u043d\u0438\u0446\u0430 \u0445\u043e\u0440\u043e\u0448\u043e &#171;\u0432\u043f\u0438\u0441\u044b\u0432\u0430\u044e\u0442\u0441\u044f&#187; \u0432 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e:<\/p>\n<p>\u0412\u043f\u043e\u043b\u043d\u0435 \u043d\u0430\u0442\u0443\u0440\u0430\u043b\u044c\u043d\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442\u0441\u044f \u0438 \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435 \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u0447\u0438\u0441\u0435\u043b:<\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 (\u0440\u0430\u0437\u0443\u043c\u0435\u0435\u0442\u0441\u044f, \u043b\u0438\u0448\u044c \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \u043e\u0442\u043b\u0438\u0447\u0435\u043d \u043e\u0442 \u043d\u0443\u043b\u044f). \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u0430\u043a \u043a\u043e\u0440\u0435\u043d\u044c \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f:<\/p>\n<p>\u041f\u0443\u0441\u0442\u044c <\/p>\n<p>\u0422\u043e\u0433\u0434\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0435 \u0440\u0430\u0432\u0435\u0441\u0442\u0432\u043e \u044d\u043a\u0432\u0438\u0432\u0430\u043b\u0435\u043d\u0442\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443:<\/p>\n<p>\u0420\u0430\u0441\u043a\u0440\u044b\u0432\u0430\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u043b\u0435\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430, \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u0438\u0441\u0442\u0435\u043c\u0443 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 e \u0438 f:<\/p>\n<p>\u041e\u0442\u0441\u044e\u0434\u0430:<\/p>\n<p>\u0413\u043b\u0430\u0432\u043d\u044b\u0439 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c \u044d\u0442\u043e\u0439 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0440\u0430\u0432\u0435\u043d:<\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 a \u0438 b \u0437\u0434\u0435\u0441\u044c \u0446\u0435\u043b\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044f \u0432\u0441\u0435\u0433\u0434\u0430 \u043e\u0442\u043b\u0438\u0447\u043d\u043e \u043e\u0442 \u043d\u0443\u043b\u044f, \u0430 \u0437\u043d\u0430\u0447\u0438\u0442, \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0438\u043c\u0435\u0435\u0442 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438 \u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e. \u0412\u043f\u0440\u043e\u0447\u0435\u043c, \u043c\u044b \u0443\u0432\u043b\u0435\u043a\u043b\u0438\u0441\u044c. \u0414\u0435\u043b\u0435\u043d\u0438\u0435 \u043d\u0430\u043c \u043d\u0435 \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f.<\/p>\n<p>\u041c\u044b \u043f\u0440\u0438\u0448\u043b\u0438 \u043a \u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0441 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u044f \u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u043a\u043e\u043b\u044c\u0446\u043e [4].<\/p>\n<p><strong>\u0410 \u0442\u0435\u043f\u0435\u0440\u044c &#8212; \u0441\u0430\u043c\u043e\u0435 \u0433\u043b\u0430\u0432\u043d\u043e\u0435! \u0417\u0430\u0447\u0435\u043c \u043d\u0430\u043c \u043d\u0443\u0436\u0435\u043d \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438?<\/strong>  \u041d\u0438\u043a\u0442\u043e \u043d\u0435 \u043c\u0435\u0448\u0430\u0435\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443 \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u043f\u0430\u0440 (a,b), \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u043b\u043e\u0436\u0435\u043d\u0438\u0435, \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435 \u0438 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u0431\u0443\u0434\u0435\u0442 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430\u043c\u0438:<\/p>\n<p><strong>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043c\u043e\u0436\u043d\u043e \u201c\u0431\u043b\u0430\u0433\u043e\u043f\u043e\u043b\u0443\u0447\u043d\u043e \u0437\u0430\u0431\u044b\u0442\u044c\u201d \u043f\u0440\u043e \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438\u00a0 \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0440\u044f\u043c\u043e\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u0411\u0438\u043d\u0435.<\/strong> \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c \u0446\u0435\u043b\u044b\u043c (\u0438 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438 \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u043b\u0441\u044f), \u043d\u0443\u0436\u043d\u043e, \u0447\u0442\u043e\u0431\u044b \u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c \u0434\u0440\u043e\u0431\u0438 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u0411\u0438\u043d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u043b \u0441\u043e\u0431\u043e\u0439 \u0447\u0438\u0441\u043b\u043e \u0432\u0438\u0434\u0430:<\/p>\n<p>\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u044b \u043e\u0442\u043e\u0436\u0434\u0435\u0441\u0442\u0432\u0438\u043c \u0441 &#171;\u043e\u0431\u044b\u0447\u043d\u044b\u043c&#187; \u0447\u0438\u0441\u043b\u043e\u043c <\/p>\n<p>\u0414\u0435\u043b\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e &#171;\u043e\u0431\u044b\u0447\u043d\u043e\u0433\u043e&#187; \u0438\u0440\u0440\u0430\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043d\u0430 \u043a\u043e\u0440\u0435\u043d\u044c \u0438\u0437 \u043f\u044f\u0442\u0438 \u0438 \u0434\u0430\u0441\u0442 \u043d\u0430\u043c \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u0446\u0435\u043b\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0447\u0442\u043e \u0432 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f, \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c (\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u0443\u044e \u0432\u044b\u0448\u0435 \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0443 \u043f\u0430\u0440) \u0434\u0432\u0430 \u0431\u0438\u043d\u043e\u043c\u0430:<\/p>\n<p>\u0438 <\/p>\n<p>\u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0432\u044b\u0447\u0438\u0442\u0430\u043d\u0438\u0435. \u041d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0442\u0440\u0443\u0434\u0430 \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e\u0442 \u043f\u043e\u0434\u0445\u043e\u0434 \u043d\u0430 \u043b\u044e\u0431\u043e\u043c \u044f\u0437\u044b\u043a\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u041c\u044b \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u044d\u0442\u043e \u043d\u0430 \u041f\u0438\u0442\u043e\u043d\u0435 (\u043f\u0440\u0438\u0432\u043b\u0435\u043a\u0430\u0435\u0442 \u043d\u0435\u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u0430\u044f \u0440\u0430\u0437\u0440\u044f\u0434\u043d\u043e\u0441\u0442\u044c \u0446\u0435\u043b\u044b\u0445 \u0432 \u044d\u0442\u043e\u043c \u044f\u0437\u044b\u043a\u0435).<\/p>\n<pre><code class=\"python\">def prod_pairs(a,b):     return (a[0]*b[0]+5*a[1]*b[1],a[0]*b[1]+a[1]*b[0]) def sub_pairs(a,b):     return (a[0]-b[0],a[1]-b[1]) def pow_pair(a,n):     c=a     for _ in range(n-1):         c=prod_pairs(c,a)     return c def fib_bine(n):     x1=pow_pair((1,1),n)     x2=pow_pair((1,-1),n)     z=sub_pairs(x1,x2)     return z[1]\/\/(2**n) <\/code><\/pre>\n<p>\u041a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0438 \u0438\u0437\u043b\u0438\u0448\u043d\u0438 &#8212; \u0432\u0441\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e. \u0421\u0440\u0430\u0437\u0443 \u0436\u0435 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432\u043e\u043f\u0440\u043e\u0441, \u0430 \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u044d\u0442\u043e\u0442 \u043a\u043e\u0434? \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u0447\u0442\u043e &#171;\u0443\u0437\u043a\u0438\u043c \u043c\u0435\u0441\u0442\u043e\u043c&#187; \u0437\u0434\u0435\u0441\u044c \u044f\u0432\u043b\u044f\u0442\u0441\u044f \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u043f\u0430\u0440\u044b \u0432 \u0446\u0435\u043b\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c. \u0414\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0438\u043c\u0435\u0435\u0442\u0441\u044f \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0439 \u043f\u0440\u0438\u0435\u043c &#8212; \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0432 \u0441\u0442\u0435\u043f\u0435\u043d\u044c (\u044d\u0442\u0438\u043c \u0436\u0435 \u043f\u0440\u0438\u0435\u043c\u043e\u043c \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0441\u044f \u0438 \u0430\u0432\u0442\u043e\u0440 [2]). \u0418\u0434\u0435\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f x<sup>n<\/sup> \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u0446\u0435\u043f\u043e\u0447\u043a\u0430 x -> x<sup>2<\/sup> -> x<sup>4<\/sup> ->\u2026->x<sup>2k<\/sup> \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 2<sup>k<\/sup>&lt;=n, \u0430 \u0437\u0430\u0442\u0435\u043c \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f x<sup>(n-2k)<\/sup>.   <\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0431\u044b\u0441\u0442\u0440\u043e\u0435 \u0432\u043e\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u044f \u043f\u0430\u0440\u044b \u0432 \u0446\u0435\u043b\u0443\u044e \u0441\u0442\u0435\u043f\u0435\u043d\u044c:<\/p>\n<pre><code class=\"python\">def pow_pair(a,n): if (n==1):     return a c=copy(a) k=1 while k*2&lt;=n:     if k&lt;=n:        c=prod_pairs(c,c)        k=k*2     p=n-k     if p>=1:        tmp=pow_pair(a,p)        return prod_pairs(tmp,c)     else:        return c <\/code><\/pre>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u0435\u043c\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0437\u0430 \u0432\u0440\u0435\u043c\u044f, \u0431\u043b\u0438\u0437\u043a\u043e\u0435 \u043a \u043b\u043e\u0433\u0430\u0440\u0438\u0444\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 \u043f\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u0411\u0438\u043d\u0435 \u0438 \u0431\u0435\u0437 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0430\u0440\u0438\u0444\u043c\u0435\u0442\u0438\u043a\u0438 \u0441 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u043e\u0439. \u0414\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u0433\u043e \u043c\u0435\u0442\u043e\u0434\u0430 \u0441 \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438, \u043d\u0430\u043f\u0438\u0441\u0430\u043d \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0439 \u043a\u043e\u0434:<\/p>\n<pre><code class=\"python\">def fib_ite(n):     c,p=0,1     for _ in range(n):         c,p=c+p,c     return c <\/code><\/pre>\n<p>\u0418 \u0447\u0442\u043e \u0436\u0435? \u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u0443\u044e \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443 \u043a\u043e\u0434\u0430 fib_ite, \u0444\u0443\u043d\u043a\u0446\u0438\u044f fib_bine \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043b\u0443\u0447\u0448\u0438\u0435 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b. \u0422\u0430\u043a, \u043d\u0430 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u0435 \u0430\u0432\u0442\u043e\u0440\u0430 \u0447\u0435\u0442\u044b\u0440\u0435\u0445\u0441\u043e\u0442\u0442\u044b\u0441\u044f\u0447\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u043f\u043e \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u043c\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u043c\u0435\u0440\u043d\u043e \u0437\u0430 2 \u0441\u0435\u043a, \u0430 \u043f\u0440\u044f\u043c\u044b\u043c\u0438 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u2013 \u0437\u0430 27 \u0441\u0435\u043a.   \u041d\u0430 \u043f\u0440\u0438\u043b\u0430\u0433\u0430\u0435\u043c\u043e\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u0440\u0430\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u044b \u0442\u0435\u0441\u0442\u043e\u0432:<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u041f\u043e \u0433\u043e\u0440\u0438\u0437\u043e\u043d\u0442\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u0441\u0438 \u043e\u0442\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u043e\u043c\u0435\u0440 \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438, \u043f\u043e \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u044c\u043d\u043e\u0439 \u2013 \u0432\u0440\u0435\u043c\u044f \u0432 \u0441\u0435\u043a\u0443\u043d\u0434\u0430\u0445. <\/p>\n<p>\u041f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0430 \u0411\u0438\u043d\u0435 \u0432\u043f\u043e\u043b\u043d\u0435 \u043f\u0440\u0438\u0433\u043e\u0434\u043d\u0430 \u0434\u043b\u044f \u0431\u044b\u0441\u0442\u0440\u044b\u0445 \u0438 \u0442\u043e\u0447\u043d\u044b\u0445 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u0447\u0438\u0441\u0435\u043b \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438.<\/p>\n<p>\u0421\u043f\u0430\u0441\u0438\u0431\u043e, \u0447\u0442\u043e \u0434\u043e\u0447\u0438\u0442\u0430\u043b\u0438 \u0434\u043e \u043a\u043e\u043d\u0446\u0430, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0438\u0441\u043a\u0440\u0435\u043d\u043d\u0435\u0435 \u0441\u043f\u0430\u0441\u0438\u0431\u043e \u0430\u0432\u0442\u043e\u0440\u0430\u043c, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u044f \u0441\u0441\u044b\u043b\u0430\u043b\u0441\u044f \u0432 \u044d\u0442\u043e\u0439 \u0437\u0430\u043c\u0435\u0442\u043a\u0435:<\/p>\n<p><strong>1.\u00a0<\/strong>\u0414.\u041a\u043d\u0443\u0442 \u0418\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0430 \u042d\u0412\u041c, \u0442.1, \u041e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u2013 \u041c: \u0412\u0438\u043b\u044c\u044f\u043c\u0441, &#8212; 2017. &#8212; 720 C.<\/p>\n<p><strong>2.\u00a0<\/strong>N-\u0435 \u0447\u0438\u0441\u043b\u043e \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 \u0437\u0430 O(log N) <a href=\"https:\/\/habr.com\/ru\/post\/148336\/\" rel=\"noopener noreferrer nofollow\">https:\/\/habr.com\/ru\/post\/148336\/<\/a> <\/p>\n<p><strong>3.\u00a0<\/strong>\u0420\u0430\u0441\u0447\u0435\u0442 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0424\u0438\u0431\u043e\u043d\u0430\u0447\u0447\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/skillfactory\/blog\/555914\/\" rel=\"noopener noreferrer nofollow\">https:\/\/habr.com\/ru\/company\/skillfactory\/blog\/555914\/<\/a> <\/p>\n<p><strong>4.\u00a0<\/strong>\u0421.\u041b\u0435\u043d\u0433 \u0410\u043b\u0433\u0435\u0431\u0440\u0430. \u041c.: \u041d\u0430\u0443\u043a\u0430, &#8212; 1965. &#8212; 431 C.<\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"v-portal\" style=\"display:none;\"><\/div>\n<\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/645829\/\"> https:\/\/habr.com\/ru\/post\/645829\/<\/a><br \/><\/br><\/br><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-328076","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/328076","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=328076"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/328076\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=328076"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=328076"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=328076"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}