Сортировка пузырьковым методом.
Практическая работа № 1
«Применение методов построения алгоритмов»
Цель работы: изучить основы алгебры логики
Задание для практического занятия:
1. Используя метод последовательной детализации, постройте блок-схему и программу решения квадратного уравнения.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
using namespace std;
int main() {
double a,b,c;
double x;
cout << " a: ";
cin >> a;
cout << " b: ";
cin >> b;
cout << " c: ";
cin >> c;
if ((b*b - 4*a*c) >= 0)
{
x = (-1*b + sqrt(b*b - 4*a*c)) / (2*a);
cout << "Perviy koren raven" << x << endl;
x = (-1*b + sqrt(b*b - 4*a*c)) / (2*a);
cout << "Vtoroy koren raven" << x << endl;
} else
{
cout << "Diskriminant menshe 0, korni neveshestvennie" << endl;
}
cin >> x;
return 0;
}
2. Используя метод последовательной детализации, постройте блок-схему и программу решения системы линейных алгебраических уравнений методом Гаусса.
#include <iostream>
#include <math.h>
#include <cmath>
using namespace std;
void sysout(double **a, double *y, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cout << a[i][j] << "*x" << j;
if (j < n - 1)
cout << " + ";
}
cout << " = " << y[i] << endl;
}
return;
}
double * gauss(double **a, double *y, int n)
{
double *x, max;
int k, index;
const double eps = 0.00001;
x = new double[n];
k = 0;
while (k < n)
{
max = abs(a[k][k]);
index = k;
for (int i = k + 1; i < n; i++)
{
if (abs(a[i][k]) > max)
{
max = abs(a[i][k]);
index = i;
}
}
if (max < eps)
{
cout << "Reshenie poluchit nevozmozhno iz-za nulevogo stolbca ";
|
|
|
cout << index << " Matrici A" << endl;
return 0;
}
for (int j = 0; j < n; j++)
{
double temp = a[k][j];
a[k][j] = a[index][j];
a[index][j] = temp;
}
double temp = y[k];
y[k] = y[index];
y[index] = temp;
for (int i = k; i < n; i++)
{
double temp = a[i][k];
if (abs(temp) < eps) continue;
for (int j = 0; j < n; j++)
a[i][j] = a[i][j] / temp;
y[i] = y[i] / temp;
if (i == k) continue;
for (int j = 0; j < n; j++)
a[i][j] = a[i][j] - a[k][j];
y[i] = y[i] - y[k];
}
k++;
}
for (k = n - 1; k >= 0; k--)
{
x[k] = y[k];
for (int i = 0; i < k; i++)
y[i] = y[i] - a[i][k] * x[k];
}
return x;
}
int main()
{
double **a, *y, *x;
int n;
cout << "Vvedite kolichestvo uravneniy: ";
cin >> n;
a = new double*[n];
y = new double[n];
for (int i = 0; i < n; i++)
{
a[i] = new double[n];
for (int j = 0; j < n; j++)
{
cout << "a[" << i << "][" << j << "]= ";
cin >> a[i][j];
}
}
for (int i = 0; i < n; i++)
{
cout << "y[" << i << "]= ";
cin >> y[i];
}
sysout(a, y, n);
x = gauss(a, y, n);
for (int i = 0; i < n; i++)
cout << "x[" << i << "]=" << x[i] << endl;
cin.get(); cin.get();
return 0;
}
Контрольные вопросы:
- В чем заключаются основные принципы структурного программирования?
Абстракция позволяет программисту вообразить требуемое решение проблемы без сиюминутного учета множества деталей. Программист может рассматривать программу по уровням: верхний уровень показывает большую абстракцию, упрощает взгляд на проект, в то время как нижний уровень показывает мелкие детали реализации.
|
|
|
Формальность Использование при разработке программы строгого методического подхода, что является базой для превращения программирования из импровизации в инженерную дисциплину. Этот принцип дает основания для доказательства правильности программ, так как позволяет изучать программы (алгоритмы) как математические объекты.
«Разделяй и властвуй» Разделение программы на отдельные фрагменты (модули), которые просты по управлению и допускают независимую отладку и тестирование. Иерархическое упорядочение Структура разбиения на части не менее важна, чем сам факт такого разделения. Этот принцип выдвигает требование иерархического структурирования взаимосвязей между модулями программного комплекса, что облегчает достижение целей структурного программирования.
- На чем основано нисходящее проектирование?
Метод основан на идее уровней абстракции, которые становятся уровнями модулей в разрабатываемой программе. На этапе проектирования строится схема иерархии, изображающая эти уровни. Схема иерархии позволяет программисту сначала сконцентрировать внимание на определении того, что надо сделать в программе, а лишь затем решать, как это надо делать. При нисходящем проектировании исходная, подлежащая решению задача разбивается на ряд подзадач, подчиненных по своему содержанию главной задаче. Такое разбиение называется детализацией или декомпозицией
|
|
|
- В чем заключается метод последовательной детализации?
Сначала анализируется исходная задача. В ней выделяются подзадачи. Строится иерархия таких подзадач. Затем составляются алгоритмы (или программы), начиная с основного алгоритма (основной программы), далее — вспомогательные алгоритмы (подпрограммы) с последовательным углублением уровня, пока не получим алгоритмы, состоящие из простых команд.
Практическая работа №2
«Определение сложности алгоритмов»
Цель работы: Научиться оценивать временную сложность алгоритмов
Задания для практического занятия:
Оцените сложность следующих алгоритмов сортировки и сделайте сравнительный анализ:
1. сортировка пузырьковым методом;
2. сортировка вставкой;
3. сортировка посредством выбора;
4. сортировка Хоара;
5. сортировка Шелла.
Сортировка пузырьковым методом.
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются 1 {\displaystyle N-1} раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде — отсюда и название алгоритма).
|
|
|
Сортировка вставкой
Сортировка вставками (Insertion Sort) — это простой алгоритм сортировки. Суть его заключается в том что, на каждом шаге алгоритма мы берем один из элементов массива, находим позицию для вставки и вставляем. Стоит отметить что массив из 1-го элемента считается отсортированным.
Словесное описание алгоритма звучит довольно сложно, но на деле это самая простая в реализации сортировка. Каждый из нас, не зависимо от рода деятельности, применял алгоритм сортировки, просто не осознавал это:) Например когда сортировали купюры в кошельке — берем 100 рублей и смотрим — идут 10, 50 и 500 рублёвые купюры. Вот как раз между 50 и 500 и вставляем нашу сотню:) Или приведу пример из всех книжек — игра в карточного «Дурака». Когда мы тянем карту из колоды, смотрим на наши разложенные по возрастанию карты и в зависимости от достоинства вытянутой карты помещаем карту в соответствующее место. Для большей наглядности приведу анимацию из википедии.
Дата добавления: 2021-12-10; просмотров: 52; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!