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

Как вывести количество локальных минимумов алгоритмическом языке

  • автор:

Есть ли польза от решения алгоритмических задач на LeetCode?

Пожалуй каждый программист, который сталкивался с вопросом: «А как устроиться на работу в FAANG?» — получал ответ, что ему нужно разобраться с алгоритмами, со структурами данных и прорешать порядка 300-400 задач на leetcode по алгоритмам.

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

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

Как обычно приступают к изучению алгоритмов

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

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

  • «Алгоритмы — Руководство по разработке» — Стивена Скиена.
  • «Карьера программиста (Cracking the coding interview)» — ЛакманМакДауэлл.

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

Так же, если у вас нет хорошего бекграунда (например, профильного университета), то неплохо бы ознакомиться с базовым computer science перед тем, как начинать читать книги по алгоритмам. Для этого так же есть неплохая книга, которую я могу вам рекомендовать:

  • «Гид по Computer Science» — Вильям Спрингер

И вот после того, как вы прочитали 2-3 книги, которые могут у вас занять порядка 3-4 месяцев, можно приступать к решению задач на Leetcode.

Как правило, нет смысла просто открывать список задач и начинать их решать подряд, рекомендуется открывать либо специальные подборки от самого Литкода, либо от ребят, которые их составили на основе опыта интервью в FAANG (например, от автора Neetcode — https://neetcode.io/practice)

Как выглядит процесс решения каждой алгоритмической задачи

1) Открывается задача — читается описание. Нужно понимать, что далеко не всегда задача поставлена очевидно. Чем выше номер задачи, тем более синтетической может оказаться ситуация. Поэтому, если не получается понять, что же от нас требуется — прибегаем к помощи гугла и Youtube.

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

3) После этого нужно задать вопрос: «А можно ли сделать решение более эффективным?» Если ничего на ум не приходит, то сначала следует открыть подсказки внизу каждой задачи литкода. Там, как правило, проставлены теги по тем приемам, которые можно использовать (Два указателя, Бинарный поиск, Битовые операции и так далее). Это отличная возможность, чтобы загуглить данные приемы и познакомиться с тем, как их следует использовать, и на каких типах задач они помогают. Например, есть неплохой канал с объяснениями — https://www.youtube.com/@WilliamFiset-videos/videos

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

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

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

Что дает нам решение задач от LeetСode?

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

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

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

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

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

5) Пройти собеседование в компанию, которая требует от вас алгоритмы и получить работу мечты. Если у вас, конечно, есть такая цель.

Применим ли подход с Leetcode в настоящей работе?

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

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

3) Так же, как Ливерпуль никогда не останется один, так же и задачи никогда не приходят без контекста. Как правило, вам не нужно готовить свое решение для какого-то непредсказуемого набора данных. Вы настраиваете валидацию, смотрите примеры данных в базе, смотрите бизнес-правила, и понимаете, что в условную функцию может прийти какой-то узкий набор данных предсказуемой длины. И чаще всего не имеет значение, обработаются эти данные O(1), O(N) или O(N*N) и так далее.

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

Так делает ли LeetСode тебя более лучшим программистом, чем ты есть?

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

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

Так же стоит обратиться к словам Стивена Скиена из книги по алгоритмам. Он смеялся и говорил, что очень рад тому, что FAANG пропускают людей через алгоритмическое интервью, так как это увеличивает тираж его книг и приносит дополнительную копеечку, а есть ли польза от алгоритмов или нет — покажет время.

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

Но все же, почему именно алгоритмические задачи?

Чтобы понять, почему Бигтех спрашивает у каждого человека алгоритмические задачи, нужно немного погрузиться в контекст найма в Бигтех. Если на рынке РФ разница между предложениями «обычных» компаний и tier-1 компаний не сильно отличаются по денежке и количеству бенефитов, то в США Бигтех делает офферы, которые в разы перекрывают предложения от обычных компаний. Поэтому, количество людей, которые хотят работать в бигтехе просто колоссальное (люди едут со всего мира, чтобы работать в Гугле, Фейсбуке, Майкрософте и так далее).

Имея огромный поток людей высокой квалификации, которые хотят у тебя работать, можно поставить барьер, который отсеет тех, кто не готовился к собеседованию именно в твою компанию. Зачем нанимать просто опытных, если можно нанимать опытных, усердных и мотивированных. Именно поэтому появляются различные истории типа той, где на работу не взяли создателя homebrew, потому что он не смог сделать вайтбоард в гугле: Логично ли, что Гугл отклонил кандидатуру Макса Хауэлла, автора Homebrew, за неумение инвертировать двоичные деревья?

Поэтому да, если какой-то программист в США хочет сменить работу на бигтех, сколько бы у него не было опыта, он садится и начинает готовиться к собеседованию. И порой процесс подготовки занимает 5-6 месяцев, включая различные сервисы и персональных тренеров, которые подтягивают его по каким-то моментам собеседования. Например, вот целый сервис, который учит тебя правильно вести на собеседовании и правильно обсуждать зарплату:

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

Алгоритм, содержащий цикл и ветвление

Термин «алгоритм», впервые употребленный в современном значении. Лейбницем (1646–1716), является латинизированной формой имени великого персидского математика Мухаммеда бен Муссы аль-Хорезми (ок. 783 – ок. 850). Его книга «Об индийском счете» в XII в. была переведена на латинский язык и пользовалась широкой популярностью не одно столетие. Имя автора европейцы произносили как Алгоритми (Algorithmi), и со временем так стали называть в Европе всю систему десятичной арифметики.

Научное определение алгоритма дал А. Чёрч в 1930 году. В наше время понятие алгоритма является одним из основополагающих понятий вычислительной математики и информатики.

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

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

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

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

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

Основные требования, предъявляемые к алгоритмам:

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

Определенность (детерминированность; лат. determinate — определенность, точность): шаги (операции) алгоритма должны допускать однозначную трактовку и быть понятными для исполнителя алгоритма. Это свойство указывает на то, что любое действие в алгоритме должно быть строго определено и описано для каждого случая.

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

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

Конечность: количество шагов алгоритма должно быть конечным.

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

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

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

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

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

  1. следование — образуется из последовательности действий, следующих одно за другим;
  2. ветвление (развилка) — обеспечивает в зависимости от результатов проверки условия (ДА или НЕТ) выбор одного из альтернативных путей алгоритма;
  3. цикл — обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.

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

Обычный язык. Изложение алгоритма ведется на обычном языке с разделением на последовательные шаги.

Блок-схемы. Графическое изображение алгоритма с помощью специальных значков-блоков.

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

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

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

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

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

Название символа Графическое изображение Комментарии
Пуск/Останов (блоки начала и конца алгоритма) Указание на начало или конец алгоритма
Ввод/Вывод данных (блоки ввода, вывода Организация ввода/вывода в общем виде
Процесс (операторные блоки) Выполнение вычислительного действия или последовательности действий (можно объединять в один блок), которые изменяют значение, форму представления или размещение данных
Условие (условный блок) Выбор направления выполнения алгоритма. Если условие, записанное внутри ромба, выполняется, то управление передается по стрелке «да», в противном случае — по стрелке «нет». Таким образом, реализуется процесс изменения последовательности вычислений в зависимости от выполнения условия
Начало цикла с параметром Используется для организации циклических конструкций с известным количеством итераций (повторений) и известным шагом изменения параметра цикла. Внутри блока для параметра цикла указываются через запятую его начальное значение, конечное значение и шаг изменения. Цикл, для которого неизвестно количество повторений, записывается с помощью условного и операторных блоков
Предопределенный процесс Используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращения к библиотечным подпрограммам
Печать сообщений (документ) Вывод результатов на печать

При составлении блок-схемы необходимо проверять выполнение следующих условий:

  1. из каждого прямоугольника и параллелограмма (кроме конца алгоритма) должна выходить только одна стрелка;
  2. в каждый прямоугольник и параллелограмм (кроме начала алгоритма) должна входить хотя бы одна стрелка;
  3. в каждый ромб должна входить хотя бы одна стрелка, а выходить из него — две стрелки, помеченные словами «ДА» и «НЕТ».

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

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

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

Общий вид записи алгоритма на псевдокоде:

алг — название алгоритма (аргументы и результаты)

дано — условие применимости алгоритма

надо — цель выполнения алгоритма

нач — описание промежуточных величин

последовательность команд (тело алгоритма)

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

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

Команды учебного языка:

1. Оператор присваивания, который обозначается «:=» и служит для вычисления выражений, стоящих справа, и присваивания их значений переменным, указанным в левой части. Например, если переменная а имела значение 5, то после выполнения оператора присваивания а := а + 1, значение переменной а изменится на 6.

2. Операторы ввода/вывода:

ввод (список имен переменных)

вывод (список вывода)

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

3. Оператор ветвления (с использованием команды если. то… иначе…всё; выбор);

4. Операторы цикла (с использованием команд для, пока, до).

Запись алгоритма на псевдокоде:

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

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

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

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

Примеры решения задач

Пример 1. Исполнитель Утроитель может выполнить только две команды, которым присвоены номера:

Первая команда уменьшает число на 1, вторая — увеличивает его втрое.

Написать набор команд (не более пяти) получения из числа 3 числа 16. В ответе указать только номера команд.

Ответ: 13311

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

Система команд Исполнителя алгоритма:

1. «Вперед N» (Исполнитель алгоритма делает шаг вперед на N единиц).

2. «Назад M» (Исполнитель алгоритма делает шаг назад на M единиц).

Переменные N и M могут принимать любые целые положительные значения. Известно, что Исполнитель алгоритма выполнил программу из 50 команд, в которой команд «Назад 2» на 12 больше, чем команд «Вперед 3». Других команд в программе не было. Какой одной командой можно заменить эту программу, чтобы Исполнитель алгоритма оказался в той же точке, что и после выполнения программы?

1. Найдем, сколько было команд «Вперед», а сколько «Назад». Учитывая, что общее количество команд равно 50 и что команд «Назад» на 12 больше, чем команд «Вперед». Получим уравнение: x + (x + 12) = 50, где x — количество команд «Вперед». Тогда общее количество команд «Вперед»: x = 19, а количество команд «Назад»: 19 + 12 = 31.

2. Будем вести отсчет от начала числовой оси. Выполнив 19 раз команду «Вперед 3», Исполнитель алгоритма оказался бы на отметке числовой оси 57 (19 * 3 = 57). После выполнения 31 раз команды «Назад 2» (31 * 2 = 62) он оказался бы на отметке –5 (57 – 62 = –5).

3. Все эти команды можно заменить одной — «Назад 5».

Ответ: команда«Назад 5».

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

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

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

Записать для исполнителя Черепашка алгоритмы:

а) построения квадрата со стороной 100;

б) построения правильного шестиугольника со стороной 50.

в) построения изображения цифры 4, если голова Черепашки смотрит на север.

Ответ: а) Повтори 4 [вп 100 пр 90]; б) Повтори 6 [вп 50 пр 360/6]; в) вп 100; повтори [лв 135 вп 50].

Пример 4. Два игрока играют в следующую игру (это вариант восточной игры). Перед ними лежат три кучки камней, в первой из которых 2, во второй — 3, в третьей — 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в одной из кучек, или добавляет по два камня в каждую из них. Выигрывает игрок, после хода которого либо в одной из кучек становится не менее 15 камней, либо общее число камней в трех кучках становится не менее 25. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ следует обосновать.

Решение. Удобнее всего составить таблицу возможных ходов обоих игроков. Заметим, что в каждом случае возможны всего четыре варианта хода. В таблице курсивом выделены случаи, которые сразу же приносят поражение игроку, делающему этот ход (например, когда камней в какой-либо кучке становится больше или равно 8, другой игрок непременно выигрывает следующим ходом, удваивая количество камней в этой кучке). Из таблицы видно, что при безошибочной игре обоих игроков первый всегда выиграет, если первым ходом сделает 4, 5, 6. У второго игрока в этом случае все ходы проигрышные.

1-й ход 2-й ход
Начало 1-й игрок 2-й игрок 1-й игрок 2-й игрок
2,3,4 4,3,4 8,3,4 выигрыш
4,6,4 8,6,4 выигрыш
4,12,4 выигрыш
4,6,8 выигрыш
6,8,6 выигрыш
4,3,8 выигрыш
6,5,6 12,5,6 выигрыш
6,10,6 выигрыш
6,5,12 выигрыш
8,7,8 выигрыш
2,6,4 4,6,4 8,6,4 выигрыш
4,12,4 выигрыш
4,6,8 выигрыш
6,8,6 выигрыш
2,12,4 выигрыш
2,6,8 выигрыш
4,8,6 выигрыш
2,3,8 выигрыш
4,5,6 8,5,6 выигрыш
4,10,6 выигрыш
4,5,12 выигрыш
6,7,8 выигрыш

Пример 5. Записано 7 строк, каждая из которых имеет свой номер. В нулевой строке после номера записана цифра 001. Каждая последующая строка содержит два повторения предыдущей строки и добавленной в конец большой буквы латинского алфавита (первая строка — A, вторая строка — B и т. д.). Ниже приведены первые три строкиєтой записи (в скобках указан номер строки):

Какой символ находится в последней строке на 250-м месте (считая слева направо)?

Примечание. Первые семь букв латинского алфавита: A, B, C, D, E, F, G.

Решение. Найдем длину каждой строки. Длина каждой следующей строки в два раза больше длины предыдущей плюс один символ, длина строк составит:

(6) 127*2+1=255 символов.

Так как задано 7 строк, а нумерация начинается с нулевой строки, последняя строка имеет номер 6 и содержит 255 символов. Последний символ в строке — F. Предпоследний элемент — E, далее идут символы D, C, B, A, 1 (по правилу формирования строк). Таким образом, 250-й символ — это 1.

Пример 6. Имеется фрагмент алгоритма, записанный на учебном алгоритмическом языке:

n := Длина(а)

b := Извлечь(а, k)

нц для i от 7 до n – 1

с := Извлечь(а, i)

b := Склеить(b, с)

Здесь переменные а, b, с — строкового типа; переменные n, i — целые.

В алгоритме используются следующие функции:

Длина(х) — возвращает количество символов в строке х. Имеет тип «целое».

Извлечь(х, i) — возвращает i-й символ слева в строке х. Имеет строковый тип.

Склеить(х, у) — возвращает строку, в которой находятся все символы строки х, а затем все символы строки у. Имеет строковый тип.

Какое значение примет переменная b после выполнения этого фрагмента алгоритма, если переменная а имела значение «ВОСКРЕСЕНЬЕ»?

Решение. Находим общее число символов в строке а, получим, что n = 11.

Выполняя команду b := Извлечь(а, k) при k = 2, получим, что b примет значение «О«.

В цикле последовательно, начиная с 7-го символа строки а и заканчивая предпоследним (n – 1), извлекаем символ из строки а и присоединяем к строке b.

В результате получим слово «ОСЕНЬ» (символы с номерами 2 + 7 + 8 + 9 + 10).

Ответ: «ОСЕНЬ«

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

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

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

Решение. Словесный алгоритм:

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

Приведенный словесный алгоритм в пункте 1, 2 содержит начальные установки, в пункте 3 — цикл с условием, а пункт 4 — это вывод результата работы алгоритма.

F — текущее число ряда Фибоначчи;

F1 и F2 — два предыдущих числа ряда Фибоначчи для числа F;

n — число, для которого требуется определить, является ли оно числом из ряда Фибоначчи.

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

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

Базовая структура СЛЕДОВАНИЕ указывает на то, что управление передается последовательно от одного действия к другому.

Учебный алгоритмический язык Язык блок-схем
действие 1
действие 2

действие n

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

В качестве примера рассмотрим решение простой задачи.

Пример. Найти y(x) = x2 + 3x + 5, используя только операции умножения и сложения.

Решение. На рис. приводятся два алгоритма, реализующие решение поставленной задачи.

Порядок вычисления y(x) в первом случае — обычный, а во втором — (x + 3) x + 5. Обе формулы эквивалентны, но в первом случае для вычисления необходимо 2 умножения, 2 сложения и 3 переменных (x, y, z), а во втором используются 1 умножение, 2 сложения и 2 переменные (x, y).

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

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

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

В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных правой части уже определены.

Базовая структура ВЕТВЛЕНИЕ (РАЗВИЛКА) используется в случае, когда выполнение программы может измениться в зависимости от результата проверки условия и пойти двумя разными (альтернативными) путями. Другими словами, условие является некоторым высказыванием (предикатом) и может быть истинным или ложным (принимать значение TRUE или FALSE). Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.

Различают две структуры этого типа — полную и неполную. В случае полной структуры, если условие выполняется (является истинным), вслед за ним выполняется действие 1, иначе — действие 2. В случае неполной структуры, если условие выполняется (является истинным), то вслед за ним выполняется действие 1, иначе ничего не происходит.

Важную роль в операторах ветвления играют содержащиеся в них условия. В простейшем случае условиями служат отношения между величинами. Условия с одним отношением называют простыми условными выражениями, или простыми условиями. В некоторых задачах необходимы более сложные условия, состоящие из нескольких простых, например условие А < X < С, т. е. Х < А и (Х >C) (возможна запись (Х < А) and (Х >C)). Объединение нескольких простых условий в одно образует составное условное выражение, или составное условие. Составные условия образуются с помощью логических операторов not (отрицание), and (логическое И), or (логическое ИЛИ), хоr (исключающее ИЛИ).

Структура ВЕТВЛЕНИЕ существует в четырех основных вариантах:

если — то (неполная структура);

если — то — иначе (полная структура);

выбор (неполный);

выбор — иначе (полный).

если условие

то действие 1

если условие

то действие 1

иначедействие 2

при условие 1: действие 1

при условии 2: действие 2

при условие N: действие N

при условие 1: действие 1

при условие 2: действие 2

при условие N: действие N + 1

иначе действия N + 1

В качестве простого примера рассмотрим нахождение модуля числа y(x) = |x|. Решение приведено на рис. для случаев полной (а) и неполной (б) структур ветвления.

Базовая структура ЦИКЛ служит для записи алгоритмов, в которых некоторая часть алгоритма (тело цикла) должна повторяться несколько раз. Количество повторений цикла может определяться разными способами, в зависимости от которых различают три вида циклов.

1. Цикл с предусловием, или цикл «пока». При реализации этого цикла сначала проверяется условие его выполнения. Пока оно выполняется, будут происходить повторения тела цикла. Отсюда и другое его название — цикл «пока». Если условие не выполняется при первой проверке, то тело цикла не будет выполняться вообще. После выхода из цикла управление передается следующей структуре. Для того чтобы избежать зацикливания, т. е. бесконечного цикла, в теле цикла обязательно должны изменяться параметры, записанные в условии.

пока условие

тело цикла (последовательность действий)

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

для i от i1 до i2

тело цикла (последовательность действий)

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

тело цикла (последовательность действий)

до условие

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

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

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

Пример. Вычислить сумму знакопеременного ряда $S=x-/+/-/+. $ с заданной точностью $ε$.

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

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

$S$ — частичная сумма ряда (стартовое значение равно 0);

$ε$ — точность вычисления;

$i$ — номер очередного слагаемого;

$m$ — значение очередного слагаемого;

$p$ — числитель очередного слагаемого.

На псевдокоде алгоритм можно записать следующим образом:

Примечание. Следует отметить, что ряд будет сходящимся только при выполнении условия 0 < х < 1.

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

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

Пример. Вычислить сумму элементов для заданной матрицы (таблицы из 5 строк и 3 столбцов) А(5,3).

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

Основная часть блок-схемы нахождения суммы элементов матрицы будет иметь следующий вид:

Здесь порядок выполнения вложенных циклов следующий: счетчик внутреннего цикла изменяется быстрее, т. е. для i = 1(внешний цикл), j пробегает значения 1, 2, 3 (внутренний цикл); далее i = 2, j опять пробегает значения 1, 2, 3 и т. д.

Примеры решения задач

Пример 1. Дан фрагмент блок-схемы некоторого алгоритма.

Определить значение переменной А после выполнения фрагмента алгоритма.

Какие исправления нужно внести, чтобы изменение значения переменной А происходило в обратном порядке?

Как записать исходный алгоритм с помощью двух других видов цикла?

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

Начальные установки: A = 100000; N = 2
1-я итерация A = 10000; N = 4
2-я итерация A = 1000; N = 6
3-я итерация A = 100; N = 8
4-я итерация A = 10; N = 10
5-я итерация, выполнилось условие выхода: N > 10 Ответ: А = 1; N = 12

Таблица обратного хода изменения значения А будет иметь такой вид:

Начальные установки: A = 1; N = 2
1-я итерация A = 10; N = 4
2-я итерация A = 100; N = 6
3-я итерация A = 1000; N = 8
4-я итерация A = 10000; N = 10
5-я итерация, выполнилось условие выхода: N > 10 А = 100000; N = 12

Блок-схема алгоритма примет такой вид:

В алгоритме нужно изменить начальное значение А и операцию деления заменить операцией умножения. Счетчик N в данном случае изменять не нужно.

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

Понятно, что цикл должен выполниться пять раз. В заголовке цикла необходимо указать начальное и конечное значение счетчика цикла N (приращение по умолчанию равно 1).

Для цикла с постусловием блок-схема исходного алгоритма имеет такой вид:

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

Пример 2. Сколько раз выполнится тело цикла в программе?

нц пока (div(Q, 5) = div(P, 7))

Примечание. Результат функции div(X, Y) — целая часть от деления X на Y.

Решение. Рассмотрим пошаговое выполнение алгоритма, оформив его в виде таблицы.

Начальные установки Q := 27; P := 36
Проверка выполнения условия div(27, 5) = 5;
div(36, 7) = 5;
5 = 5
1-я итерация; выполнение тела цикла Q := 29; P := 39
Проверка выполнения условия div(29, 5) = 5;
div(39, 7) = 5;
5 = 5
2-я итерация; выполнение тела цикла Q := 31; P := 42
Проверка выполнения условия div(31, 5) = 6;
div(42, 7) = 6;
6 = 6
3-я итерация; выполнение тела цикла Q := 33; P := 45
Проверка выполнения условия div(33, 5) = 6;
div(45, 7) = 6
6 = 6
4-я итерация; выполнение тела цикла Q := 35; P := 48
Проверка выполнения условия. Условие не выполняется, цикл завершает работу div(35, 5) = 7;
div(48, 7) = 6;
7 ≠ 6

Ответ: цикл выполнится 4 раза.

Использование переменных. Объявление переменной (тип, имя, значение). Локальные и глобальные переменные

Величины служат для описания объектов и процессов в материальном мире. Каждая величина имеет некоторые характеристики. В программировании понятие величины несколько отличается от понятия величины в естественных науках — оно является более формальным. Величиной называют объект — переменную, с которым связывается определенное множество значений. Такому объекту присваивается имя — идентификатор. Понятие переменной в программировании сходно с понятием переменной в математике. Например, в алгебраическом равенстве C = F + 2B – 5 значение переменной С зависит от значений переменных F и B, указанных в правой части равенства. Например, при F = 2 и B = 6, С = 9. Такое же равенство можно записать в программе, например на языке программирования Бейсик: C = F + 2*B – 5. В терминах языка программирования C, F и B — это идентификаторы (имена) переменных.

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

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

Назначение программы состоит в обработке информации, при этом, конечно, основную роль играют переменные.

  • идентификатором;
  • типом;
  • значением.

Каждая переменная имеет свой идентификатор, т. е. свое уникальное имя. Имя переменной показывает, в каком месте памяти компьютера она хранится, значение переменной считывается из указанного ее именем места в памяти. Двух переменных с одним именем в одном программном модуле (блоке) быть не должно. Примерами идентификаторов величин могут быть, например, следующие последовательности символов: a1, SUMMA, X_1, Y_1, My_program.

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

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

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

Стандартные типы — это числовые, литерные и логические типы.

Числовой тип, к которому относятся целые и вещественные величины, позволяет оперировать с числами. Целые числа, которые в учебном алгоритмическом языке составляют тип цел, сверху ограничены положительным числом Nmax, а снизу — отрицательным числом Nmin. Значения Nmax и Nmin определяются объемом ячеек памяти, в которые записываются целые числа. Обычно для целых чисел выделяется два байта памяти, соответственно границы диапазона равны [Nmin = –32768 и Nmax = 32767]. Считается, что все операции с величинами типа цел выполняются по обычным правилам арифметики, за одним исключением: возможны две операции деления div и mod.

Операция div обозначает целочисленное деление. При делении с точностью до целых чисел получается два результата — частное и остаток. Знак результата берется по обычным правилам, а полученный остаток игнорируется. Например:

Операция mod определяет остаток при делении двух целых чисел.

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

К другому числовому типу относятся вещественные (вещ) величины. Значения вещественных величин могут изображаться в форме с фиксированной запятой (например, 0,3333; 2,0; –4,567 и т. д.) и с плавающей запятой (например, 7,0*10 2 , 5,173*10 –3 и т. д.).

В отличие от целых чисел, действия с вещественными числами могут быть неточными — это связано с ошибками округлений. Объем памяти, который предоставляется для хранения значений вещественной переменной, — от 4 до 10 байтов (в зависимости от выбранного формата числа). Над числовыми величинами можно выполнять как арифметические операции, так и операции сравнения (>, =,

Литерный тип, включающий символы и строки, дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов: букв, цифр, знаков препинания, пробела и других специальных знаков (возможными символами могут быть символы таблицы ASCII). Литерные величины обычно заключаются в кавычки: «а», «В», «СТРОКА», «1_2_3». В учебном алгоритмическом языке литерные величины обозначаются как лит. В других языках программирования (например, в Паскале) различают символьный (char) и строковый (string) типы. Величины символьного типа состоят из одного символа и занимают в памяти всего 1 байт. Величины строкового типа представляют собой различные последовательности символов, которые предусмотрены кодовой страницей, установленной в компьютере. Длина строки может составлять от 0 до 255 символов. Над всеми литерными величинами возможны операции сравнения. С помощью отношений типа «a» < "b", "b" < "c", "c" < "d". выполняется упорядочение литерных величин (сортировка по возрастанию или убыванию).

Еще одной операцией, характерной для символьных и строковых величин, является операция конкатенации (слияния): «a» + «b» = «ab».

Логический тип позволяет определять логические переменные, которые могут принимать только два значения: истина (true) или ложь (false). Для представления логической величины достаточно одного бита, однако, поскольку место в памяти выделяется по байтам, логической величине отводится минимальная «порция» памяти — один байт. Над логическими величинами можно выполнять все стандартные логические операции.

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

Оператор присваивания

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

В операторах присваивания используется либо обычный знак равенства, либо сочетание двоеточия и знака равенства «:=». Поскольку знак присваивания — это не знак равенства, возможны записи вида Х := Х + 1 или А := А – В. Нужно учитывать, что оператор присваивания будет выполняться только в том случае, если значения всех переменных в правой части уже определены и выполняется соответствие типов для правой и левой части оператора присваивания. Например, С := А > B выполнится только в том случае, если для переменной С определен булевский (логический) тип. Операция присваивания может быть применена к большинству типов величин. Однако для каждого из типов предусмотрен свой набор операций.

Локальные, глобальные и общие переменные

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

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

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

Примеры решения задач

Пример 1. Значения заданных переменных А, В перераспределить таким образом, чтобы А и В поменялись значениями.

Решение. Возможны два варианта решения:

С использованием промежуточной переменной С Без использования дополнительной переменной
C := A;
A := B;
B := C
A := A + B;
B := A – B;
A := A – B

Пример 2. Определить значение переменной A после выполнения фрагмента алгоритма:

Решение. Оформим решение в виде таблицы.

A B D Условие
2 –2 10 да
–4 –2 12 да
8 –2 14 да
–16 –2 16 да
32 –2 18 да
–64 –2 20 да
128 –2 22 нет — окончание цикла

Ответ: А = 128.

Пример 3. Определить значение переменной S:

нц пока A + B < 10

A := A + 1; B := B + A

Решение. Оформим решение в виде таблицы.

A B A + B S
–1 1 0
0 1 1
1 2 3
2 4 6
3 7 10 — условие выхода из цикла 21

Ответ: S = 21.

Пример 4. Записать последовательность операций присваивания (:=), которая позволит определить номера подъезда и этажа по номеру N квартиры девятиэтажного дома, считая, что на каждом этаже по 4 квартиры, а нумерация квартир начинается с первого подъезда.

Х := (N – 1) div 36 + 1

Y := (N – 1) div 4 + 1

Например, для квартиры с номером 150 получим:

Х = (150 – 1) div 36 + 1 = 4 + 1 = 5;

N = 150 – (5 – 1) * 36 = 6;

Y = (6 – 1) div 4 + 1 = 2.

Ответ: квартира с номером 150 находится в пятом подъезде, на втором этаже.

Работа с массивами (заполнение, считывание, поиск, сортировка, массовые операции и др.)

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

  1. объединением однородных элементов данных;
  2. объединением разнородных элементов данных.

В первом случае примером могут служить массивы, а во втором — записи.

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

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

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

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

Количество элементов массива называется размерностью массива.

Итак, массив характеризуется:

  • размерностью;
  • базовым типом элементов;
  • типом индекса (может быть только порядковым типом);
  • множеством значений для индекса.

Массив может быть одномерным (вектор) и многомерным (матрица).

Одномерный массив содержит одно измерение; каждый элемент массива обозначается идентификатором (именем) массива с индексом. Многомерный массив содержит n-е количество измерений; каждый элемент массива обозначается идентификатором массива для n индексов.

Существует несколько способов заполнения массива данными:

  1. непосредственное присваивание значений элементам;
  2. заполнение массива произвольными элементами, случайными числами;
  3. ввод значений элементов с клавиатуры или чтение из файла.

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

Примечание. Строковый тип данных напоминает одномерный массив, в котором элементами являются символы. К примеру, строку «МАМА КУПИЛА ХЛЕБ» можно рассматривать как одномерный массив из 16 символов (включая пробелы). Эту строку можно обозначить идентификатором (например, Novost) и пронумеровать все символы, считая их элементами массива: Novost (l) = «М», . Novost (16) = «Б».

Однако для работы с символьной информацией более гибким инструментом является не одномерный массив, а строка (string). Это связано с тем, что количество символов в строке, в отличие от массива, не фиксировано. Благодаря этому к строке можно без ограничений применять стандартные операции и функции, предназначенные для работы с текстом.

Задачи, связанные с обработкой массивов, как и все задачи вообще, условно можно разделить на два вида:

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

Очевидно, что без умения решать задачи первых двух видов невозможно решать нестандартные задачи.

Стандартные задачи обработки массивов

Пример 1. В массиве А каждый элемент равен 0 или 1. Заменить все нули единицами и наоборот.

Решение. Достаточно одного оператора присваивания в теле цикла:

Пример 2. В массиве каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все 0, затем все 1 и, наконец, все 2. Дополнительный массив не использовать.

Решение. Можно не переставлять элементы массива, а подсчитать количество 0, 1, 2 и заново заполнить массив требуемым образом.

Пример 3. Даны два n-элементных массива Х и Y одного типа. Поменять местами все Xi и Yi, (i = 1. n), не используя промежуточные величины.

Решение. Обмен можно выполнить в цикле для всех i от 1 до n с помощью серии из трех операторов присваивания:

Пример 4. Записать алгоритм нахождения максимального элемента массива А(n) и его номера.

Решение. На псевдокоде требуемый алгоритм запишется следующим образом:

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

Пример 5. Найти сумму элементов одномерного массива А(n).

Решение. На псевдокоде алгоритм нахождения суммы запишется следующим образом:

Примечание. Для нахождения суммы положительных элементов массива вместо оператора

S := S + A[i] необходимо записать:

если A[i] > 0

то S := S + A[i]

Пример 6. Записать алгоритм вычисления произведения элементов столбцов заданной вещественной двумерной матрицы A(n, m).

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 7. Подсчитать количество элементов для заданной целочисленной матрицы A(n, m), равных ее максимальному элементу.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 8. Запиcать алгоритм обмена элементами строк с номерами P и Q в заданной вещественной матрице A(n, m).

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 9. Включить заданное число D в одномерный упорядоченный по возрастанию массив F(n) с сохранением упорядоченности.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 10. Сформировать новый массив B из элементов целочисленного массива A(n), для которых выполняется условие D < Ai < C.

Решение. На псевдокоде алгоритм запишется следующим образом:

Пример 11. Найти в заданном целочисленном массиве А(m) хотя бы одну пару элементов, совпадающих по значению.

Решение. На псевдокоде алгоритм запишется следующим образом:

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

  1. элемент найден;
  2. весь массив просмотрен — элемент не найден.

В упорядоченном массиве поиск можно значительно ускорить, применяя метод половинного деления, или бинарный поиск. Его идея заключается в следующем. Пусть фиксированный массив упорядочен по неубыванию (ai ≤ ai + 1). Случайно выбранный элемент am (обычно берут средний элемент) сравнивают с элементом поиска х. Если он меньше х, то искомый элемент может быть среди элементов am + i, . аn, т. е. в правой половине массива. Если он больше х — то среди элементов левой части массива. Если же он равен х, то поиск успешно заканчивается.

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

К простым методам сортировки относят:

  • сортировку с помощью обмена (метод пузырька);
  • сортировку с помощью прямого включения;
  • сортировку с помощью выбора.

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

Алгоритм сортировки массива A(n) по возрастанию на псевдокоде:

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

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

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

Примеры решения задач

Пример 1. Одномерный массив, содержащий десять элементов, заполняется по следующему закону: A[1] = 1; A[2] = X; A[i] = 2 * X * A[i – 1] – A[i – 2], где i = 3, 4, . 10. Каким будет значение A[5] при X = 1?

Решение. Представим значения первых пяти элементов массива А, полученные по заданному закону при Х = 1:

A[3] = 2 * Х * A[2] – A[1] = 2 * 1 * 1 – 1 = 1;

A[4] = 2 * Х * A[3] – A[2] = 2 * 1 * 1 – 1 = 1;

A[5] = 2 * Х * A[4] – A[3] = 2 * 1 * 1 – 1 = 1.

Таким образом, значение A[5] при Х = 1 будет равно 1.

Пример 2. Задан двумерный массив А(n, n). Определить, что вычисляет приведенный фрагмент алгоритма:

Решение. В данном алгоритме переменной S присваивается значение 0. Затем в структуре циклов по переменным i и j каждый из элементов массива Аij сравнивается с нулем (А[i, j] > 0) и если элементы Аij положительны, то квадраты А[i, j]^2 положительных элементов Аij увеличивают значение суммы S (S := S + A[i, j]^2).

Ответ: фрагмент алгоритма вычисляет сумму квадратов положительных элементов массива.

Пример 3. Задан фрагмент алгоритма, использующий двумерный массив (таблицу) М(n, n), два одномерных массива A(n), B(n) и переменную X. Определить назначение массивов А и В и переменной.

Решение. Представим фрагмент алгоритма словесно.

  1. Переменной X присвоить значение 0.
  2. Переменной i присвоить значение 1.
  3. Если i ≤ n, то перейти к следующему пункту; в противном случае — конец фрагмента алгоритма.
  4. Элементу одномерного массива А с индексом i присвоить значение элемента двумерного массива М, находящегося в i-й строке и первом столбце.
  5. Элементу одномерного массива В с индексом i присвоить значение 1.
  6. Переменной j присвоить значение 1.
  7. Если j ≤ n, то перейти к следующему пункту; в противном случае — к п. 13.
  8. Если М[i, j] < A[i], то перейти к следующему пункту; иначе — к п. 11.
  9. Элементу A[i] присвоить значение элемента массива М, находящегося в i-й строке и j-м столбце.
  10. Элементу В[i] присвоить значение переменной j.
  11. Переменной Х присвоить значение суммы X + M[i, j].
  12. Переменной j присвоить значение суммы j + 1 и вернуться к п. 7.
  13. Переменной i присвоить значение суммы i + 1 и вернуться к п. 3.

Таким образом, анализ алгоритма показывает, что переменная X накапливала сумму всех элементов массива М; массив А — минимальные элементы соответствующих строк массива М; массив В — индексы (порядковые номера столбцов) минимальных элементов в соответствующих строках массива М.

Пример 4. Составить алгоритм определения наличия среди элементов главной диагонали заданной целочисленной матрицы A(n, m) хотя бы одного положительного нечетного элемента.

Решение. Для всех элементов Аij главной диагонали выполняется условие i = j. Определение наличия нечетных элементов выполняется с помощью операции mod (остаток от целочисленного деления), при этом, если результат mod равен 1, — число нечетное.

Структурирование задачи при ее решении для использования вспомогательного алгоритма. Вспомогательные алгоритмы: процедуры и функции

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

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

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

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

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

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

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

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

Команда вызова подпрограммы выполняется в три этапа:

  1. вычисление фактических аргументов;
  2. исполнение алгоритма подпрограммы;
  3. присвоение полученных значений результатов алгоритма-подпрограммы соответствующим фактическим переменным.

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

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

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

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

Технология программирования

Чтение короткой (30±50 строк) простой программы на алгоритмическом языке (языке программирования)

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

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

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

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

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

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

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

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

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

Примеры чтения программ на языках Pascal, QBASIC

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

Пример 1. Дана программа на двух языках программирования. Определить, какую задачу она решает.

Решение. Проанализируем тексты программы:

  1. формируется тело программы и описываются переменные;
  2. вводятся натуральные числа М и N, причем проверяется условие корректности ввода: числа должны быть положительные. Если введенные значения не удовлетворяют условию, то ввод повторяют, пока условие не будет выполнено;
  3. выбирается наименьшее значение из М и N, результат записывается в K;
  4. NOD присваивается значение 1;
  5. в цикле от двух до K генерируется число I;
  6. тело цикла — в условном операторе проверяется, является ли значение переменной I одновременно делителем М и N. Если условие выполняется, то текущее значение I сохраняется в переменной NOD; если условие не выполняется, NOD не изменит своего значения;
  7. после перебора всех значений I в NOD или запишется наибольший делитель двух чисел М и N, или останется значение 1;
  8. последний оператор программы служит для вывода результата работы программы — значения переменной NOD.

Переменные, используемые в программе:

N, М — исследуемые числа;

I — переменная цикла;

NOD — наибольший общий делитель;

К — наименьшее из М и N.

Ответ: данная программа позволяет определить для двух чисел М и N их наибольший общий делитель NOD.

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

Пример 2. Дана программа на двух языках программирования. Определить, какую задачу она решает.

  • ООО «Экзамер», 2024
  • Написать нам
  • Юридические документы

Среднеквадратичная аппроксимация четным неотрицательным полиномом Текст научной статьи по специальности «Математика»

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Супруненко С. Н.

Среднеквадратичная аппроксимация четными неотрицательными дробно-рациональными функциями
Методы решения сеточных уравнений конечно-элементной аппроксимации пространственных течений
Выбор метода аппроксимации вязких членов в методе Галеркина с разрывными базисными функциями

Программа построения моделей элементов СВЧ монолитных интегральных схем на основе многомерных полиномов

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

Текст научной работы на тему «Среднеквадратичная аппроксимация четным неотрицательным полиномом»

УЧЕНЫЕ ЗАПИСКИ ЦА Г И Том XIX 198 8

СРЕДНЕКВАДРАТИЧНАЯ АППРОКСИМАЦИЯ ЧЕТНЫМ НЕОТРИЦАТЕЛЬНЫМ ПОЛИНОМОМ

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

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

исходя из минимизации взвешенной среднеквадратичной ошибки аппроксимации

по коэффициентам полинома при дополнительном условии

П(ш2, 0)>О для всех м. (2)

В (1) функция ф(со) —ограниченная и неубывающая на отрезке

со е [0, 1] — задает распределение весов аппроксимации. Относительно

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

Особенностью рассматриваемой аппроксимационной задачи является необходимость соблюдения условия (2), в силу чего минимизация функции е(0) в общем случае требует привлечения алгоритмов условной минимизации [1]. Однако использование последних в данном случае встречает затруднения из-за сложности преобразования условия (2) к соответствующим нелинейным ограничениям на коэффициенты полинома П(со2, ф) (см. приведенные в [2] громоздкие соотношения для п = 4 и 5). Другой альтернативой могла бы быть минимизация е(0) в классе решения задач квадратичного программирования с континуумом ограничений (2). Применение этого подхода так же проблематично из-за необходимости поиска активных ограничений среди бесконечного числа заданных.

Предлагаемый в статье метод решения позволяет обойти данные затруднения путем преобразования исходной задачи условной минимизации к минимизации безусловной на основе использования соотношения спектральной факторизации. Известно [3], что вещественный четный полином, если он неотрицателен, может быть представлен в виде произведения двух комплексно сопряженных полиномов, имеющих вещественные коэффициенты, т. е. П(со2, 0) =Р(т, а) Р(—/со, а), где Р(з, а) =а1 + а2з + а382+. +ansn~i — так называемый спектральный фактор полинома П(со2, 0). При подстановке этого соотношения в (1) функция Ошибки аппроксимации преобразуется в зависимость от коэффициентов спектрального фактора и ее минимизация по этим коэффициентам может выполняться на открытом множестве. Вычислительная эффективность предлагаемого метода достигнута главным образом за счет того, что оказалось возможным получить в явной компактной зависимости от степенных моментов аппроксимируемой функции и от коэффициентов спектрального фактора все необходимые для построения практических алгоритмов минимизации соотношения. В статье определены условия единственности решения преобразованной задачи и показана возможность отыскания его с применением известных итерационных алгоритмов ньютоновского типа.

Отметим ряд конкретных примеров практического использования аппроксимации рассматриваемого вида. Так, при синтезе оптимальных линейных динамических систем на основне решения интегрального уравнения Винера—Хопфа, требуется спектральная факторизация числителя и знаменателя дробно-рациональной функции спектральной плотности [4]. Спектральная факторизация в рамках решения аппроксимационной задачи (см. соответствующий пример в данной статье) позволяет сделать точность решения частотно зависимой, а так же дает возможность расширить класс факторизуемых функций, включив в него в том числе и функции знаконеопределенные. Указанные обстоятельства отделяют соответствующий алгоритм решения от уже известных (см. например [5]). Аппроксимация четным неотрицательным полиномом может быть применена при синтезе линейных фильтров с желаемыми амплитудно-частотными характеристиками при условии, что заданы

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

2. Минимизация ошибки аппроксимации. Рассмотрим вначале исходную задачу минимизации функции е(0). Используя соотношение ПК, 6) = 2Т0, в котором й = [1, со2, . ш2п~2]т — я-мерный вектор, преобразуем (1) к виду

в(9) = 80 — 2Ртъ + втне,

Элементы вектора Р определяются по формуле (3). Матрица Н — ган-келева, элементы ее образованы последовательностью степенных четных моментов:

В силу принятых для функции ф(со) ограничений эта последовательность позитивна и соответственно матрица Н — положительно определена [7].

Выделим в евклидовом пространстве Яп, прямоугольными координатами которого являются элементы вектора 0, область С>, во внутренних точках которой полином П((о2, 0) положителен, а в граничных точках может принимать и нулевые значения. Вследствие линейности (по 0) ограничения (2) область С> представляет собой выпуклый конус [8]. Для решения рассматриваемой задачи существенно следующее утверждение: функция е(0) имеет в области С> единственный локальный минимум, являющийся также и абсолютным. Если бы не было ограничения (2), этот минимум легко можно было определить, приравнивая нулю градиент функции е(0). Соответствующее решение, полученное с учетом (4), имеет вид:

0*=//~1/7 е(9*) = е0 — Р* Н~1 Р.

В общем случае 0* (£ С>, поэтому для решения задачи необходимо применение более сложных методов поиска минимума, учитывающих (2).

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

Вспомогательным к исходному полиному Р(з, а) назовем полином Р(5, х), коэффициенты которого определяются по правилу:

(Квадратные скобки здесь означают символ целой части числа.)

Расширенной матрицей Гурвица (РМГ) вектора х = [хи . х„]т назовем пХп матрицу Г (х), элементы которой определены правилом:

~ 1 0 в остальных случаях.

Обычная матрица Гурвица, рассматриваемая в задаче устойчивости полинома [9], отличается от РМГ отсутствием первых строки и столбца.

Четно-разреженной ганкелевой матрицей (ЧРГМ) вектора х назовем пХп ганкелеву матрицу (/(х), элементы которой определены правилом:

Г Х(1+п12 при /+7 —четном,

В матрице ЧРГМ каждая четная косая диагональ нулевая.

Матрицы РМГ и ЧРГМ обладают двумя важными свойствами, которые будут использоваться при выводе ряда формул алгоритма минимизации:

Г(у)тх = Г(л;)т_у, Г (y)x = G(x)y.

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

С учетом введенных понятий можно получить следующее представление для четного неотрицательного полинома:

П (ш2, 6)= ЙТГ (х)т х.

Здесь х — вектор коэффициентов вспомогательного к спектральному фактору P(s, а) полинома.

Из этого представления нетрудно усмотреть формулу взаимосвязи для коэффициентов полиномов П(ю2, 0) и P(s, х):

Подставляя (5) в (4), преобразуем тем самым функцию ошибки аппроксимации к явной зависимости от х:

г (х) = е0 — 2FTГ (х)тх + х’Г(х)НГ(х)тх. (6)

Нелинейное преобразование (5), назовем его здесь отображением Ф, отображает всю открытую область Rn определения вещественного вектора х в замкнутую область Q, в которой коэффициенты полинома П(со2, 0) удовлетворяют условию его неотрицательности, т. е. имеет место #: Rn-+Q. Поэтому поиск минимума функции е(х) может проводиться на открытом множестве. Так как между коэффициентами полиномов P(s, а) и P(s, х) имеется простое взаимно однозначное соответствие, то рассматриваемое преобразование по своей сути означает переход к минимизации ошибки аппроксимации непосредственно по коэффициентам спектрального фактора.

Следует, однако, отметить, что отображение 0 свойством гомеоморфизма, т. е. взаимно-однозначного соответствия не обладает. Это слепляющее отображение, поскольку разным x^Rn может соответствовать

Выделим в евклидовом пространстве Яп, прямоугольными координатами которого являются элементы вектора х, п связных областей Од, (? = 0, 1 — 1, во внутренних точках которых корни полинома

Р(5, а(х)) принадлежат правой полуплоскости комплексного аргумента 5, а в граничных точках среди этих корней появляются чисто мнимые [10]. Области Од являются коническими, причем, если хе/),, то и —х^Од. Так как смена знака х мало что добавляет к процессу определения минимума функции е(х), то в дальнейшем за область Од будем принимать только часть конуса, соответствующую положительным значениям XI.

У каждой области существует образ (2д = 0(/)д), который при не обязательно совпадает со всей областью ф, а возможно составляет только часть ее. Например, при п = 3 имеет место

62;> — 2/Мз, в80). В то же время область =

Данные обстоятельства приводят к необходимости поиска минимума функции е(х) только в тех областях Од, которые гарантированно отображаются на всю область (?. Известно [3], что таким свойством обладают области А) и /)«-1- Так как в практических приложениях основной интерес представляет устойчивый спектральный фактор [3, 4], то в дальнейшем будем рассматривать только одну область £>0. В связи с этим введем ограниченное отображение которое как и Ф задается формулой (5), но действие которого ограничено пределами области О,. Это отображение обладает тем важным свойством, что оно обеспечи-

Обратимся к задаче отыскания локальных минимумов функции е(х). Раскладывая г(х) в ряд Тейлора в окрестности произвольной точки х и выполняя преобразования, учитывающие свойства матриц РМГ-ЧРГМ, нетрудно получить следующие выражения для вектора градиента и матрицы вторых производных минимизируемой функции:

у*, г (х) = АО (ё (х)) + 8Г (х) ЯГ (х)т, (8)

В экстремальных точках градиент функции е(х) равен нулю, т. е.:

Структура уравнения (9) предполагает возможность существования решений, удовлетворяющих условию £(х) = 0, т. е. уравнению

Нетрудно заметить, что решениям уравнения (10) соответствует образ 0* = Н~1 Р, являющийся глобальным минимизатором функции е(0) на открытом множестве. Поэтому все вещественные решения уравнения (10), если они имеются, обеспечивают абсолютный минимум ошибки аппроксимации с соблюдением условия (2). Среди таких решений найдется и точка, принадлежащая области £)0.

Рассмотрим теперь решения (9), которые уравнению (10) не удовлетворяют. Из условия разрешимости (9) относительно £(-*0=0 следует, что такие экстремальные точки должны принадлежать гиперповерхности в Яп, задаваемой соотношением с!е1:Г(л;) = 0. Можно показать, что если эти точки принадлежат также£)0, то спектральный фактор находится на границе устойчивости (т. е. граница области £>0 является частью указанной гиперповерхности). В зависимости от знаковой

определенности матрицы экстремальная точка может быть сед-

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

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

ний квадрант в координатах х1х2. Точечным пунктиром на рисунках отмечены линии уровня, проходящие через седловые точки.

3. Итерационные алгоритмы поиска минимума. Для отыскания точек локального минимума функции г(х) можно применить большинство известных методов безусловной минимизации. Если удается обеспечить принадлежность решения области Д, то найденный таким образом локальный минимум будет абсолютным. Наличие явных выражений для вектора градиента (7) и матрицы вторых производных (8) минимизируемой функции делает привлекательным применение ньютоновских ‘итерационных алгоритмов минимизации, обладающих, как известно [1]. свойством квадратичной сходимости. Рассмотрим эти алгоритмы.

Пусть хк — известное приближение к точке локального минимума на шаге итерации к. Решение на шаге й+1 представляется в виде хк+1 = хк -\-аькхк, где вектор Ахк и параметр задают соответственно направление и длину шага итерации.

Алгоритм Ньютона (АН). В исходном варианте этого алгоритма, именуемом иногда алгоритмом Ньютона — Рафсона, принимается аь=1 и Ахк = — (у^8(л*)ГЧ^(л*).

С учетом соотношений (7) и (8) в данном случае имеем:

Для того чтобы вектор Ахк был направлением убывания е (л:), необходима положительная определенность матрицы J

туры этой матрицы показывает, что областью положительной определенности является все открытое пространство исключая центральную его часть, имеющую форму звезды. Благодаря этому всегда можно обеспечить положительную определенность матрицы J (х) путем необходимого удлинения вектора х. Другим способом обеспечения положительной определенности матрицы У (х) является модификация этой матрицы в случае нарушения данного свойства. Вопросы восстановления положительной определенности матрицы путем некоторой модификации ее элементов достаточно широко освящен в соответствующей литературе. Отметим здесь только наиболее удобный в вычислительном отношении метод Гилла и Мюррея [11], который предусматривает автоматическую коррекцию диагональных элементов матрицы в процессе решения системы уравнений типа (11) с разложением матрицы системы на треугольные множители (т. е. с Ьи или 1^Е)и факторизацией матрицы). Ввиду универсальности и простоты метода, применение его в алгоритме АН наиболее предпочтительно.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Алгоритм Гаусса—Ньютона (АГН). От рассмотренного выше этот алгоритм отличается только тем, что вместо полной матрицы вторых производных используется ее «укороченный» аналог. В данном случае это матрица J(х) = 2Г (х) НГ (х)с. Из (11) с использованием такой замены можно получить:

2Г (л:*)т Ахк — 6* — Ьк, (12)

где 0й = Г (хкУ хк, 0* = Н~х Р.

Специальная структура матрицы Г(х) дает возможность, используя метод исключения Гаусса [9], построить быстродействующий алгоритм решения (12). Подобный алгоритм рассмотрен в [5]. Однако эффективность данного подхода теряется, если точка 0* близка к границе области (2, поскольку в точке решения матрица Г(х) близка к вырождению. Получение решения непосредственно из уравнения типа (11) более надежно, так как имеется возможность обеспечения строгой положительной определенности матрицы /(*) путем ее модификации как и в алгоритме АН.

Алгоритм АГН обладает весьма важным свойством, выделяющим его среди всех прочих алгоритмов поиска минимума е(х). А именно если 0*еС, то итерации АГН с параметром длины шага а, эту область не покидают.

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

Оптимизация длины шага. Используя (6) и (11), получим величину приращения е(х) вдоль направления Ах в зависимости от а:

Ае (а) = — 4А1 а + 2Л2 а2 + 4А3 а® ->- А4 а*,

А1 = ^x!J (х) Ах, А2 = Ахт/(х)Ах,

Л3 = хтГ (Ах)//Г (Ах)тАх, Л4 = ДхТ (Ах) ЯГ (Ах)1 Ах.

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

У (х) должна быть положительно определена, поэтому Л^О (при АхФО). Очевидно, так же и Л4>0, поэтому функция Де(а) обязательно имеет один или два минимума при положительных а. Эти минимумы удовлетворяют условию дЛе(а)/

Оптимальное масштабирование. Путем выбора масштабного множителя в преобразовании х-^-хх можно обеспечить дополнительную минимизацию ошибки аппроксимации без существенных вычислительных затрат. Используя (4) получим

г (х) = е0 — 2т2 Г 6 + х4 6Т Я0.

Минимум функции г (г) достигается при тор4 = I «еТ/лГ) и Равен

г(?6Р1) = г0—-рЖ’ Масштабирование х удобно тем, что оно не ме-

няет статуса принадлежности х области О0.

Комбинированный алгоритм. Рассмотренные алгоритмы АН и АГН вместе с соответствующими модификациями ‘можно объединить в

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

1. Задать стартовую точку х°еД и установить счетчик циклов переноса решений

2. Проверить выполнение условия окончания счета (например, по малости нормы градиента IIУхе(х°) ||). В случае выполнения условия окончания уйти на 6.

3. Найти локальный минимум е(х), используя итерации АН с оптимальным выбором т, а и по необходимости с модификацией матрицы У(х). Итерации начинать с точки х°. При с запоминанием в х° последней итерации, еще принадлежащей Д (учитывая возможность выхода итераций АН из области О0). При 1 такой проверке подвергается только найденное решение х*. Если найденное решение х* (<7^1) принадлежит В0, то принять х°=х* и уйти на 6.

6. Выполнить преобразование а = а(х°) и выдать а в качестве готового решения.

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

Отметим, что в качестве стартовой точки х° на шаге 1 может быть использована точка х(а), полученная с использованием спектрального фактора нулевого приближения следующего вида: Р(в, а) = (1 + 5)п-1. Коэффициенты этого полинома являются биномиальными коэффициентами, т. е.: = &=1. я. Требуемая на шаге 3 проверка при-

4. Примеры. Предложенный выше комбинированный алгоритм реализован в виде программы на алгоритмическом языке ФОРТРАН. Рассмотрим конкретные примеры, иллюстрирующие, работоспособность этого алгоритма.

Спектральная факторизация. Для четного полинома П (8, который на интервале ве[0, 67,

О, 80] отрицателен (на рис. 4 соответствующая зависимость показана сплошной линией) и поэтому не имеет спектрального фактора с действительными коэффициентами, выполнена приближенная спектральная факторизация путем минимизации среднеквадратичной ошибки аппроксимации следующего вида:

е = ^[П(о>2, 6) — Р(ш, а)Р(—ш, а)]2о)й?ш.

В данном случае использовалась функция распределения весов аппроксимации ср (св) = -1— со2, обеспечивающая повышение точности аппроксимации с ростом аргумента частоты со. При поиске минимума е(х) в качестве стартовой точки итераций АН принято х°=[1; —4; —6; 4; 1]т. Останов итераций производился по достижению заданной величины относительного приращения ошибки аппроксимации (принята величина 10-11). В процессе решения потребовалось выполнить 12 итераций АН, 18 итераций АГН (перенос решения в £>0), затем две итерации АН

(стартовой точкой этих итераций было решение предыдущих итераций АГН) и одна итерация АГН (перенос решения в Б0 с использованием той же стартовой точки, что и в предыдущих итерациях АН). Получено:

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

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

характеристик объекта управления. В [12] для модели динамики ЛА по крену с передаточной функцией

Гл* (5) — 4500 [і (1 + 5,2) (і + тет- + -да) (> + 2ШГ + 2да) х:

приведена следующая передаточная функция оптимального регулятора:

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

№ су (5) более низкого порядка, достаточно хорошо аппроксимирующим №су(5) в основном диапазоне рабочих частот регулятора. Воспользуемся для этой цели методом среднеквадратичной аппроксимации функции /(со) = | Шсу(ш) |2. В результате аппроксимации должен быть получен

четный неотрицательный полином | №су(«й) |2 и его устойчивый (воз-

можно на границе устойчивости) спектральный фактор И7су(«). В качестве примера рассмотрим результаты расчетов, полученные с использованием среднеквадратичной ошибки аппроксимации в виде конечной суммы:

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

вались полиномы №су($) 1, 2, 3-го порядков, для которых установлены разные диапазоны аппроксимации: от 1 рад/с до соответственно 50, 100, 150 рад/с. Запись ошибки аппроксимации в виде конечной суммы означает, что функция распределения весов аппроксимации <р((о) является разрывной ступенчатой со скачками в точках со^. Поэтому при вычислении степенных моментов, из которых формируются вектор Р и матрица Н, интегралы в соответствующих формулах расчета степенных моментов заменялись на конечные суммы с суммированием по указанным выше значениям частоты &>&. В конечном итоге получены следующие аппроксимации исходного регулятора:

Гоф) = 0,05 (1 -М/12.1)(і + + -§г)(і + + -^і) X

£ = Х(|№су (*»,) і 2 — і і^су (*Ч) і *)*•

НРсу («) = 0,05 (1 + 8,2-10-*2 5),

ІГсу (5) = 0,05 (1,152 + 8,1 • 10-г х + 8,2-10~4 я2),

ГСУ (5) = 0,05 (1,074 + 9,1 • 10~2 Я + 1,18 • Ю-Зв2 + 6,5 • 10″5 53).

6—«Ученые записки» № 2

На рис. 5 показаны амплитудно-фазово-частотные характеристики разомкнутого контура ЛА+СУ с исходным регулятором 7-го порядка и с регуляторами пониженного порядка, полученными путем аппроксимации. Видно, что даже с регулятором 1-го порядка могут быть обеспечены вполне удовлетворительные динамические характеристики ЛА с системой управления (в данном случае запасы устойчивости по амплитуде и фазе равны соответственно 5,03 дБ и 33,5°).

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

1. Единственность локально-абсолютного минимума е(в) на ()■

Множество ф, во внутренних точках которого полином П( 0] и поэтому является выпуклым замкнутым конусом [8]. В силу положительной определенности матрицы Н функция е(0) является выпуклой всюду в Яп. Выпуклая функция имеет на выпуклом замкнутом множестве единственную точку локального минимума, являющуюся так же и минимумом абсолютным [1].

2. Векторно-матричное представление для четного неотрицательного полинома П(со2, 0).

п («3, в) = Р(т, а)Р(— Ы, а) = ^ (т)к+1-2 ак аг ^ “6+,~2-*й хг .

Полученное выражение есть квадратичная форма хТ0(&)х, в чем легко убедиться, если учесть, что элементы матрицы 0(2) равны g/г^ = юк+1~2 при к+1 четном и gkl — 0 при к-\-1 нечетном. Учитывая, что О (2) х = Г (х) 2, получим П (о>2, 6) = = 2Т Г (*)т х.

3. Основное свойство итераций АГН при минимизации е(х).

Справедливо следующее утверждение. Если Н~1 У7 = 6* £ и хк 0 (здесь

символ М означает внутреннюю часть области без ее граничных точек), то для всех значений параметра длины шага итерации а/* е [0, 1) выполняется хк+1 £ шЮ0> 3 для 01/1=1 выполняется Хк + 1£Оо.

и с учетом (12) получим:

а\ Г (Дл:*)т Д** =0*+I-(l — ak) 6* — я* 6*.

Так как для всех Axk£Rn справедливо 2Т Г (Длс*)т Дат*^0, то должно выполняться

QT6*+l^aA QT0* + (1 _ а/г) QT0* > (! _aft)2T0ft.

В рассматриваемом случае xk£inl D0, поэтому и 0* ^ int Q. Но тогда для всех 1) должно выполняться 2Т0Й+1>О, т. е. 6ft+1£intQ. Так как в данном случае граница Q не достигается, то в силу непрерывности зависимости л’*+1 от я* и в силу свойства гомеоморфизма отображения *>0 не достигается и граница D0, а значит xk+1£int D0. Если же а* = 1, то х*+* является предельной точкой последовательности при ak 1. Очевидно, что самое многое эта точка может принадлежать границе D0. Поэтому в общем случае xk+lcDo.

4. Проверка устойчивости спектрального фактора по коэффициентам вспомогательного полинома.

Докажем вначале следующее утверждение.

Главные диагональные определители k-ro порядка матриц РМГ векторов исходного и вспомогательного полиномов отличаются только знаками, причем имеет место

det (Г (a))ft = (-l)^det(r (x))k,

Доказательство. Рассмотрим знаковую структуру матрицы, полученной из матрицы Г (а) заменой элементов вектора а элементами вектора х. Она имеет вид:

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Если на —1 умножить все элементы четных столбцов этой матрицы, а затем все элементы строк 3, 4, 7, 8. то знаковая структура матрицы станет полностью положительной. Элементарный подсчет показывает, что общее по числу строк и столбцов количество таких умножений нечетно только для порядков матрицы, равных 2, 6, 10, 14. Этому циклическому чередованию соответствует приведенная выше функция четности ц(6). Применение теперь известного правила умножения строк и столбцов определителя на число [9] и завершает доказательство.

Используя данное утверждение, преобразуем детерминантный критерий Гурвица [9] проверки устойчивости полинома P(s, а) к системе неравенств, включающих только коэффициенты вспомогательного полинома P(s. х):

(— 1 )•*■det (Г (х))й > 0, * = п.

На основании этих неравенств нетрудно получить и модификацию критерия Рауса [9]:

С — 1 >^*/21 £>0, k=\.п. Здесь Я, j, — k-ft элемент первого столбца таблицы

Рауса, составленной по коэффициентам вспомогательного полинома P(s, х). Отметим, что если исходный полином P(s, а) находится на границе устойчивости, т. е. среди его корней имеются чисто мнимые, то должно выполняться det (Г (л:))п = 0.

1. Поляк Б. Т. Введение в оптимизацию. — М.: Наука, 1983.

2. Д ж у р и Э. Инноры и устойчивость динамических систем. — М.: Наука, 1979.

3. К а л м а н Р. Е. Когда линейная система управления является оптимальной. — Теоретические основы инженерных расчетов. Труды амер. общества инженеров-механиков, 1964, № 1.

4. Чанг Ш. А. С. Синтез оптимальных систем автоматического управления.— М.: Машиностроение, 1964.

5. V о s t г у Z. ‘New algorithm for polynomial spectral factorization with quadratic convergence. — Kybernetika (CSSR), vol. 12, 1976.

6. Б e с e к e p с к и й В. А., Н е б а л о в А. В. Робастные системы автоматического управления. — М.: Наука, 1983.

7. Ахиезер Н. И. Классическая проблема моментов.— М.: Физ-матгиз, 1966.

8. Никайдо X. Выпуклые структуры и математическая экономика.— М.: Мир, 1972.

9. Гантмахер Ф. Р. Теория матриц. — М.: Наука, 1967.

10. Чеботарев Н. Г., М е й м а н Н. Н. Проблема Рауса—Гурвица для полиномов и целых функций. — Труды математич. ин-та им. Стеклова, 1949, т. 26.

И. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация.— М.: Мир, 1985.

12. Несли Ф. В., Зархан П. Причины возникновения неустойчивости при практическом применении систем, разработанных с помощью современной теории управления. — Аэрокосмическая техника, 1985, т. 3. № 3.

Рукопись поступила 25/XII 1986

Проверочная работа по информатике на тему «Массивы в Паскале» (10 класс)

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

Структура работы: работа рассчитана на четыре варианта. Общее количество заданий в работе – 3.

Время проведения работы: проверочная работа проводится в урочное время согласно рабочей программе. На выполнение работы отводится 45 минут.

Требования к оборудованию – индивидуально распечатанная карточка.

1) Дан массив, содержащий 2014 положительных целых чисел. Напишите на одном из языков программирования программу, которая находит в этом массиве количество локальных минимумов. Локальным минимумом называется элемент массива, который меньше всех своих соседей. Например, в массиве из 6 элементов, содержащем числа 4, 6, 12, 7, 3, 8, есть два локальных минимума: это элементы, равные 4 и 3. Программа должна вывести общее количество подходящих элементов, значения элементов выводить не нужно. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных.

var a: array [1..N] of integer;

i, j, k: integer;

for i:=1 to N do

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *