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

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

Условие: упорядочить по возрастанию массив вещественных чисел, в массиве N элементов.

1.1 Исходные данные

N:целое ( количество элементов )

A:массив[1..N] вещественных

1.2 Ограничения

1.3 Результаты

A:массив[1..N] вещественных;

1.4 Связь

Упорядочить массив методом ”пузырька”.

i N

i

Метод перебора

пр:=a[i] при

a[i]:=a[j] a[j]<a[i] для j=i+1,N для i=1,N-1

a[j]:=пр

Метод пузырька

r:=a[imin]

a[imin]:=a[i]

a[i]:=r

min:=a[j] a[j]<min для j= i+1,N

imin:=j для i=1,N-1

min:=a[i]

imin:=i

6 КОДИРОВАНИЕ АЛГОРИТМОВ НА ЯЗЫКЕ СИ

6.1 Принцип виртуальной Си-машины

Рисунок 6.1- Виртуальная Си-машина

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

1-й этап:

2-й этап:

Различают следующие виды ошибок:

1) Ошибки этапа компиляции:

- Лексические;

-Синтаксические;

- Семантические;

2) Ошибки этапа выполнения:

- Деление на нуль;

- Переполнение;

3) Ошибки, не идентифицируемые Си машиной.

Рисунок 6.2 – Работа виртуальной Си-машины на двух этапах

6.2 Язык Си

Характеристики языка Си:

1) язык процедурного типа;

2) язык со статической проверкой типов (в каждой точке программы на этапе компиляции, известно с какими данными выполняется операция).

Достоинства языка Си:

1) язык Си современный, т.е. поддерживает основные принципы:

- нисходящее проектирование,

- структурное программирование,

- пошаговая разработка программ;

2) язык эффективный;

3) мобильность (переносимость), т.е. программы, написанные на Си, переносятся в другую операционную систему (на другую платформу) либо без изменений, либо с минимальными изменениями;

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

5) язык системного программирования (в Си есть все конструкции позволяющие работать на уровне Ассемблера);

6) язык стандартизован - стандарт языка Си – ANSI-C;

стандарт наложен на:

- сам язык;

- препроцессор;

- библиотеки.

Язык поддерживается всеми фирмами, которые разрабатывали операционную систему UNIX и ей подобные:

UNIX: AT&T, SUN;

UNIX-V: IBM, DEC, HP, SIMENS.

6.3 Описание синтаксиса языка программирования

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

- БНФ (формулы Бэкуса-Наура);

- синтаксические диаграммы (разработаны Н.Виртом).

БНФ

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

Каждая БНФ состоит из двух частей разделённых специальным символом ::=

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

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

Пример 6.1:

<программа> ::= <последовательность директив препроцессора>

<заголовок программы> <тело программы>

<последовательность директив препроцессора> ::= <директива> [<директива>]

<директива>::=#<тело директивы>

<заголовок программы> ::= main([список аргументов])

< список аргументов > ::= <имя аргумента> [,<имя аргумента>]

<имя аргумента> ::= <имя>

<имя> ::= <буква> | <имя> <буква> | <имя> <цифра>

6.3.2 Синтаксические диаграммы

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

Пример 6.2:

ИМЯ

6.4 Типы, операторы и выражения в языке Си

Основные объекты программы – переменные и константы. В Си требуется, чтобы все переменные были объявлены оператором описания (декларирования) до первого их использования.

Объект программы:

-константы

-переменные

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

Тип данных переменной определяет:

1. Множество допустимых значений

2. Множество операций (функций), допустимых для этого типа

Имена переменных