Теоретичний матеріал до уроку «Алгоритми сортування»

Зміст

Функція sizeof

Сортування простим пошуком

3. Метод “бульбашки”

Задачі

Література

 

Слайд № 3

 

Сортування одновимірних масивів. Сортування простим пошуком

Алгоритм:

Заповнити масив з n елементів

Організувати перегляд масиву n-1 разів

Знайти максимальний елемент у невідсортованій частини масиву; запам'ятати його номер

2.2. Поміняти значення знайденого максимального елементу зі значення початкового елементу невідсортованої частини масиву

3. Вивести отриманий масив

 

Слайд № 5

 

Сортування одновимірних масивів. Метод “бульбашки”

Алгоритм:

Заповнити масив з n елементів

Організувати перегляд масиву n-1 разів

Організувати порівняння значень кожної пари сусідніх елементів

Якщо значення попереднього елементу більше, ніж наступного, переставити сусідні елементи місцями

Вивести отриманий масив

void bubl(int *mas[], int n)
{

int i.j;
int rab;
for(j=1; j<n; j++)
for (i=1; i<n; i++)
if (*mas[i-1]>*mas[i])
{
rab=*mas[i-1];
*mas[i-1]=*mas[i];
*mas[i]=rab;
}
}
….bubl(&a, n); //виклик

.

Слайд № 7

 

Задачі (Слайд № 8)

Дослідити, чому у функції buble використовується вказівники. Що буде, якщо їх прибрати?

Випробуйте наведені методи сортування. Масиви впорядковуються за зростанням чи за спаданням. Змініть порядок сортування.

Вдоскональте програми, доповнивши їх двома функціями: для виведення масиву і для обміну двох значень (swap)

Підрахуйте, скільки різних чисел є значеннями елементів масиву

Визначте, яке число найчастіше зустрічається в масиві

Увести два масиви. Знайти числа, які зустрічаються в кожному з двох масивів

Увести два впорядкованих за зростанням масиви. Об'єднати їх в один масив так, щоб він виявився впорядкованим за зростанням

Література

1. Лєхан С.Ф. Інформатика С++. Спецкурс. 10-12 класи. – Шепетівка; Аспект, 2007.

2. Глинський Я.М., Анохін В.Є., Ряжська В.А. С++ і С++ Builder. Навчальний посібник. – Львів: СПД Глинський, 2006.

3. Глушаков С.В., Смирнов С.В., Коваль А.В. Практикум по С++. – Харьков: Фолио, 2006.

4. Павловская Т.А. С/С++. Программирование на языке высокого уровня. – СПб.: Питер, 2003

Лисенко Т.І. Поглиблене вивчення програмування в школі. – К.:ТОВ Редакція “Комп'ютер”, 2007.

 

Ров’язки завдань

Слайд № 8

Задача 3a

#include <iostream.h>

#include <conio.h>

void show_array(inta[], int n)

{for (int I=0; I<n; I++) cout<<a[I]<<” “;

cout<<endl;}

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

void get_array(int a[], int n)

{for (int I=0; I<n; I++) cin>>a[I];}

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

int MaxEl(int a[], int m, int n)

{int max=a[m]; int L=m;

for (int I=m+1; I<n; I++)

if (a[I]>=max) {max=a[I]; L=І;}

return (L);}

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

void swap(int*a, int*b)

{int temp=*a; * a= b; *b=temp;}

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

int main()

{int n; cin>>n; int a[100];

get_array(a,n);

int mc=0; int L;

int nc=sizeof(a)/sizeof(a[0]);

while (mc<nc)

{ L=MaxEl(a, mc, nc);

swap(&a[mc], &a[L]);

mc++;}

show_array(a, n);

getch();

return 0;

}

Задача 3b

#include <iostream.h>

#include <conio.h>

void show_array(inta[], int n)

{for (int I=0; I<n; I++) cout<<a[I]<<” “;

cout<<endl;}

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

void get_array(int a[], int n)

{for (int I=0; I<n; I++) cin>>a[I];}

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

void swap(int*a, int*b)

{int temp=*a; * a= b; *b=temp;}

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

void bubl(int *mas[], int n)

{bool fl=false; int j=1;

do

{fl=false;

for (int I=0; I<n-j; I++)

if (*max[I]>*mas[I+1])

{swap(&mas[I], &mas[I+1];

fl=true;}

j++}

while (fl)

}

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

int main()

{int n; cin>>n; int a[100];

get_array(a,n);

int nc=sizeof(a)/sizeof(a[0]);

bubl(&a, nc)

show_array(a, n);

getch();

return 0;

}

 

Задача 4

(після сортування, замість виведення елементів масиву)

for (int k=1; int I=0; I<n-1; I++)

if (a[I]!=a[I+1]) k++;

cout<<k<<endl;

 

Задача 5

(після сортування, замість виведення елементів масиву)

int k=1, km=1, b=a[0];

for (int I=0; I<n-1; I++)

if (a[I]==a[I+1]) k++;

else

if (k>km) {km=k; b=a[I], k=1;}

cout<<b<<endl;

Задача 6

(зміни внести в головну функцію)

int main()

{int n; cin>>n; int a[100];

get_array(a,n);

int m; cin>>m; int b[100];

get_array(b, m);

bubl(&a, n);

bubl(&b, m);

int I=0, L=0;

do

{if (a[I]!=b[L]) I++;

else {cout<<a[I]<<” “; I++; L++;}

while (I<n && L<m);

getch();

return 0;

}

Задача 7

#include <iostream.h>

#include <conio.h>

void show_array(inta[], int n)

{for (int I=0; I<n; I++) cout<<a[I]<<” “;

cout<<endl;}

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

void get_array(int a[], int n)

{for (int I=0; I<n; I++) cin>>a[I];}

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

int main()

{int n; cin>>n; int a[100];

get_array(a,n);

int m; cin>>m; int b[100];

get_array(b, m);

int c[200];

int I=L=k=0;

do

{if (a[I]<b[L]) {c[k]=a[I]; k++;}

else

if (a[I]=b[L]) {c[k]=a[I]; I++; k++; c[k]=b[L]; L++; k++;}

else {c[k]=b[L]; L++; k++;}

}

while (I<n && L<m);

if (I==n && L!=m)

{for (I=l; I<m; I++) {c[k]=b[L]; k++;}}

else

if (L==m && I!=n)

{for I=L; I<n; I++) {c[k]=a[I]; k++;}}

show_array(c, m+n);

getch (); return 0;}

Урок № 28

Тема: Практична робота “Впорядкування масивів”

Мета:

1. Розвиток навичок роботи опрацювання масивів
2. Розвиток навичок аналізу та локалізації помилок
3. Формування самостійності

Тип: Р озвиток навичок

Обладнання:

1. Презентація “Впорядкування масивів”
2. Програми, що були збережені на попередньому уроці

Епіграф “Глаза бояться – руки делают” /народна мудрість/

Хід уроку

№	Етап уроку	Діяльність учителя	Діяльність учнів
	Організаційний момент	Оголошення теми та плану уроку. Мотивація. Визначення стратегії роботи: Тестові приклади – обов’язкові! Кожна пара учнів реалізує по 3 задачі слайду № 8 або, кожна пара реалізує одну задачу, а потім міні-турнір (тобто, доповідь, рецензування, робота опонента)	Записують у зошит     Обирають варіант роботи
	Самостійна практична робота	Спостереження. Надання допомоги в разі необхідності. Перевірка виконання завдань	Розв’язування задач та їх реалізація. Міні-турнір (оцінка від кожної пари учнів)
	Домашнє завдання	Доопрацювати завдання з урахуванням зауважень	Записати в зошит Запитання по виконанню завдань

Урок № 29