Екип на Learn2Code - 30.05.2020 - Образование
В предишния блог се занимавахме с прости числа. Показахме пример на програма, която разпознава дали въведеното число е просто число или не. Днес бих искал да ви покажа, като използвам конкретен пример, как подзаглавието на този блог го решава и по този начин ще открия простите числа на определен интервал от естествени числа, докато горната граница на интервала ще бъде въведена от потребител. Долната граница на интервала ще бъде 0, което, разбира се, не е просто число, защото простото число се дели на 1 и само по себе си. От това следва, че 0, макар и делимо на 1, не се дели на 0, тъй като изразът 0/0 не е дефиниран. Въпреки че човек би си помислил, че резултатът може да бъде равен на числото 1, това не е така. Нулата просто не може да раздели никой израз.
Нека да отидем малко по-напред сега. В последния блог заключих, че дори 1 не е просто число, защото се дели на 1 и само по себе си, което отново е числото 1. И 1 и 1, няма два различни фактора.
Условието, което изключва 0 и 1, не са прости числа, разбира се е разгледано в моята програма. Но какво да кажем за други числа, които са на интервала, чиято горна граница е въведена от потребителя. Един прост алгоритъм, наречен Eratosthene sito ще ни даде директен отговор на този въпрос.
Ератостен от Киренея бил, наред с други неща, гръцки математик, работил в древна Александрия около 280 години. преди Христа. В допълнение към изчисляването на земния периметър, той също така дефинира алгоритъм, който внедрих за вас в езика за програмиране на по-високо ниво C++.
Преди да анализираме подробно програма, написана на C ++, показваме алгоритъма на следните естествени числа: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19.
Така че имаме последователност, която е определена в началото с числото 0 включително и в края с числото 20, което вече е извън интервала на последователността. И това е точно горната граница, която беше спомената по-горе.
Ще поставим тази последователност в едноредова таблица, която в моята програма ще бъде представена от вектор на цели числа (int vector).
Като забележка ще използваме библиотечния клас STL, който е вектор. Векторът е обект, който е по-добре манипулиран от масив. Ето защо тази статия е предназначена за онези читатели, които поне донякъде са запознати с въпроса за векторите. За тези, които не са запознати с векторните проблеми, препоръчвам първо да проучите типа size_t, векторния клас и метода член на векторния push_back () клас. След това с усърдие тези читатели могат да се впуснат в този блог.
Но да се върнем към дефинирания ни проблем. Така че нека имаме споменатата последователност:
В тази таблица в синьо посочваме факта, че 0 и 1 не са прости числа:
Следователно няма да се връщаме към индексите, на които са разположени числата 0 и 1. Нека да разгледаме числото 2. Знаем, че това число е най-малкото просто число в този интервал, което е основното условие за решаване на подзаглавието на този блог. Ще тестваме останалите елементи (числа) на последователността със сито Eratosten - тоест сега ще премахнем кратни на числото 2. Тъй като числото 3 не е кратно на числото 2, то ще премине през ситото Eratosten . Така че нека да запишем кратните на числото 2 в червено в таблицата.
Виждаме, че в една стъпка алгоритъмът (сито Ератостен) премахна числата 4, 6, 8, 10, 12, 14, 16 и 18. В същото време няма да се върнем по никакъв начин към индекса на числото 2. От предишната таблица също е очевидно, че числото 3 е просто число. Нека сега премахнем кратните му от таблицата и да отбележим този факт в зелено.
В следващата стъпка алгоритъмът премахна числата 6, 9, 12, 15, 18, които не са прости числа. Да, ние също маркирахме в зелено някои числа, които бяха премахнати в предишната стъпка с кратно на 2. Това обаче не променя факта, че тази стъпка премахна други числа от последователността, които са числа: 9 и 15. След изпълнение споменатата стъпка виждаме, че числото 5 остава маркирано в жълто. Следователно числото 5 е просто число, тъй като е преминало през сито на Ератостен. Ако премахнем кратните на числото 5 в следващата стъпка, ще открием, че числата 10 и 15 вече са премахнати от кратно на друго число. И така, кога ще свърши алгоритъмът? Това ще бъде така, докато всъщност стигнем до числото 19. Числото 19 вече няма задачата да премахва кратно, защото зад тях в нашата таблица няма нищо. Постигането на неговия индекс чрез определена променлива за взаимодействие е условие за края на алгоритъма, въпреки че нищо не се променя в състоянието на прости числа или премахнати числа.
Нека сега изберем всички числа, маркирани в жълто от нашата таблица:
Ще ни останат числа, които със сигурност са прости числа. Така стигнахме до резултата от нашия алгоритъм, които са числата 2, 3, 5, 7, 11, 13, 17 и 19. За да проверите, можете да сравните тези числа с простите числа, дадени в други източници, но ще определено да получите същия резултат.
Нека сега да разгледаме подробно следния изходен код, написан на C ++, който е изпълнение на словесното обяснение на алгоритъма, споменат по-горе. Езикът C ++ ни предлага други възможности как да направим изчислението по-ефективно. Те са напр. скача в програмата, която можем да изпълним с помощта на ключовите думи прекъсване и продължаване. Но повече за това по-късно. Нека се подредим от първия ред.
На ред 1 имаме заглавния файл iostream.h, добавен от директивата на препроцесора. Това означава, че съдържанието на файла iostream.h се вмъква в този ред. По същия начин на редове 2 и 3 вмъкваме заглавните файлове vector.h и string.h със същата директива. Ред 4 декларира, че ще използваме std пространство от имена в целия изходен код, който съставлява един файл, така че не е нужно да го извикваме изрично в основната функция, когато се нуждаем от клас или обект от него. Пример може да бъде обект cin или cout. На ред 6 дефинираме функцията main и след това на линия 7 започва нейното тяло. На ред 8 декларираме променлива от интегрален тип, по-специално char с идентификатора на променливата c_end. Тази променлива представлява един знак, който решава дали да прекрати външния цикъл след изпълнение на собствения алгоритъм на Eratosten. Ето защо, на ред 89, потребителят е подканен да натисне клавиша a или n. Ако потисне n, програмата продължава със следващия цикъл на цикъл while. Ако се натисне друг клавиш, програмата приключва.
Ред 9 дефинира нов екземпляр на низ от клас с идентификатор sz, който се инициализира до празна стойност.
След тази инициализация, ред 10 показва декларацията на променливата iSZ за типа int без допълнителна инициализация.
На ред 11 декларираме променлива от тип bool, която ще съхранява информация в програмата, дали потребителят е отговорил на подкана на програмата чрез въвеждане на валидна стойност (т.е. целочислена стойност), която ще се съхранява в променливата iSZ. Ако потребителят въведе валидна входна информация от прозореца на конзолното приложение, променливата is_size_t е зададена на true, в противен случай (освен ако потребителят не въведе валидна стойност от цяло числото) променливата is_size_t е зададена на false. Променливата is_size_t първоначално се инициализира до false на линията. Това представлява състояние, че променливата iSZ все още не е инициализирана и това всъщност е вярно. Ред 13 показва ключовата дума към. Това означава, че тялото на цикъла започва с известно време, при което условието е сравнение на съдържанието на променливата c_end със символа n (виж ред 95).
Когато програмата продължи, тя стига до ред 14, който отваря тялото на споменатия цикъл за известно време, последван от цикъл while на ред 15, което означава цикъл с условие в началото на всеки цикъл. Тук програмата пита (сравнява) дали стойността false се съхранява в променливата. Ако е така, програмата продължава с положителен клон и подканва на ред 17 потребителят да влезе в горната граница на ситото Eratosten. Тази стойност няма да бъде взета предвид при тестване на просто число. На ред 18 входът, въведен от потребителя, се зарежда в променливата (обект) sz, която е нов екземпляр на низовия клас. Зареждането се извършва по метода getline (), който има два параметъра, а именно cin обект и sz обект.
Ред 20 е последван от блог с код за опит и улов, който се използва за разпознаване на валидността на стойността, въведена от потребителя в sz обекта. В клона try програмата се опитва да преобразува стойността в обекта sz в стойност на цяло число, което представлява дължината на интервала, на който търсим всички прости числа през ситото Eratosten. Функцията stoi се използва за това преобразуване, което накратко означава низ към цяло число (на словашки низ към цяло число). След преобразуването се проверява на ред 24 дали потребителят не е въвел на входа числото 0. Ако е така, програмата задава променливата is_size_t на false и преминава към преоценените условия на следващия цикъл while, докато използва продължи изявление. Тъй като в променливата is_size_t отново е фалшиво, програмата продължава в цикъл while, когато на ред 17 потребителят отново е помолен да въведе горната граница на интервала на ситото Eratosten. По този начин програмата може да се циклира, докато потребителят не въведе валидна стойност на входа на конзолното приложение.
Нека да разгледаме сега, когато потребителят не въведе стойност от интегралния диапазон на типа (например невалидна стойност "hsfu"). Вероятно вече знаете, че това не е интегрална стойност на типа, а безсмислени знаци, които потребителят може да въведе, тъй като тези стойности могат да бъдат присвоени на типа низ, но тази стойност не може да бъде преобразувана в целочислена стойност. Ето защо в нашата програма има блок за хващане на ред 34, който улавя това изключение. И какво всъщност ще се случи след това? Но същото като в случая на въвеждане на 0, това означава, че стойността false е зададена на променливата is_size_t и програмата скача с оператора continue в началото на цикъла while, където условието се оценява отново, за да продължи, като подкани потребител, за да въведе валидна горна стойност.Ситото на Eratosten и тъй като отрицанието на стойността в променливата is_size_t е вярно, програмата ще го направи така или иначе. И така програмата ще подкани потребителя да въведе валидна стойност.
Ако потребителят въведе валидна стойност, програмата преминава към клона try, където след това скача към отрицателния клон на оператора if (клауза else на ред 29), където стойността на is_size_t вече е зададена на true. По този начин в този цикъл програмата изскача от цикъла while, защото вече не отговаря на условието за следващото изпълнение на цикъла.
Когато потребителят е въвел валидна горна граница на ситото Eratosten, тази информация може да се използва за разпределяне на вектор с дължина iSZ (векторно разпределение с идентификатор vNumberVector), който е реализиран на ред 41. На ред 42 е присвоен вектор с дължина 0 (вектор с идентификатор vPrimeVektor). В този вектор ще съхраняваме прости числа, които преминават през ситото на Ератостен. Векторът има дължина 0, защото е възможно да се добави просто число след него само когато част от алгоритъма вземе решение дали числото, избрано от вектора vNumberVector, е просто число или не.
На линия 44 започва цикълът for, който в отделните си цикли се контролира от итеративна променлива i, която се увеличава във всеки цикъл, докато достигне стойността iSZ. Този цикъл for в тялото му запълва вектора vNumberVector с числа от 0 до 19 (защото горната граница, която дефинирахме в примера, е 20).
Ако остатъкът след разделянето е равен на нула, тестваното число не е просто число, което означава, че задаваме променливата на флага на false, прескачаме до края на цикъла for, използвайки ключовата дума break (итерационна променлива j). В този случай нищо не се съхранява във vPrimeVector вектор, тъй като променливата на стойност се съхранява в променливата на флага. външният цикъл for се прекратява, когато се тестват всички числа, съхранявани във vNumberVector вектора. Следователно последното тествано число е числото 19.
След тестване на всички числа, простите числа се записват в прозореца на конзолното приложение (виж редове 78 до 83), за което използваме обекта cout и цикъла for. Разбира се, записът включва и преместване на курсора на нов ред на ред 85.
След това в прозореца на конзолното приложение се извежда подкана да попита потребителя дали иска да излезе от програмата или не. Ако потребителят натисне клавиша n, програмата продължава и потребителят е подканен да въведе отново горната граница на ситото Eratosten, като стойността is_s отново се съхранява false.
Ако потребителят потисне друг ключ (което означава прекратяване на програмата), програмата скача след външния цикъл while към ред 97, основната функция връща 0 към операционната система и цялата програма се прекратява. Нека ви напомня, че на ред 98 има дясна програмна скоба, която затваря тялото на основната функция.
Списък на програмите main.cpp
Прозорец за приложение на конзолата в горната граница на ситото Eratosten 20
На фигурата може да се види, че получените прости числа са същите като простите числа, които сме изчислили аналитично (вижте последната таблица в текста).
Надявам се, че се интересувате от примера и програмата със сито Eratosten, всичко, което трябва да направите, е да го внедрите на вашия компютър.
Този блог е написан от Marek ŠURKA, преподавател по курсове C ++. Ако имате някакви въпроси, напишете ги в коментарите.
Ние учим хората да проектират, създават уеб сайтове и програмират. Можете да намерите нашите редовни курсове в няколко града в Словакия и с помощта на онлайн курсове можете да се поучите от уюта на вашия дом.