Алгоритмы со структурой вложенных циклов

 

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

Матрицы – удобный пример для демонстрации алгоритмов со структурой вложенных циклов.

В матрице [A] М столбцов и N строк. Каждый элемент матрицы определен двумя индексами, которые указывают положение этого элемента. На первом месте записывается номер строки, на втором – номер столбца. Например, а – элемент матрицы [A ], расположенный во второй строке третьего столбца.

Если необходимо задать значение матрицы, значит нужно задать значения всех ее элементов. Назовем элемент матрицы аij. Для всей матрицы в целом i пробегает значения от 1 до N, а j от 1 до М.

Каждую строку матрицы можно рассматривать как одномерный массив. С вводом одномерного массива мы знакомы. Ввод первой строки матрицы определяет следующая совокупность элементов схемы (рис. 24).

Такая же схема должна быть использована для второй строки матрицы, для третьей и так далее до М – ой строки. То есть номер строки может быть задан циклом и этот цикл будет внешним по отношению к циклу по столбцу. Cхема ввода матрицы [A] без блока модификации дана на рис. 25.

Внешний цикл по i – блоки 3, 4, 5, 6, 7, 8, 9.

Блок 3 – подготовка цикла по i.

Блок 8 – изменение параметра цикла.

Блок 9 – проверка условия окончания цикла.

Блоки 4, 5, 6, 7, 8 – тело цикла.

Внутренний цикл по j – блоки 4, 5, 6, 7.

Блок 4 – подготовка цикла по j.

Блок 6 – изменение параметра цикла.

Блок 7 – проверка условия окончания цикла.

Блоки 5, 6 – тело цикла.

При переходе к следующему значению i (к следующей строке) j – восстанавливает первоначальное значение равное 1.

Задана матрица

 

 

При использовании разработанной схемы алгоритма элементы матрицы должны быть введены в следующем порядке: 1, 0, 2, 3, 0, 1, 1, 1, 5, 4, 6, 0.

Для того, чтобы ввести элементы матрицы по столбцам (1, 0, 5, 0, 1, 4, 2, 1, 6, 3, 1, 0), нужно цикл по j сделать внешним, а цикл по i внутренним. В этом случае второй индекс меняется медленнее первого.

а11, а21, а31,..., аМ1, а12, а22, а32,...,аМ2,... аМN.

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

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

Задача 12. Задана квадратная матрица [A], состоящая из N строк и N столбцов. Найти сумму диагональных элементов.

Разработка алгоритма. Исходные данные: количество строк N, количество столбцов N, элементы матрицы.

Диагональные элементы матрицы а11, а22, а33,..., аNN удовлетворяют условию i = j. Необходимо осуществить перебор элементов матрицы и просуммировать те, что отвечают условию i = j.

Блоки 2, 3, 4, 5 – ввод матрицы [A].

Блок 6 – задание начального значения для суммы.

Блоки 7, 8 – циклы, осуществляющие перебор элементов матрицы.

Блок 9 – проверка условия для суммирования.

Блок 10 – накопление суммы.

Блок 11 – вывод суммы.

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

Задача 13. Группа из N человек сдавала в зимнюю сессию M экзаменов. Известны результаты экзаменов. Подсчитать средний балл каждого студента в зимнюю сессию.

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

 

Тогда среднее: Si= Si/M.

Результатом расчета будет одномерный массив S, состоящий из N элементов (рис. 28).

Блок 6 – цикл по строкам. В задаче i – это номер студента в ведомости. Блок 7 – обнуление суммы. S – переменная, в которой накапливается сумма оценок i–го студента. Блок 8 – перебор предметов от 1 до М. Блок 9 – суммирование оценок. Блок 10 – определение среднего. После того, как цикл по j отработал, полученная сумма делится на количество предметов. Блоки 11, 12 – вывод одномерного массива.

Задача 14. Задана матрица [A], состоящая из N строк и М столбцов. Определить количество нулевых элементов в четных столбцах.

Разработка алгоритма (рис. 29). Чтобы просмотреть четные столбцы, необходимо организовать цикл с шагом 2, начиная со второго.

Блоки 2, 3, 4, 5 – ввод матрицы.

Блок 6 – начальное значение для переменной К. К – это количество нулевых элементов. Блок 7 – цикл – для просмотра матрицы по строкам. Блок 8 – цикл для просмотра матрицы по столбцам. Перебираем только четные столбцы. Блок 9 – проверка равенства нулю элементов матрицы. Блок 10 подсчет количества. Блок 11 – вывод результата.

Подчиненные алгоритмы

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

Задача 15. Составить алгоритм вычисления числа сочетаний. Число сочетаний рассчитывается по формуле:

Вычисление факториала оформить в виде подалгоритма.

В блоках “начало” и “останов” в подчиненном алгоритме записываются слова “вход” и “выход” (рис. 30 В).

В данной задаче необходимо трижды вычислить факториал: n!, m! и (n – m)!. Для расчета факториала разработан подалгоритм. Вместо полной записи последовательности блоков подалгоритма, которая должна повторяться трижды в основной схеме, введены блоки обращения к подалгоритму.

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

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

3. Турбо Паскаль – язык высокого уровня

Системы программирования

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Языки Ассемблера и Макроассемблера применяются системными программистами–профессионалами с целью использования всех возможностей оборудования ЭВМ и получения эффективной, как по времени выполнения, так и по потребному объему памяти, программы.

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

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

Язык Фортран был разработан в 1956 году, затем появились новые его версии Фортран–II, Фортран–IV, Фортран–66, Фортран–77, Фортран–8x, Фортран–88. В свое время этот язык был поистине “рабочей лошадью” научных работников и широко используется в настоящее время, несмотря на его ограниченность и корявость. Он предоставляет пользователям большие возможности для обработки числовых данных, особенно комплексных чисел. Еще в версии Фортран–II впервые была реализована идея раздельной компиляции модулей, что дало возможность создавать библиотеки научных подпрограмм.

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

Язык программирования APL создан в 1969 году. К числу его основных преимуществ относятся богатый набор мощных операторов, позволяющих работать с многомерными массивами как с единым целым, а также предоставление пользователю возможности определять собственные операторы. Основное его назначение – обработка массивов.

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