Программирование: теоремы и задачи

Description

Книга содержит задачи по программированию различной трудности. Большинство задач приводятся с решениями. Цель книги | научить основным методам построения корректных и быстрых алгоритмов. Для учителей информатики, старшеклассников, студентов младших курсов высших учебных заведений. Пособие может быть использовано на кружковых и факультативных занятиях в общеобразовательных учреждениях, в школах с углублённым изучением математики и информатики, а также в иных целях, не противоречащих законодательству РФ. Предыдущее издание книги вышло в 2014 г. ðÅÒÅÍÅÎÎÙÅ, ×ÙÒÁÖÅÎÉÑ, ÐÒÉÓ×ÁÉ×ÁÎÉÑ úÁÄÁÞÉ ÂÅÚ ÍÁÓÓÉ×Ï× íÁÓÓÉ×Ù éÎÄÕËÔÉ×ÎÙÅ ÆÕÎËÃÉÉ (ÐÏ á.ç.ëÕÛÎÉÒÅÎËÏ) ðÏÒÏÖÄÅÎÉÅ ËÏÍÂÉÎÁÔÏÒÎÙÈ ÏÂßÅËÔÏ× òÁÚÍÅÝÅÎÉÑ Ó ÐÏ×ÔÏÒÅÎÉÑÍÉ ðÅÒÅÓÔÁÎÏ×ËÉ ðÏÄÍÎÏÖÅÓÔ×Á òÁÚÂÉÅÎÉÑ ëÏÄÙ çÒÅÑ É ÁÎÁÌÏÇÉÞÎÙÅ ÚÁÄÁÞÉ îÅÓËÏÌØËÏ ÚÁÍÅÞÁÎÉÊ ðÏÄÓÞ£Ô ËÏÌÉÞÅÓÔ× ïÂÈÏÄ ÄÅÒÅ×Á. ðÅÒÅÂÏÒ Ó ×ÏÚ×ÒÁÔÁÍÉ æÅÒÚÉ, ÎÅ ÂØÀÝÉÅ ÄÒÕÇ ÄÒÕÇÁ: ÏÂÈÏÄ ÄÅÒÅ×Á ÐÏÚÉÃÉÊ ïÂÈÏÄ ÄÅÒÅ×Á × ÄÒÕÇÉÈ ÚÁÄÁÞÁÈ óÏÒÔÉÒÏ×ËÁ ë×ÁÄÒÁÔÉÞÎÙÅ ÁÌÇÏÒÉÔÍÙ áÌÇÏÒÉÔÍÙ ÐÏÒÑÄËÁ nlogn ðÒÉÍÅÎÅÎÉÑ ÓÏÒÔÉÒÏ×ËÉ îÉÖÎÉÅ ÏÃÅÎËÉ ÄÌÑ ÞÉÓÌÁ ÓÒÁ×ÎÅÎÉÊ ÐÒÉ ÓÏÒÔÉÒÏ×ËÅ òÏÄÓÔ×ÅÎÎÙÅ ÓÏÒÔÉÒÏ×ËÅ ÚÁÄÁÞÉ ëÏÎÅÞÎÙÅ Á×ÔÏÍÁÔÙ É ÏÂÒÁÂÏÔËÁ ÔÅËÓÔÏ× óÏÓÔÁ×ÎÙÅ ÓÉÍ×ÏÌÙ, ËÏÍÍÅÎÔÁÒÉÉ É Ô.Ð. ÷×ÏÄ ÞÉÓÅÌ ôÉÐÙ ÄÁÎÎÙÈ óÔÅËÉ ïÞÅÒÅÄÉ íÎÏÖÅÓÔ×Á òÁÚÎÙÅ ÚÁÄÁÞÉ òÅËÕÒÓÉÑ ðÒÉÍÅÒÙ ÒÅËÕÒÓÉ×ÎÙÈ ÐÒÏÇÒÁÍÍ òÅËÕÒÓÉ×ÎÁÑ ÏÂÒÁÂÏÔËÁ ÄÅÒÅ×ØÅ× ðÏÒÏÖÄÅÎÉÅ ËÏÍÂÉÎÁÔÏÒÎÙÈ ÏÂßÅËÔÏ×, ÐÅÒÅÂÏÒ äÒÕÇÉÅ ÐÒÉÍÅÎÅÎÉÑ ÒÅËÕÒÓÉÉ ëÁË ÏÂÏÊÔÉÓØ ÂÅÚ ÒÅËÕÒÓÉÉ ôÁÂÌÉÃÁ ÚÎÁÞÅÎÉÊ (ÄÉÎÁÍÉÞÅÓËÏÅ ÐÒÏÇÒÁÍÍÉÒÏ×ÁÎÉÅ) óÔÅË ÏÔÌÏÖÅÎÎÙÈ ÚÁÄÁÎÉÊ âÏÌÅÅ ÓÌÏÖÎÙÅ ÓÌÕÞÁÉ ÒÅËÕÒÓÉÉ òÁÚÎÙÅ ÁÌÇÏÒÉÔÍÙ ÎÁ ÇÒÁÆÁÈ ëÒÁÔÞÁÊÛÉÅ ÐÕÔÉ ó×ÑÚÎÙÅ ËÏÍÐÏÎÅÎÔÙ, ÐÏÉÓË × ÇÌÕÂÉÎÕ É ÛÉÒÉÎÕ óÅÔÉ, ÐÏÔÏËÉ É ÒÁÚÒÅÚÙ óÏÐÏÓÔÁ×ÌÅÎÉÅ Ó ÏÂÒÁÚÃÏÍ ðÒÏÓÔÅÊÛÉÊ ÐÒÉÍÅÒ ðÏ×ÔÏÒÅÎÉÑ × ÏÂÒÁÚÃÅ — ÉÓÔÏÞÎÉËÐÒÏÂÌÅÍ ÷ÓÐÏÍÏÇÁÔÅÌØÎÙÅ ÕÔ×ÅÒÖÄÅÎÉÑ áÌÇÏÒÉÔÍ ëÎÕÔÁ–íÏÒÒÉÓÁ–ðÒÁÔÔÁ áÌÇÏÒÉÔÍ âÏÊÅÒÁ–íÕÒÁ áÌÇÏÒÉÔÍ òÁÂÉÎÁ âÏÌÅÅ ÓÌÏÖÎÙÅ ÏÂÒÁÚÃÙ É Á×ÔÏÍÁÔÙ óÕÆÆÉËÓÎÙÅ ÄÅÒÅ×ØÑ áÎÁÌÉÚ ÉÇÒ ðÒÉÍÅÒÙ ÉÇÒ ãÅÎÁ ÉÇÒÙ ÷ÙÞÉÓÌÅÎÉÅ ÃÅÎÙ: ÐÏÌÎÙÊ ÏÂÈÏÄ áÌØÆÁ-ÂÅÔÁ-ÐÒÏÃÅÄÕÒÁ òÅÔÒÏÓÐÅËÔÉ×ÎÙÊ ÁÎÁÌÉÚ ïÐÔÉÍÁÌØÎÏÅ ËÏÄÉÒÏ×ÁÎÉÅ ëÏÄÙ îÅÒÁ×ÅÎÓÔ×Ï ëÒÁÆÔÁ–íÁËÍÉÌÌÁÎÁ ëÏÄ èÁÆÆÍÁÎÁ ëÏÄ ûÅÎÎÏÎÁ–æÁÎÏ ðÒÅÄÓÔÁ×ÌÅÎÉÅ ÍÎÏÖÅÓÔ×. èÅÛÉÒÏ×ÁÎÉÅ èÅÛÉÒÏ×ÁÎÉÅ Ó ÏÔËÒÙÔÏÊ ÁÄÒÅÓÁÃÉÅÊ èÅÛÉÒÏ×ÁÎÉÅ ÓÏ ÓÐÉÓËÁÍÉ äÅÒÅ×ØÑ. óÂÁÌÁÎÓÉÒÏ×ÁÎÎÙÅ ÄÅÒÅ×ØÑ ðÒÅÄÓÔÁ×ÌÅÎÉÅ ÍÎÏÖÅÓÔ× Ó ÐÏÍÏÝØÀ ÄÅÒÅ×ØÅ× óÂÁÌÁÎÓÉÒÏ×ÁÎÎÙÅ ÄÅÒÅ×ØÑ ëÏÎÔÅËÓÔÎÏ-Ó×ÏÂÏÄÎÙÅ ÇÒÁÍÍÁÔÉËÉ ïÂÝÉÊ ÁÌÇÏÒÉÔÍ ÒÁÚÂÏÒÁ íÅÔÏÄ ÒÅËÕÒÓÉ×ÎÏÇÏ ÓÐÕÓËÁ áÌÇÏÒÉÔÍ ÒÁÚÂÏÒÁ ÄÌÑ LL(1)-ÇÒÁÍÍÁÔÉË óÉÎÔÁËÓÉÞÅÓËÉÊ ÒÁÚÂÏÒ ÓÌÅ×Á ÎÁÐÒÁ×Ï (LR) LR-ÐÒÏÃÅÓÓÙ LR(0)-ÇÒÁÍÍÁÔÉËÉ SLR(1)-ÇÒÁÍÍÁÔÉËÉ LR(1)-ÇÒÁÍÍÁÔÉËÉ, LALR(1)-ÇÒÁÍÍÁÔÉËÉ ïÂÝÉÅ ÚÁÍÅÞÁÎÉÑ Ï ÒÁÚÎÙÈ ÍÅÔÏÄÁÈ ÒÁÚÂÏÒÁ ëÎÉÇÉ ÄÌÑ ÞÔÅÎÉÑ ðÒÅÄÍÅÔÎÙÊ ÕËÁÚÁÔÅÌØ õËÁÚÁÔÅÌØ ÉÍ£Î