Неформальное определение алгоритма. Примеры

Неформальное определение алгоритма таково: алгоритм – это совокупность определенных правил, позволяющих решить задачу.

Примеры:

1. при .

2. , ;

Решение:

; , ;

.

Алгоритм Евклида призван решить следующую задачу. Имеются отрезки , найти отрезок , который бы укладывался целое (конечное) количество раз между и :

Решение. Пусть . Рассмотрим и .В зависимости от их величины, отложим либо в , либо в .

Окончание алгоритма: . Искомым отрезком является отрезок .

Всегда ли этот алгоритм конечен? Ответ – нет.

Отрезки называются несоизмеримыми, если алгоритм Евклида не останавливается. Евклид доказал, что сторона квадрата и его диагональ несоизмеримы.

Докажем это:

, ;

;

.

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

Вариантом алгоритма Евклида является алгоритм нахождения наибольшего общего делителя двух целых чисел:

, ;

; ; ; ; .

Теория алгоритмов в математике рассматривается как формальная теория.

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

Контрольное задание

С помощью алгоритма Евклида решить две задачи: сократить дробь; сократить произведение дробей (табл. 3.1).

Таблица 3.1

Варианты задания

Номер варианта	Сократить дробь	Сократить произведение дробей
	52725971 / 254437301	77161633/604120273 и 207134329/368859367
	58552849 / 326769323	15525971/68110201 и 68449807/90174017
	30071387 / 170007581	176933873/101583107 и 81925829/123110629
	17850821 / 38830369	104279849/89034301 и 34291541/258238081
	160313459 / 239773111	4613201/282998921 и 249201371/20641549
	111246313 / 374840971	17408179/158527297 и 51875869/56038343
	46187333 / 232771321	11663569/4737323 и 2670827/33630829
	94062767 / 188748817	327488407/916892029 и 108797989/205615681
	57609763 / 96401821	193609151/255319723 и 129986167/56572639
	77718737 / 163343251	149118941/73734071 и 102595453/40453379
	22735831 / 304181989	107842741/181624727 и 89581363/195091283

Окончание табл. 3.1

Номер варианта	Сократить дробь	Сократить произведение дробей
	189893387 / 317475121	34311449/94440121 и 24555577/114690461
	189851489 / 337434893	22481159/251494459 и 728534899/26604341
	11394751 / 533138153	3149219/47584891 и 142852999/10422001
	164866963 / 183307393	30989663/8886803 и 92316083/70098389
	7755763/22201229	273025681/326332781 и 60182887/142699223
	5232167/46446797	50707091/475916849 и 96644047/32431037
	559565177/564351707	100256467/560734051 и 396003901/71545069
	20938363/461350159	48243703/198544123 и 6291707/60044321
	19997903/61970549	654536191/37218179 и 20170259/96022133
	34458659/45917203	167406073/147293749 и 194806331/29949587
	130976849/208084271	127596197/21055403 и 45447131/23784667
	87918773/206463031	97471589/173317099 и 51121673/97244647
	151832357/311301629	342946861/19288891 и 53976619/190839013

Дата добавления: 2015-06-04