Теорема Ламме

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «ВГТУ»)

Инженерно-экономический  факультет

Кафедра управления персоналом

Специальность «Бизнес-информатика»

 

КУРСОВОЙ ПРОЕКТ

по дисциплине «Теоретические основы информатики»

Тема работы

 

 

Пояснительная записка

Разработал                                     

          Руководитель                                

          Нормоконтроль провел                

          Защищена______________            Оценка ______________

 

Воронеж 2013

Задача №4

Даны 2 целых числа: и , из которых >. Последовательным делением ( на , на первый остаток и т.д.) находится наибольший общий делитель.

Требуется указать число, которого не превзойдет число операций последовательных делений, а при некоторых и будет ему равно.

Решение.

Обозначая частное от деления на через , а остаток через , частное от деления на через d2, а остаток через , и т.д. получим систему равенств:

=+,

=+,

=+,

…   …   …  …

=+,

=+,

=

Совершенно очевидно, что  наибольшее число операций m будет в том случае, когда все частные ,,,..,, будут единицами. Введем поэтому числа ,,,.., при условиях:

=0,

=1,

=1,

=2,

…  …  …

=+

Совершенно очевидно, что  при этом должен выполняться неравенства:

=,

 ≥ ,

 ≥ ,

 ≥ ,

          …  …  …

 ≥ ,

 ≥ ,

 ≥ ,

Последнее из этих неравенств может служить для определения числа m, если только будет известно выражение как функция m. Поэтому надо найти .

Решим для этого уравнение:

=+

При начальных условиях =0, =1.

Характеристическое уравнение  для него будет:

=t+1 с корнями

           = ,

          = .

           Общее решение нашего уравнения будет иметь вид:

=(+(

         Константы мы найдем из условий =0, =1. Действительно, мы будем иметь:

        =+=0, =+=1

        или

        +=0

       +2,

       Откуда:

       =, = -

       Теперь  мы можем написать окончательное  выражение для :

       = [() - ()]

       Нетрудно  увидеть, что если >, то > и n>m. Поэтому, если найти такое     n, что будет больше , а   будет меньше , то это n и будет совпадать с нашим m.

  1,

то из неравенства 

m= =

p – число цифр

 

 

Все это носит название теоремы Ламе.