билеты. 1. Алгоритм и его свойства. Способы записи алгоритма. Программа. Языки программирования. Примеры алгоритмов и программ

• Название: 1. Алгоритм и его свойства. Способы записи алгоритма. Программа. Языки программирования. Примеры алгоритмов и программ
• Дата: 20.11.2020
• Размер: 83.2 Kb.
• Имя файла: билеты.docx
• Тип: Программа; #152211
• страница: 2 из 4

Билет №7

1. Этапы решения задачи. Виды ошибок. Тестирование.

Этап 1:

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

1) При постановке задачи выясняется конечная цель и вырабатывается общий подход к решению задачи.

2) Выясняется сколько решений имеет задача и имеет ли их вообще.

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

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

Этап 2: Выбор (или разработка) метода решения задачи.

Вариант 1: Выбор решения

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

Вариант 2: Разработка

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

Этап 3: Разработка алгоритма

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

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

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

Этап 5: Отладка программы

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

Этап 6: Вычисление и обработка результатов

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

Типы ошибок

Логическая ошибка

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

Синтаксическая ошибка

Каждый компьютерный язык, такой как C, Java, Perl и Python имеет специфический синтаксис, в котором будет написан код. Когда программист не придерживаться "грамматики" спецификациями компьютерного языка, возникнет ошибка синтаксиса. Такого рода ошибки легко устраняются на этапе компиляции.

Ошибка компиляции

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

Ошибки среды выполнения (RunTime)

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

Арифметическая ошибка

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

Ошибки ресурса

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

Ошибка взаимодействия

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

Тестирование

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

Уровни тестирования

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

Интеграционное тестирование - это процесс исследования ПО, при котором тестируется интерфейсы между компонентами или подсистемами.

Системное тестирование - это процесс исследования ПО, при котором тестируется интегрированная система на её соответствие требованиям заказчика. Альфа и Бета тестирование относятся к подкатегориям системного тестирования.

2. Перегрузка функции. Шаблоны функций. Примеры

Перегрузка функций — это особенность в C++, которая позволяет определять несколько функций с одним и тем же именем, но с разными параметрами. Например:

int subtract(int a, int b)

{ return a - b; }

Мы можем просто объявить ещё одну функцию subtract(), которая принимает параметры типа double:

double subtract(double a, double b)

{

return a - b;

}

Теперь у нас есть две версии функции subtract():

int subtract(int a, int b); // целочисленная версия

double subtract(double a, double b); // версия типа с плавающей запятой

Хотя может показаться, что произойдёт конфликт имён, но это не так. Компилятор может определить сам, какую версию subtract() следует вызывать на основе аргументов, используемых в вызове функции. Если параметрами будут переменные типа int, то C++ понимает, что мы хотим вызвать subtract(int, int).

Если же мы предоставим два значения типа с плавающей запятой, то C++ поймёт, что мы хотим вызвать subtract(double, double). Фактически, мы можем определить столько перегруженных функций subtract(), сколько хотим, до тех пор, пока каждая из них будет иметь свои (уникальные) параметры.

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

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

Создание шаблонов функций

Сейчас вам, вероятно, интересно, как создаются шаблоны функций в C++. Оказывается, это не так уж и сложно. Рассмотрим ещё раз целочисленную версию функции max():

int max(int a, int b)

{

return (a > b) ? a : b;

}

Здесь мы трижды указываем тип данных: в параметрах a, b и в типе возврата функции. Для создания шаблона этой функции нам нужно заменить тип int на тип параметра шаблона функции. Поскольку в этом случае используется только один тип данных (int), то нам нужно указать только один тип параметра шаблона.

Мы можем назвать этот тип как угодно, главное, чтобы это не было зарезервированным/ключевым словом. В C++ принято называть типы параметров шаблонов большой буквой T (сокращение от Type).

Вот наша переделанная функция max():

T max(T a, T b)

{

return (a > b) ? a : b;

}

Но это ещё не всё. Программа работать не будет, так как компилятор не знает, что такое Т! Чтобы всё заработало, нам нужно сообщить компилятору две вещи:

· Определение шаблона функции.

· То, что T является типом параметра шаблона функции.

Мы можем сделать это в одной строке кода, выполнив объявление шаблона (а вернее объявление параметров шаблона):

template // объявление параметра шаблона функции

T max(T a, T b)

{

return (a > b) ? a : b;

}

Билет №8

1. Массивы (определение, инициализация, способы перебора).

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

В C++ поддерживается два вида инициализации массивов:· инициализация с заданием размера массива;· «безразмерная» инициализация.

Общий вид инициализации с заданием размера массива:

тип имя_массива[размер] = { список_значений };

Общий вид «безразмерной» инициализации:

тип имя_массива[] = { список_значений };

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

Пример 1. Массив B инициализирован с заданием размера.

int B[10] = { 5, 6, 9, -8, 3, 2, 4, -90, -103, 0 };

Пример 2. Массив C инициализирован на основе списка значений («безразмерная» инициализация).

float C[] = { -3.9, 2.8, -1.6, 2.2 };

Способы перебора

Элементы можно перебирать:

1) Слева направо с шагом 1, используя цикл с параметром for(int I=0;I=0;I--){обработка a[I];}

2) Слева направо с шагом отличным от 1, используя цикл с параметром for (int I=0;I=0;I--){обработка a[I];}

3) Справа налево с шагом 1, используя цикл с параметром for(int I=n-1;I>=0;I--){обработка a[I];}

4) Справа налево с шагом отличным от 1, используя цикл с параметром for (int I=n-1;I>=0;I-=step){обработка a[I];}

Перебор массива по два элементу

1) Элементы массива можно обрабатывать по два элемента, двигаясь с обеих сторон массива к его середине: int I=0, J=N-1; while( I
{обработка a[I] и a[J];I++;J--;}

2) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 1(т. е. обрабатываются пары элементов a[1]и a[2], a[2]и a[3] и т. д.):

for (I=1;I
3) Элементы массива можно обрабатывать по два элемента, двигаясь от начала к концу с шагом 2 (т. е. обрабатываются пары элементов a[1]и a[2], a[3]и a[4] и т. д.)

int I=1; while (I
{обработка a[I] и a[I+1]; I+=2;}

2. Указатели на функции. Примеры.

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

int boo() // код функции boo находится в ячейке памяти 002B1050

{ return 7;}

int main()

{ boo(); // переходим к адресу 002B1050

return 0; }

пример вызова функции через указатель

int boo(int a)

{ return a;}

int main()

{

int (*fcnPtr)(int) = boo; // присваиваем функцию boo для fcnPtr

(*fcnPtr)(7); // вызываем функцию boo(7), используя fcnPtr

return 0;}

Билет №9

1. Сортировка массивов (простой обмен, простое включение, простой выбор).

Сортировка простого обмена

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

Процесс повторяется с оставшимися элементами массива.

for(int i=1;i=i;j--)

if(a[j]
Сортировка простого включения

Элементы массива делятся на уже готовую последовательность и исходную. При каждом шаге, начиная с I=2, из исходной последовательности извлекается I-ый элемент и вставляется на нужное место готовой последовательности, затем I увеличивается на 1 и т. д.

В процессе поиска нужного места осуществляются пересылки элементов больше выбранного на одну позицию вправо, т. е. выбранный элемент сравнивают с очередным элементом отсортированной части, начиная с J:=I-1. Если выбранный элемент больше a[I], то его включают в отсортированную часть, в противном случае a[J] сдвигают на одну позицию, а выбранный элемент сравнивают со следующим элементом отсортированной последовательности. Процесс поиска подходящего места заканчивается при двух различных условиях:

- если найден элемент a[J]>a[I];

- достигнут левый конец готовой последовательности.

int i,j,x;

for(i=1;i
j=i-1; while(x=0)//поиск подходящего места{

a[j+1]=a[j];//сдвиг вправо; j--;}

a[j+1]=x;//вставка элемента}

Сортировка простого выбора

Выбирается минимальный элемент массива и меняется местами с первым элементом массива. Затем процесс повторяется с оставшимися элементами и т. int i,min,n_min,j;

for(i=0;i
{ min=a[i];n_min=i;//поиск минимального

for(j=i+1;j
if(a[j]
a[n_min]=a[i];//обмен

a[i]=min;}

2. Ссылки на функции. Примеры.

------

Билет №10

1.Поиск в одномерных массивах (дихотомический и линейный).

Дихотомический поиск(бинарный поиск)

Обозначим через l – левую границу поиска, r – правую границу поиска и sr – индекс элемента, находящегося в середине массива. Сравним искомый элемент k со средним элементом a[sr]. Если они совпадают, то поиск завершен успешно и местоположение определено. Если искомый элемент больше, то берем правую половину массива (элементы с индексами от sr + 1 до r); если меньше – то левую (элементы с индексами от l до sr – 1). Процесс повторяется до тех пор, пока не будет найден нужный элемент или диапазон поиска не будет исчерпан.

Линейный, последовательный поиск

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

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

2. Типы данных, определяемые пользователем (переименование типов, перечисление, структуры, объединения). Примеры.

Переименование типов

Типу можно задать имя с помощью ключевого слова typedef:

typedef тип имя_типа[размерность]

Примеры:

typedef unsigned int UNIT;

typedef char Msg[100];

Такое имя можно затем использовать также как и стандартное имя типа:

UNIT a,b,c;//переменные типа unsigned int

Msg str[10];// массив из 10 строк по 100 символов

Перечисления

Если надо определить несколько именованных констант таким образом, чтобы все они имели разные значения, можно воспользоваться перечисляемым типом:

enum [имя_типа] {список констант};

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

Структуры

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

struct имя_типа {

тип элемент;

тип элемент; и тд

};

Объединения

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

Пример

union{ char s[10];

int x; }u1;