Преподаватель который помогает студентам и школьникам в учёбе.

Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Теоретическая часть)

Содержание:

Введение

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

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

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

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

Теоретическая часть

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

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

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

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

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

Алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.

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

Массовость — применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных.

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

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

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

1.2 Основные структуры алгоритмов

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

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

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

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

Циклическая структура, называемая , повторением, содержит некоторую последовательность действий, выполняемых многократно. Такая структура содержит несколько типовых блоков. Тело цикла – та последовательность действий, которая выполняется многократно. Начальные присвоения – задание начальных значений тем переменным, которые используются в теле цикла. Различают 2 типа цикла «ДО» и «Пока». Цикл «до» применяется при необходимости выполнить какие-либо действия несколько раз до тех пор, пока выполняется некоторое условие. Цикл «Пока» - проверка условия выполняется до выполнения цикла.

Алгоритмизация задач.

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

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

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

1.3 Способы описания алгоритмов

Существуют следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

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

Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем.

Блок, характеризующий начало/конец алгоритма (для

Начало

Конец

подпрограмм - вызов/возврат):

<Действие>

Блок — процесс, предназначенный для описания

отдельных действий:

Блок — предопределенный процесс, предназначенный для обращения к _______________________________________________________________________________________________________________________________вспомогательным алгоритмам (подпрограммам):

Блок — ввода/вывода с неопределенного носителя:

Блок - ввод с клавиатуры:

Блок — вывод на монитор:

Блок — вывод на печатающее устройство:

Блок — решение (проверка условия или условный блок):

Нет Да

<тело цикла>

Блок, описывающий цикл с параметром:

Блок — границы цикла, описывающий циклические

<тело цикла>

процессы типа: «цикл с предусловием», «цикл

с постусловием»:

Соединительные блоки:

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

Программа — описание структуры алгоритма на языке алгоритмического программирования.

1.4 Основные алгоритмические конструкции

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

1.4.1 Линейная алгоритмическая конструкция

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

Линейные вычислительные процессы имеют место, например, при вычислении арифметических выражений, когда имеются конкретные числовые данные и над ними выполняются соответствующие условию задачи действия. На рисунке 1 показан пример линейного алгоритма, определяющего процесс вычисления арифметического выражения у=(b2-ас):(а+с).

Рисунок 1 – Линейный алгоритм

1.4.2 Разветвляющаяся алгоритмическая конструкция

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

Условие

Действие 2

Действие 1

Ложь (Нет) Истина (Да)

Рисунок 2 - Полное ветвление

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

Условие

Действия

Истина (Да)

Ложь (Нет)

Рисунок 3 - Неполное ветвление

В зависимости от типа и числа проверяемых условий различают:

- ветвление с простым условием (условие - выражение отношения);

- ветвление с составным условием (условие - логическое выражение);

- сложное ветвление (несколько условий).

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

1.4.3 Алгоритмическая конструкция «Цикл»

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

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

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

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

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

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

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

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

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

На приведенных ниже рисунках показаны примеры циклических процессов.

Рисунок 4 - Блок-схема цикла с предусловием

Рисунок 5 - Блок-схема цикла с постусловием

1.5 Анализ алгоритмов

1.5.1 Сравнительные оценки алгоритмов

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

Для оперирования с формальной моделью алгоритма рассматривают абстрактную машину, включающую: процессор, поддерживающий адресную память набор элементарных операций соотнесенных с языком высокого уровня. Допущения: каждая команда выполняется не более чем за фиксированное время; исходные данные алгоритма представляются N машинными словами по αθ битов каждое. На входе алгоритма Nα = N*α бит информации Программа, реализующая алгоритм состоит из М машинных инструкций по β битов Мβ = М*β бит информации. Дополнительные ресурсы абстрактной машины на реализацию алгоритма: Sd – память для хранения промежуточных результатов;θ Sγ – память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов). При решении конкретной задачи, заданной

N+М+Sd+Sy

словами памяти алгоритм выполняет конечное количество «элементарных» операций абстрактной машины. В связи с этим вводится определение: Под трудоѐмкостью алгоритма Fa (n) для данного конкретного входа¬ для решения конкретной проблемы (задачи)¬ в данной формальной системе¬ понимается количество «элементарных» операций (n) совершаемых алгоритмом. Комплексный анализ алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной машины, требуемых алгоритмом для решения конкретных задач. Для различных областей применения веса ресурсов ci будут различны.

1.5.2 Классификация алгоритмов по виду функции трудоёмкости

1.Количественно-зависимые по трудоемкости алгоритмы Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений: Fa(n), n=f(N) Пример: • алгоритмы для стандартных операций с массивами и матрицами – умножение матриц, умножение матрицы на вектор и т.д.

2. Параметрически-зависимые по трудоемкости алгоритмы Это алгоритмы, трудоемкость которых определяется конкретными значениями обрабатываемых слов памяти: Fa(n), n=f(р1…,рi ) У таких алгоритмов на входе два числовых значения – аргумент функции и точность. Пример: • алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов. Классификация алгоритмов по виду функции трудоёмкости.

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

Fa(n), n=f (N, р1…, рi )

Пример: • алгоритмы численных методов, в которых существует параметрически зависимый цикл по точности и цикл количественно зависимый по размерности. Среди параметрически - зависимых алгоритмов выделяют группу алгоритмов для которой количество операций зависит от порядка расположения исходных объектов.

Пример: • алгоритмы сортировки,

• алгоритмы поиска минимума/максимума в массиве.

1.6 Трудоемкость алгоритмов и временные оценки

1.6.1 Примеры анализа простых алгоритмов

Алгоритм выполняет одинаковое количество операций при фиксированном значении n, и следовательно является количественно-зависимым. Применение методики анализа конструкции «Цикл 1» дает: Внутренний: f1(n)=1+3n+4n Внешний: f2(n)=1+3n+ n f1(n) Окончательно: F(n)=1+1+3n+n(1+3n+4n)=2+4n+7n 2= Θ( n 2 ) Под n понимается линейная размерность матрицы, в то время как на вход алгоритма подается n 2 значений.

Пример 2 Задача поиска максимума в массиве

< > Max = S(1) 2 For i = 2 to n n-1 If Max < S(i) 2 (< и S[i]) Max = S(i) 2 (= и S[i]) еnd if Next i Print (Max) < >

Данный алгоритм является количественно-параметрическим, поэтому для фиксированной размерности исходных данных необходимо проводить анализ для худшего, лучшего и среднего случая. Худший случай Максимальное количество переприсваиваний максимума (на каждом проходе цикла) будет в том случае, если элементы массива отсортированы по возрастанию. Трудоемкость алгоритма в этом случае равна: F(n)=2+1+3(n-1)+(n-1)(2+2)=7n-4= Θ(n) Лучший случай Минимальное количество переприсваиваний максимума - если максимальный элемент расположен на первом месте в массиве. Трудоемкость алгоритма в этом случае равна: F(n)=2+1+3(n-1)+(n-1)(2)=5n-2= Θ(n)

Средний случай Элементарное усреднение Fc(n) =(Fх(n)+ Fл(n) )/2= 6n-3= Θ(n). ?

1.6.2 Переход к временным оценкам

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

Дано: F(A) - трудоёмкость алгоритма требуется определить время работы программной реализации алгоритма – T(A).

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

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

1.6.3 Конструирование алгоритма

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

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

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

- проверки результатов выполнения на конкретных исходных данных,

- логического анализа конечных результатов относительно постановки задачи.

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

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

Анализ алгоритма включает в себя анализ:

- логической структуры,

- выполнения,

- правильности.

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

Практическая часть

Задача 1. Даны x,y,z. Вычислить a, b если

Постановка задачи.

Входные данные –значения x, y, z, а также функции а и b

Выходные данные – значение функции a и bдля различных значений аргумента х,y,z

Цель реализации алгоритма: нахождение значенийa и b при заданных значениях x, y, z.

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

Словесное описание алгоритма.

Начало

Ввести x, y, z;
a:=y+(x/(y*y+(x*x/(y+(x*x*x/3)))));
b:=(1+sqr(sin(z/2)/cos(z/2)));
Вывод (a, b).

Конец

Текст программы приведен ниже

Program zadacha1;

Var

x, y, z:real;

a, b:real;

begin

writeln(‘vvedite x,y,z’);

readln(x,y,z);

a:=y+(x/(y*y+(x*x/(y+(x*x*x/3)))));

b:=(1+sqr(sin(z/2)/cos(z/2)));

writeln(‘a=’,a:7:3,’b=’,b:7:3);

end.

Задача 2. Даны действительные числа x, y. Определить принадлежит ли точка с координатами х и у заштрихованной части плоскости.

У1

-11х

-1

Постановка задачи.

Входные данные –значения x, y.

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

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

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

Словесное описание алгоритма.

Начало

Читаем с экранаx и y
Определяем положение заданной точки относительно первогоотрезка (1,0;0,1)

Положение определяем, считаяпроизведениевекторов проходящих через:

1-й вектор начальная – конечная точка отрезка,

2-й вектор начальная точка отрезка – заданная точка.

Произведение > 0 => точка лежит слева от отрезка,

Произведение < 0 => справа,

Произведение = 0 =>лежит на отрезке.

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

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

Выводим ответ.

Конец

(Направление отрезков против часовой стрелки)

Текст программы приведен ниже

programzadacha2;

var

x,y,z: real;

function location(xlin1,ylin1,xlin2,ylin2: real): integer;

var

tmp: real;

begin

tmp := (xlin2-xlin1)*(y-ylin1) - (ylin2-ylin1)*(x-xlin1);

if tmp < 0 then location:= -1

else if tmp > 0 then location:= 1

else location:= 0;

end;

begin

repeat

write('x = ');

Readln(x);

write('y = ');

Readln(y);

if ((location(1,0,0,1)> 0) and (location(0,1,-1,0)>0) and (location(-1,0,0,-1)> 0) and (location(0,-1,1,0)>0))

then writeln('tochka prinadlegit oblasti')

else if ((location(1,0,0,1)< 0) or (location(0,1,-1,0)<0) or (location(-1,0,0,-1)< 0) or (location(0,-1,1,0)<0))

then writeln('tochka ne prinadlegit oblasti')

else writeln('tochka na granice oblasti');

Writeln;

until false;

end.

Задача 3.Дано действительное число а. Вычислить f(a), если

Постановка задачи.

Входные данные – значение а, а так же функция f(x).

Выходные данные – значение функции f(a).

Цель реализации алгоритма: ввести значение а, вычислить значение f(a), при известной функции f(x).

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

Словесное описание алгоритма:

Начало

Читаем а
Проверяем условие-2<=a<=2
Если верно, то f(a) = 2*a^2иначе f(a) = 4

Выводим f

Конец

Текст программы приведен ниже

program zadacha3;

var

a,f: double;

begin

repeat

write('a = ');

readln(a);

if ( (a>= -2) and (a<= 2) ) then

f:= 2*sqr(a)

else f:= 4;

write('f(a) = ');

writeln(f:0:3);

writeln;

until false;

end.

Задача 4. Даны натуральное число n, действительная матрица размером n*9. Найти среднее арифметическое каждой из строк.

Постановка задачи.

Входные данные – натурально число n, матрица размером n*9

Выходные данные – в зависимости от n, получаем определенное количество строк и выводим среднее арифметическое каждой из строк.

Цель реализации алгоритма: ввести значение n, создать матрицу размера n*9,вычислить среднее арифметическое каждой из строк.

Словесное описание алгоритма:

Начало

Читаем n
Создаем динамический массив размерностьюnx9
В цикле поочередно считываем с экрана его элементы
В цикле считаем сумму элементов в строке и делим ее на 9
Выводим полученный ответ на экран

Конец

Текстпрограммы

program Project4;

var

A: array of array of double;

n, i, j: integer;

tmp: double;

begin

write('n = ');

readln(n);

SetLength(A,n);

for i:=0 to n-1 do

SetLength(A[i],9);

for i:=0 to n-1 do

for j:=0 to 8 do

begin

write('A[',i,',',j,'] = ');

readln(A[i,j]);

end;

for i:=0 to n-1 do

begin

tmp:= 0;

for j:= 0 to 8 do

begin

tmp:= tmp + A[i,j];

end;

writeln('str',i+1,'',tmp/9:0:3);

end;

readln;

end.

Задача 5. Получить единичную квадратную матрицу порядка n.

Постановка задачи.

Входные данные – n-число строк и столбцов

Выходные данные – матрица размером n*n.

Цель реализации алгоритма: ввести значение n, создать единичную матрицу размера n*n, для этого будем использовать массив.

Словесное описание алгоритма:

Начало

Читаем n
Создаем динамический массив размерностью nxn
В цикле заполняем значениями его элементы:

Если номер строки и номер столбца совпадают, то 1

Иначе 0.

Выводим массив на экран.

Конец

Текстпрограммы

program Project5;

var

A: array of array of byte;

n,i,j: integer;

begin

write('n = ');

readln(n);

SetLength(A,n);

for i:= 0 to n-1 do

SetLength(A[i],n);

for i:= 0 to n-1 do

for j:= 0 to n-1 do

if (i = j) then A[i,j]:= 1

else A[i,j]:= 0;

for i:= 0 to n-1 do

begin

writeln;

for j:= 0 to n-1 do

write(A[i,j],'');

end;

writeln;

readln;

end.

Задача 6. Вычислить значения z, соответствующие каждому значению х (хn<=x<=xk шаг изменения х равен dx) по формуле .

Вычислить , сумму значений z, произведение отрицательных значений z, количество вычислительных z.Контрольный расчет провести при а=2.62, хn=-3, xk=3, dx=0.6.

Постановка задачи.

Входные данные - Xn, Xk, dx, a.

Выходные данне – Z и F.

Цель реализации алгоритма: ввести значение Xn, Xk, dx, a, и при этих значениях вычислить по приведенным фомуламZ и F.

Словесное описание алгоритма:

Начало

Читаем Xn, Xk, dx, a
x = Xn
Пока x <= Xk делаем:
Вычисляем z
Если z>=0 то добавляем его в сумму положительных z

Иначе в произведение отрицательных

Добавляем z в общую сумму
Увеличиваем на 1 количество посчитанных z
x = x + dx
F =произведение отрицательных z + сумма положительных z
Выводим полученные значения на экран

Конец

Текст программы

program Project6;

var

Xn, Xk, x, dx, a, tmp,

summa,

proizveden,

allsumma : double;

Count: integer;

first: boolean;

function z(x: double): double;

begin

z:= (sqr(a*x)*exp(1/3*ln(1/sqr(a+x))) )/(a*ln(a + sqr(x))) ;

end;

begin

write('Xn = ' );

readln(Xn);

write('Xk = ');

readln(Xk);

write('dx = ');

readln(dx);

write('a = ');

readln(a);

if (Xk < Xn)then

begin

tmp:= Xk;

Xk:= Xn;

Xn:= tmp;

end;

x:= Xn;

proizveden:= 0;

summa:= 0;

count:= 0;

allsumma:= 0;

first:= true;

while(x<=Xk) do

begin

tmp:= z(x);

if (tmp < 0)then if first then

begin

proizveden:= tmp;

first:= false;

end

else

proizveden:= proizveden * tmp

else summa:= summa + tmp;

allsumma:= allsumma + tmp;

Count:= Count + 1;

x:= x + dx;

end;

F:= proizveden + summa;

writeln;

writeln('F = ', F:0:5);

writeln('summa znachenij z = ', allsumma:0:5);

writeln('proizvedenie otricatelnih z = ', proizveden:0:5);

writeln('kolichestvo vicheslitelnih z = ', Count);

readln;

end.

Задача 7.Дано: а=5 da=-0.5. Z вычислять по формуле:, где q=a2-a. Считать до тех пор, пока q>0. Определить k-количество вычисленных Z.Вывести на экран a, q, Z, k.

Постановка задачи

Входные данные - а=5 da=-0.5.

Выходные данне – a, q, Z, k.

Цель реализации алгоритма: ввести значение а=5 da=-0.5-константы и при этих значениях вычислить по приведенным фомуламZи вывести на экран a, q, Z, k.

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

Словесное описание алгоритма:

Начало

A = 5, da = -0.5
q = a^2 – a
пока q > 0 делать
z = q + 1/(q+1)
увеличиваем К (кол-во вычислений) на 1
a = a + da
q = a^2- a
выводим на экран a, q, Z, k

Конец

Текст программы

var

k: integer;

a,da,z,q: double;

sd: array of integer;

begin

a:=5;

da:=-0.5;

k:=0;

q:=sqr(a) - a;

while(q > 0) do

begin

z:= q + 1/(q+1);

k:= k + 1;

a:= a + da;

q:=sqr(a) - a;

end;

writeln('a = ', a:0:5);

writeln('q = ', q:0:5);

writeln('Z = ', z:0:5);

writeln('k = ', k);

readln;

end.

Задача 8. Решить в excel.

Названиеучебногоцентра	Количество неаттестованных учащихся
Названиеучебногоцентра	2001	2002	2003	2004	2005	2006
Softline	14	32	31	26	12	40
Интерком	12	24	32	15	18	20

Найти:

1. Общее число неаттестованных учащихся за каждый год.
2. Среднее число неаттестованных учащихся за каждый год по каждому учебному центру.
3. Учебный центр, в котором наибольшее количество неаттестованных учащихся (за год).
4. Построить гистограмму неаттестации за каждый год.

1 этап: ввод исходных данных в MS Excel.

Рисунок 1- Ввод данных

2 этап: вычисления.

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

1. Математические:

СУММ - сумма аргументов

2. Статистические:

СРЗНАЧ - среднее арифметическое аргументов
МАКС - максимальное значение из списка аргументов
МИН - минимальное значение из списка аргументов

Рисунок 2 – Результаты

Рисунок 2.1 – Результаты

Этап 3:Построение гистограммы. Выделяем таблицу, выполняем команду Вставка – Гистограмма и выбираем простую гистограмму.

Результат показан на рисунке

Рисунок 2.2- Гистограмма

Задание 9. Построить график функции f(x) в Excel.

1. ,

Определение функции f(x). Для этого в ячейки B2:B19 вводим значение аргумента при помощи автозаполнения, в данном случае с шагом 0,1. В ячейку С3 вводится значение функции, вычисляемое по формуле = 4*B3^3+3*B3^2-8*B3-2/2-3*B3^2. Ячейки С4:С19 заполняются копированием формулы из ячейки С3.
Построение графика: выделяем диапазон В2:С19, вызываем «Мастер диаграмм». Для построения графика функции лучше выбрать точечную диаграмму, со значениями, соединенными сглаживающими линиями без маркеров. Чтобы график получился выразительным, можно определить промежуток изменения аргумента, увеличить толщину линий, выделить оси координат, нанести на них соответствующие деления, сделать подписи на осях и вывести заголовок.

Рисунок 3 - Построение графика функции

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

Рисунок 3.1 - Построение графика функции

Заключение

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

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

Единственный способ изучать новый язык программирования – писать на нём программы.

Библиография

Б.В.Соболь [и др.]«Информатика и программирование»– Ростов н/Д: Феникс, 2006 – 354 с.
Информатика. Базовый курс./С.В.Симонович и др. - СПб.: Питер, 2001
Информатика: базовый курс: учебник для студентов вузов, бакалавров, магистров, обучающихся по направлению «Информатика»/О.А. Акулов, Н.В. Медведев. 6-е изд., испр. и доп.-М.: Издательство «Омега-Л», 2009.-574 с. – (Высшее техническое образование).
Каймин В.А. Информатика: Учебник для вузов. - М.: Высшее образование, 1998.
Каймин В.А., Касаев Б.С. Информатика.: Практикум на ЭВМ. Учебное пособие.
Культин Н.Б. Программирование в TurboPascal 7.0 и Delphi.- 2-е издание, перераб. и доп.- Спб.: БХВ-Петербург,2002.-416 с.;ил.
Турбо Паскаль 7.0. Самоучитель. – СПб.: Питер; К.: Издательская группа BHV, 2002.-576 с.