Основы алгоритмизации, программирования и баз данных

Основы алгоритмизации, программирования и баз данных

Рогов Алексей Юрьевич

 

Основы алгоритмизации и программирования

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

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

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

1. Дискретность — разделение решения задачи на отдельные операции, выполняемые исполнителем по определенным командам;

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

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

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

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

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

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

1. На естественном языке;

2. В виде блок-схемы;

3. На алгоритмическом языке.

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

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

Основные элементы блок-схем

 

	Блок вычислений/блок действий	Вычислительное действие, или последовательность действий
	Логический блок/блок условия	Выбор направления выполнения алгоритма в зависимости от некоторого условия
	Блок ввода/вывода	Общее обозначение ввода/вывода вне зависимости от физического носителя
	Блок начала/конца	Начало или конец алгоритма, вход или выход в подпрограмме
	Процесс пользователя (подпрограмма)	Вычисление по стандартной программе или подпрограмме
	Блок модификации	Функция выполняет действие, изменяющее пункты алгоритма
	Соединитель	Указание связи прерванными линиями между потоками информации в пределах одного листа (парный)
#1	Межстраничный соединитель	Указание связи прерванными линиями между потоками информации между листами (парный)

 

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

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

К основным структурам относятся:

1. Линейные — алгоритмы, в которых действия осуществляются последовательно друг за другом;

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

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

1. Блок проверки условия;

2. Тело цикла.

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

В языке C в любом типе цикла указывается условие продолжения цикла.

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

Начало

a,b,c

a>b

b>c

a>c

i=a

i=c

i=b

i=c

i

Конец

Начало

a,b,c

i=max(a,b)

i=max(i,c)

i

Конец

Начало

x>y

max=x

max=y

max

Конец

 

#include <stdio.h>

#include <conio.h>

int max (int x, int y)

{

int max;

if (x>=y)

max=x;

else

max=y;

return max;

}

void main()

{

int a, b, с, i;

scanf(''%i%i%i'', &a,&b, &c);

i=max(a,b);

i=max(i,c);

printf(''%i'',i);

}

Функция main() является основным алгоритмом. Функция max — вспомогательным. В заголовке вспомогательного алгоритма перечисляются переменные-аргументы (x,y) с указанием их типов. Это формальные параметры вспомогательного алгоритма. В основном алгоритме обращение к вспомогательному производится путем указания имени вспомогательного алгоритма с последующим в скобках списком фактических параметров. Между формальными и фактическими параметрами должны выполнятся следующие правила соответствия:

1. По количеству (сколько формальных, столько и фактических);

2. По последовательности (первому формальному соответствует первый фактический и т.д.);

3. По типам (типы соответствующих формальных и фактических параметров должны совпадать).

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

1. Значения фактических параметров передаются соответствующим формальным параметрам;

2. Выполняется тело процедуры;

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

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

Типы данных

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

Типы данных

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

1. Целый;

2. Вещественный;

3. Логический;

4. Символьный.

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

Тип данных — это такая характеристика данных, которая, с одной стороны, задает множество значений для возможного изменения данных, с другой стороны — определяет множество операций, которые можно применять к этим данным, и правила выполнения этих операций. Пример: целочисленное: 48 + 49 = 97; символьное: 48 (0) + 49 (1) = «01».

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

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

2. Запись — это наиболее общий метод получения структурированных типов данных. Он заключается в объединении элементов различных типов данных. Пример:

Студент (запись) -

- ФИО (запись)

- Фамилия (строка)

- Имя (строка)

- Отчество (строка)

- Д.р. (запись)

- Дата (целое)

- Месяц (целое)

- Год (целое)

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

 

Разделы программы

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

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

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

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

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

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

 

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

Признак классификации	Типы
Набор исходных языков	Одноязыковые
Многоязыковые
Возможности расширения	Открытые
Замкнутые
Трансляция	Компиляция
Интерпретация

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

Результат

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

Выполнение

Абсолютный модуль

Библиотека программ пользователя

Загрузчик

Загрузочный модуль

Библиотека системных программ

Компоновщик (редактор связей)

Объектный модуль

Транслятор (компилятор)

Расширенный модуль

Препроцессор

Исходный модуль

Текстовый редактор

Исходный текст

Схема обработки прикладных программ в среде системы программирования

 

Ввод

 

 

Препроцессинг

 

Трансляция (компиляция)

 

Этапы:

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

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

3. Директивы препроцессора представляют собой помеченные спецсимволами (%, # и т. д.) строки, содержащие аббревиатуры или другие символические обозначения конструкций, включаемых в состав исходной программы перед ее обработкой компилятором;

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

1. Синтаксический анализ — проверка правильности конструкций, использованных при подготовке текста;

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

3. Генерация объектного кода.

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

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

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

 

Библиотеки подпрограмм

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

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

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

 

Исходный код

Статическая библиотека

Компилятор

Откомпилированный код

Компоновщик

Исполняемый модуль

Компоновщик

Статическая библиотека

Исполняемый модуль

Динамическая структура

Динамическая структура

 

 

Внешнее описание

 

 

Программирование на языке С

Типы данных

Базовые типы: целые; вещественные; перечисляемые.
Структурированные типы данных: массивы; структуры; объединения; типы, опеределяемые пользователем.

Тип данных	Размер (байт)	Диапазон значений	Эквивалентное название типа
char		-128..+127
int	2|4	Зависит от системы
unsigned char		0..255
unsigned int	2|4	Зависит от системы
short int		-32768..+32767
unsigned short		0..65535
long int		-2147483648..+2147483647
unsigned long int		0..4294967295
float		± 3.4 Е
double
long double

 

Описание переменных имеет вид var_name var_list.

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

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

Описание констант: #define a 4/const int 4;

 

Операция присваивания

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

 

Арифметические операции

Бинарными (имеющими 2 аргумента) являются арифметические операции +, -, =, *, /, % (остаток от деления нацело). Приоритет арифметических операций сохраняется из математики. Действия одного приоритетного уровня выполняются слева направо. В языке С имеются дополнительные операции присваивания, совмещающие присваивание с выполнением других операций. +=, -=, *=, /=, %=.

 

Функции ввода/вывода

Циклы

 

Цикл с предусловием. Цикл с предусловием реализуется с помощтю конструкции while.

 

While (выражение)

{

Оператор;

}

 

 

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

 

Пример.

 

#include <iostream.h>

#include<conio.h>

Void main ()

{

Int f,n;

Cout <<”n”;cin>>n;

F=i=1;

While (i<=n)

{

f=f*i;

i++;

}

Cout <<n<< “!=”<<f;

Getch;

}

 

Цикл с пост условием. Реализуется с помощью конструкции do while.

 

Do

{

Оператор;

 

}

While (выражение);

оператор

ввыражение

 

 

 

 

Цикл выполняется до тех пор, пока значение выражения истинно.

Начало

#include <iostream.h>а

#include<conio.h>

n

Void main ()

{

Int f,n;

F=i=1

Cout <<”n”;cin>>n;

F=i=1;

F=f*i

Do

{

I++

f=f*i;

i++;

I<=n

}

While (i<=n);

Cout <<n<< “!=”<<f;

n,f

Getch;

}

 

конец

 

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

 

For (выражение_1; выражение_2; выражение_3;)

{

Оператор;

}

 

Выражение 1 Выражение 2 Выражение 3

оператор

 

Выражение 1 – выполняется только один раз в начале цикла, обычно определяет начальное значение параметра цикла. Выражение 2 – условие выполнения цикла.Выражение 3 – изменение параметра цикла. Любое из этих 3 выражений может отсутсвовать, но разделяющие их «;» ставятся обязательно. При отсутсвии выражения 1 или выражения 3 считается что их просто нет в конструкции цикла. При отсутсвии выражения 2 предполагается что его значение как бы всегда истинно. For (;;) – бесконечный цикл (условие считается всегда истинным). Цикл for применяется там, где есть простая инициализация, и пошаговое измение значения некоторой переменной. Удобство использования, заключается в том, что организующая его часть сосредоточена в начале.

 

начало

Выечсление факториала

 

#include <iostream.h>

n

#include<conio.h>

Void main ()

{

F=1

Int f,n;

Cout <<”n”;cin>>n;

F=1;

I=1; i<=n; i++

For (i=1;i<i=n;i++)

{

f=f*i;

i++;

}

F=f*i

Cout <<n<< “!=”<<f;

Getch;

U ptOE4Miho+KcNV5b1jilybry9pgTO9mWP/3+nG9m14sJx9B50qAWCQik2tuOGg3Vx9vdGkSIhqzp PaGGHwywKa6vcpNZf6YSp11sBIdQyIyGNsYhkzLULToTFn5A4t3Bj85EHsdG2tGcOdz1Mk2SlXSm I77QmgFfWqyPu5PTUH4e/Hs19ceyenXptvlaqZq+tb69mbfPICLO8R+GP31Wh4Kd9v5ENohew0O6 VIxquFdcGViuH7nZM5k8KZBFLi9fKH4BAAD//wMAUEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEA ABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h /9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYACAAAACEA7VYh fNkBAAADBAAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEA 5Bu2F90AAAAKAQAADwAAAAAAAAAAAAAAAAAzBAAAZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA 8wAAAD0FAAAAAA== " strokecolor="#4579b8 [3044]">

N,f

}

Конец

 

Массивы

 

Массив – это структура однотипных элементов занимающих не прерывную область памяти.

 

Формат описания массива:

 

тип_элементов имя [константное_выражение]

 

Свойства массива:

 

Имя;

Тип;

Размерность;

 

Описание массива:

 

int A[10] c A[0] по A[9] – мусор

int A[]=(1, 5, 2); A[0]=1 A[1]=5 A[2]=2

int A[10]= (1, 5, 2); A[0]=1 A[1]=5 A[2]=2 с A[3] по A[9] – мусор

 

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

 

Случайные числа

Stdlib.h

Randomize() – инициализация генератора случайных чисел;

Random(N) – генерация случайного числа в диапазоне от 0 до N-1;

Random (Max-Min+1)+Min – генерация случайного числа в диапазоне от Min до Max.

 

Rand () %N; 0/N-1;

Rand_max =7FFF=32767

 

Заполнение и вывод одномерного массива

начало

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

n=10

#define n 10

Void main ()

{

int a[n],i;

i=0; i<n; i++

clrscr();

randomize();

for (i=0;i<n;i++)

}

конец

>

a[i]=random(10)

A[i]=random(10);

Printf(“%3i”,a[i]);

}

Getch();

a[i]

}

 

начало

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

n=5;s=0

#define n 5

Void main ()

{

Int a[n], i, s=0;

6 [3209]" strokeweight="2pt">

i=0; i<n; i++

Clrscr();

Randomize();

for (i=0; i<n; i++);

{

A[i]=random(10)

s

A[i]=random(10);

S=s+a[i];

Printf(“%3i”,a[i]);

}

конец

S=s+a[i]

Printf(“\n s=%i”,s);

Getch();

A[i]

}

 

Нахождение минимального значения (Для поиска максимального значения требуется изменить знак “<” на знак “>”. Для поиска номера элемента в циклы нужно добавить (n_min=i).

 

начало

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

n=5

#define n 5

Void main ()

{

int a[n], i, min;

6 [3209]" strokeweight="2pt">

i=0; i<n; i++

Clrscr();

Randomize();

For (i=0; i<n; i++);

3 bnJldi54bWxMj8FOwzAQRO9I/IO1SNyoU1BTlMapAClCQlxa4NCbG2/jqPY6it00/D2LONDbjGY0 +7ZcT96JEYfYBVIwn2UgkJpgOmoVfH7Ud48gYtJktAuECr4xwrq6vip1YcKZNjhuUyt4hGKhFdiU +kLK2Fj0Os5Cj8TZIQxeJ7ZDK82gzzzunbzPslx63RFfsLrHF4vNcXvyCmp8PXa5w91m2rXWj4v6 /e35S6nbm+lpBSLhlP7L8IvP6FAx0z6cyEThFCzybM5VFksQnP/5PYuHJciqlJcPVD8AAAD//wMA UEsBAi0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5 cGVzXS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3Jl bHMvLnJlbHNQSwECLQAUAAYACAAAACEACvA7kfUBAAD+AwAADgAAAAAAAAAAAAAAAAAuAgAAZHJz L2Uyb0RvYy54bWxQSwECLQAUAAYACAAAACEAf2r6cNwAAAAIAQAADwAAAAAAAAAAAAAAAABPBAAA ZHJzL2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAFgFAAAAAA== " strokecolor="black [3040]"> {

A[i]=random(10)

min

A[i]=random(10);

If(i==0) min=a[i];

If(a[i]<min) min=a[i];

Printf(“%3i”,a[i]);

i=0

конец

}

Нет

Да

Printf(“\n s=%i”,min);

Getch();

}

 

>

Min=a[i]

a[i]<min

Min=a[i]

A[i]

Да

Нет

 

 

Лабораторная работа №11

Вариант 3: Массив A из 10 элементов заполняется случайными числами от 0 до 9. Сформировать новый массив B, заполенный элементами массива A в обратном порядке (Пример: A:0,1,2,3,4,5,6,7,8,9; B:9,8,7,6,5,4,3,2,1,0) Вывести на экран массивы A и B.

 

 

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

void main ()

{

int a[10],b[10],i,n=9;

clrscr();

randomize ();

for (i=0;i<10;i++)

{

a[i]=random (10);

printf ("%3i",a[i]);

for (i=0;i<10;i++)

{

b[i]=a[n];

n--;

printf ("%3i",b[i]);

}

getch();

}

 

Сортировка массивов

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

 

 

Сортировка массива методом прямого обмена (метод пузырька)

 

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

# define n 5

Void main ()

{

Int a[n],i,k,p,temp;

Clrscr();

Randomize();

For (i=0;i<n;i++)

{

A[i]=random(10);

Printf (“%3i”,a[i]);

}

Printf (“\n”);

For (i=0;i<n;i++)

{

P=0;

For (k=0;k<n-i-1;k++)

If (a[k]>a[k+1])

{

Temp=a[k];

a[k]=a[k+1];

a[k+1]=temp;

P++;

}

If (p==0) break;

}

For (i=0;i<n;i++)

Printf (“%3i”,a[i]);

Getch ();

}

Оптимизация алгоритма сортировки осуществляется двумя методами:

1. Сокращением длины прохода (т.к. один элемент за проход встает на свое место);

2. За счет сокращения количества проходов (вводится счетчик количества перестановок за проход, и если после очередного прохода он равен нулю, то массив считается отсортированным и сортировка прекращается);

 

Сортировка прямым выбором

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

 

Сортировка массива методом прямого выбора.

 

 

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

 

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

 

Сортировка методом прямого выбора

 

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

# define n 10

void main ()

{

int a[n],i,k,min,n_min,temp;

clrscr();

randomize();

for (i=0;i<n;i++)

{

a[i]=random(10);

printf (“%3i”,a[i]);

}

for (i=0;i<n-1;i++);

{

min=a[i];

n_min=i;

for (k=i+1;k<n;k++)

if (a[k]<min)

{

min=a[k];

n_min=k;

}

temp=a[i]

a[i]=a[n_min];

a[n_min]=temp

}

printf (“\n”);

for (i=0;i<n;i++)

printf (“%3i”,a[i]);

getch ();

}

 

Бинарный поиск в массиве

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

 

#include <stdio.h>

#include <conio.h>

#define n 10

Void main()

{

Int a[n],I,b,c;

Int low =0; high=n-1;

For (i=0;i<n;i++)

{

A[i]=I;

Printf (“%3i”,a[i]);

}

Printf (“\n”);

Scanf (“%i”,&b);

While (low<high)

{

C=(high+low)/2;

If (a[c]<b)

Low=c+1;

Else

High=c;

}

If (a[low]==b)

Printf (“a[%i]=%i,low,a[low]);

Else

Printf (“NO”);

getch ();

}

 

Многомерные массивы

 

Float a[5][10] – пример описания двумерного массива.

 

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

A[0][0]	A[0][1]	A[0][2]	…	A[0][9]
A[1][0]	A[1][1]	A[1][2]	…	A[1][9]
…	…	…	…	…
A[4][0]	A[4][1]	A[4][2]	…	A[4][9]

 

Данная запись объявляет массив из 5-ти элементов каждый из которых есть массив из 10-ти вещественных чисел. Отдельные величины этого массива обозначаются именами с двумя индексами.

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

Инициализация – это задание начальных значений.

 

int B[3][3]={11,12,13,21,22,23,31,32,33};

 

A[0][0]=11	A[0][1]=12	A[0][2]=13
A[1][0]=21	A[1][1]=22	A[1][2]=23
A[2][0]=31	A[2][1]=32	A[2][2]=33

 

 

Лабораторная работа № 13

Вариант №3

 

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

void main ()

{

int a[1][1],i,n,m,k;

clrscr();

randomize();

\\printf ("Enter the number of lines ");

scanf ("%i",&m);

\\printf ("Enter the number of column ");

scanf ("%i",&n);

for (i=0;i<n;i++)

{

for(k=0;k<m;k++)

{

a[i][k]=random(6+6+1)-6;

if (a[i][k]<0) a[i][k]=0;

printf ("%3i",a[i][k]);

}

printf ("\n");

}

getch();

 

 

Указатель

 

Указатель – это адрес поля памяти занимаемого программным объектом.

Формат описания указателя:

Тип *имя_указателя;

Операция взятия адреса переменной – &; Применение этой операции к имени переменной дает в результате её адрес в памяти.

 

Int a=5;

Char c=”G”;

Float r=1.2;

Память	FFC0	FFC1	FFC2	FFC3	FFC4	FFC5	FFC6
Переменные	A		C	R
Значения		G	1.2

 

Int *pti; pti=&a;