Алгоритм преобразует алгоритм


Содержание

Алгоритм преобразования данных

Читайте также:

  1. Buch — книга, halter — держатель, что в переводе означает «регистратор хозяйственных операций, или ответственный за организацию и правильное прочтение учетных данных».
  2. D — преобразования
  3. D – преобразования
  4. I. РАЗРАБОТКА АЛГОРИТМОВ. ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ (БЛОК-СХЕМЫ) И СЛОВЕСНАЯ ЗАПИСЬ АЛГОРИТМОВ
  5. T не константа, время преобразования зависит от величины преобразуемого напряжения
  6. Trading Techniques Inc. предоставляет месячные, недельные, дневные и почасовые (60 минут) данные по всем фьючерсам с помощью сервиса загрузки данных.
  7. V. УПРАВЛЕНИЕ ПОТОКАМИ ДАННЫХ
  8. V1: <<02>> 02_Типы данных и преобразования
  9. VI. Воззрения Иакова на проблему иудео-христианства в свете фактических данных Нового Завета, апокрифических произведений и его Соборного послания.
  10. Автоматическое исправление орфографических ошибок при вводе данных
  11. Адресация, имена, спецификация данных в ОС
  12. АЛГОРИТМ

Способ хранения данных

В задании было указано на необходимость создания, хранения и последующего просмотра протокола работы. Протокол работы можно хранить на жестком или на гибком диске. Обеспечим возможность различных вариантов хранения протокола и на жестком и на гибком диске. Поэтому в табл. 3.2 необходимо добавить три строчки с данными LogDisk, LogPath и LogFile, соответствующими имени диска, пути к файлу протокола и имени файла протокола. Все три величины имеют тип string, видимость – public, организацию – «переменные».

Для хранения протокола можно выбрать как файл последовательного доступа, так и файл прямого доступа. В данном случае это совершенно безразлично, но для работы с файлом прямого доступа потребуется создать сложный тип данных. Выбираем файл последовательного доступа с многокомпонентной записью данных в последовательности a,b. Корень х уравнения можно было бы также записать в файл, что упростило бы процесс чтения протокола, но знание метода решения уравнения позволяет предвидеть необходимость записи при а=0 сообщений «не определен» или «не существует».

Метод решения уравнения А*х+В=0 предельно прост:

х не определен при А=0 и В=0

не существует при А=0 и В¹0.

Анализ алгоритма решения уравнения показывает, что для его полной реализации должна быть введена промежуточная переменная типа string или вычисляющая ее функция, в которую записывается символьный эквивалент значения х или текст соответствующего сообщения. С учетом соображений, высказанных в 3.6.3 и в данном подразделе, табл. 3.2 можно придать вид
табл. 3.3.

Уточненное описание наборов данных

Имя Тип Способ организации Видимость Назначение
Входные данные
A Single Переменная Public Коэффициент а
B Single Переменная Public Коэффициент b
Выходные данные
X Single Переменная Public Корень уравнения
Промежуточные данные
TBA.Text String Свойство Text Box Public Ввод коэффициента а
TBB.Text String Свойство Text Box Public Ввод коэффициента b
LBX.Caption String Свойство Label Public Отображение корня х
MessX String Функция Public Сообщение о корне х
LogDisk LogPath LogFile String String String переменная переменная переменная Public Public Public Данные протокола: Имя диска Путь Имя файла

Алгоритм преобразования данных показан на Р-графе (рис. 3.1) и в
табл. 3.4. На рис. 3.1 жирным шрифтом показаны обозначения формул (иногда совпадающие с самими формулами), курсивом – имена состояний процесса, а нормальным шрифтом – условия, разрешающие выполнение соответствующих действий. В качестве имен состояний процесса выбраны слова «Вход» (начало процесса), «Выход» (завершение процесса) и номера состояний. Ввиду простоты задачи описание состояний не делается. Если возникнет необходимость в этой операции, то описание состояний можно сделать в таблице, в которой для каждого имени состояния указать имена данных, значения которых определенны.

Вход 1 а¹0 2 3 Выход

TBA.Text>a x= — b/a x →MessX LB.Caption=MessX

TBB.Text>b a=0 4 b¹0

MessX=»не существует»

MessX=»не определен»

Рис. 3.1. Р-граф алгоритма преобразования данных

Таблица формул к алгоритму преобразования данных

Дата добавления: 2014-11-29 ; Просмотров: 669 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Алгоритм преобразования

В его построении участвуют:

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

Хранимые процедуры позволяют в значительной мере снизить объемы информации, передаваемые по сети (трафик). К ним в БД относится Grup_Sum, которая осуществляет подсчет числа «платных», «частично платных» и «бесплатных» студентов, обучающихся в каждой конкретной группе, а также осуществляет подсчет числа юношей и девушек в группе.

Создание видов (View) таблиц служит для повышения быстродействия системы запросов. Приведем команды по созданию вида EKZAMVIEW из РБД «Учебный процесс»:

Г View: EKZAMVIEW, Owner: SYSDBA */

CREATE VIEW EKZAMVIEW (NZK, OTCHET, SEMESTR, SH_SPEC, POSL_SES, FIO, KURS) AS

from uspevaem, gruppa, student

where uspevaem.ng=gruppa.ng and

uspevaem.nzk=student.nzk and semestr <>12

group uspevaem.nzk,otchet,uspevaem.semestr,sh_spec,posl_ses, student.fio,gruppa.kurs by having otchet-‘экз’;

Как видно из примера, выборку данных можно осуществлять одновременно из неограниченного числа связанных таблиц. Так, данный вид осуществляет выборку записей из трех связанных таблиц, после чего группирует полученную информацию по полям nzk, otchet, semestr, sh spec, posl_ses, fio, kurs. Этот вид используется при генерации отчета по успеваемости студентов в текущем семестре. Информация, полученная из этого вида, в дальнейшем перерабатывается интерфейсной частью и используется для генерации отчетов типа:

  • • студенты, не сдавшие .сессию;
  • • студенты, сдавшие сессию на все пятерки;
  • • студенты, сдавшие сессию на пятерки и одну четверку;
  • • студенты, сдавшие сессию на пятерки и две четверки.

В программе имеются следующие виды, которые используются:

  • • EkzamView – для генерации отчетов о сдаче студентами сессии;
  • • GruppaView – для ускорения доступа к связанным полям;
  • • StudentView – для ускорения доступа к связанным полям;
  • • ZadolgView – для генерации отчетов о сдаче студентами сессии.

Программа содержит большое количество алгоритмов, необходимых для обработки тех или иных действий пользователя, генерации сложных отчетов, взаимодействия с РБД и переработки информации. Многие из этих алгоритмов было практически невозможно реализовать, используя лишь стандартные конструкции Object Pascal, поэтому в них наряду с Pascal использовался также и язык SQL. Такой симбиоз языков позволяет в значительной мере ускорить выполнение данных алгоритмов. В качестве примера программного кода, содержащего как Pascal, так и SQL, приведем фрагмент процедуры генерирующей «зачетную (экзаменационную) ведомость».

procedure TForml 1 .Button5Click(Sender: TObject);

Загрузка в переменную tl текущего значения колонки otchet таблицы izuchenie

if t1 =’зач’ then form) 2.QRLabel1 .сарбоп:=’Зачетная ведомость’;

Если tl=зач, то вывести в отчет ‘Зачетная ведомость’

if t1=’аттес’ then form12.QRLabel1.caption:=’Аттестационная ведомость’;

if t1=’экз’ then form12.QRLabel1.caption:=’Экзаменационная ведомость’;

if t1=’K/np’ then form12.QRLabel1 ,сарбоп:=’Курсовой проект’;

if t1=» then exit;

Сброс текущих SQL-команд, загруженных в запрос Qucryrep1

datamodule2.queryrep1 .sql.add(‘select * from predmet’);

Добавление SQL команды ‘select * from predmet’ r запрос Qucryrep1

datamodule2.queryrep1 ,sql.add(‘where kpred=’+

Выводит в отчет название предмета

Закрытие запроса queryrep)

datamodute2.queryrep1.sql.add(‘select * from prepod’);

datamodule2.queryrep1 ,sql.add(‘where kprep=’+

Выводит в отчет ФИО преподавателя

datamodule2.queryrep1 ,sql.add(‘select ng,sh_specfrom gruppa’);

datamodule2.queryrep1 ,sql.add(‘where ng=’+»»+

Выводит в отчет шифр специальности.

datamodule2.queryrep1 .sql.addf’select * from student’);

datamodule2.queryrep1 .sql.addfwhere student. ng=’+»»+

datamodule2.queryrep 1 ,sql.add(‘order by nomer_stud’);

Выводит в отчет список студентов выбранной группы . form12.QRLabel7.caption:=

Выводит в отчет номер семестра

Рис. 14.20. Блок-схема процедуры, генерирующей «зачетную (экзаменационную) ведомость»

Выводит в отчет номер группы

Выводит отчет на предварительный просмотр

Данную процедуру можно представить в виде блок-схемы, изображенной на рис. 14.20.

На этом закончим описание распределенной БД «Учебный процесс».

Особенности работы нормальных алгоритмов Маркова.

Нормальные алгоритмы Маркова.

В данном параграфе дается представление об еще одном подходе к уточнению понятия алгоритма, предложенном в 1947 году А.А. Марковым и называемом нормальные алгоритмы (в авторской транскрипции – алгорифмы). Данный подход связывает неформальное понятие эффективности с переработкой слов в некотором конечном алфавите в соответствии с определенными правилами. В качестве элементарного преобразования используется подстановка одного слова вместо другого. Множество таких подстановок определяет схему алгоритма. Правила, определяющие порядок применения подстановок, а также правила остановки являются общими для всех нормальных алгоритмов. Дадим формальные определения.

Определение 19:Нормальный алгоритм Маркова – это аппарат преобразования слов. Под словом подразумевается произвольная последовательность символов, входящих в конечный алфавит.

Обозначения: – слово, – алфавит.

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

Определение 20: Каждый нормальный алгоритм Маркова представляет собой совокупность правил , которыеназываются правилами подстановки. Каждое правило подстановки можно представить в виде преобразования: .

Преобразование произвольного слова состоит в поиске в нем подслова, совпадающего с левой частью некоторого правила подстановки , и замене этого подслова правой частью данного правила.

Для краткости в дальнейшем правила подстановки будем обозначать натуральными числами.

Приведем пример нормального алгоритма Маркова.

Пример 1. Алфавит символов . Данный алгоритм содержит два правила подстановки:

Применить этот алгоритм к слову .

Решение.

Применяя данный алгоритм к данному слову, будут произведены следующие замены (преобразования):

Ответ: на выходе получается слово .


Дадим четкое описание алгоритма преобразования произвольного слова.

Согласно концепции нормальных алгоритмов Маркова, преобразование слова по правилам подстановки представляет собой последовательность однотипных шагов. Опишем один шаг преобразования.

1) Последовательно просматриваются правила .

2) Если левая часть некоторого правила подстановки входит в слово, то вхождение меняется на .

Эти шаги преобразования последовательно выполняются один за другим. Возникает вопрос: когда следует завершать преобразование слова? Согласно концепции нормальных алгоритмов Маркова, завершение преобразование слова происходит в двух случаях:

1) На некотором шаге преобразования ни одно из правил оказывается неприменимым к данному слову, т.е. ни одна из левых частей не содержится в слове.

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

В терминальных правилах вместо символа используется символ .

Замечание 1. Если левая часть некоторого правила входит в слово более одного раза, то заменяется только самое левое вхождение в слово (на одном шаге преобразования).

Замечание 2. После каждого применения к слову некоторого правила новый просмотр правил всегда начинается с правила .

Замечание 3. Левая часть правила может быть пустой. Правило с пустой левой частью считается применимым к любому слову. Его действие состоит в том, что к началу слова добавляется правая часть правила.

Замечание 4. Правая часть правила тоже может быть пустой. Результатом применения такого правила является удаление из слова последовательности символов, совпадающих с левой частью данного правила.

Если вернуться к примеру 1, можно понять, что правило 1 применяется до тех пор, пока его можно применять. Правило 2 начинает применяться к слову только после того как правило 1 становится к нему неприменимым. После третьего шага оба правила неприменимы.

Пример 2. Алфавит символов . Данный алгоритм содержит два правила подстановки:

Применить этот алгоритм к словам , .

Решение.

Этот алгоритм из нескольких одинаковых подряд стоящих букв оставляет только одну букву.

Пример 3. Алфавит символов . Данный алгоритм содержит два правила подстановки:

Применить этот алгоритм к слову .

Решение.

Заметим, что правая часть второго правила пустая.

На двух последних шагах происходит удаление пары . Итоговое слово . Ни одно из правил подстановки к нему не применимо.

Вывод: Данный нормальный алгоритм Маркова сначала переставляет в слове буквы и так, чтобы все буквы стояли раньше, чем . Правило 1 применяется до тех пор, пока хотя бы одна буква стоит перед . После того, как пар не останется, удаляются пары . На выходе в слове останутся те буквы, которых в исходном слове было больше. При одинаковом количестве букв результатом будет пустая строка.

Пример 4. Алфавит символов . Данный алгоритм содержит два правила подстановки:

Применить этот алгоритм к слову .

Решение.

Данный алгоритм Маркова эквивалентен алгоритму, рассмотренному в предыдущем примере. Оба алгоритма дают один и тот же результат, происходит удаление пар символов. Однако, это алгоритм работает быстрее предыдущего. Для преобразования одного и того же слова потребовалось всего два шага вместо пяти. Значит, данный способ преобразования более эффективный.

Особенности работы нормальных алгоритмов Маркова.

1) Перестановка местами правил подстановки может влиять как на последовательность преобразований, так и на конечный результат.

Чтобы этот факт проиллюстрировать, рассмотрим пример 3, но правила подстановки поменяем местами.

Преобразуем то же слово: .

Видно, что меняется последовательность преобразований, но результат остается прежним.

Пример 5. Алфавит символов . Данный алгоритм содержит два правила подстановки:

Применить этот алгоритм к словам .

Решение.

Изменим порядок следования правил подстановки и применим алгоритм к тому же слову:

Видно, что меняется как результат, так и последовательность преобразований.

2) Правило подстановки с пустой левой частью применимо к любому слову. Это означает, что оно должно всегда быть последним в списке правил. Иначе оно блокирует все последующие правила.

Пример 6. Алфавит символов . Данный алгоритм содержит три правила подстановки:

Применить этот алгоритм к словам .

Решение.

Третье правило заблокировано, оно недостижимо и никогда не выполнится.

3) Если в списке правил подстановки есть правило с пустой левой частью, то для завершения работы алгоритма Маркова в нем должно присутствовать хотя бы одно терминальное правило подстановки.

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

Пример 7. Алфавит символов . В данном случае среди правил нет терминального правила подстановки, следовательно, процесс преобразования любого слова будет бесконечным.

Второе правило всегда применимо и добавляет к началу слова буквы . Применим этот алгоритм к словам :

Если в первое правило будет терминальным, тогда процесс преобразования слова завершится сразу после его применения, в нашем случае на втором шаге:

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

4) Пусть имеется два правила подстановки , такие, что левая часть одного правила является подстрокой левой части другого правила. Тогда правило (более длинное слово) должно стоять в списке правил выше правила (короткое слово). В противном случае правило никогда не выполнится.

Пример 8. Алфавит символов . Рассмотрим следующие правила подстановки:

Видно, что левая часть первого правила — это подстрока левой части второго правила. Второе правило подстановки никогда не будет применено ни к какому слову. В самом деле, если в некоторое слово входит , то входит и одна буква . Следовательно, к такому слову всегда будет применяться только первое правило подстановки. Можно сказать, что первое правило блокирует выполнение второго правила.

Рассмотрим применение этого алгоритма к слову :

Поменяем правила местами:

Тогда в процессе преобразования слова может быть применено как первое, так и второе правила подстановки:

Задачи.

Рассмотрим примеры на составление нормальных алгоритмов Маркова.

Задача 1. Алфавит символов . Составить нормальный алгоритм Маркова, удваивающий в слове каждую букву .

Решение.

Можно рассмотреть алгоритм Маркова, состоящий из одного правила подстановки:

Сразу отметим, что этот алгоритм задачу удвоения не решает, так как он просто добавляет по одной букве к слову на каждом шаге преобразования. Например, на входе слово :

Удваивания символа не происходит. Значит, приведенный алгоритм не верный.

Для решения подобных задач составляется нормальный алгоритм Маркова, который выполняет следующие преобразования слова:

1) К началу слова добавляется дополнительный символ . Этот символ не входит в алфавит.

2) Дополнительный символ «прогоняется» через слово с одновременной заменой каждого символа в слове согласно условию задачи.

3) В конце преобразований дополнительный символ удаляется.

Данные действия для нашей задачи удвоения символов будут реализованы следующим нормальным алгоритмом Маркова:

Имеется три правила подстановки. Третье правило добавляет к слову дополнительный символ . Это правило состоит из пустой левой части, его можно применить всегда к любому слову. С помощью первого правила подстановки символ «прогоняется» через слово с одновременной заменой на . В результате этого символ оказывается в конце слова. Второе правило удаляет символ по окончании преобразования слова. Это правило является терминальным, поэтому его применение означает завершение преобразования слова. Новый просмотр правил не производится.

Посмотрим, как данный нормальный алгоритм Маркова преобразует входное слово и :

По опыту предыдущей задачи можно сделать следующие важные замечания.

Замечание 1. Правило с пустой левой частью всегда должно стоять в списке правил на последнем месте. Применяться же оно должно раньше остальных правил. То есть никакое другое правило не должно быть применено к слову до применения к нему последнего правила. А это в свою очередь означает, что все правила (кроме последнего) должны содержать в своей левой части дополнительный символ .

Согласно концепции нормальных алгоритмов Маркова, дополнительные символы (символы, не входящие в алфавит) не могут содержаться в исходном слове. Они могут входить в слово в процессе его преобразования. Поэтому, любое правило, содержащее в своей левой части дополнительный символ, к исходному слову не применимо.

Замечание 2. Правило, удаляющее дополнительный символ, должно быть применено лишь после того, как будет завершен процесс преобразования слова согласно условию задачи, т.е. после «прохода» символа через слово.

В нашем примере это происходит только тогда, когда становится неприменимым первое правило.

Замечание 3. Правило, удаляющее дополнительный символ, должно быть терминальным. Иначе процесс преобразования слова станет бесконечным.

Задача 2. Алфавит символов . Составить нормальный алгоритм Маркова, который выполняет инверсию (букву меняет на и наоборот).

Решение.

Сразу заметим, что алгоритм Маркова, состоящий из двух правил:

задачу не решает.

Эта задача не решается и с помощью алгоритма Маркова, состоящего из трех правил (обмен значений двух переменных с использованием дополнительной третьей переменной):

В случае алгоритмов Маркова этот метод не работает.

Для решения этой задачи необходимо действовать так же, как в предыдущей задаче (по пунктам 1-3 плана). Все эти действия реализуют нормальный алгоритм Маркова:

Посмотрим, как данный нормальный алгоритм Маркова преобразует входное слово :

Задача 3. Алфавит символов . Составить нормальный алгоритм Маркова, который удваивает последнюю букву в слове.

Решение.

Идея построения алгоритма аналогична рассмотренному в предыдущих примерах. Сначала вводим дополнительный символ (правило 6). «Прогоняем» его через слово без изменения слова (правила 1 и 2). После этого (справа от не осталось символов) удваиваем символ слева от (терминальные правила 3 и 4). Удаляем вспомогательный символ. Правило 5 необходимо для корректной обработки пустого слова. Согласно концепции нормальных алгоритмов Маркова, исходное слово может быть пустым, т.е. не содержать ни одного символа. В данном случае пустое слово нужно оставить без изменения.


Посмотрим, как данный нормальный алгоритм Маркова преобразует входные слова , и пустое слово:

Задача 4. Алфавит символов . Удвоить в слове все буквы, кроме последней.

Решение.

Идея алгоритма состоит в том, что символ «прогоняется» через слово с одновременным удваиванием в нем каждой буквы (правила 1 и 2). После этого удаляется вместе с последним символом строки (терминальные правила 3 и 4). Правило 5 необходимо для корректной обработки пустого слова. Эти этапы реализуются следующим нормальным алгоритмом Маркова:

Задача 5. Алфавит символов . Составить нормальный алгоритм Маркова, который удаляет из слова первую букву.

Решение.

В данном случае символ не надо «прогонять» через слово. Он будет удален с первой буквой слова. Задачу решает алгоритм Маркова, содержащий пять правил подстановки:

Задача 6. Алфавит символов . Составить нормальный алгоритм Маркова, который оставляет в слове только первую букву.

Решение.

Идея алгоритма состоит в том, чтобы удалить из слова вторую, третью и последующие буквы (правила 1-4). Эти правила удаляют второй символ после символа . При этом, символ находится слева от слова. Как только все буквы, кроме первой, будут удалены, преобразование слова завершается. Пятое терминальное правило удаляет вспомогательный символ.

Преобразуем с помощью алгоритма слова и :

Для нормальных алгоритмов разработана техника программирования, позволяющая осуществлять операции композиции алгоритмов, реализовывать операторы «если Ф, то выполнить F1, иначе F2», «пока Ф, выполнять F1, иначе F2». Следовательно, класс функций достаточно широк.

Теорема. Класс функций М, вычислимых по Маркову, совпадает с классом функций Т, вычислимых по Тьюрингу, и, следовательно, с классом частично рекурсивных функций Ч и с классом вычислимых функций Е.

Дата добавления: 2020-02-15 ; просмотров: 1994 ; ЗАКАЗАТЬ РАБОТУ

Правила построения алгоритма

Понятие алгоритма

Понятие алгоритма является центральным понятием информатики. Слово «алгоритм» произошло от имени узбекского математика аль-Хорезми, который еще в IX веке сформулировал правила выполнения арифметических действий. В современной математике и информатике термин алгоритм имеет следующие определения:

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

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

Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете па конкретного исполнителя.

Каждый исполнитель может выполнять команды только из некоторого строго заданного списка — системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. После вызова команды исполнитель совершает соответствующее элементарное действие.

В информатике универсальным исполнителем алгоритмов является компьютер.

Виды алгоритмов

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

Алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:

  • Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
  • Эвристический алгоритм (от греческого слова «эврика») — это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.
  • Линейный алгоритм — набор команд (указаний), выполняемых последовательно друг за другом.
  • Разветвляющийся алгоритм — алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
  • Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) Над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторому условию.
  • Вспомогательный (подчиненный) алгоритм (процедура) — алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм.

Алгоритм можно задать несколькими способами:

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

Блок-схема алгоритма

Задание алгоритмов с помощью блок-схем оказалось очень удобным средством изображения алгоритмов и получило широкое распространение.

Блок-схема алгоритма — графическое изображение алгоритма в виде связанных между собой с помощью стрелок (линий перехода) и блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия.

В таблице приведены наиболее часто употребляемые символы.

Символы блок-схемы
Название символа Обозначение и пример заполнения Пояснение
Процесс Вычислительное действие или последовательность действий
Решение Проверка условий
Модификация Начало цикла
Предопределенный процесс Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод Ввод-вывод в общем виде
Пуск-остановка Начало, конец алгоритма, вход и выход в подпрограмму
Документ Вывод результатов

Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно.

Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок «модификация» используется для организации циклических конструкций. (Слово «модификация» означает «видоизменение, преобразование»). Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.

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

Для примера приведем блок-схемы алгоритма нахождения максимального из двух значений:

Правила построения алгоритма

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

Первое правило — при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результата своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

Второе правило — для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т. е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти.

Третье правило — дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Точнее — из множества шагов.

Четвертое правило — детерминированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.

Пятое правило — сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.

Запись опубликована в рубрике Информатика с метками алгоритм, правила, программирование. Добавьте в закладки постоянную ссылку.

Свойства алгоритма

Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.

Определенность — каждое правило алгоритма должно быть четким, однозначным. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.

Результативность (конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.

Массовость — алгоритм решения задачи разрабатывается в общем виде, то есть он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.

Примеры составления алгоритмов

Определение 1.4. Под алгоритмизацией понимают процесс разработки алгоритма решения какой-либо задачи.

Для некоторых задач этот процесс достаточно прост, для других — требует определенных усилий, особенно в тех случаях, когда алгоритм должен удовлетворять наперед заданным условиям, например максимальному быстродействию решения задачи, минимальному требованию к объему памяти ЭВМ и др. В настоящем параграфе на примерах многих задач от простейших до относительно сложных изложены способы рационального составления алгоритмов. Задачи представлены в математической или почти в математической форме. При этом они подобраны так, что их решение не требует тех знаний, которые выходят за пределы курса математики общеобразовательных средних школ.

Опыт обучения программированию показывает, что студенты весьма часто пренебрегают составлением блок-схем алгоритмов. Желание быстрее написать программу порождает ощущение, что рисование блок-схемы как бы лишняя работа. Такой подход однако ошибочен и должен подавляться в самом начале обучения.

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

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

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

Задача 1.1. Даны два действительных числа а и Ь. Необходимо найти их сумму 5, разность Я, произведение Р и частное Н от деления а на Ь.

Алгоритм кажется очевидным: ввести в память ЭВМ числа а и Ь, выполнить вычисления 5 = а + Ь, Я = а — Ь, Р= а : Ь, Н = а/Ь и вывести на экран (принтер) полученные результаты. Однако такой алгоритм ошибочен для случая, когда Ь = 0. В этом случае чисто математически мы могли бы записать, что Н- а/Ь = со. Однако в компьютере операция деления на нуль не определена, вследствие чего на экране дисплея будет выведено сообщение «деление на нуль» и вычисление программы прервано. Поэтому проверка, равно ли Ь нулю, в алгоритме должна быть предусмотрена. Правильный алгоритм приведен на рис. 1.3. Ниже дана текстовая его форма.

Шаг 2. Вычислить Б = а + Ь, Я = а — Ь, Р= аЬ.

Шаг 3. Вывести Я, Р.

Шаг 4. Если Ь = 0, перейти к шагу 7.

Шаг 5. Вычислить Н = а/Ь .

Шаг 6. Вывести Н и перейти к шагу 8.

Шаг 7. Вывести Ь = 0, Н — СО.

Шаг 8. Остановиться.

Задача 1.2. Даны два действительных положительных числа а и Ь. Найти среднее арифметическое и среднее геометрическое этих чисел.

Как известно, среднее арифметическое чисел а, Ь определяется как ?= + Ь)/2, а среднее геометрическое как С =у[аЬ. Поэтому блок-схема алгоритма представлена на рис. 1.4. Текстовая его форма будет такой.

Шаг 1. Ввести а, Ь.

Шаг 2. Вычислить ?= (а + Ь)/2, С = 4аЬ.

Рис. 1.3. Алгоритм выполнения арифметических действий над действительными

Рис. 1.4. Алгоритм вычисления среднего арифметического и среднего геометрического двух чисел

Шаг 3. Вывести (7. Шаг 4. Остановиться.

В приведенном алгоритме записана операция среднего геометрического (7 = 4аЬ. Казалось бы, следовало вначале вычислить значение с=аЬ, а затем, используя, например, алгоритм Ньютона (см. рис. 1.1), вычислить (7. Однако в наборе стандартных программ компьютера имеется программа, вычисляющая квадратный корень из положительного числа. Поэтому при соответствующем обращении к этой программе она и вычислит (7.

Задача 1.3. Даны два действительных числа а и Ь. Определить, какое из чисел большее или они равны. Алгоритм решения задачи изображен на рис. 1.5.

Текстовая его форма такая.

Шаг 2. Если а = Ь, перейти к шагу 6.


Шаг 3. Если а > Ь, перейти к шагу 5.

Шаг 4. Вывести Ъ> а и перейти к шагу 7. Шаг 5. Вывести а> Ь и перейти к шагу 7. Шаг 6. Вывести а = Ь.

Шаг 7. Остановиться.

Вычислить значение функции 1 —х, если* 3 . если 2 2 , если 1 2 , еслих > 3.

Алгоритм вычисления ? представлен на рис. 1.6. Текстовая его форма следующая.

Шаг 2. Если х 2 и перейти к шагу 9.

Шаг 6. Вычислить ? = V1 + х 3 и перейти к шагу 9.

Шаг 7. Вычислить ?= 1/х 2 и перейти к шагу 9.

Шаг 8. Вычислить ?- 1 — х.

Шаг 9. Вывести х, ?.

Шаг 10. Остановиться.

Задача 1.5. Составить алгоритм вычисления корней квадратного уравнения ах 2 + Ьх + с = Ос действительными коэффициентами а, Ь, с ф 0, когда а ф 0, Ь ф0, с ф0.

Как известно, в зависимости от знака дискриминанта с1 = Ь 2 — 4 ас квадратное уравнение ах 2 + Ьх + с = Ос действительными коэффициентами а, Ь, сф 0 может иметь три типа корней: разные действительные корни, если с1> 0, равные действительные корни, если с!= 0, и комплексные сопряженные корни, если с! 24ас, к = а + а, к = -Ь/к.

Шаг 3. Если 0, перейти к шагу 6.

Шаг 5. Положить х, = к и перейти к шагу 10.

Шаг 6. Вычислить g = 4(4, г = g/h, хх = к + г, х2 = к — г и перейти к шагу 9.

Шаг 7. Вычислить g = у<4, г = g/h.

Шаг 8. Вывести: «Корни комплексные х, = /:+/>, х2 = /:-/>» и перейти к шагу 11.

Шаг 9. Вывести: «Корни действительные» х,, х2 и перейти к шагу 11.

Шаг 10. Вывести: «Корни, равные х, = х2» х,.

Шаг 11. Остановиться.

Большинство приведенных алгоритмов содержат так называемые разветвления, т. е. места в блок-схемах, где вычисления направляются по разным путям. Эти места определяются блоками сравнения величин. Из каждого блока имеется два выхода, один из которых соответствует тому случаю, когда условие сравнения выполняется («да»), другой — случаю, когда оно не выполняется («нет»). Такие алгоритмы называются алгоритмами с разветвляющейся структурой.

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

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

В циклах итерационного типа, в которых число повторений наперед неизвестно, их прекращение (выход из цикла) осуществляется при выполнении некоторого условия. Обычно это условие формулируется, например, так: выполнять повторения до тех пор, пока х с, повторения вычислений не будет вообще, для второй всегда выполнится хотя бы один цикл. Все арифметические циклы — это циклы с предусловием.

Задача 1.6. Дан ряд чисел х15 х2. х,-, . хп. Найти их сумму 5.

Так как сумма 5 = х, + х2 + . + х,- + . + хп и суммирование чисел выполняется последовательно, т. е. к найденной сумме 5М добавляется х,- число, то вычисление 5, = 5М + х,- повторяется п — 1 раз, если положить 5М х. Поэтому алгоритм вычисления суммы будет таким, как изображен на рис. 1.8. Текстовая его форма включает следующие действия.

Шаг 2. Положить 5=х,.

Шаг 3. Положить / = 2.

Шаг 4. Если /> п, перейти к шагу 7.

Шаг 5. Положить 5=5+ х,-.

Шаг 6. Положить / = / + 1 и вернуться к шагу 4.

Шаг 7. Вывести 5.

Шаг 8. Остановиться.

Рис. 1.8. Алгоритм вычисления суммы п чисел

В этом алгоритме роль счетчика циклов отводится переменной /, которая изменяется с шагом 1. Если бы требовалось вычисление суммы чисел х>, . хп через одно число, то очевидно, что шаг изменения переменной / должен быть взят равным 2, а начальное ее значение 3. Таким образом, в четвертом блоке схемы алгоритма следовало бы указать /= 3, а в седьмом / = /’ + 2.

Задача 1.7. Составить алгоритм вычисления функции п («л-факториал»). Как известно, п — это произведение п натуральных чисел 1 • 2 • 3 •. • п. При этом принимают, что 1! = 1. Поэтому вычисление значения п можно рассматривать как последовательное повторение операции умножения предшествующего значения факториала Т 7 на очередное натуральное число. Алгоритм вычисления п приведен на рис. 1.9.

Его текстовая форма такая.

Шаг 2. Положить Р= 1.

Шаг 3. Вычислить /= 2.

Шаг 4. Если / > п, перейти к шагу 7.

Шаг 5. Положить Г- Я.

Шаг 6. Положить /= /+ 1 и вернуться к шагу 4.

Шаг 7. Вывести Т 7 .

Шаг 8. Остановиться.

Аналогичным образом можно построить алгоритмы вычисления значений 2″, а п , где а — вещественное, а п — целые числа.

Задача 1.8. Составить алгоритм вычисления выражения к = = ^2 + ^2

+ ^2 + . + л/2 . Нетрудно видеть, что если в качестве

начального значения взять к = а/2 , то повторяющимся действием будет вычисление выражения V2 + к. Поэтому алгоритм решения этой задачи имеет вид, изображенный на рис. 1.10. Его текстовая форма такая.

Шаг 2. Вычислить к = а/2.

Шаг 3. Положить /= 2.

Шаг 4. Если /> п, перейти к шагу 7.

Шаг 5. Вычислить к = л/2 + к.

Шаг 6. Положить /’=/’+ 1 и вернуться к шагу 4. Шаг 7. Вывести к.

Шаг 8. Остановиться.

Задача 1.9. Составить алгоритм вычисления выражения S = = sin л: + sin 2 * . + sin»*.

Если взять начальное значение суммы S = s’mx, то повторяющимся действием будет 5 + 5sin*. Алгоритм, вычисляющий указанную сумму, представен на рис. 1.11. Его текстовая форма такая.

Шаг 1. Ввести п, х.

Шаг 2. Вычислить 5 = sin*.

Шаг 3. Положить / = 2.

Шаг 4. Если /> п, перейти к шагу 7.

Шаг 5. Вычислить S =S + ^sinx.

Шаг 6. Положить / = / + 1 и вернуться к шагу 4. Шаг 7. Вывести S.

Шаг 8. Остановиться.

Задача 1.10. Составить алгоритм вычисления среднего квадратического п действительных чисел ху, х2, . хп.

Известно, что средним к вадратическим п действительных

чисел является величина 5* = Л -(х? + х + . + х 2 п. Поэтому ал-

горитм будет таким (рис. 1.12). Его текстовая форма включает следующие действия.

Шаг 2. Положить / = 1.

Шаг 3. Если /> п, перейти к шагу 7.

Шаг 4. Положить ^ = 0.

Шаг 6. Положить /=/-+- 1 и вернуться к шагу 3.

Шаг 8. Вычислить =д/^7.

Шаг 9. Вывести Шаг 10. Остановиться.

Задача 1.11. Составить алгоритм вычисления числа сочетаний п чисел по т для п > т > 0.

Число сочетаний из п по т, обозначаемое С» ! , вычисляется

по известной формуле С'» =

. Казалось бы построение

алгоритма не вызывает проблем: вычислить значения п,

  • (п — т), т, используя для этого алгоритм (см. рис. 1.9), а затем реализовать формулу для определения С”’. Такой подход в общем требует выполнения п — 1 + (пт — 1) + т — 1 = 2/7-3 циклов. Имеется возможность сконструировать алгоритм вычисления значения С;, который будет выполнять всего т циклов. Тогда, в худшем случае, когда т всего лишь на единицу меньше п, число циклов будет примерно в 2 раза меньше 2/7. Этот алгоритм основан на использовании рекуррентного сотношения для вычисления С»‘.
  • ?

Рис. 1.12. Алгоритм вычисления среднего квадратического

п действительных чисел

Для построения алгоритма запишем общее выражение для вычисления С» ! , которое будем вычислять в цикле. Согласно рекуррентному соотношению при т = 0 число сочетаний С^ 1 = С 1 =

При т = і число со-


Оно записывается так: С =

С’”, Сп = п и позволяет вычислять сочетания последовательно С =п, С 2 = ——-С’п,

С’п. Так как в итоге необходимо получить зна

чение С»‘ т т — 1, перейти к шагу 11.

Шаг 8. Положить /= /+ 1 и вернуться к шагу 6.

Шаг 9. Положить С= 1 и перейти к шагу 11.

Шаг 10. Положить С=п.

Шаг 11. Вывести С.

Шаг 12. Остановиться.

Заметим, что в приведенной блок-схеме предусмотрен контроль правильности ввода чисел т так, чтобы п> т.

Задача 1.12. Сконструировать алгоритм вычисления многочлена (полинома) Рп(х) степени п для некоторого действительного значения х

Используя традиционную форму представления многочлена рп(х) =апх п + ап_хх п

было бы изобразить, как на рис. 1.14.

Рис. 1.14. Алгоритм вычисления полинома, представленного

в канонической форме

В этом алгоритме в цикле используются две операции умножения и одна операция сложения. Существует, однако, другой более быстрый способ вычисления значения многочлена. Он основан на использовании схемы Горнера, согласно которой полином представляется следующим образом:

Например, для п = 4 он имеет такой вид:

Алгоритм, вычисляющий полином по схеме Горнера, приведен на рис. 1.15. В цикле он выполняет всего одну операцию умножения.

Задача 1.13. Разработать алгоритм табулирования функции у = /(х) на интервале [а, Ь], а я, перейти к шагу 10.

Шаг 7. Положить х = х + Ах, вычислить у = Дх).

Шаг 8. Вывести х, у.

Шаг 9. Положить /= /’+ 1 и вернуться к шагу 6.

Шаг 10. Остановиться.

Алгоритм решения задачи с применением итерационного цикла приведен на рис. 1.17.

В этом алгоритме шаги 7, 8 проверяют, совпадает ли последняя точка табуляции функции со значением конца интервала Ь.

Задача 1.14. Составить алгоритм поиска наибольшего общего делителя (НОД) двух целых чисел a, b и наименьшего общего кратного (НОК) этих чисел.

Как известно, НОД чисел a, b — такое наибольшее целое число, которое делит эти числа без остатка. Наименьшим общим кратным целых чисел а, b является целое число, которое делится на а и Ь. Если известен НОД, то НОК вычисляется по следующей формуле: НОК (а, b) = ab/Oj(a, b). Поэтому прежде чем вычислять НОК, необходимо найти НОД.

Существует несколько алгоритмов вычисления НОД. Приведем простейший из них, который принадлежит древнегреческому математику Евклиду. Он заметил, что НОД (а, b) равен НОД ((аb), Ь), где а > Ь. Поэтому суть его алгоритма сводится к последовательному вычитанию из большего числа меньшего до тех пор, пока эти числа станут равными между собой. Алгоритм приведен на рис. 1.18 и содержит цикл итерационного типа.

Текстовая форма алгоритма вычисления НОД, НОК следующая.

Шаг 1. Ввести а, Ь.

Шаг 2. Положить и = a, v = b.

Шаг 3. Если а = Ь, перейти к шагу 7.

Шаг 4. Если а> Ь, перейти к шагу 6.

Рис. 1.17. Алгоритм табулирования функции /(х) с использованием

Рис. 1.18. Алгоритм вычисления наибольшего общего делителя чисел а, Ь и наименьшего их кратного

Шаг 5. Положить х = а, а = Ь, Ь = х.

Шаг 6. Положить х = а — Ь, а = х и вернуться к шагу 3.

Шаг 7. Положить НОД = а.

Шаг 8. Вычислить НОК = и • г/НОД.

Шаг 9. Вывести а, Ь, НОД, НОК. Шаг 10. Остановиться.

Задача 1.15. Разработать алгоритм вычисления значения цеп-

ной дроби У =—для х ф 0.

Как следует из записи дроби, последним в ней делителем яв-

ляется выражение С=х + —, значение которого при задан- ном х легко может быть найдено. Предпоследним делителем яв-

ляется выражение С = х +

х щим ему делителем является выражение С =х + — , где С —

найденное перед этим значение делителя. Таким путем может

быть найдено значение делителя С =х + — , а затем значение дроби У = —.

Очевидно, что повторяющимся действием в этой задаче является поиск очередного делителя. Учитывая, что 2 = 2 1 , а 256 = 2 8 , всего необходимо найти восемь делителей. Исключая последний делитель, всего получаем семь повторяющихся действий. На основании изложенных рассуждений конструируем алгоритм, вычисляющий заданное выражение (рис. 1.19). Его текстовая форма такая.

Шаг 2. Положить а = хх, Ь = 256.

Шаг 4. Положить і = 7.

Шаг 5. Если і min, перейти к шагу 8.

Шаг 7. Положить min = ак, j = к.

Шаг 8. Положить к= к+ 1.

Этот алгоритм в худшем случае, т. е. когда число не обнаружено, выполняет 2п сравнений. Вместе с тем есть алгоритм, который при п > 8 заметно сокращает это число, а следовательно, и время поиска. Улучшенный алгоритм приведен на рис. 1.22. Уменьшение количества сравнений достигается за счет исключения постоянных сравнений / с п, характерных для первого алгоритма. Выход из цикла осуществляется либо когда а, = Ь, либо когда на (п+ 1)-м повторении обнаружится число Ь, записанное в (п + 1)-й ячейке массива.

Последние две задачи относят к задачам обработки массивов — наборов данных одного вида — чисел или символов. В программировании различают массивы одномерные и многомерные. Одномерный массив образуют последовательные его элементы. Место элемента в массиве определяется его номером — индексом, представляющим собой положительное число. Рассмотренные последовательности чисел а., аъ

Ь являются одномерными массивами.

Двумерные массивы — это прямоугольные таблицы данных, состоящие из заданного количества строк и колонок (столбцов). В математике такие таблицы называются матрицами и весьма широко используются как непосредственно при математических вычислениях, так и в программировании. Элемент матрицы размещается на пересечении строки и столбца и идентифицируется двумя индексами: номером строки, например /, и номером столбца, например у. Если матрица содержит т строк и п столбцов, всего элементов этой матрицы тп и а] произвольный ее элемент. Матрица, содержащая т строк и т столбцов, называется прямоугольной.

В квадратной матрице выделяют главную и побочную диагонали. Матрица А = ац размером т х п, т. е. содержащая т строк

и п столбцов, т = п, имеет вид:

Главную диагональ матрицы образуют элементы аи, а22, . атп, т. е. элементы, лежащие на прямой, проведенной слева направо от элемента ап к элементу атп.

Побочную диагональ образуют элементы матрицы а1п, а2п_х, . ат1, лежащие на прямой, проведенной от элемента а1п к элементу ат<, т. е. справа налево.

Элементы матрицы А, лежащие справа и вверху от главной диагонали, образуют верхнюю треугольную матрицу. Элементы, лежащие слева внизу от главной диагонали, образуют нижнюю треугольную матрицу.

Матрица называется симметричной, если элементы, симметричные относительно главной диагонали, равны между собой, т. е. а и = й/ ( .

Одной из важнейших задач обработки одномерных массивов является их сортировка — расположение элементов массивов в определенном порядке. Чаще всего рассматривается упорядочение элементов числовых массивов по возрастанию или убыванию. По статистическим данным, примерно 25 % времени работы ЭВМ расходуется на сортировку данных, потому что отсортированные данные обрабатывать значительно проще. Когда элементы массива отсортированы, их быстрее найти, обновить, исключить из массива и т. п.

Существует целый ряд алгоритмов сортировки. Среднее время их работы или временная сложность лежит в пределах от 0(п 2 /4) до 0(ппп), где п — число элементов массива. К сожалению, нет алгоритма сортировки, который был бы наилучшим в любом случае.

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

Рассмотрим эту сортировку на массиве целых чисел

    71 27 412 81 59 14 273 87, который требуется упорядочить по возрастанию. Первым сортируемым элементом массива является второй элемент — число 27. Образно говоря, «вынимаем» его из массива, т. е. освобождаем место для будущего сдвига чисел вправо, и сравниваем второй элемент (число 27) с первым элементом (число 71). Так как 27 71, а 71 > 21, оставляем число 412 на своем месте, т. е. получаем прежний массив

27 71 412 81 59 14 273 87.

Выбираем четвертый элемент массива — число 81. Запоминаем его и сравниваем с предшествующим элементом — числом 412. Так как 81 59, сдвигаем его на одну позицию вправо. Нетрудно видеть, что процесс сравнения и сдвига элементов закончится на числе 27. В результате получим

27 59 71 81 412 14 273 87.

Шестым элементом массива является число 14. Путем сравнения его с предшествующими элементами и сдвигов их вправо получим массив

14 27 59 71 81 412 273 87.

Выполнив описанные действия с седьмым и восьмым элементами массива, получим отсортированный список

14 27 59 71 81 87 273 412.

Задача 1.18. Разработать алгоритм сортировки вставками.

Согласно изложенному методу сортировки общим повторяющимся действием является выбор очередного сортируемого элемента и его запоминание. Элементы выбираются, начиная со второго и заканчивая последним п-м элементом массива. Эти действия составят внешний цикл алгоритма. Внутренний цикл алгоритма образуют действия сравнения и, если необходимо, сдвига элементов, а также его вставки в необходимую позицию массива. Поэтому алгоритм, реализуемый рассматриваемым методом, будет иметь такой вид (рис. 1.23). Его текстовая форма следующая.

Шаг 2. Положить / = 2.

Шаг 3. Положить к = я,,

Шаг 4. Положить у = /’- 1.

Шаг 5. Если к > ар перейти к шагу 8.

Шаг 6. Если у 0 в приведенной блок-схеме необходима для того, чтобы при сравнении сортируемого элемента к с предшествующими ар я-_,, я, не выйти за пределы массива. Иначе алгоритм не будет определен. В заключение отметим, что сортировка вставками согласно [7] достаточно эффективна для массивов с максимальным количеством элементов п 3/2 ), и быстрой сортировке, средняя сложность которой 0(1п(я)). Как правило, такая сортировка применяется для массивов с числом элементов п > 1000.

В тех случаях, когда в некотором массиве постоянно осуществляется поиск элементов, этот массив предварительно сортируется и в дальнейшем поиск осуществляется в упорядоченном

Рис. 1.23. Алгоритм сортировки элементов массива вставкой

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


Суть бинарного поиска следующая. Пусть задан упорядоченный по возрастанию массив чисел ах, а2, ап ап и число Ь. Требуется найти элемент массива ак, равный Ь, или сообщить, что такого элемента в массиве нет. Обозначим первый индекс массива /, а последний и. Тогда индекс у числа ар стоящего примерно в середине массива, может быть найден по выражению у = |(/ + и)/2_|, где символы |_ ] определяют целую часть числа (/ + и)/2. Если

я- = Ь, процесс поиска завершен. Если же Ь ар то по той же причине число следует искать в подмассиве яу+1, . ап. Таким образом, в результате выбора числа а] и сравнения его с числом Ь можно перейти к поиску в массиве с числом элементов, меньших в 2 раза, чем п. Далее процесс выбора элемента я. осуществляется в одном из подмассивов, сокращая поиск в массиве с числом элементов, меньших в 2 раза, чем в подмассиве. Этот процесс выбора а] и деления очередного массива пополам продолжается до тех пор, пока не будет найдено заданное число либо установлено, что его в массиве нет. Описанный процесс продемонстрируем на поиске элемента Ь = 59 в следующем массиве

14 27 59 71 81 87 273 412 501.

Массив содержит девять элементов, поэтому у = |_(1 + 9)/2_| =

= 5. Элемент с индексом 5 — это а5 = 81. Сравниваем его с Ь = 59. В результате переходим к поиску в массиве 14 27 59 71 (/= 1, и =у — 1 = 5 — 1 = 4). Теперь вычисляем индекс у = |_(1 + 4)/2_| = 2.

Элемент с индексом 2 — это а2 = 27. Сравниваем его с Ь = 59. В результате переходим к поиску в массиве 59 71 (/=у+1 =

= 2+1 = 3, и = 4). Вычисляем индекс у = |_(3 + 4)/2_| = 3. Элемент

с индексом 3 — это я3 = 59. Сравниваем его с Ь = 59 и устанавливаем, что это искомый элемент массива.

Теперь рассмотрим случай, когда элемент Ь= 12, т. е. он не принадлежит массиву. Первый индекс у = 5 и мы переходим к поиску в массиве 14 27 59 71 (/ = 1, и = 4). Второй индекс у = 2, что дает очередной массив поиска 14 27 (/= 1, и = 2). Третий индекс поиска у = 1(1 + 2)/2 I = 1 и мы переходим к массиву поиска 14

(/ = 1, и = 0). Однако в массиве нет элемента с индексом и = 0. Это означает, что мы проверили весь массив и не нашли элемента я;= Ь. Таким образом, можно сделать вывод, что признаком отсутствия элемента в массиве служит неравенство и х — х — 2 = 0, и известно, что его корень принадлежит интервалу [а, Ь. Требуется найти значение этого корня.

В общем виде уравнение может быть записано как /(х) = 0, где Дх) — непрерывная функция, рассматриваемая на интервале [а, Ь]. Поскольку решение уравнения, т. е. его корень, х е [а, Ь] обращает уравнение в тождество, то левая часть равенства /(х) = 0 в точке х е а,Ь] должна быть равна нулю. С геометрической точки зрения это означает, что функция /(х) в точке х пересекает ось абсцисс. Эту точку пересечения и необходимо найти.

Для этого поступаем следующим образом. По выражению IV= (а + Ь)/2 находим координату IVсередины отрезка [а, Ь. Если Дх) = 0, то корень уравнения х= IV найден. Если /(а)/(ВО > 0, т. е. /(а) и /(ВО одного знака, корня на интервале нет (рис. 1.25), и мы переходим к его поиску на интервале [IV, Ь], который вполовину короче исходного интервала [а, Ь]. Если /(а)/(ВО 0, мы сокращаем интервал поиска ровно вдвое. В результате после п таких действий получим интервал п, Ьп], которому принадлежит корень уравнения, в 2″ раз меньший исходного интервала [а, Ь, т. е. ап — Ьп = а — ^/2″. Приняв в качестве точности вычисления корня а длину интервала |ап — Ьп, можно определить, что для получения этой точности необходимо сделать п = па — Ь|/е шагов. Описанный метод по-

Рис. 1.25. Иллюстрация к уточнению корня методом половинного деления

иска корня получил название метода половинного деления, или дихотомии.

Задача 1.20. Разработать алгоритм уточнения корня уравнения /(х) = 0 методом дихотомии.

Метод предполагает, что задан интервал а, Ь, которому принадлежит корень, функция /(х) = 0 непрерывна и ограничена на этом интервале и f(a) f(b) а + , w = f(x).

Шаг 4. Если w = 0, перейти к шагу 10.

Шаг 5. Если uw> 0, перейти к шагу 7.

Шаг 6. Положить b = x, v=w и перейти к шагу 8.

Шаг 7. Положить а = х, u=w.

Шаг 8. Если а — Ь > с, вернуться к шагу 3.

Шаг 9. Положить х = а — Ь.

Шаг 10. Вывести х, s.

Шаг 11. Остановиться.

При решении различных задач часто приходится использовать значения элементарных функций, таких как sin (х), cos (х), log (х), In (х), е х и др. Для того чтобы облегчить процесс вычис-

Рис. 1.26. Алгоритм вычисления корня уравнения /(х) = 0 методом дихотомии

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

дующим бесконечным рядом е х = 1 + X +-+

Для функций sin (х), cos (х) соответственно имеем:

В каждом из указанных разложений точность представления той или иной функции определяется числом членов ряда. Чем больше это число, тем точнее вычисляется функция при одном и том же х. Поэтому для вычисления значения функции с заданной точностью с поступают следующим образом. Вычисляют и суммируют члены ряда до тех пор, пока очередное слагаемое не станет по модулю меньше 8.

Звдача 1.21. Составить алгоритм вычисления функции зт(х) с точностью 8 при помощи разложения ее в ряд.

Из формулы, которая приближенно представляет функцию бш(х) в виде бесконечного ряда, следует, что алгоритм вычисления значения 8ш(х) с заданной точностью е будет включать повторяющиеся действия вычисления очередного члена ряда, суммирования членов ряда и изменения знака перед соответствующим членом ряда. Нетрудно видеть, что каждый очередной член ряда Уп и может быть вычислен по рекуррентной формуле Уп =

у хх2 _ * 3 у _у

Знаки членов ряда меняются поочередно, если начинать с Ух.

Поэтому начальными установками алгоритма будут такие ?=х, 6’ = х, Z= хх, а = —1. В цикле будем вычислять очередной

член ряда ? =— и прибавлять его к предшествующей

сумме с соответствующим знаком. Блок-схема алгоритма приведена на рис. 1.27. Его текстовая форма дана ниже.

Рис. 1.27. Блок-схема вычисления значения функции 8Іп(х)

Шаг 5. Вычислить 6’= 5 + у.

Шаг 6. Если у а 2 а

Шаг 1. Шаг 2. Шаг 3.

Положить у = х, 5 = х, Z= хх, а = Положить п= 1.

Вычислить к= 2п, У =

Как было сказано раньше, след матрицы — это сумма эле-

ментов ее главной диагонали, т. е. Я, — ^аи. Поэтому алгоритм

определения следа сводится к вычислению суммы Блок-схема этого алгоритма приведена на рис. 1.28.

Вместе с тем есть способ построить более эффективный алгоритм решения этой задачи. Он основан на вычислении адреса очередного диагонального элемента матрицы А не в двумерном, а в одномерном массиве.

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

Через индексы строк и столбцов /, у номер любого элемента в линейном массиве вычисляется по формуле х = (/ — 1)я+/ Например, номер элемента а22 определяется так (2 — 1)3 + 2 = 5. Таким образом, чтобы выбрать какой-либо элемент из линейного

Рис. 1.28. Алгоритм вычисления следа матрицы А

массива, необходимо вычислять его номер по выражению А / ‘= (/— 1 )п + у, т. е. выполнить три арифметические операции.

В то же время можно видеть, что номер очередного диагонального элемента в линейном массиве отличается от номера предшествующего диагонального элемента на постоянную величину к = п + 1. Например, номер а22 — 5 равен номеру ап — 1, т. е. 1 +4 = 5. Поэтому в линейном массиве очередной диагональный элемент определяется по номеру / = / + к. В результате его вычисление требует выполнить вместо трех всего одну арифметическую операцию, что в целом приводит к уменьшению объема вычислений и повышению быстродействия алгоритма. Блок-схема этого алгоритма приведена на рис. 1.29.

Задача 1.23. Разработать алгоритм вычисления суммы элементов побочной диагонали квадратной матрицы А.

В качестве примера рассмотрим матрицу с тремя строками и

тремя столбцами А =

Рис. 1.29. Эффективный алгоритм вычислени следа матрицы А

. Через элементы побочной

диагонали этой матрицы для их выделения проведена прямая линия. Первый индекс диагональных элементов — это номер строки /, второй, как нетрудно видеть, вычисляется по выражению у = п + 1 — /’, где к — п + 1. Поэтому блок-схема алгоритма, решающего эту задачу, будет иметь вид, представленный на рис. 1.30. Его текстовая форма приведена ниже.

Рис. 1.30. Блок-схема алгоритма вычисления суммы элементов побочной

диагонали квадратной матрицы А

Шаг 1. Ввести п, элементы матрицы А.

Шаг 2. Положить ? = 0, / = 1, к= п + 1.

Шаг 4. Положить / = /’ + 1.

Шаг 5. Если / а п

. Нетрудно видеть, что первый индекс эле

мента верхней треугольной матрицы — это индекс строки /. Второй индекс определяется по выражению у = / + 1. Поэтому блок-схема алгоритма будет иметь вид, представленный на рис. 1.31. В алгоритме имеется два цикла: один внешний и второй внутренний. Такие циклы называются вложенными. Текстовая форма алгоритма приведена ниже.

Шаг 1. Ввести п, элементы матрицы А.

Шаг 2. Положить Ат = 0, /’= 1.

Шаг 3. Положить у = / + 1.

Шаг 5. Положить у =у + 1.

Шаг 6. Если у а 13

нали. Пусть задана исходная матрица А =

Согласно определению транспонированная к ней матрица

будет иметь такой вид: А,. =

. Мы видим, что в ней

Шаг 5. Положить у =у + 1.

Второй его элемент

Третий элемент столбца

«з Ь = а31Ь1 + а32 Ь2 + т . Блок-схема алгоритма приведена на рис. 1.33. Текстовая форма дана ниже.

Шаг 1. Ввести п, т, элементы Ли Ь.

Шаг 2. Положить /= 1.

Шаг 3. Положить у = 1, А* = 0.

Шаг 4. Вычислить А* = 5* + а^Ьг

Шаг 5. Положить у =у + 1.

Шаг 6. Если у а х


методом исключения Гаусса.

Суть метода Гаусса состоит в том, что сначала исключается первое неизвестное х, из всех уравнений, кроме первого. Затем исключается второе неизвестное х2 из всех уравнений, кроме первых двух. Последним исключается п — 1 неизвестное х„_, из последних двух уравнений. В результате получают систему уравнений треугольного вида

из которой сначала находят неизвестное хп = Ь’п1а’пп, затем методом подстановки значения хп в предшествующее уравнение очередное неизвестное потом

и заканчивают этот процесс вычислением значения

Таким образом, метод содержит два этапа: последовательное исключение неизвестных и последовательное их вычисление. Рассмотрим технику исключения неизвестных на примере трех уравнений с тремя неизвестными. Для этого систему уравнений

представим в матричном виде АХ = В, где А — матрица коэффи-

циентов уравнений А =

ры-столбцы неизвестных и правых частей уравнений. Далее рас

смотрим расширенную матрицу А’ =

В первом столбце матрицы А’ найдем наибольший по модулю, не равный нулю элемент. Если ненулевого элемента в столбце нет, рассмотренная система уравнений не имеет решений. Если наибольший ненулевой элемент содержится в любой строке матрицы А’, кроме первой, поменяем местами эту строку матрицы А’ с первой ее строкой. Этими действиями осуществляется контроль совместности системы уравнений и уменьшается чувствительность метода к округлению чисел, сопровождающему вычисления на ЭВМ.

Для того чтобы исключить первое неизвестное х, из второго уравнения системы, вычислим множитель т2 = ап, умножим первую строку матрицы А’ на этот множитель и вычтем результат умножения из второй строки А’.

— ^з«22 )*2 “(«33 — ^3«2з)*3 = ^3 — т Ъ ^2 •

из которой методом последовательной подстановки получим значения неизвестных

Обобщая изложенное, можно сказать, что алгоритм должен выполнить п — 1 действие по исключению п — 1 неизвестных. Если к — номер исключаемого переменного, то необходимо в каждом из этих действий сделать от / = к + 1 до п вычитаний уравнений. При этом каждое вычитание осуществляется выполнением у = к + 1 до п арифметических действий. Кроме этого, при каждом исключении переменной необходимо найти максимальный элемент в соответствующем столбце матрицы А. И последнее, что нужно сделать, вычислить значения неизвестных хп, . х,. Таким образом, общая укрупненная блок-схема алгоритма представляется такой (рис. 1.35).

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

Поиск индекса максимального элемента в ряду чисел рассмотрен в задаче 1.16. В данном случае он ничем не отличается от метода, который изложен там. Полагаем, что максимальный элемент первый в столбце Ли 1= к. Затем в цикле сравниваем с этим элементом остальные элементы этого столбца и тем самым выделяем наибольший элемент и устанавливаем его индекс. Алгоритм поиска минимального элемента в столбце матрицы А приведен на рис. 1.36. Там же показан фрагмент проверки условий совместности системы уравнений. На рис. 1.37 показана блок-схема алгоритма вычитания строк.

Алгоритм определения значений переменных хп, хп_х, . х, последовательно реализует формулы, по которым вычисляются эти переменные хп = Ьппп, хя_, = п_хап_ххп)/ап_х . Его блок-схема приведена на рис. 1.38. Ниже приведена текстовая форма полного алгоритма.

Шаг 1. Ввести п, А, В.

Шаг 2. Положить к= 1.

Шаг 3. Положить 1= к, / = к + 1.

Шаг 5. Положить / = / + 1, если / 1, вернуться к шагу 22. Шаг 28. Вывести х,, . л. и перейти к шагу 30.

Шаг 29. Вывести «Система несовместна».

Шаг 30. Остановиться.

Задача 1.29. Сконструировать алгоритм записи последовательности чисел 1, 2, 3, . 49 в квадратную матрицу А с 7 строками и 7 столбцами по спирали (рис. 1.39).

Рис. 1.39. Схема записи в матрицу А последовательности чисел

Самое простое решение этой задачи следующее. Двигаясь по спирали, составить две последовательности индексов элементов матрицы А. В первую последовательность занести значение индексов строк 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, . во вторую последовательность — значения индексов столбцов 1, 2, 3, 4, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, . . Затем организовать цикл от 1 до 49, в котором последовательно выбирать числа из двух последовательностей — индексы соответствующего элемента матрицы А и по этим индексам на место элемента матрицы а] заносить значение управляющей переменной цикла к.

Пусть / — строчные индексы матрицы А, у — индексы ее столбцов, к — управляющая переменная цикла. Пусть далее 4 — к-е значение строчного индекса, а ]к — к-е значение ее столбцевого индекса. С учетом этих обозначений алгоритм будет иметь вид, показанный на рис. 1.40.

Рис. 1.40. Алгоритм записи чисел натурального ряда 1, . 49 в матрицу А

Недостаток этого алгоритма заключается в том, что сначала необходимо составить последовательности индексов, отображающих движение по спирали, а затем программировать.

Можно предложить другой алгоритм, в котором записываются только начальные и конечные индексы сторон спирали. Например, для первых четырех ее сторон получим:

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

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

Задача 1.30. Рассмотрим шахматную доску и два положения коня на ней (рис. 1.41). Возможные ходы коня показаны стрелками и пронумерованы. Конь слева (поле (1,2)), не выходя за пределы доски, может пойти только на три поля. Конь справа (поле(5,6)) может пойти на восемь полей, что является макси-

мальным количеством допустимых ходов коня из одного ПОЛЯ. Маршрутом коня называется последовательное перемещение коня по полям доски такое, что он не попадает на одно и то же поле дважды. Конечной точкой маршрута является поле, с которого нет допустимого хода либо по причине выхода коня за пределы доски, либо по причине повторного попадания на какое-либо поле маршрута. Составить алгоритм, строящий маршрут коня, возможно наибольшей длины.

Очевидно, что наибольшая длина маршрута — это 63 поля шахматной доски. Попытаться найти такой маршрут можно путем перебора всех маршрутов коня, начинающихся из всех 64 полей. Поэтому, кроме процедуры построения маршрута, алгоритм должен содержать цикл из 64 повторений задания исходного поля.

Для того чтобы построить маршрут коня, начинающийся с любого поля доски, кроме учета ограничений, обеспечивающих допустимый ход, необходимо определить стратегию выбора очередного хода. Возможной такой стратегией может быть первый допустимый ход коня, если просматривать его ходы по часовой стрелке (см. 2-е положение коня, рис. 1.41). В том случае, когда допустимого хода нет, маршрут считается законченным.

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

Выход коня за пределы доски может фиксироваться путем обрамления доски двумя полями, в которые записано произвольное число больше нуля, например 66. На рис. 1.42 приведены исходные данные о доске и показано начало маршрута коня из поля (7, 8).

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

  • 1) инициализацию полей обрамления доски, т. е. запись в эти поля числа 66 или любого другого, например 99;
  • 2) инициализацию начала цикла по всем маршрутам с указанием начальной длины маршрута / = -1 для выбора лучшего маршрута;

Рис. 1.42. Исходные данные о доске и начало маршрута коня

  • 3) инициализацию полей доски, т. е. запись в эти поля числа 0;
  • 4) построение маршрута коня, запоминание его длины и выделение лучшего текущего маршрута;
  • 5) вывод лучшего маршрута и его длины.

Укрупненная блок-схема алгоритма поиска лучшего маршрута коня приведена на рис. 1.43.

На рис. 1.44 приведена блок-схема алгоритма инициализации верхнего обрамления доски с учетом того, что вся доска с обрамлением представляет собой квадратную матрицу /) = 11 I*-:

Рис. 1.44. Блок-схема алгоритма инициа- Рис. 1.45. Блок-схема алгоритма

лизации верхнего обрамления доски инициализации левого и правого

Блок-схема инициализации непосредственно шахматной доски реализует процедуру занесения в двумерный массив /) = dyW с индексами /5=3, 1Р = 10, у5=3, ]р = 10 значений с1 Она

легко может быть построена, в связи с этим не приводится.

Теперь рассмотрим, как может быть представлен алгоритм построения маршрута коня. Условимся, что последовательность полей, с которого начинается маршрут коня, будет задаваться с помощью двух индексов-строки / матрицы О и ее столбца у. Тогда согласно рис. 1.42 индексы всех полей, на которые может попасть конь, с произвольного поля (/, у) идя по часовой стрелке, будут следующими.

Таким образом, для исходного поля очередного маршрута и каждого допустимого поля (/,_/’) необходимо организовать просмотр максимум 8 полей. Для этого следует организовать цикл переменной по к от 1 до 8. В свою очередь изменение индекса удобно вычислять как / = / + 4, у =у + у*. Для этого значения 4? Л необходимо представить двумя одномерными массивами 4 = (-2 -112 2 1-1 -2), у4 = (1 2 2 1-1-2-2 -1).

На основании изложенного построение маршрута может быть организовано следующим образом. Получив поле (/,у) начала очередного маршрута, установить его номер п= 1, положить 8, перейти к шагу 10.

Шаг 7. Положить / = / + /А, у = у + у*.

Шаг 8. Если ф о 0, положить к = к+ 1 и вернуться к шагу 6.

Шаг 9. Положить я = п + 1, т1 = /, ту = у, к = 1 и вернуться к шагу 6.

Шаг 10. Если л > /, перейти к шагу 12.

Шаг 11. Заменить текущий маршрут ;, т^) на лучший (т,„ тм).

Шаг 12. Положить /? = /?+ 1.

Шаг 13. Если И 123 1 будет повторять первоначальную перестановку. Чтобы фиксировать этот момент, необходимо все время сравнивать число вращаемых чисел (в данном случае 3) с последним числом перестановки и когда они совпадут, перейти к очередному действию алгоритма. Очередное действие состоит в проверке, равно ли число вращаемых чисел, в данном случае 3, двум. Если это так, все количество перестановок получено. Иначе уменьшается число вращаемых чисел на единицу и продолжается вращение, в данном случае первых двух чисел. Получаем перестановку 213. Сравниваем 2 с последним числом перестановки 3. Они не равны. Восстанавливаем число вращаемых чисел до 3 и вращаем перестановку 213. Получаем 132. Сравниваем число вращаемых чисел 3 с последним числом 2. Они по-прежнему не равны. Вращаем 132 и получаем 321. Дальнейшее вращение перестановки 321 дает 213 , т. е. перестановку, которая уже была получена в начале второго этапа вращений. Сравниваем число вращаемых чисел 3 с двойкой. Они не равны. Уменьшаем число вращаемых чисел до двух и вращаем первых два числа в перестановке 213. Получаем 123, сравниваем число вращаемых чисел 2 с последним числом вращаемых чисел 2. Они равны. Далее сравниваем число вращаемых чисел 2 с двойкой и заканчиваем построение перестановок. Все перестановки построены. Они приведены ниже. Повторяющиеся перестановки заключены в прямоугольники.

Пусть 1,2, . п — последовательность чисел натурального ряда; т — количество вращаемых чисел в перестановке; к — последнее число вращаемой перестановки. С учетом этих обозначений блок-схема алгоритма построения всех перестановок п чисел натурального ряда будет такой (рис. 1.48).

На рис. 1.49 изображены фрагменты алгоритма «сформировать перестановку 1, 2, . п» и «произвести вращение первых т чисел в последней перестановке», где Р, — /’-е число в перестановке.

Задача 1.32. Рассмотрим следующую задачу. На закрытом интервале , Ь задана унимодальная функция у = /(х), х е [а, Ь.

Требуется сконструировать алгоритм поиска точки х* е [а, Ь, которая доставляет наибольшее значение функции у*.

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

То обстоятельство, что унимодальная функция одногорбая, позволяет по двум различным точкам х2, х2 е [а, Ь] определить интервал а, Ь, которому принадлежит х*. Различные варианты соотношений /(х,) /(х2), /(х,) =/(х2) выделяют свои подынтервалы [х,, Ь], [а, х2], [х,, х2], которым принадлежит х*. Все они меньше первоначального интервала [а, Ь. Для наглядности на рис. 1.51 эти подынтервалы заштрихованы.

Унимодальность функции у=/(х) и возможность вычислять ее в двух точках х,, х2 позволяют построить следующую процедуру поиска х* с определенной погрешностью ?. Возьмем точку х = (а + Ь)/2, делящую интервал [а, Ь] пополам. Сместимся влево

Рис. 1.48. Блок-схема алгоритма построения всех перестановок п чисел

Рис. 1.49. Фрагменты блок-схемы алгоритма

от нее и вправо на расстояние е/2, т. е. получим точки х, = = х — е/2, х2 = х + е/2, где е — малое расстояние между этими точками, равное принятой погрешности вычисления х*. В точках х1? х2 вычислим значения функции у,, у2. Если у, у2, то х* находится в интервале [а, х2. Если же у, = у2, то точка х — это значение х*, найденное с погрешностью е. В связи с этим процедуру считаем завершенной. В противном случае полагаем х, = а или х2 = Ь и приступаем к делению пополам интервала [х,, Ь] или [а, х2] с дальнейшим получением изложенным способом точек х,, х2, вычислением у,, у2, сравнением их между собой и остановкой в случае ух = у2 или

продолжением дальнейшего деления. Процесс завершаем в том случае, когда будет получен интервал ґ

третьего деления — к интервалу длиной

є. Таким образом, после п деле-

ний исходного интервала [а, Ь] будет получен интервал длиной а-Ь (2″-1)

є. Откуда при заданных значениях а, Ь, є мож-

но вычислить значение п, показывающее, сколько делений [а, Ь] нужно выполнить, чтобы получить заданную точность.

Блок-схема алгоритма, реализующая эту процедуру, приведена на рис. 1.51. Описанный метод поиска наибольшего значения

Рис. 1.51. Блок-схема алгоритма поиска наибольшего значения унимодальной

функции методом половинного деления

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

Рассмотрим простейший из них — метод золотого сечения.

Согласно этому методу вначале вычисляются два значения функции х,, х2, как и в методе дихотомии. Затем в полученном подинтервале [х,, Ь] от точки х2 вправо откладывается величина |х2 — х, | и вычисляется значение функции в точке х2+|х2 — х, |.

Если в результате первых двух вычислений функции в точках х,, х2 получен интервал неопределенности [а, х2], от точки х, влево откладывается величина Х[ — х2 и вычисляется функция в точке х, — | х, -х2|. Процесс продолжается до тех пор, пока не будет

достигнута заданная точность сокращения интервала. Схематично он показан на рис. 1.52.

Рис. 1.52. К поиску наибольшего значения унимодальной функции


методом золотого сечения

Метод получил название от известного с древности способа деления интервала а, Ь точкой с на две неравные части так, что отношение всей длины интервала к длине большей части равно отношению длины большей части к длине меньшей части. В данном случае интервал неопределенности [х,, Ь] или [а, х2] делится точкой х, или х2 именно в таком отношении.

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

Подборка алгоритмов, которые правят миром

Однажды на Reddit засветился интересный пост, написанный Джорджем Дворским под названием «10 алгоритмов, которые правят миром» ( статья на русском языке ). В нём автор попытался объяснить важность алгоритмов в наши дни и составил список самых важных для современной жизни алгоритмов .

Если вы изуч а ли алгоритмы, первое, что может прийти вам на ум после прочтения того поста: «Автор вообще знает, что такое алгоритм?» — или, может быть : «Новостной канал Facebook — алгоритм?» — потому что если новостной канал Facebook является алгоритмом, то в конечном итоге мы можем почти всё классифицировать как алгоритм. Чтобы внести ясность, в этой статье будет дано определение алгоритму, и будет составлен список из 10 (или больше) алгоритмов, которые на самом деле правят нашим миром.

Что такое алгоритм?

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

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

  1. Он должен работать за конечное количество времени. Е сли ваш алгоритм не может разобраться с проблемой, для которой он был создан, за конечное количество времени, то он бесполезе н.
  2. Он должен иметь чётко определённые инструкции. К аждый шаг алгоритма должен быть точно определён. Инструкции должны быть однозначны для каждого случая.
  3. Он должен быть пригодным к использованию. А лгоритм должен решать проблему, для решения которой он был написан. Должна быть возможность продемонстрировать его работу при наличии только карандаша и бумаги.

Также важно отметить, что алгоритмы используются не только в информатике, но и в математике. По факту, самые ранние математические алгоритмы — разложение на простые множители и извлечение квадратного корня — использовались вавилонянами уже в 1600 г. до н. э. Таким образом , мы имеем проблему, связанную с упомянутой ранее записью, которая рассматривает алгоритмы как компьютерные сущности. Однако, если применить формальный смысл слова, то одним из претендентов в десятку лучших алгоритмов м ожет стать любая арифметическая операция (сложение, вычитание, произведение и т. д .).

Поэтому в этой статье мы будем говорить о компьютерных алгоритмах. Т огда остаётся вопрос: какие 10 (или больше) алгоритмов правят нашим миром?

Алгоритмы сортировки (быстрая, пирамидальная, слиянием)

Какой алгоритм сортировки элементов лучший? Всё з ависит от ваших нужд, и этим объясняется выбор именно трёх наиболее часто используемых алгоритмов . В озможно, вы предпочитаете какой-то из них другим, но все три имеют одинаковое значение.

Сортировка слиянием — один из наиболее важных алгоритмов на сегодняшний день. Он базируется на сравнении элементов и использует подход «разделяй и властвуй» для более эффективного решения проблемы , которая когда-то решалась за время O (n^2) . Алгоритм был изобретён математиком Джоном фон Нейманом в 1945 году.

Подробнее об оценке сложности алгоритмов читайте в нашем материале

Быстрая сортировка — другой подход к сортировке, чей алгоритм может базироваться как на in-place разделении, так и на «ра зделяй и властвуй». Проблема этой сортировки заключается в том, что она не является стабильной, но эффективна для сортировки массивов в оперативной памяти.

Пирамидальная сортировка — in-place алгоритм, использующий приоритетную очередь, за счёт которой уменьшается время поиска данных. Неустойчив.

Эти алгоритмы намного лучше по сравнению с другими подходами (например, сортировк ой пузыр ь ком), использовавшимися ранее. По сути, благодаря им у нас есть глубинный анализ данных, искусственный интеллект, анализ связей и большинство вычислительных инструментов в мире, включая интернет.

Преобразование Фурье и Быстрое преобразование Фурье

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

Интернет, Wi-Fi , смартфон, телефон, компьютер, маршрутизатор, спутники — почти всё , что имеет внутри себя электронно-вычислительное устройство, так или иначе использует эти алгоритмы для функционирования. Вы не сможете получить диплом по электронике, вычислительной технике или телекоммуникации без изучения этих важных алгоритмов.

Алгоритм Дейкстры

Как ни странно, интернет не смог бы работать эффективно без существования этого алгоритма. Он используется в задачах, где п роблему можно представить в виде графа, для поиска кратчайшего пути между двумя узлами.

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

Алгоритм RSA

Интернет не был бы так глубоко интегрирован в нашу жизнь, как в наше время, если бы не криптография и кибербезопасность. Вы можете сказать: «Конечно, безопасность в эпоху спецслужб » — или: « Вы должны быть очень наивны, чтобы считать, что в сети вы в безопасности». Однако, чтобы тратить свои деньги, люди должны чувствовать себя в безопасности. В конце концов, вы не станете вводить номер своей кредитной карты в веб – сервисе, если не будете уверены в его надёжности.

Из криптографии пришёл алгоритм, который остаётся одним из самых важных в мире, — алгоритм RSA. Разработанный основателями компании RSA, этот алгоритм сделал криптографию доступной для всех в мире и предопределил её будущее. Алгоритм RSA создан для простой задачи с неочевидным решением : как делиться открытыми ключами между независимыми платформами и конечными пользователями так, чтобы была возможность использовать шифрование (стоит отметить, что на самом деле эта проблема до сих пор решена не полностью).

Алгоритм безопасного хэширования

Это не совсем алгоритм, а скорее семейство криптографических хэш-функций (SHA-1, SHA-2, и т.д.), разработанных Национальным институтом стандартов и технологий в США. Оно имеет основополагающее значение для функционирования всего мира. Магазины приложений, антивир усы, электронная почта, браузе ры и т. д . — все они используют эти алгоритмы (на самом дел е — х эш, который является результатом их работы), чтобы определить, загрузили ли вы то, что хотели, а также не стали ли вы жертвой атаки « человек посередине» или фишинга.

Алгоритм факторизации целых чисел

Сложность, связанная с разложением числа на простые множител и, ш ироко используется в машинной области. Без неё криптография могла бы быть не такой безопасной, какой мы её знаем.

Многие криптографические протоколы — например, RSA — основаны на сложности факторизации больших составных целых чисел или на сходных проблемах . Алгоритм, который эффективно сможет разбивать на простые множители произвольное целое число, сделает криптографию с открытым ключом на основе RSA небезопасной.

Анализ связей

В информационную эру взаимоотношени я между различными субъектами имеют большое значение. От поисковых систем и социальных сетей до инструментов анализа рынка — каждый пытается найти реальную структуру интернета на все времена.

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

Идея анализа связей проста : вы можете представить график в виде матрицы, что сводит задачу к проблеме собственной значимости каждого узла. Такой подход к структуре графа даёт нам возможность оценить относительную важность каждого объекта, включённого в систему. Алгоритм был разработан в 1976 году Габриэлем Пински и Фрэнсисом Нарином .

Где используется этот алгоритм? При ранжировании страниц во время поиска в Google, при генерации ленты новосте й в Facebook ( поэтому новостной канал Facebook — не алгоритм, а его результат), при составлении списка возможных друзей на Google+ и Facebook, при работе с контактами в LinkedIn и т. д. Каждый из вышеперечисленных сервисов работает с разными параметрами и объектами, но математика за каждым алгоритмом остаётся неизменной.

Кстати, видимо, Google является не первой компанией, начавшей работу с подобными типами алгоритмов . В 1996 году (за два года до основания Google) небольшая поисковая система под названием «RankDex», основанная Робином Ли , уже использовала эту идею для ранжирования страниц. Также, Массимо Марчиори , основатель «HyperSearch», использовал алгоритм ранжирования страниц, основанный на отношениях между отдельными страницами (эти два основателя упоминаются в патентах Google).

Пропорционально-интегрально-дифференцирующий алгоритм

Вы когда-нибудь пользовались самолётом, автомобилем, спутниковой службой или сотовой сетью? Вы когда-нибудь видели робота или, может, бывали на заводе? В таком случае, вы видели этот алгоритм в действии.

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

Можно сказать, что без этого алгоритма наша технологическая цивилизация не существовала бы.

Алгоритмы сжатия данных

Трудно решить, какой алгоритм сжатия является наиболее важным, поскольку в зависимости от задачи используемый алгоритм может изменяться от zip до mp3 и от JPEG до MPEG-2. Но всем известно, насколько важны эти алгоритмы почти во всех сферах деятельности.

Где может использоваться алгоритм сжатия помимо очевидного заархивированного документа? Например, эта веб-страница использует сжатие данных во время загрузки на ваш компьютер. Также эти алгоритмы используются в видеоиграх, видео, музыке, облачных вычислениях, базах данных и т. д. Можно сказать, что почти все используют алгоритмы сжатия данных, потому что они помогают сделать системы более дешёвыми и эффективными.

Алгоритм генерации случайных чисел

Сегодня у нас нет « настоящего » генератора случайных чисел, но у нас есть некоторые генераторы псевдослучайных чисел, которые достойно справляются со своей задачей. Они имеют большую вариативность использовани я: от разнообразных приложений, криптографии, алгоритмов хеширования, видеоигр и искусственного интеллекта до тестов при разработке программ и т. д.

Подводя итоги

В конце хочется добавить, что этот список — субъективный выбор автора, поскольку существуют алгоритмы в таких задачах, как машинное обучение, умножение матриц, категоризация и т. д ., которые не менее важны в современном мире и при этом здесь не упоминаются.

Больше информации по алгоритмам вы можете найти у нас на сайте

Алгоритмы используемые при сжатии данных

Вступление

Одна из самых главных проблем при работе с данными — это их размер. Нам всегда хочется, что бы уместилось как можно больше. Но иногда этого не сделать. Поэтому нам на помощь приходят различные архиваторы. Но как они сжимают данные? Я не буду писать о принципе их работы, лишь расскажу о нескольких алгоритмах сжатия, которые они используют.

Алгоритм Хаффмана

Построение кода
Обрабатываем b и c

Следующим шагом будет построение дерева, где вершины — «символы», а пути до них соответствуют их префиксным кодам. Для этого на каждом шаге будем брать два символа с минимальной частотой вхождения, и объединять их в новые так называемые символы с частотой равной сумме частот тех, которые мы объединяли, а также соединять их рёбрами, образуя таким образом дерево(см. рисунок). Выбирать минимальные два символа будем из всех символов, исключая те, которые мы уже выбирали. В примере мы объединим символы b и с в символ bc с частотой 3. Далее объединим a и bc в символ abc, получив тем самым дерево. Теперь пути от корня (abc) до листьев и есть Коды Хаффмана(каждому ребру соответствует либо 1 либо 0)

  • a b c
  • 0 11 10
Получившееся дерево

Преобразование MTF

Построение кода
Обратное преобразование

Пусть даны строка s= «1222100» и исходный алфавит «ABC». Символ с номером 1 в алфавите — это ‘B’. На вывод подаётся ‘B’, и этот символ перемещается в начало алфавита. Символ с номером 2 в алфавите — это ‘A’, поэтому ‘A’ подается на вывод и перемещается в начало алфавита. Дальнейшее преобразование происходит аналогично.

  • Символ Список Вывод
  • 1 ABC B
  • 2 BAC C
  • 2 CBA A
  • 2 ACB B
  • 1 BAC A
  • 0 ABC A
  • 0 ABC A

Значит, исходная строка s = «BCABAAA».

Преобразование Барроуза-Уиллера

Работа алгоритма

Преобразование выполняется в три этапа. На первом этапе составляется таблица всех циклических сдвигов входной строки. На втором этапе производится лексикографическая (в алфавитном порядке) сортировка строк таблицы. На третьем этапе в качестве выходной строки выбирается последний столбец таблицы преобразования. Следующий пример иллюстрирует описанный алгоритм:
Пусть нам дана исходная строка s=«ABACABA».

Результат вкратце запишем так: BWT(s)=(«BCABAAA», 3), где 3 — это номер исходной строки в отсортированной матрице, так как он может понадобиться для обратного преобразования.
Следует заметить, что иногда в исходной строке приводится так называемый символ конца строки $, который в преобразовании будет считаться последним символом, тогда сохранение номера исходной строки не требуется. При аналогичном вышеприведённом преобразовании та строчка в матрице, которая будет заканчиваться на символ конца строки и будет исходной («ABACABA$»). При этом при сортировке матрицы данный символ будет рассматриваться как самый последний после всех символов алфавита. Тогда результат можно записать так BWT(s)=»$CBBAAAA». Он будет эквивалентен первому, так как также содержит все символы исходной строки.

Обратное преобразование

Пусть нам дано: BWT(s)=(«BCABAAA», 3). Тогда выпишем в столбик нашу преобразованную последовательность символов «BCABAAA». Запишем её как последний столбик предыдущей матрицы (при прямом преобразовании Барроуза — Уилера), при этом все предыдущие столбцы оставляем пустыми. Далее построчно отсортируем матрицу, затем в предыдущий столбец запишем «BCABAAA». Опять построчно отсортируем матрицу. Продолжая таким образом, можно восстановить полный список всех циклических перестановок строки, которую нам надо найти. Выстроив полный отсортированный список перестановок, выберем строку с номером, который нам был изначально дан. В итоге мы получим искомую строку. Алгоритм обратного преобразования описан в таблице ниже:

Следует также заметить, что если нам было бы дано BWT(s)=»$CBBAAAA», то мы также получили бы нашу исходную строку, только с символом конца строки $ на конце: ABACABA$.

Для чего нужны алгоритмы? Основные алгоритмы программирования

Каждый программист знает о важности использования алгоритмов. В этой статье мы поговорим о том, что такое алгоритм и какими характеристиками он обладает. А самое главное — составим список алгоритмов, которые широко применяются в программировании и, стало быть, будут полезны для программиста.

Алгоритм — что это?

Если говорить неофициально, то алгоритмом можно назвать любую корректно определённую вычислительную процедуру, когда на вход подаётся какая-нибудь величина либо набор величин, а результатом выполнения становится выходная величина либо набор значений. Можно сказать, что алгоритм — это некая последовательность вычислительных шагов, благодаря чему происходит преобразование входных данных в выходные.

Также нужно понимать, что алгоритм как последовательность шагов позволяет решать конкретную задачу и должен: 1. Работать за конечный объём времени. Если алгоритм не способен разобраться с проблемой за конечное количество времени, можно сказать, что этот алгоритм бесполезен. 2. Иметь чётко определённые инструкции. Любой шаг алгоритма должен точно определяться. При этом его инструкции должны быть однозначны для любого случая. 3. Быть пригоден к использованию. Речь идёт о том, что алгоритм должен быть способен решить проблему, для устранения которой его создавали.

Сегодня алгоритмы используются как в информатике и программировании, так и в математике. Кстати, наиболее ранними математическими алгоритмами называют разложение на простые множители и извлечение квадратного корня — их использовали в древнем Вавилоне ещё в 1600 г. до н. э. Но мы не будем уходить далеко в прошлое, а рассмотрим, как и обещали, основные алгоритмы программирования на сегодняшний день.

Алгоритмы сортировки (пирамидальная, быстрая, слиянием)

Какой алгоритм сортировки считают лучшим? Здесь нет однозначного ответа, ведь всё зависит от ваших предпочтений и поставленных перед вами задач. Рассмотрим каждый из алгоритмов: 1. Сортировка слиянием. Важнейший на сегодня алгоритм. Базируется на принципе сравнения элементов и задействует подход «разделяй и властвуй», позволяя более эффективно решать проблемы, которые когда-то решались за время O (n^2). Сортировка слиянием была изобретена математиком Джоном фон Нейманом в далёком 1945 году. 2. Быстрая сортировка. Это уже другой подход к сортировке. Тут алгоритм базируется, как на in-place разделении, так и на принципе «разделяй и властвуй». Однако эта сортировка нестабильна, что и является её проблемой. Зато алгоритм эффективен при сортировке массивов в оперативной памяти. 3. Пирамидальная сортировка. Алгоритм in-place который использует приоритетную очередь (за счёт этой очереди сокращается время поиска данных).

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

Преобразование Фурье. Быстрое преобразование Фурье

Электронно-вычислительные устройства используют алгоритмы для функционирования, в том числе и алгоритм преобразования Фурье. И телефон, и смартфон, и компьютер, и маршрутизатор, и интернет — всё это не может работать без алгоритмов для функционирования, запомните это.

Алгоритм Дейкстры


Без этого алгоритма, опять же, не сможет эффективно работать тот же интернет. С его помощью решаются задачи, в которых проблема представляется в виде графа, обеспечивающего поиск наикратчайшего пути между 2-мя узлами. Даже сегодня, когда у нас есть решения и получше, программисты по-прежнему используют поиск кратчайшего пути, если речь идёт о системах, требующих повышенной стабильности.

Алгоритм RSA

Это алгоритм пришёл к нам из криптографии. Он сделал криптографию доступной всем, предопределив её будущее. Вообще, RSA-алгоритм сделан для решения простой задачи с неочевидным решением. Он позволяет делиться открытыми ключами между конечными пользователями и независимыми платформами таким образом, чтобы можно было применять шифрование.

Алгоритм безопасного хэширования

Ну, это не совсем алгоритм. Скорее, его можно назвать семейством криптографических хэш-функций (SHA-1, SHA-2 и т.д.), которые разработаны в США и имеют важнейшее значение для всего мира. Антивирусы, электронная почта, магазины приложений, браузеры и т. п. — во всём этом используются алгоритмы безопасного хэширования (на деле хэш является результатом их работы). Алгоритм нужен для определения, удалось ли вам загрузить то, что хотели, а также не подверглись ли вы фишингу или атаке «человек посередине».

Анализ связей

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

Алгоритм был создан в далёком 1976 году и используется сегодня при ранжировании страниц в процессе поиска в Google, при генерации ленты новостей, при составлении списка возможных друзей на Facebook, при работе с контактами в LinkedIn и во многих других случаях. Любой из перечисленных сервисов работает с различными объектами и параметрами и объектами, однако сама математика по сути не меняется.

Пропорционально-интегрально-дифференцирующий алгоритм

Пользовались ли вы автомобилем, самолётом, сотовой связью? Видели ли вы робота в работе? Во всех этих случаях вы можете сказать, что видели данный алгоритм в действии.

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

Алгоритмы сжатия данных

Сложно сказать, какой алгоритм для сжатия наиболее важен, ведь в зависимости от поставленных задач он может меняться от zip до mp3 либо от JPEG до MPEG-2. Но эти алгоритмы важны почти для всех сфер деятельности.

Алгоритм сжатия — это не только очередной заархивированный документ. Он позволяет выполнять сжатие данных на веб-странице при их загрузке на компьютер. Или задействуется в базах данных, видео, музыке, облачных вычислениях. По сути алгоритмы сжатия данных делают системы дешевле и эффективнее.

Алгоритм генерации случайных чисел

На самом деле не существует «настоящего» генератора случайных чисел, и мы уже об этом говорили. Зато у нас существуют генераторы псевдослучайных чисел, которые прекрасно с этим справляются. Они имеют расширенную вариативность использования: программные приложения в программировании, криптография, алгоритмы хэширования, видеоигры, искусственный интеллект, тесты при разработке программ и т. д.

Урок 12
Основы алгоритмизации

Алгоритмы

Изучив эту тему, вы узнаете:

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

12.7. Вспомогательный алгоритм

Вспомните рассмотренный ранее алгоритм «Приготовление гречневой каши». Он начинался с пункта «Обратитесь к алгоритму „Разжигание костра»».

Процесс разведения костра был описан заранее и явился вспомогательным алгоритмом в данной задаче. При обращении к этому алгоритму достаточно было указать его название — имя. Этот вспомогательный алгоритм может быть использован и в других алгоритмах, например в алгоритмах «Сушка одежды», «Запекание картошки» и др.

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

Любая из выполняемых при редактировании операций (копирование, вырезание, удаление фрагмента текста и т. д.) представляет собой определенную последовательность действий, то есть алгоритм. Содержание этих алгоритмов благодаря частому их использованию уже не вызывает вопросов. Стоит понять, что необходимо использовать определенную операцию, например копирование, как руки сами воспроизводят соответствующий алгоритм. Таким образом, мозг человека хранит огромное количество ранее определенных алгоритмов, которые используются по мере необходимости при решении различных задач.

Алгоритм, из которого производится вызов вспомогательного алгоритма, получил название основного алгоритма.

Например, для набора текста песни, содержащей три куплета с припевом, можно воспользоваться основным алгоритмом под названием «Набор текста песни».

Алгоритм «Набор текста песни»

1. Набрать название песни.
2. Набрать первый куплет.
3. Набрать припев.
4. Набрать второй куплет.
5. Скопировать припев.
6. Набрать третий куплет.
7. Скопировать припев.

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

Здесь слово скопировать является именем алгоритма, определенного ранее, то есть вспомогательного алгоритма. Слово «припев» обозначает конкретный объект, над которым нужно произвести действие копирования.

Рассмотрим, что представляет собой алгоритм копирования, который является вспомогательным по отношению к основному алгоритму «Набор текста песни». Назовем такой вспомогательный алгоритм «Скопировать (объект копирования)».

Алгоритм «Скопировать (объект копирования)»

1. Выделить объект.
2. Выбрать команду Правка/Копировать.
3. Указать щелчком мыши место вставки.
4. Выбрать команду Правка/Вставить.

При записи данного вспомогательного алгоритма мы указали его имя и в скобках — название параметра, с которым алгоритм работает. В данном случае параметр один — объект копирования. У параметра «объект копирования» могут быть разные значения. При наборе песни в качестве объекта копирования будет использоваться припев. При рисовании в качестве объекта копирования будет использоваться заранее созданный графический элемент. При создании формулы в качестве объекта копирования может использоваться, например, функция или ранее созданное простое математическое выражение.

После выполнения вспомогательного алгоритма вы возвращаетесь в основной алгоритм для его продолжения.

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

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

На рисунке 12.12 приведен пример создания сложной графической композиции на одном из языков программирования. Программирование ведется от простого к сложному. Предварительно разрабатываются вспомогательные алгоритмы, позволяющие нарисовать: а) дугу, б) лепесток, в) группу лепестков. Каждый из этих вспомогательных алгоритмов содержит два параметра, указывающие радиус и направление рисования (по часовой или против часовой стрелки):

— алгоритм Дуга (радиус, направление);
— алгоритм Лепесток (радиус, направление);
— алгоритм Группа (радиус, направление).

Рис. 12.12. Этапы создания сложной графической композиции

Алгоритм Дуга используется в качестве вспомогательного для рисования лепестка. Алгоритм Лепесток используется в качестве вспомогательного для рисования группы лепестков. Алгоритм Группа используется в качестве вспомогательного в основном алгоритме для рисования цветка. В результате сложный алгоритм рисования цветка был составлен из простых циклических алгоритмов рисования его элементов.

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

12.8. Стадии создания алгоритма

Человек легко читает и печатный, и рукописный текст. Однако написать алгоритм этого процесса так, чтобы он стал понятен компьютеру, — чрезвычайно непростая задача. В настоящее время уже разработан алгоритм распознавания компьютером печатного текста. А вот создать алгоритм, в соответствии с которым компьютер мог бы прочесть (распознать) рукописный текст, пока не удается. Компьютер воспринимает такой текст как картинку.

Завязать шнурки на ботинках бантиком умеют многие дети в 6 лет, но описать этот процесс так, чтобы он стал понятен другому человеку или компьютеру, задача не из легких.

Существует определенный алгоритм поведения водителей автомашин на дороге. Этот алгоритм определяется правилами дорожного движения, которые должен знать каждый водитель. Кроме того, шоферы особыми знаками предупреждают друг друга об опасности на дороге или подают сигналы помощи.

Те же самые люди в другой обстановке будут общаться между собой совершенно по-иному, в соответствии с принятыми для этой обстановки правилами поведения.

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

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

Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:
♦ первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
♦ вторая стадия — алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия. В том случае, если эти действия станет выполнять сам разработчик алгоритма, вторая стадия будет отсутствовать.

Поясним стадии создания алгоритма на примере. Предположим, вы с другом хотите в жаркий летний день покататься на велосипедах. Вы должны продумать план подготовки и осуществления задуманного путешествия, то есть его алгоритм:

1. Достать карту местности.
2. Оговорить продолжительность путешествия.
3. Проложить предстоящий маршрут.

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

В дальнейшем, исследуя карту, вы обнаруживаете, что наиболее привлекательным местом является берег речки, расположенный довольно далеко. Ваша цель меняется. Теперь вы мечтаете совершить путешествие именно к этому месту. Поэтому вы вынуждены откорректировать намеченный план действий:
4. Подготовить перечень необходимых продуктов, которые вы возьмете с собой.
5. Подготовить велосипед к длительному пути — смазать маслом, накачать шины и т. д.
6. Собрать необходимые вещи — купальные принадлежности, удочку и т. д.

Новый план нужно изложить другу достаточно убедительно, чтобы он согласился и принял новую цель. Предположим, он согласился и вы договорились готовиться к путешествию независимо друг от друга. Каждый из вас должен изменить уже имеющийся план в соответствии со своим опытом и умением.

Это вторая стадия разработки алгоритма, когда необходимо ориентироваться на тот объект, который будет этот алгоритм исполнять. На этом этапе выбираются среда и инструменты — объекты, которые могут осуществить ваш план.

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

Кто-то обратится к взрослым, которые все сделают за него, другой сам будет готовить велосипед и покупать продукты. Результаты при этом могут оказаться разными.

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

Рассмотрим другой пример. Вы хотите поздравить друзей с Новым годом. Для этого вы наметили подготовить красочные открытки. На первой стадии вы разрабатываете алгоритм для себя:

1. Придумать сюжет.
2. Нарисовать картинку по сюжету.
3. Написать стихи до сюжету.
4. Подготовить открытки с адресами.
5. На каждую открытку поместить рисунок и текст.

Если вы обладаете воображением, умеете рисовать и писать стихи, а также можете воспользоваться компьютером для создания и тиражирования открыток, то этот алгоритм вам по силам выполнить самостоятельно. В этом случае вам не нужна вторая стадия разработки алгоритма.

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

Запомните правила разработки любого алгоритма.

Первая стадия — разработка приближенного алгоритма, ориентированного на создающего его человека:
— определить цель, для достижения которой будет создан алгоритм;
— наметить приблизительный план действий для достижения поставленной цели.

Вторая стадия — детализация алгоритма с учетом специфики среды и других объектов:
— выбрать среду и объекты, посредством которых алгоритм будет реализован;
— детализировать алгоритм с учетом особенностей выбранной среды.

Контрольные вопросы и задания

1. Дайте определение алгоритма и приведите примеры.
2. Что такое алгоритмизация?
3. Приведите пример математического выражения и составьте алгоритм его вычисления.
4. Поясните на примерах свойства алгоритма.
5. Как вы понимаете свойство конечности алгоритма? Приведите примеры.
6. Как вы понимаете свойство массовости алгоритма? Приведите примеры.
7. Что такое линейный алгоритм? Приведите примеры.
8. Что такое циклический алгоритм? Приведите примеры.
9. Напишите циклический алгоритм и укажите в нем тело цикла.
10. Как происходит окончание циклического алгоритма?
11. Что такое разветвляющийся алгоритм? Приведите примеры.
12. Как в алгоритме записывается условие?
13. Как записывается полная форма разветвляющегося алгоритма? Приведите примеры.
14. Как записывается неполная форма разветвляющегося алгоритма? Приведите примеры.
15. Что такое вспомогательный алгоритм? Приведите примеры.
16. Зачем нужна блок-схема алгоритма?
17. Придумайте пример алгоритма и представьте его в виде блок-схемы.
18. Какие стадии разработки алгоритма вы знаете и в чем их суть?
19. Приведите пример разработки алгоритма по стадиям в виде двух блок-схем.

Тест по теме: “Основные понятия алгоритма”

1. Свойство алгоритма, заключающееся в том, что каждое действие и алгоритм в целом должны иметь возможность завершения.
а) дискретность;
б) детерминированность;
в) конечность;
г) массовость.

2. Алгоритм называется циклическим:
а) если он начинается с конца;
б) если серия команд повторяется многократно, в зависимости от условия задачи;
в) если в программе упорядочены действия;
г) всё выше перечисленное верно.

3. Свойством алгоритма является:
а) результативность;
б) цикличность;
в) возможность изменения последовательности выполнения команд;
г) возможность выполнения алгоритма в обратном порядке.

4. Алгоритмом является:
а) прайс лист;
б) инструкция по получению денег в банкомате;
в) расписание уроков;
г) список класса.

5. Алгоритм это:
а) правила выполнения определённых действий;
б) ориентированный граф, указывающий порядок выполнения некоторого набора команд;
в) описание последовательности действий, строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов;
г) набор команд ля компьютера.

Практикум

Циклические алгоритмы

Цикл с предусловием

Выполнив задания этой темы, вы научитесь:

— использовать цикл с предусловием для организации повторяющихся действий;
— тестировать циклические алгоритмы;
— использовать цикл Пока как универсальный для решения разного вида задач;
— использовать переменные разного типа для организации цикла.

Цикл с предусловием относится к циклам с неизвестным числом повторений.

В цикле с предусловием сначала проверяется выполнение условия продолжения цикла. Если условие истинно (да, true), то выполняется тело цикла, а иначе (нет, False) цикл завершается. Особенностью этого цикла является то, что если при 1-й проверке условие ложно, то тело цикла не выполнится ни разу.

Специального блока для реализации цикла с предусловием в блок-схемах нет.

Блок-схема алгоритма реализуется при помощи блока принятия решения, выполнения действий и др.

Блок-схемы алгоритмов, содержащих циклы, легко узнаваемы, так как содержат возврат на предыдущие блоки («петлю»). Во всех языках программирования есть специальные операторы, реализующие этот цикл.


Задание 8.7

Существуют простые правила определения делимости чисел на числа 3, 4, 5:

♦ на 3 без остатка делятся числа, сумма цифр которых делится на 3;
♦ на 4 без остатка делятся числа, у которых две последние цифры составляют число, делящееся на 4;
♦ на 5 без остатка делятся числа, заканчивающиеся на цифры 5 и 0.

Впервые эти правила были сформулированы в знаменитой «Книге Абака» итальянского математика Леонардо Фибоначчи (XII век). Требуется проверить делимость введенных чисел на 3 по первому из перечисленных правил.

Словесный алгоритм

Начало алгоритма
1. Введите число.
2. Пока цифры числа не закончатся:

а) выделите очередную цифру как остаток от деления на 10;
б) прибавьте эту цифру к общей сумме;
в) удалите обработанную цифру из числа, получив новое число в виде частного от деления на 10.
3. Проверьте, делится ли полученная сумма на 3 без остатка:

• если делится, то сообщите, что исходное число делится на 3;
• иначе сообщите, что исходное число не делится на 3.
Конец алгоритма

Алгоритм в виде блок-схемы

На рис. 8.9 приведена блок-схема, составленная по словесному алгоритму.

Рис. 8.9. Блок-схема алгоритма (к заданию 8.7)

Алгоритм в виде программы

В табл. 8.13 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.14 приведены тексты программ на языках Паскаль и Visual Basic.

Таблица 8.13. Программа на Кумире с пояснениями (к заданию 8.7)

Таблица 8.14. Примеры программ на Паскале и Visual Basic (к заданию 8.7)

Задание 8.8

Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, носящий в наше время имя Фибоначчи, вырос из проблемы с кроликами, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих (рис. 8.10). Требуется составить алгоритм проверки принадлежности введенного числа ряду чисел Фибоначчи.

Словесный алгоритм

Начало алгоритма
1. Введите число.
2. Установите значение первых трех чисел Фибоначчи: 1,1,1 + 1
(сумма двух предыдущих чисел).
3. Пока введенное число больше очередного числа Фибоначчи,
возьмите два последних числа и получите из них новое число
Фибоначчи.
4. Если число Фибоначчи, полученное по выходу из цикла,
равно введенному (n) или было введено число п = 1, то сообщите
«Да» (введено число Фибоначчи), в противном случае — сообщите
«Нет» (введенное число не является числом Фибоначчи)
Конец алгоритма

Алгоритм в виде блок-схемы

На рис. 8.11 приведена блок-схема, составленная по словесному алгоритму.

Алгоритм в виде программы

В табл. 8.15 приведена программа на алгоритмическом языке Кумир.

Таблица 8.15. Программа на Кумире с пояснениями (к заданию 8.8)

В табл. 8.16 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.16. Примеры программ на Паскале и Visual Basic (к заданию 8.8)

Задание 8.9

В телевизионном эфире в США проводится марафон, цель которого — сбор средств для поддержки незащищенных слоев населения. Во время эфира слушатели отправляют на адрес студии телеграммы с указанием суммы пожертвования и цели, на реализацию которой пойдет эта сумма, например: «Посылаю 521$ в фонд помощи безработным. Смит».

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

Словесный алгоритм

Начало алгоритма
1. Запросите текст телеграммы.
2. Поместите текст в строку st.
3. Определите длину строки n.
4. Пока не закончатся все символы в строке или пока не встретится знак $, рассмотрите три ситуации:

а) если символ — цифра, то получите цифровой эквивалент символа; добавьте полученную цифру в следующую позицию числа, из которого будет сформирована сумма пожертвования, и перейдите к следующему символу, увеличив счетчик символов: i = i + 1;
б) если символ — «$», то установите признак окончания цифр d, который будет признаком досрочного выхода из цикла;
в) если это другой символ (буква, знак препинания и т. п.), то перейдите к следующему символу, увеличив счетчик символов: i = i + 1.
5. Проанализируйте признак окончания цифр d. Если он равен 1, то сообщите сумму пожертвования, если нет — сообщите, что указания о сумме пожертвования в телеграмме нет.
Конец алгоритма

Алгоритм в виде блок-схемы

На рис. 8.12 приведена блок-схема, составленная по словесному алгоритму.

Алгоритм в виде программы

В табл. 8.17 приведена программа на алгоритмическом языке Кумир.

Таблица 8.17. Программа на Кумире (к заданию 8.9)

В табл. 8.18 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.18. Примеры программ на Паскале и Visual Basic (к заданию 8.9)

Контрольные вопросы и задания

К заданию 8.7

1. Для чего нужны начальные установки в алгоритме?
2. Пройдите алгоритм по блок-схеме для числа 521 (см. рис. 8.9). Какое значение будет в переменных nl и Sum перед выходом из цикла?
3. Добавьте в любую из программ оператор вывода переменных cifra и Sum. Какое значение и сколько раз будет выведено для числа 222?
4. Что произойдет, если пользователь введет число п равным нулю?
5. Напишите комментарий к п. 9 программы на Кумире (см. табл. 8.13).

К заданию 8.8

1. Какие действия выполняются в блоке 6 (см. рис. 8.11) и соответствующем фрагменте программы на Кумире (см. табл. 8.15)?
2. Какое условие проверяется в данном алгоритме при входе в цикл с предусловием?
3. Запишите в тетради тело цикла с предусловием, используемое в данном алгоритме.
4. Придумайте и запишите пример ситуации, когда тело цикла не выполняется ни одного раза.
5. В блоке 3 алгоритма (см. рис. 8.11) было введено число 5. Сколько раз выполнится тело цикла?
6. Напишите пояснение к строкам 2 и 3 программы на Кумире (см. табл. 8.15).
7*. В блоке 6 программы на Кумире (см. табл. 8.15) производится переприсваивание содержимого ячеек (предпредыдущей, предыдущей и текущей). Можно ли поменять местами операторы присваивания? Ответ обоснуйте.
8*. Можно ли в данном алгоритме обойтись только двумя переменными ƒ1 и ƒ2?

К заданию 8.9

1. В блоке 4 блок-схемы (см. рис. 8.12) определяется длина строки n. Для чего это делается? Где далее используется эта переменная?
2. В алгоритме используется цикл с предусловием. Может ли возникнуть такая ситуация, что тело цикла не исполнится ни разу? Придумайте и запишите в тетради пример телеграммы, текст которой приведет к такой ситуации.
3. Что произойдет в алгоритме, если в адрес телемарафона придет телеграмма из России: «Я пенсионерка, но хочу пожертвовать 3 доллара в фонд помощи бездомным животным. Татьяна». Предложите вариант алгоритма, учитывающего подобную ситуацию.
4. Добавится ли к сумме число, указанное в телеграмме: «Я родился в 1900 году, средств не имею, но считаю, что нужно помогать старикам. Джон»?
5*. Если вы отлаживаете программы на Паскале или на Visual Basic, упростите поиск упоминания доллара (знак или текст).
6. Что означает сложное условие sim >= «0» и sim *

Слышали ли вы о «золотом» прямоугольнике? Если от него отсечь квадрат, то остается прямоугольник с такими же пропорциями (отношением сторон), то есть полученный прямоугольник тоже будет «золотым». Этот процесс можно продолжать до бесконечности. На этой же пропорции базируются все «золотые» геометрические фигуры. Отрезки «золотой» пропорции выражаются бесконечными дробями 1,618 или 0,618.

Если вписать в квадраты, отсекаемые от прямоугольника, четверти окружности, то получается знаменитый «золотой» завиток, являющийся основой многих орнаментов, архитектурных деталей и пр.

Требуется определить по введенным сторонам, является ли прямоугольник «золотым». Принять допущение: считать прямоугольник «золотым», если одно и то же соотношение с заданной точностью (абсолютная погрешность — 0,01) повторилось 5 раз. Вывести «золотое» соотношение.

Рис. 8.18. К заданию 8.15

Словесный алгоритм

Начало алгоритма
1. Введите параметры прямоугольника.
2. Определите, какая сторона является большей, какая — меньшей.
3. Найдите и сообщите первое отношение большей стороны к меньшей.
4. Пока не закончатся 5 экспериментов или не выявится неравенство последующих отношений, выполняйте следующие действия:

а) определите стороны нового прямоугольника после отсечения квадрата и найдите их соотношение;
б) если это соотношение не равно предыдущему с заданной точностью, то завершите эксперименты.
5. Если все 5 попыток прошли успешно, то выведите сообщение «прямоугольник золотой», иначе — «прямоугольник не золотой».
Конец алгоритма

Алгоритм в виде блок-схемы

Рис. 8.19. Блок-схема алгоритма (к заданию 8.15)

На блок-схеме (рис. 8.19) пунктирной линией обведены блоки, которые будут многократно повторяться далее в цикле. Это означает, что данные блоки должны быть оформлены как вспомогательный алгоритм.

Алгоритм в виде программы

В табл. 8.29 приведена программа на алгоритмическом языке Кумир с пояснениями. В табл. 8.30 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.29. Программа на Кумире с пояснениями (к заданию 8.15)

Таблица 8.30. Примеры программ на Паскале и Visual Basic (к заданию 8.15)

Контрольные вопросы и задания

К заданию 8.13

1. В примерах программ сторона многоугольника рассчитывается через синус центрального угла. В каких единицах измерения должен быть указан угол?
2. Условием окончания цикла является отношение (l — р) 10). Что означает это сложное условие?
5*. Заполните таблицу истинности для указанного сложного условия.

6. Выпишите в тетрадь, как описана на разных языках строка фамилий?
7. Если искомая фамилия является последней в списке, по какому условию осуществился выход из цикла?

К заданию 8.15

1. Для чего нужны начальные установки в алгоритме?
2. При решении задачи принято допущение: считать прямоугольник «золотым», если одно и то же соотношение с заданной точностью (абсолютная погрешность — 0,01) повторилось 5 раз. Найдите места в примерах программ, где учитывается это соглашение.
3. Что надо изменить в блок-схеме и программах, чтобы пользователь сам указывал абсолютную погрешность?
4. После выхода из цикла анализируется переменная razn. Можно ли анализировать переменную ch?
5*. Заполните таблицу истинности для сложного логического выражения (razn > 0.01) Or (ch = 5).

6. Напишите пояснения к пп. 10 и 11 программы на Кумире (см. табл. 8.29).
7*. Золотое соотношение обеспечивают стороны, длина которых соответствует числам Фибоначчи (чем больше числа, тем точнее пропорция). Это видно на первом тесте (рис. 8.21). Что нужно изменить в программе, чтобы рассматриваемое отношение сторон поменялось с 0,618 на 1,618?
8*.На рис. 8.21 изображено два теста. Какого теста не хватает для проверки всех ветвей алгоритма?

Рис. 8.21. Примеры тестирования программы на Visual Basic (к заданию 8.15)

9. Что нужно изменить (добавить) в блок-схеме, чтобы проверялось условие равенства сторон исходного прямоугольника? Что даст подобное изменение?

Основы программирования

Разделы сайта

Задачи

Документация

Сайты партнеры

Адаптер кузовной для мотоблока

Архив

  • Январь, 2020 (1)
  • Июнь, 2015 (1)
  • Март, 2015 (1)
  • Май, 2014 (1)
  • Апрель, 2014 (1)
  • Январь, 2013 (1)
  • Декабрь, 2012 (1)
  • Май, 2012 (3)
  • Апрель, 2012 (3)
  • Март, 2012 (3)
  • Февраль, 2012 (1)
  • Декабрь, 2011 (1)

Рейтинг

Алгоритм преобразования строк по заданному правилу

Опубликовано Хубларян Вадим . в Пнд, 12/15/2008 — 12:37

  • Задачи
  • Программирование
  • C/CPP

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 — либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Пусть строка S1 состоит из цифр 0 и 1 и имеет длину N, а строка S2 (из символов A и B) — длину M.

Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки S1, а j-й столбец — j-м символом строки S2.

Возьмем в качестве примера S1=’00110′, S2=’AAAABBAA’.

Первая цифра строки S1 (цифра 0) может быть преобразована в одну из последовательностей букв ‘A’,’AA’,’AAA’,’AAAA’, являющиеся префиксами строки S2. Заносим символ ‘x’ в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей. Таким образом, помечаются элементы A[1,1], A[1,2], A[1,3] и A[1,4].

Шаг алгоритма: будем преобразовывать очередную цифру S1[i], которой соответствует строка i.

Находим ‘x’ в предыдущей строке при просмотре ее слева направо (этому столбцу соответствует последняя буква в какой-то из непустых последовательностей букв, порожденных на предыдущем шаге). Если текущую цифру можно преобразовать в последовательность букв, помечающих следующие за данным столбцы, то в этих столбцах в данной строке ставим ‘x’.

Далее от места над последней помеченной ячейкой ищем в предыдущей строке ‘x’ и, когда находим, повторяем указанные выше операции.

Илон Маск рекомендует:  Что такое код asp authpersistsinglerequest
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL