Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Идеология абсолютной монархии в

Информатика. Предмет информатики. Основные задачи информатики. 2

Устройства ввода/вывода данных, их разновидности и основные характеристики 2

Основы машинной графики. Системы компьютерной графики и анимации. 16

Электронные презентации. 21

Информационная модель объекта. 22

Этапы разработки программного обеспечения. 24

Эволюция языков программирования. Классификация языков программирования 25

Назначение и основы использования систем искусственного интеллекта; базы знаний, экспертные системы, искусственный интеллект. 32

Программы для работы в сети Интернет. 37

Классификация и характеристики компьютерных вирусов. 38

Методы защиты от компьютерных вирусов. 42

Список используемых источников. 48

Оглавление. 49

КУРСОВА РОБОТА

З дисципліни: Інформатика

Виконав студент 2-курсу ІЗДН

Спеціальність: 6.050802

“Електронні пристрої та системи”

Погорєлов Михайло Геннадійович

Зал.кн. №18.0504

Р.

Зміст

Задание………………………………………………………………………………………………3

Процедура слияния…………………………………………………………………………………3

Сортировка слиянием………………………………………………………………………………4

Лістинг програми……………………………………………………………………………………6

Задание: Ввести массивы А и В. В массив С перенести те четные элементы массива А, левее которых стоят элементы с нечетным значением. Также в массив С перенести элементы В, который по значению ближе всех к (min+max)/2? где min – значение минимального элемента массива В, а max - значение максимального элемента массива В. Массивы А,В и С отсортировать по возрастанию, используя сортировку методом слияния.

Про­це­ду­ра слия­ния

До­пу­стим, у нас есть два от­сор­ти­ро­ван­ных мас­си­ва A и B раз­ме­ра­ми и со­от­вет­ствен­но, и мы хо­тим объ­еди­нить их эле­мен­ты в один боль­шой от­сор­ти­ро­ван­ный мас­сив C раз­ме­ром . Для это­го мож­но при­ме­нить про­це­ду­ру слия­ния, суть ко­то­рой за­клю­ча­ет­ся в по­вто­ряю­щем­ся «от­де­ле­нии» эле­мен­та, наи­мень­ше­го из двух имею­щих­ся в на­ча­лах ис­ход­ных мас­си­вов, и при­со­еди­не­нии это­го эле­мен­та к кон­цу ре­зуль­ти­рую­ще­го мас­си­ва. Эле­мен­ты мы пе­ре­но­сим до тех пор, по­ка один из ис­ход­ных мас­си­вов не за­кон­чит­ся. По­сле это­го остав­ший­ся «хвост» од­но­го из вход­ных мас­си­вов до­пи­сы­ва­ет­ся в ко­нец ре­зуль­ти­рую­ще­го мас­си­ва. При­мер ра­бо­ты про­це­ду­ры по­ка­зан на ри­сун­ке:

Рис. 1. При­мер ра­бо­ты про­це­ду­ры слия­ния

Ал­го­ритм слия­ния фор­маль­но мож­но за­пи­сать сле­дую­щим об­ра­зом:

(1)

Для обес­пе­че­ния ста­биль­но­сти ал­го­рит­ма сор­ти­ров­ки нуж­но, что­бы в слу­чае ра­вен­ства эле­мен­тов тот эле­мент, что идёт рань­ше во вход­ном мас­си­ве, по­па­дал в ре­зуль­ти­рую­щий мас­сив в первую оче­редь. Мы уви­дим да­лее, что ес­ли два эле­мен­та по­па­ли в раз­ные мас­си­вы (A и B), то тот эле­мент, что шёл рань­ше, по­па­дёт в мас­сив A. Сле­до­ва­тель­но, в слу­чае ра­вен­ства эле­мент из мас­си­ва A дол­жен иметь при­о­ри­тет. По­это­му в ал­го­рит­ме стои́т знак вме­сто < при срав­не­нии эле­мен­тов.

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

(2)

Вре­мя ра­бо­ты про­це­ду­ры слия­ния со­став­ля­ет .

Реа­ли­за­ция про­це­ду­ры слия­ния на язы­ке про­грам­ми­ро­ва­ния C++ пред­став­ле­на в ли­стин­ге 1.

template<class T> void Merge ( T const *const A, int const nA,
T const *const B, int const nB,
T *const C )
{ //Выполнить слияние массива A, содержащего nA элементов,
// и массива B, содержащего nB элементов.
// Результат записать в массив C.

int a ( 0 ), b ( 0 ); //Номера текущих элементов в массивах A и B

while ( a+b < nA+nB ) //Пока остались элементы в массивах
{
if (( b>=nB ) || (( a<nA ) && ( A [ a ] <=B [ b ])))
{ //Копирую элемент из массива A
C [ a+b ] = A [ a ];
++a;
} else { //Копирую элемент из массива B
C [ a+b ] = B [ b ];
++b;
}
}
}

Ли­стинг 1. Ком­пакт­ная (не са­мая быст­рая) реа­ли­за­ция про­це­ду­ры слия­ния

Сор­ти­ров­ка слия­ни­ем

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

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

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

3. ес­ли чис­ло от­сор­ти­ро­ван­ных це­по­чек боль­ше еди­ни­цы, пе­рей­ти к ша­гу 2.

Про­ще все­го фор­ма­ли­зо­вать этот ал­го­ритм ре­кур­сив­ным спо­со­бом (в сле­дую­щем раз­де­ле мы реа­ли­зу­ем этот ал­го­ритм ите­ра­ци­он­ным спо­со­бом). Функ­ция сор­ти­ру­ет уча­сток мас­си­ва от эле­мен­та с но­ме­ром a до эле­мен­та с но­ме­ром b:

(3)

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

template<class T> void MergeSort ( T *const A, int const n )
{ //Отсортировать массив A, содержащий n элементов

if ( n < 2 ) return; //Сортировка не нужна

if ( n == 2 ) //Два элемента проще поменять местами,
{ // если нужно, чем делать слияние
if ( A [ 0 ] > A [ 1 ]) { T const t ( A [ 0 ]); A [ 0 ] =A [ 1 ]; A [ 1 ] =t; }
return;
}

MergeSort ( A, n/2 ); //Сортируем первую половину
MergeSort ( A+n/2, n-n/2 ); //Сортируем вторую половину

T *const B ( new T [ n ]); //Сюда запишем результат слияния

Merge ( A,n/2, A+n/2,n-n/2, B ); //Слияние половин

//Копирование результата слияния в исходный массив:
for ( int i ( 0 ); i<n; ++i ) A [ i ] =B [ i ];

delete [ n ] B; //Удаляем временный буфер
}

Ли­стинг 2. Реа­ли­за­ция сор­ти­ров­ки слия­ни­ем

Вре­мя ра­бо­ты сор­ти­ров­ки слия­ни­ем со­став­ля­ет . При­мер ра­бо­ты про­це­ду­ры по­ка­зан на ри­сун­ке:

Рис. 2. При­мер ра­бо­ты ре­кур­сив­но­го ал­го­рит­ма сор­ти­ров­ки слия­ни­ем

Лістинг програми

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused

#include <stdio.h>

#include <conio.h>

#include <iostream.h>

int merge (int *m1, int m1n, int *m2, int m2n, int *m3) {

int a(0), b(0);

while (a+b < m1n+m2n)

{

if((b>=m2n) || ((a<m1n) && (m1[a]<=m2[b])))

{ //Копирую элемент из массива A

m3[a+b] = m1[a];

++a;

} else { //Копирую элемент из массива B

m3[a+b] = m2[b];

++b;

}

}

}

void mergeSort (int *massiv, int n) {

if (n < 2)

return;

if (n == 2) {

if(massiv[0] > massiv[1])

{

swap (massiv[0], massiv[1]);

return;

}

}

mergeSort (massiv, n/2);

mergeSort (massiv+n/2, n-n/2);

int *TMP = new int[n];

merge(massiv,n/2,massiv+n/2,n-n/2,TMP);

for(int i(0); i<n; ++i) massiv[i]=TMP[i];

delete[n] TMP; //Удаляем временный буфер

return;

}

int main(int argc, char* argv[])

{

// Объявляем переменные размеров массивов

int An;

int Bn;

// Запрашиваем значения размера для каждого массива у пользователя

cout<<"\nRazmer massiva A:\n";

cin>>An;

cout<<"\nRazmer massiva B:\n";

cin>>Bn;

// Создаем массивы с указаными размерами (Выделяем память под них)

int *A = new int[An];

int *B = new int[Bn];

// Заполняем массивы случайными числами

for (int i = 0; i<An; i++)

{

A[i] = rand() % 100 + 1;

}

for (int i = 0; i<Bn; i++)

{

B[i] = rand() % 100 + 1;

}

// Отобразим заполненные массивы

cout<<"\nA:\n";

for (int i = 0; i<An; i++)

{

cout<<i<<"="<<A[i]<<"\n";

}

cout<<"\nB:\n";

for (int i = 0; i<Bn; i++)

{

cout<<i<<"="<<B[i]<<"\n";

}

// Посчитаем колличество нечетных значений в массиве для переноса в новый массив

int count = 0;

for (int i = 0; i<An; i++)

{

/*

Если остаток от деления на 2 равен 0 то мы имеем дело с четным индексом,

И если значение этого елемента не является четным по противоположному

принципу, то считаем этот елемент так как он попадает под условие поставленной

задачи. Его и будем переносить

*/

if (i%2==0 && A[i]%2!=0)

{

count++;

}

}

// Ищем максимально близкое по значению к (min+max)/2 в массиве В

// Сначала найдем минимальное и максимальное значение в массиве

// Сначала примем за минимальное первый елемент массива

int minB = B[0];

for (int i = 0; i<Bn; i++)

{

// И если он окажется больше какого-то значения в массиве

if (B[i] < minB)

{

// Мы примем это значение как минимальное

minB = B[i];

}

}

// По аналогии найдем максимальное значение

int maxB = B[0];

for (int i = 0; i<Bn; i++)

{

// И если он окажется больше какого-то значения в массиве

if (B[i] > maxB)

{

// Мы примем это значение как минимальное

maxB = B[i];

}

}

// Теперь посчитаем чему будет равно наче условие (min+max)/2

int uslovie;

uslovie = (minB + maxB)/2;

cout<<"\nUslovioe ravno: "<<uslovie<<"\n\n";

cout<<"\n_____________________________";

// Теперь можно найти максимально близкое к этому значение в массиве В

// Принцип схож с поиском крайних значений

int blizkoeB = B[0];

for (int i = 0; i<Bn; i++)

{

// Только здесь мы сравниваем абсолютную разницу между значением елемента

// и услоивем с абсолютной разницей между условием и значением предыдущего

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

if (abs(uslovie-B[i]) < abs(uslovie - blizkoeB))

{

blizkoeB = B[i];

}

}

// Теперь заполним массив С нашими значениями

// Размер увеличим на 1 так как к перенесенным добавляем еще максимально

// похожее к условию (min+max)/2 значение из массива В

count++;

int *C = new int[count];

// Добавим близкое первым елементом нового массива

C[0] = blizkoeB;

// Заполняем значениями из массива А

int j = 1;

int x = 0;

for (int i = 0; i<An; i++)

{

/*

Если остаток от деления на 2 равен 0 то мы имеем дело с четным индексом,

И если значение этого елемента не является четным по противоположному

принципу, то считаем этот елемент так как он попадает под условие поставленной

задачи. Его и будем переносить

*/

if (i%2==0 && A[i]%2!=0)

{

// Четные индексы с нечетными значениями в новый массив

C[j]=A[i];

j++;

}

else {

// Остальные сгруппируем в начале массива

A[x]=A[i];

x++;

}

}

// Уменьшим размер массива до колличества оставшихся в нём елементов

An=x;

// Отобразим новые массив

cout<<"\nA:\n";

for (int i = 0; i<An; i++)

{

cout<<i<<"="<<A[i]<<"\n";

}

cout<<"\nC:\n";

for (int i = 0; i<count; i++)

{

cout<<i<<"="<<C[i]<<"\n";

}

cout<<"\n_____________________________\n";

// Отсортируем массивы

mergeSort (A, An);

mergeSort (B, Bn);

mergeSort (C, count);

// Отобразим новые массив

cout<<"\nA:\n";

for (int i = 0; i<An; i++)

{

cout<<i<<"="<<A[i]<<"\n";

}

cout<<"\nB:\n";

for (int i = 0; i<Bn; i++)

{

cout<<i<<"="<<B[i]<<"\n";

}

cout<<"\nC:\n";

for (int i = 0; i<count; i++)

{

cout<<i<<"="<<C[i]<<"\n";

}

cout<<"\n_____________________________\n";

getch();

return 0;

}

Идеология абсолютной монархии в