Excel и алгоритми над цели числа

сред тях алгоритъмът на Евклид, решението на диофантовите уравнения, намирането на число по неговите остатъци.

Обикновено за решаване на такива проблеми се използва един от следните подходи:

Приложете алгоритъма на език за алгоритмично програмиране, който познавате;
Решете проблема си ръчно, на лист хартия.

В същото време почти всеки гимназист или студент е запознат с една от най-лесните за използване електронни таблици - Excel. В допълнение към удобните методи за работа с таблични данни, електронната таблица улеснява прилагането на много алгоритми върху цели числа без използване на програмиране.

Нека ви покажем как можете да използвате електронни таблици за решаване на тези проблеми и да получите правилния резултат за няколко минути.1. Методи за намиране на най-голям общ делител (gcd) на набор от числа.1.1. Алгоритъм на Евклид с изваждания

Алгоритъмът на Евклид ви позволява да намерите най-големия общ делител на числата, да решавате линейни уравнения в цели числа. Използва се и за бързо съкращаване на дроби (намерете НОД на числителя и знаменателя, след което разделете числителя и знаменателя на НОД).

Алгоритъмът за изваждане на Евклид се основава на следния факт: ако a>b, тогава gcd(a,b)=gcd(a-b,b). Сега нека вземем вместо двойка числа (a,b) двойка числа (a-b,b) и приложим правилото отново. След прилагане на правилото определен брой пъти, двете числа ще станат равни - това е НОД(a,b).

За няколко числа алгоритъмът може да се формулира по следния начин. Всякакви две ненулеви числа се избират от набора от естествени числа и по-голямото от тях (или което и да е, ако са равни) се заменя с разликата на тези числа. Това се повтаря, докато остане едно ненулево число. Това ще бъде GCD на оригиналния комплект.

^ Внедряване в Excel:

За да приложите този алгоритъм в Excel, трябва да създадете таблица със следното съдържание.

1. Присвояваме произволни две съседни клетки на оригиналните числа. Нека това са клетки A1 и B1. Например, искаме да намерим НОД на числата 10 и 5. Нека поставим съответно числата 5 и 3 в тях за теста.

2. С помощта на инструмента за създаване на формули или "ръчно" за клетка A2 задайте формулата "=IF(A1>=B1;A1-B1;A1)".

3. Изберете и копирайте клетка A2 в клетка B2.

4. Редактирайте клетка B2. Във формулата заменете знака за по-голямо или равно с по-голямо, клетка B1 с A1 и A1 с B1. Тогава ще се окаже: "=IF(B1>A1;B1-A1;B1)".

5. Изберете клетки A2: B2. И ще ги копираме няколко пъти, всеки път слизайки един ред надолу, докато едно от числата в следващия ред стане нула. Ненулево число в последния ред ще бъде НОД.1.2. Алгоритъм на Евклид с деление

Алгоритъмът за деление на Евклид е по-бърз от алгоритъма за изваждане. Единственият му недостатък е използването на по-"сложна" операция деление с остатък вместо изваждане.

Нека вземем две ненулеви числа от множеството и заменим по-голямото от тях (или което и да е в случай на равенство) с остатъка от делението на по-малкото. Освен това ще продължим по същия начин, както в случай 1.1.

Реализация на Excel:

1. Отново, нека присвоим произволни две съседни клетки на оригиналните числа. Нека са клетки D1 и E1. Нека към тях за теста добавим съответно числата 123 и 23.

2. Въведете формулата "=MOD(D1;E1)" в клетка D2.

3. Изберете и копирайте клетка D2 в клетка E2.

4. Редактирайте клетка E2. Разменете клетките E1 и D1 във формулата. Ще се окаже "= OSTAT (E1; D1)".

5. Изберете D2:E2 и копирайте, докато се получи нула в една от клетките, ненулев елемент ще бъдерешение.^ 2. Разширен алгоритъм на Евклид

Като пример за проблем, решен с помощта на разширения Евклидов алгоритъм, може да се даде следното. Има няколко кофи с различна вместимост. Разрешено е да се добавя или загребва вода от бурето с тези кофи. Отначало варелът е празен. Необходимо е да налеете 1 литър вода в цевта, като имате на разположение кофи с вместимост 17 и 45 литра. Как мога да направя това? Как може това да стане възможно най-скоро (за възможно най-малко кръвопреливания)?

Идеята на алгоритъма е в “координатното” представяне на цели числа, с които се извършват операциите на обичайния алгоритъм на Евклид: числотоaсе представя от множеството (1;0), а числотоbсе представя от множеството (0;1). След това, акоa, когато се дели наb, дава остатъкаrи частнотоq, тогава остатъкът в координатна форма ще бъде изчислен по следния начин: тъй катоa=bq+rтогаваr=a-bq=(1;0)-(0;1)q=(1 ;- q). Като цяло, ако дивидентът има координати (x1,y1) и делителя (x2,y2), тогава остатъкът ще бъде r=(x1;y1)-q(x2;y2)=(x1-qx2;y1-qy2).

Реализация на Excel:

1. Да вземем две клетки, например A7 и A8 за коефициентите на уравнението. Колони B и C ще бъдат използвани за решението. Например 123=1*123+0*23, следователно B7=1 и C7=0. 23=0*123+1*23.

2. Въведете формулата "=MOD(A7;A8)" в клетка A9.

3. Въведете формулата "=ЦЯЛО ЧИСЛО (A7/A8)" в клетка D9.

4. Въведете формулата "=B7-D9*B8" в клетка B9.

5. Копирайте клетка B9 в клетка C9. Коригирайте във формула E9 до D9. Получавате "=C7-D9*C8".

6. Копирайте ред 9 в ред 10, след това копирайте в ред 11 и така нататък, докато първата колона стане 0.

7. Разглеждаме предишния ред, там коефициентите 3 и -16 са срещу 1. Следователно, 1=3*123-16*23, получихме решението.^ 3.Намиране на число по множеството на неговите остатъци.

На практика теоремата се прилага най-често при работа с "големи" числа. Често е по-удобно да се използва не десетичното представяне на "голямо" число, а така нареченият китайски код, който е набор от остатъци от разделяне на дадено число на числа, които образуват така наречената система от модули. Модулите трябва да са взаимно прости, за да възстановят еднозначно оригиналното число от набор от остатъци.

В този случай операцията за добавяне на "големи числа" се свежда до добавяне на съответните остатъци по модул някои. Операцията на умножение на "големи числа" води до умножение на остатъци по модул някои. Операциите за изваждане и деление се извършват по подобен начин.

Легитимността на такива операции се доказва от китайската теорема за остатъка. Той също така дава метод, който позволява, въз основа на получения краен набор, да се получи отговорът в познатата ни форма.

Китайска теорема за остатък

Постановка на проблема: има набор от остатъци от деление на неизвестно число на числа от система от взаимнопрости модули. Трябва да намерим неизвестното число.

Ако са дадени естествени, двойки взаимно прости числа m1…mn и цели числа r1…rn, така че за всяко i, 0≤ri ^ Реализация в Excel:

Например, нека вземем взаимнопрости модули. Нека остатъците след разделянето на тези модули са съответно . Нека създадем таблица, чийто изглед е показан на фиг. 1:

В брой 6 от 2001 г. статията на С. С. Лавров "Продължени дроби" описва алгоритми за работа с непрекъснати дроби. Всички те могат да бъдат реализирани и с помощта на Excel. Опитай! Успех!