Алгор́итм — послідовність, система, набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій.[1] При написаннікомп'ютерних програм алгоритм описує логічну послідовність операцій. Для візуального зображення алгоритмів часто використовують блок-схеми.
Кожен алгоритм є списком добре визначених інструкцій для розв'язання задачі. Починаючи з початкового стану, інструкції алгоритму описують процес обчислення, які відбуваються через послідовність станів, які, зрештою, завершуються кінцевим станом. Перехід з одного стану до наступного не обов'язково детермінований — деякі алгоритми містять елементи випадковості.
Властивості алгоритмів. Будь-який алгоритм подає розв*язування задачі як послідовність відокремлених простих дій. Вони виконуються почергово, одна за одною, в усталеному порядку. Тільки після виконання однієї дії можна перейти до наступної. Така розчленованість процесу виконання алгоритму називається дискретністю (від лат. discretus - розділений, переривчатий).
За скінченну кількість кроків алгоритм має приводити до здобуття потрібного результату або до досягнення потрібної мети. Цю властивість алгоритму називають скінченністюабо результативністю.
Алгоритм має складатися з команд, які входять до системи команд його виконавця, адже це забезпечує зрозумілість алгоритму. Разом із заданою сукупністю вхідних даних, алгоритм цілком визначає дії виконавця та їх послідовність при розв*язанні задачі. Кожна команда алгоритму однозначно встановлює, що треба робити на даному кроці та до якої команди перейти на наступному. Будь-які розбіжності в тлумаченні дій, приписуваних командою, виключаються. Не може виникнути й потреби у будь-якій додатковій інформації ззовні або у прийнятті рішень самим виконавцем. Цю властивість алгоритму називають визначеністю або детермінованістю (від лат. determinare - визначати). Переважно один і той самий алгоритм має змогу виконати не один, а декілька виконавців - і отримати однакові результати. Ця властивість називається формальністю або певністю.
Типи алгоритмів
Є 4 типи алгоритмів:
-прості;
-розгалужені;
-циклічні;
-універсальні;
Простими є такі команди: виконати, встати, іти, вміти тощо. Якщо алгоритм складається лише з послідовності простих команд то його називають простим, або лінійним.
Якщо в алгоритмі, окрім простих команд, є команда, яка містить умову, то такий алгоритм називається розгалуженим. Умови в інформатиці називаються логічним виразом.
Циклічні алгоритми.
Циклом називають процес повторення дій. Циклічні алгоритми забезпечують повторне виконання деяких команд скінчену кількість разів.
Універсальні алгоритми – це такі які містять в собі вище перечисленні такі алгоритми.
Історія розвитку мов програмування
Поступово програми, записані за допомогою машинних кодів, змінювалися. Так,
почали записувати команди не цифрами, а літерами (що для людини набагато легше). Потім
вигадали назви комірок пам’яті, що дозволило звертатися до їхнього вмісту не за номером, а
за назвою. Як підсумок, програма, записана такими зміненими машинними кодами, мала
більш зрозумілий вигляд. Такий запис програм стали називати записом мовою Асемблер.
Програми, розроблені мовою Асемблер, виконуються надзвичайно швидко, але все
одно потребують від своїх розробників відмінно розуміти будову процесора та пам’яті (а
вони знову різні на різних комп’ютерах) і пам’ятати одночасно безліч деталей. Тому цією
мовою розробляють лише невеличкі програми (наприклад, драйвери різноманітних
пристроїв комп’ютера), які мають виконуватися швидко.
Усі розуміли, що потрібні інші мови програмування, які не залежать від процесора
певного комп’ютера та на яких зможуть розробляти свої програми інші користувачі
(наприклад, інженери та вчені). Саме це й спричинило в 50-х рр. ХХ ст. розробку
алгоритмічних мов програмування. Ці мови створювали для того, щоб кожний розробник
міг записати свою програму простими, заздалегідь визначеними словами даної мови
програмування (операторами програми), виконуючи при цьому визначені розробниками мови правила синтаксису, не вникаючи в принципі будови та функціонування процесора
комп’ютера.
Поступово розмір програм і вимоги до них збільшувалися. Тому програмісти при
розробці програм почали використовувати принцип процедурного програмування. Усі
частини програми, однакові для різних її елементів, вони оформляли у вигляді окремого
блока – підпрограми, до якого зверталися багаторазово за різних початкових умов. Однією з
перших процедурних мов програмування є мова Паскаль, яку створив у 1968-1971 рр.
швейцарський учений Ніклаус вірт з кафедри інформатики Стенфордського університету для
навчання студентів основам програмування.
Коли з’явилося процедурне програмування, нікого не турбувало, скільки часу
витрачає програміст на розробку та відлагодження своєї програми, адже його робочий час
коштував у тисячі разів дешевше, ніж дорогоцінний час роботи величезних комп’ютерів – для
яких створювались ці програми. Ця ситуація принципово змінилася в епоху появи та
поширення персональних комп’ютерів – у 80-х рр. ХХ ст. Адже комп’ютери почали
створювати у величезній кількості, і кожний з них вимагав багатьох різноманітних програм.
Комп’ютерний час перестав бути безцінним, чого не можна сказати про працю професійних
програмістів та інших користувачів персональних комп’ютерів. Саме тоді й почалися зміни
мов програмування, напрямлені на економію часу та сил розробників програмного
забезпечення.
Тому в розробку нових мов програмування було покладено принцип повторного
використання коду, тобто те, що було кимось створено та відлагоджено, не може
Візуальне програмування
Об'єктно-орієнтоване програмування
Процедурне програмування
Алгоритмічні мови програмування
Асемблер
Програмування в машинних кодахпропадати. Воно має накопичуватися, зберігатися та використовуватися як попередньо
розроблений блок в іншій програмі. Саме такі блоки й стали називати об’єктами. Отже, коли
треба розробити нову програму, можна використати об’єкти попередньо розробленої
програми та переналаштувати їх для використання в нових умовах. Це легко зрозуміти, якщо
пригадати, які подібні елементи ви бачили у програмах різного призначення, наприклад, у
середовищі текстового та графічного редактора. Ви не один раз використовували в різних
програмах однакові елементи інтерфейсу (наприклад, прапорці, кнопки чи повзунки), за
допомогою яких призначали різні значення певних характеристик. Різні програми досить
часто використовують навіть однакові типи шрифтів для відображення інформації у вікні. Усе
це створені програмістами об’єкти, які можна налагодити та використати при розробці інших
програм. Отже, добре створене один раз можна і треба використовувати багаторазово, проте
в інших умовах і, можливо, для інших потреб.
Саме так і виникло об’єктно-орієнтоване програмування, однією з перших мов якого є
С++. Після цього у мови Pascal теж з’явилася об’єктно-орієнтована версія – Object Pascal.
Проте історія розвитку мов програмування на цьому не зупинилася, що знову було
спричинено змінами у світі персональних комп’ютерів. До 90-х рр. ХХ ст. комп’ютерами
керували переважно за допомогою клавіатури, набираючи команди у спеціальному
командному рядку. Проте згодом в операційних системах почали активно використовувати
графічний інтерфейс. Зображення на моніторі комп’ютера перестали бути просто
картинками, адже більшість з них містить різноманітні елементи керування (кнопки,
прапорці, перемикачі тощо.) Тому зі створенням графічного інтерфейсу змінився і метод
розробки нових програм – він теж став графічним, або візуальним. За допомогою миші
розробник програми має із системи візуального програмування обирати готові блоки своєї
майбутньої програми, налаштовуючи їх для власних потреб на власний смак.
Мова Pascal як система програмування
Turbo, а пізніше Borland Pascal— це одна з найвдаліших та найпоширеніших реалізацій мови Pascal, створена компанією Borland. Turbo Pascal — розширення американського стандарту (ANSI Pascal), яке враховує архітектурні особливості MS-DOS та MS Windows і постачається зі значними за обсягом і різноманітності пакетами стандартних процедур. Такі принципові нововведення, як апарат модулів і об’єктно-орієнтовані засоби полегшують конструювання великих програмних систем на основі технології модульного програмування.
Компілятор Turbo Pascal працює за однопрохідною схемою, реалізує функції редагування зв'язків, формуючи на виході готовий до виконання об'єктний код. Компілятор може здійснювати широкий набір локальних оптимізацій (згортання констант, виключення невикористовуваного коду і зайвих даних, оптимізація операцій і т.д.), що сприяє високій ефективності кінцевих програм.
Система Turbo Pascal є інтегрованим середовищем (IDE), яке налічує ряд компонентів, що в сукупності підтримують усі види робіт зі створення програм. Система містить універсальний текстовий редактор, компілятор вхідної мови, редактор зв'язків і вбудований символьний зневаджувач. Багатовіконний інтерфейс із розвинутою системою меню і досконалою довідковою системою забезпечує високу продуктивність праці програміста.
Borland Pascal 7.0, 7.01 компілює програми для DOS та ОС Windows 1.0, Windows 2.0, Windows 3.x, а також містить ряд додаткових утиліт та компіляторів на кшталт: Turbo Pascal for Windows (TPW), Borland Pascal for Windows (BPW), редактор ресурсів (іконок, графічних файлів, курсорів тощо) та інші.
Склад системи програмування
Компілятор або транслятор
Інтегроване середовище розробки
Засоби створення і редагування текстів програми
Бібліотеки стандартних підпрограм (функцій)
Багатовіконний режим роботи
Вбудований асемблер
Вбудована довідкова служба інше
Мова Паскаль – це вдалий компроміс між простотою і потужністю, ефективністю, лаконічністю і багатослів’ям. У ній вперше відображено концепції структурного програмування.
Мову програмування Паскаль розробив Ніклаус Вірт у Швейцарському технологічному інституті в Цюріху на базі мови Алгол – 60. Сьогодні її широко застосовують як засіб для вивчення програмування. Вона завоювала велику популярність, що можна пояснити такими чинниками.
По-перше, мову проектували з урахуванням простоти написання транслятора (тобто програми, яка перекладає текст з мови високого рівня машинною мовою). Невеликий обсяг трансляторів дає змогу детально їх описувати і добре документувати. По-друге, ця мова значно простіша, ніж близькі за можливостями мови.
Водночас, мова Паскаль дає змогу писати складні програми, її використовують у програмному забезпеченні персональних комп’ютерів, зокрема для створення системного програмного забезпечення.
Програма для комп’ютера. Записана мовою Паскаль. Як і багатьма іншими мовами, складається з двох основних головних частин: опис дії, які яку потрібно виконати, та опис даних, з якими оперують ці дії. Дії описують з допомогою операторів, а дані – за допомогою описів і визначень.
Поділяють програму на заголовок і блок програми. У заголовку наводять ім’я програми і перечислюють її параметри. Параметри є змінні, які містять аргументи – вхідні дані та результати обчислень. Блок складається з шести розділів розташований у такій послідовності:
Блок = розділ опису позначок;
Блок = розділ визначення сталих;
Блок = розділ опису змінних;
Блок = розділ опису процедур і функцій;
Блок = розділ операторів.
Згідно з синтаксисом мови Паскаль кожна програма починається символом program, після якого зазначають її ім’я. Далів круглих дужках можна наводити параметри програми (імена файлів, через які програма спілкується з зовнішнім середовищем – операційною системою; найчастіше для нескладних програм – це імена стандартних файлів input output). Далі йде блок і закінчується програма крапкою.
Програма мовою Паскаль складається з лексем і символів – розділювачів. Лексеми Паскалю – це спеціальні символи, символи слова, імена, числа, рядки символів, позначки і дерективи.
Розділювачі. Символами – розділювачами вважають: програму, кінець рядка і коментар. Всередині лексем використання їх не допустиме, а між двома сусідніми іменами, термінальними словами або числами повинен бути хоча б один розділювач.
Коментар починається з символу { або ( * і закінчується символами } або * ) і може містити будь які символи, в тому числі кінець рядка за винятком } або * ). Для більшої наочності програми доцільно вживати прогалини, порожні рядки (символ, “кінець рядка”) і коментарі.
Спеціальні символи і зарезервовані слова.
Під час написання програм мовою Паскаль використовуються такі спеціальні символи: + - * / : = … ^ = ' < > < < = > > = ( ) [ ].
Зарезервовані слова – це program, begin, end, if, then, else, for та ін. Їх не можна застосовувати з іншою метою, наприклад, як імена. Вони є символами, а не послідовністю літер.
Імена. Для позначення змінних, сталих, типів, процедур, функцій використовують імена або ідентифікатори. Імена складаються з літер і цифр, однак першим символом повинна бути літера.
Числа. Числа у мові Паскаля використовують цілі та дійсні. Перед числом може стояти знак “+” або “-”. Дійсні числа записують з десятковою крапкою, з порядком, або із крапкою і порядком.
Структура програми на Паскалі
Програма на Паскалі в загальному випадку складається з декількох файлів. Один з них містить головну програму, а решта - модулі. Головна програма складається з заголовка, блоку і закінчується крапкою - ознакою кінця програми. У свою чергу, блок містить розділи описів і розділ операторів. У загальному випадку «скелет» програми можна уявити наступним чином: {Специфікація програми} program <ім'я програми> (заголовок програми); uses (Розділ оголошення модулів); label (розділ оголошення міток); const (розділ оголошення констант); type (розділ оголошення типів); var (розділ оголошення змінних); procedure (function) (розділ оголошення підпрограм: процедур або функцій); begin <Оператори> (розділ операторів, обов'язкова частина); end. Всі зазначені розділи відокремлюються один від одного крапкою з комою. Розділ операторів повинен обов'язково бути присутнім у будь-якій програмі і є основним. Попередні розділи носять характер описів і не обов'язково міститися в програмі. Тема програми складається з зарезервованого слова program та імені програми (зі списком параметрів, укладених в круглі дужки). Завершується заголовок крапкою з комою. У Turbo Pascal є особливості в структурі програми. Так, заголовок програми необов'язковий, і ігнорується компілятором. Порядок розміщення розділів довільний, можна створювати кілька однакових розділів. Єдине правило, яке необхідно витримувати, - у будь-якому місці програми можна використовувати лише елементи (мітки, типи, константи, змінні, підпрограми і т. д.), які були визначені раніше по тексту програми або є зумовленими елементами мови. Винятком з цього правила може бути лише визначення типу-покажчика через невизначений до цього тип. Проте цей тип надалі повинен бути обов'язково визначений. Оператори в розділі операторів відокремлюються один від одного крапкою з комою. Перед e nd крапка з комою не ставиться, але її наявність не є помилкою, а лише означає присутність між останнім виконуваним оператором і службовим словом end ще одного оператора - порожнього оператора. Закінчується програма словом end, після якого обов'язково ставиться крапка. На початку програми необхідно розташовувати її специфікацію - коментар у фігурних дужках, що містить призначення програми, дані про програмістові, дату створення програми. Мова програмування Паскаль є мовою структурного програмування. У ньому є всі необхідні керуючі конструкції для структурної побудови програми. Наочність такій побудові надає структуризація зовнішнього вигляду тексту програми. Основний використовуваний для цього прийом - зрушення рядків, які повинні підкорятися такими правилами: § конструкції одного рівня вкладеності записуються на одному вертикальному рівні (починаються з однієї позиції в рядку); § вкладена конструкція записується зміщеною по рядку на декілька позицій праворуч щодо зовнішнього для неї конструкції.
ТИПИ І ЗНАЧЕННЯ ЗМІННИХ
Рішення задач цього розділу не передбачає складання скільки-небудь складних алгоритмів, написання скільки-небудь серйозних програм і проектування хитромудрого інтерфейсу Windows-додатків за допомогою засобів Visual Basic 6.
Все, що потрібно для розв'язання цих задач, це знання типів змінних мови Visual Basic 6, способів оголошення типів і діапазонів зміни значень змінних різних типів.
Вам знадобляться знання різних типів числових змінних Byte, Integer, Long, Single, Double, Currency. Буде розглянутий і тип нечисловий (текстової) змінної String. Згадаємо тип логічної змінної Boolean. Розглянемо ми і тип Date для представлення дати числа, місяця і року будь-якого дня нинішнього (і не тільки нинішнього) тисячоліття. У мові Visual Basic ключове слово Date використовується не тільки як назва типу змінної, але і як ім'я функції. Ця функція не має аргументів. Вона повертає значення, яке є поточною датою.
Ви повинні мати уявлення і про особливий тип Variant, про те, що змінні цього типу можуть мати будь-який тип.
Для розв'язання задач потрібно знати способи оголошення типу змінною:
за допомогою оператора оголошення типу Def... (DefByte, DefInt, DefLng, DefSng і т.д.);
за допомогою операторів визначення змінної Dim. .. As. .. (або Private. .. As. .., або Public. .. As. ..);
за допомогою суфікса (одного із знаків %, &, !, #, @, $, який записується в кінці імені змінної).
Окремим випадком змінної є константа постійна величина. Вона оголошується за допомогою оператора визначення константи Const. .. As. ...
Ви повинні розуміти, що оголошувати тип змінної зовсім не обов'язково в цьому випадку він буде «оголошений» самою системою Visual Basic за замовчанням. Система буде вважати, що Ваша змінна має тип Variant. А після привласнення цієї змінної значення певного типу система автоматично змінить і тип змінної.
У задачах цього розділу використовується оператор привласнення X=Е, з допомогою якого змінній X привласнюється значення виразу Е. (Старомодне слово Let перед ім'ям змінної X ми не записуємо, хоч робити це не возбраняется.) І хоч обчислення значень виразів це тема наступного розділу, тут ми вимушені скористатися найпростішими арифметичними операціями додавання (+), відніманням ( - ), множенням (*) і ділення (/).
У деяких програмах цього розділу Ви можете побачити і один з методів Visual Basic це метод Print, за допомогою якого результат роботи програми можна просто «надрукувати» на екранній формі.
Під файлом розуміється іменована область пам'яті на носії, використовувана для довгострокового зберігання деякої логічно зв'язаної інформації. У цю область зовнішньої пам'яті можна як помістити певні дані, так і витягти їх з неї. Ці дії мають загальну назву - ввід-вивід.
Файл - це одномірний масив байтів, що має як мінімум один твердий зв'язок (ім'я файлу). Файли можуть містити інформацію у двійковому або в текстовому виді. Файли містять дані, сценарії оболонки або програми. Крім того, деякі імена файлів являють собою такі абстрактні об'єкти, як сокети й драйвери пристроїв.
Передбачено безліч функцій для роботи з файлами. Більшість цих функцій можна віднести до однієї з наступних двох категорій:
Функції для створення файлів.
Функції для керування файлами.
Наприклад у паскалі робота з файлами здійснюється через спеціальні типи. Це файлові типи, які визначають тип файлу, тобто фактично вказують його вміст.
За допомогою цієї змінної, котрої привласнений необхідний тип, і здійснюється вся робота з файлами - відкриття, запис, читання, закриття й т.п.
При роботі з файлами існує певний порядок дій, якого необхідно дотримуватися. От всі ці дії:
Створення (опис) файлової змінної;
Зв'язування цієї змінної з конкретним файлом на диску або із пристроєм вводу-висновку (екран, клавіатура, принтер і т.п.);
Відкриття файлу для запису або читання;
Дії з файлом: читання або запис;
Закриття файлу.
Програмування доступу до файлу в язиці Turbo Pascal починається з опису файлової змінної (змінної файлового типу). Цей опис будується за допомогою службового слова file, після якого може бути зазначений тип окремих елементів файлу.
Залежно від способу опису можна виділити текстові файли, двійкові або типізовані й нетипизовані. Вид файлу визначає спосіб зберігання інформації у файлі.
Текстовий файл є файлом послідовного доступу, і його можна представити як набір рядків довільної довжини. Логічно послідовний файл можна представити як іменований ланцюжок байтів, що має початок і кінець. Послідовний файл відрізняється від файлів з іншою організацією тим, що читання (або запис) з файлу (у файл) ведуться байт за байтом від початку до кінця.
Також існують так називані "типізовані" файли, тобто файли, що мають тип. Цей тип визначає, якого роду інформація втримується у файлі й задається в параметрі.
Нетипизований файл - файл, у якому ми вказуємо як тип файлу просто File, тобто без типу.
Те одержуємо "нетипизований" файл, читання й запис у який відрізняється від роботи з файлами інших типів. Ці дії виробляються шляхом вказівки кількості байт, які потрібно прочитати, а також вказівкою області пам'яті, у яку потрібно прочитати ці дані.
Кожній програмі доступні два стандартних файли input (клавіатура) і output (екран). Це - текстові файли. Будь-які інші файли стають доступними після виконання спеціальних процедур.
Любий файл має три характерні риси. По-перше, у нього є ім'я, що дає можливість програмі працювати одночасно з декількома файлами. По-друге, він містить компоненти одного типу. По-третє, довжина знову створюваного файлу ніяк не обмовляється при його оголошенні й обмежується тільки ємністю пристроїв пам'яті.
Відкриття файлу - це вже більше ускладнений процес, ніж зв'язування з ним змінної. Тут ураховується, навіщо відкривається файл - для запису або читання, а також залежно від типу файлу процедури виконують різні дії.
Цей процес полягає у використанні однієї із трьох наявних процедур:
1. Відкриття файлу на читання. Це може бути текстовий, типізований або не типізований файл. У випадку з текстовим файлом, він відкривається тільки на читання. У випадку з типізованим і не типізованим файлом - він відкривається на читання й запис.
2. Процедура відкриття текстового файлу на запис. Вище було сказано, що при завданні параметра типу Text не дозволить писати в нього дані, відкривши файл лише для читання. Тобто якщо використається текстовий файл і необхідно робити в нього запис, використовується ця процедура.
3. Процедура створення нового файлу або перезаписування існуючого.
Читання файлів. Читання файлів виробляється за допомогою відмінно відомих нам процедур Read і Readln. Вони використаються також, як і при читанні інформації із клавітури. Відмінність лише в тім, що перед змінної, у яку міститься лічене значення, указується змінна файлового типу (дескриптор файлу).
Запис у файли вироблятися точно так само, як і запис на екран - за допомогою процедур Write і Writeln. Як і у випадку із читанням, перед записуваною у файл змінної вказується дескриптор файлу.
TURBO PASCAL уводить ряд процедур і функцій, застосовних для будь-яких типів файлів: Assign, Reset, Rewrite, Close, Rename, Erase, Eof,
Процедура Assign зв'язує логічний файл із фізичним файлом, повне ім'я якого задане в рядку FileName.
Процедура Reset відкриває логічний файл для наступного читання даних або, як говорять, відкриває вхідний файл. Після успішного виконання процедури Reset файл готовий до читання з нього першого елемента.
Процедура Rewrite відкриває логічний файл для наступного запису даних. Після успішного виконання цієї процедури файл готовий до запису в нього першого елемента.
Процедура Close закриває відкритий до цього логічний файл. Виклик процедури Close необхідний при завершенні роботи з файлом.
Логічна функція EOF Boolean повертає значення TRUE, коли при читанні досягнуть кінець файлу. Це означає, що вже прочитано останній елемент у файлі або файл після відкриття виявився порожній.
Процедура Rename дозволяє перейменувати фізичний файл на диску, пов'язаний з логічним файлом. Перейменування можливо після закриття файлу.
Процедура Erase знищує фізичний файл на диску, що був пов'язаний з файлової змінної. Файл до моменту виклику процедури Erase повинен бути закритий.
Пример. Запись текстового файла на диск и ввод в него текста.
program wtf;
type fil=text;
var f1:fil; name:string[35]; txt:string;
begin
write('Введите имя файла для записи текста>');
readln(name);
writeln;
assign(f1,name);
rewrite(f1);
writeln('Введите текст для записи (для окончания-Enter):');
writeln;
repeat
write(':>');
readln(txt);
writeln(f1,txt);
until txt='';
close(f1);
writeln;
writeln('Ввод окончен, нажмите Enter.');
readln;
end.
Логічний, символьний і рядковий типи змінних Turbo-Pascal.
У розділі var рядка описуються наступним образом1): var <імя_строкі>: string [[<довжина>]] 2) Максимальна довжина рядка - 255 символів. Нумеруються її компоненти починаючи з 0, але цей нульовий байт зберігає довжину рядка. Якщо <довжина> не вказана, то вважається, що в рядку 255 символів. Тому дляекономії пам'яті слід по можливості точно вказувати довжину використовуванихрядків. Приклади описів: var s1: string [10]; (* рядок довжиною 10 символів *) s2: string; (* рядок довжиною 255 символів *) Необхідно відзначити, що один символ і рядок довжиною в одін3) символ var c: char; s: string [1]; абсолютно не еквівалентні один одному. Незалежно від своєї реальної довжини,рядок стосується конструйованих структурованим типам даних, а не до базовихпорядковим
Логічний тип boolean має два значення: false і true, і для них виконуються такі рівності: ord (false) = 0, ord (true) = 1, false <true, pred (true) = false, succ (false) = true, inc (true) = false, inc (false) = true, dec (true) = false, dec (false) = true. У символьний тип char входить 256 символів розширеної таблиці ASCII (наприклад, 'a','b', 'я', '7 ','#'). Номер символу, що повертається функцією ord (), збігається з номеромцього символу в таблиці ASCII.
33.Пірамідальне сортування
var i, k, j, N, x: integer;
a: array [1..100] of integer;
begin
read(n);
randomize;
for i := 1 to n do
a[i] := random (50);
for i := 1 to N do
write(a[i],' ');
writeln;
for i:= (N div 2)downto 1 do
begin j:= i;
while j<=(N div 2) do
begin k:= 2*j;
if (k+1<=N) and (a[k]<a[k+1])
then k:= k+1;
if a[k]>a[j]
then begin x:= a[j];
a[j]:= a[k];
a[k]:= x;
j:= k
end
else break
end
end;
for i:= N downto 2 do
begin x:= a[1];
a[1]:= a[i];
a[i]:= x;
j:= 1;
while j<=((i-1)div 2) do
begin k:= 2*j;
if (k+1<=i-1) and (a[k]<a[k+1])
then k:= k+1;
if a[k]>a[j]
then begin x:= a[j];
a[j]:= a[k];
a[k]:= x;
j:= k
end
else break
end
end;
for i := 1 to N do
write(a[i],' ');
readln;
end.
27.Швидке сортування
var a: array [1..100] of integer;
n, i: integer;
procedure qsort(l, r: integer);
var middle, temp, i, j: integer;
begin
middle := a[(l+r) div 2];
i := l;
j := r;
while i<=j do
begin
while a[i] < middle do
inc(i);
while a[j] > middle do
dec(j);
if i <= j then
begin
temp := a[i];
a[i] := a[j];
a[j] := temp;
inc(i);
dec(j);
end;
end;
if l<j then
qsort(l, j);
if r>i then
qsort(i, r);
end;
begin
randomize;
writeln('vvedit kil-t elementiv:');
read(n);
for i := 1 to n do
begin
a[i] := random(50);
write(a[i],' ');
end;
writeln;
qsort(1, n);
for i := 1 to n do
write(a[i], ' ');
end.
30.Шейкерне сортування
var A:array[1..100] of integer;
N,i,k,x,j,d : integer;
begin
randomize;
read(N);
for i:=1 to n do
a[i] := random(50);
for i := 1 to n do
write(a[i],' ');
writeln;
d := 1;
i := 0;
for k:=n-1 downto 1 do { k - количество сравниваемых пар }
begin
i := i+d;
for j := 1 to k do
begin
if (a[i]-a[i+d])*d>0 then
{меняем местами соседние элементы}
begin
x := a[i];
a[i] := a[i+d];
a[i+d] := x;
end;
i := i+d;
end;
d := -d;
{меняем направление движения на противоположное}
end;
for i := 1 to n do
write(a[i],' '); {упорядоченный массив}
end.
32.шелла
var ii,m,x,s,p,t,k,r,i,j,n: integer;
a: array[1..100] of integer;
begin
randomize;
for i:=1 to 20 do
begin
a[i]:=random(50);
write(a[i],' ');
end;
writeln;
n:=20;
t:= trunc(ln(n)/ln(2));
repeat
t:= t-1;
k:= (1 shl t)-1;
p:= n mod k;
s:= n div k;
if p=0 then p:= k
else s:= s+1;
for i:= 1 to k do
begin
if i= p+1 then s:= s-1;
for j:= 1 to s-1 do
if a[i+(j-1)*k]>a[i+j*k]
then begin x:= a[i+j*k];
m:= i+(j-1)*k;
while (m>0) and (a[m]>x) do
begin a[m+k]:= a[m];
m:= m-k;
end;
a[m+k]:= x;
end;
for ii:= 1 to n do write(a[ii],' ');
writeln;
end;
until k=1;
end.
program sort_3;
{$APPTYPE CONSOLE}
uses
SysUtils;
var mass: array [1..100] of Integer;
i, j, n, temp, min, min_i, k: Integer;
begin
Writeln('Vvedit kilkist elementiv massiva:');
read(n);
Randomize;
for i := 1 to n do
begin
mass[i] := Random(50) - 25;
write(mass[i],' ');
end;
writeln;
// Buble sort
{for i := 2 to n do
for j := n downto i do
begin
if (mass[j] < mass[j-1]) then
begin
temp := mass[j];
mass[j] := mass[j-1];
mass[j-1] := temp;
end;
end; }
//Select sort
{for i := 1 to n-1 do
begin
min_i := i;
for j := i+1 to n do
begin
if (mass[min_i] > mass[j]) then
begin
min_i := j;
end;
end;
temp := mass[min_i];
mass[min_i] := mass[i];
mass[i] := temp;
end; }
//Insert sort
for i := 2 to n do
begin
temp := mass[i];
j := 1;
while (temp > mass[j]) do
Inc(j);
for k := i-1 downto j do
mass[k+1] := mass[k];
mass[j] := temp;
end;
for i := 1 to n do
write(mass[i],' ');
readln;
readln;
end.
31.
Метод бінарних вставок
for i:= 2 to n do
if a[i-1]>a[i] then
begin x:= a[i];
left:= 1;
right:= n-1;
repeat
sred:= (left+right) div 2;
if a[sred]<x then left:= sred+1
else right:= sred-1;
until left>right;
for j:= i-1 downto left do a[j+1]:= a[j];
a[left]:= x;
end;
Злиттям.
const
n1 = 5;
n2 = 8;
var
P: array [1..n1 + n2] of integer;
M: array [1..n1] of integer;
N: array [1..n2] of integer;
i, j,l, x: integer;
begin
writeln('Заполните массив M (ввод ', n1, ' элементов )');
for i := 1 to n1 do
read(M[i]);
writeln('Заполните массив N (ввод ', n2, ' элементов )');
for i := 1 to n2 do
read(N[i]);
j := 1;
l := 1;
for i := 1 to n1+n2 do
if j>n1
then
begin
P[i] := N[l];
l := l+1;
end
else
if l>n2
then
begin
P[i] := M[j];
j := j+1;
end
else
if M[j]<=N[l]
then
begin
P[i] := M[j];
j := j+1;
end
else
begin
P[i] := N[l];
l := l+1;
end;
for i := 1 to n1 + n2 do
write(P[i]:3);
end.