Метод вибору мінімальних елементів

Розглянемо такий приклад. Нехай ми на великій кількості карток напишемо деякі числа. Кожна окрема картка – це окремий елемент деякого масиву. Як навести порядок у картках, на яких написані ці числа? Спочатку необхідно знайти мінімальний елемент у всьому заданому масиві і поміняти його з елементом, який поки що стоїть на першому місці, тому що саме на цьому місці повинен стояти шуканий мінімальний елемент. Тепер вже перший елемент знаходиться на своєму місці і можемо його не розглядати далі, тобто будемо повторно починати пошук в масиві, але з другого елемента. З новим масивом виконаємо ті самі дії: знайдемо в ньому мінімальний елемент і поміняємо його місцями з першим відкритим елементом (насправді він є другим елементом у початковому масиві). Таким чином будемо продовжувати доти, доки на останньому кроці не залишаться два останні елементи. Якщо необхідно, поміняємо і їх місцями.

#include<iostream.h>

#include<conio.h>

voidinput(int *a, int n)

{

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

{ cout<<"a["<<i<<"] = ";

cin>>*(a+i); }

}

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

Void output(int *a, int n)

{

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

cout<<a[i]<<" ";

cout<<endl;

}

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

Void sorting(int *a,int n)

{

int j,k,min;

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

{

min =*(a+i);k=i;

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

if (*(a+j)<min){min=*(a+j);k=j;}

j=*(a+i);*(a+i)=min;*(a+k)=j;

}

}

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

voidmain()

{

clrscr();

cout<<"Введiть масив:\n";

cout<<"Кiлькiсть елем. = ";

int n; cin>>n;

int a[100]; input(a,n);

sorting(a,n);

output(a,n);getch();

}

49. Багатовимірні масиви – це масиви,які мають не один,а декілька індексів.

Головна діагональ квадратної матриці — діагональ, що проходить через лівий верхній та правий нижній кути. Наприклад, у наступної матриці елементи головної діагоналі рівні одиниці:

Побічна діагональ – це діагональ з південного заходу на північний схід

Метод прямого обміну («бульбашки»)

В основі алгоритму лежить метод обміну сусідніх елементів масиву. Кожен елемент масива, починаючи з першого, порівнюється з наступним і якщо він бульний наступного, то ці елементи міняються місцями. Таким чином, елементи з меншим значенням переміщаються до початку масива (вспливають), а елементи з більшим значенням – до кінця масива (тонуть). Тому цей метод називають методом «бульбашки». Цей процес повторюється на 1 менше разів, чим елементів у масиві.

53. Рядки символів і дії з ними. На відміну від інших мов програмування у C++ не визначено спеціального типу для опрацювання рядків. Рядок символів розглядається як масив елементів типу char, який закінчується символом '\0' (нуль-символ) що є ознакою кінця рядка. Такі рядки називають ASCIІ-рядками. Сталі типу рядок записують у лапках, на­приклад, "Львівська політехніка", "студенти", ' " — рядок, що містить один символ-пропуск. У сталих рядках нуль-сим-вол дописується автоматично.

54. Функції для опрацювання рядків. Для опрацювання масивів символів у мові C++ є стандартні функції, які опи­сані у модулі string.h. Розглянемо деякі з них.

strlen(<рядок>) - визначає фактичну кількість символів у рядку, застосовується у виразах;

strcat(r1, r2) - команда з'єднання рядків r1, r2 в один ря­док, результат присвоює змінній r1;

strncat(r1, r2, n) - до змінної r1 додає перших n символів рядка r2, команда;

strcpy(r1, r2) - копіює символи з рядка r2 в рядок r1, команда;

strncpy(r1, r2, n) - копіює перших п символів рядка r2 в рядок r1, команда;

strchr(r1, <символ>) - визначає перше входження деякого символу у рядок r1 так: повертає рядок, який почи­нається від першого входження заданого символу до кінця рядка r1, застосовується у виразах;

strrchr(r1, <символ>) - визначає останнє входження зада­ного символу у рядок, застосовується у виразах;

strspn(r1, r2) - визначає номер першого символу, якийвходить у рядок r1, але не входить у рядок r2, застосовується у виразах;

strstr(r1, r2) - визначає в рядку її підрядок, що починаєть­ся з першого входження рядка г2 у рядок її, засто­совуєтьсяу виразах;

strtok(r1, r2) - визначає частину рядка її, яка закінчується перед періпим однаковим символом рядків її та г2;

strnset(r1, <символ>, п) - вставляє п разів заданий символ перед рядком її, застосовується у виразах;

strupr(r1) - перетворює усі малі літери рядка у великі;

strlwr(r1) - перетворює усі великі літери рядка у малі;

strrev(r1) - записує рядок у зворотному порядку.

57. Під час оголошення структури можна задавати обсяг пам'яті, який займатимуть змінні певного поля. Для цього після назви поля ставиться знак двокрапки та зазна­чається ціле число або стала - кількість байтів. Такі поля називають бітовими. Визначити обсяг, який займає ціла структура, можна так: sizeof(<Haзва типу структури>). Коли у програмі описана структура, то оголосити змінні або вказівники цього типу можна так:

<назва типу структури><список змінних і вказівників>;

Ініціалізація структур(на прикладі):

Оголосимо структуру grupal та дві змінні grA, дгВ цього типу. Нехай структура grupal містить поля прізвище, ім'я, середній бал і структуру дату народження (birthday), яка складається з полів: рік, місяць, число.

struct grupa1 {

char name[20], surname[20];

struct

{

int year, month, day;

} birthday;

floatserball;

} grA, grB;

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

63. Адреса даних – це адреса в оперативній пам’яті.

Операція визначення адреси:

&<назва даного>

63. Здійснення доступу до змінної по вказівнику(на прикладі):

Нехай у програмі оголошено змінні – int n = 10; float stud1, stud2, stud3;

Тоді можна оголосити вказівники nomer і rist на ці змінні:

Nomer=&n;

rist=&stud1;

rist=&stud3;

Отримати вмістиме комірки, на яку вказує вказівник,можна за допомогою конструкції *<вказівник>.Вказівники застосовують також для надання значень змінним:

rist=&stud1;

*rist=1,65; //У комірку пам’яті для змінної stud1 буде занесено число 1.65

Тут вказівник rist вказуватиме на адресу змінної stud1, а власне змінній stud1 буде присвоєно значення 1.65.

64. Щоб звернутись до деякого елемента,необхідно зазначити ім’я масиву,а у квадратних дужках – його номер. Наприклад, змінна stud[2] є третім елементом масиву stud, a stud[4] – п’ятим, оскільки масив stud має елементи: stud[0] stud[1] stud[2] stud[3] та stud[4]

Назва масиву stud є вказівником на його перший елемент. Змінна * stud містить значення першого елементу масиву (елементу масиву stud[0]).Оскільки всі елементи масиву розміщені у послідовних комірках опер. пам’яті компа, то вказівник (stud + 1) вказуватиме на другий елемент масиву (зміщення відносно вказівника stud на одну одиницю пам’яті), а вказівник (stud + 4) – на п’ятий (зміщення на чотири одиниці).

65.Змінювати посилання в програмі не можна. Посилання завжди вказує на одну і ту саму адресу в опер.пам. Це використовують під час створення та виклику функцій. Під час виклику функції копії усіх її фактичних параметрів заносяться у спеціально організовану область пам’яті. Потім виконуються відповідні команди функції і результат повертається у програму командою return. Оскільки всі дії відбуваються з копіями параметрів, а не із самими параметрами (копії та власне параметри розміщені у різних ділянках пам’яті), то значення фактичних параметрів в основній програмі не змінюються. Як параметри функції можна використовувати посилання або вказівники. Тоді значення фактичних параметрів у основній програмі змінюватимуться, оскільки функція буде повертати значення в основну програму не тільки через змінну з командою return, а й через відповідні посилання та вказівники, бо вони вказують на ту саму ділянку пам’яті, де розміщені фактичні параметри.

66. Щоб передати посилання чи вказівники у функцію як параметри і не змінити значення фактичних параметрів,треба в оголошенні функції до кожного параметра дописати ключове слово const.

У С++ посиланням може бути не тільки змінна чи стала, а і функція:

<тип>&<назва функції>(<список формальних параметрів>)

68. Оголошення символів масивів:

char<назва рядка>[довжина рядка];

Рядки можна опрацьовувати посимвольно за допомогою вказівників або назви масиву. Увести весь масив символів можна за допомогою команди:

cin>><назва масиву>;

Якщо рядок даних містить символ пропуску,то команда cin>> зчитає дані лише до першого пропуску. Щоб зчитати весь рядок до символу вводу, необхідно застосувати програму:

cin.get(<назва рядка>,<максимальна довжина рядка>);

Посимвольно вводити чи виводити елементи рядка можна за допомогою команд циклу for або while.

Найголовніша мета будь-якої задачі з масивами — обробити їх елементи. Для цього при обробці одномірних масивів використовуємо цикл for, в якому нумерацію (значення змінної циклу i) ведемо з першого елементу, закінчуємо його виконання останнім (поки i <n), з кроком рівним одиниці (i = i + 1). У цьому циклі ми повинні виконувати перетворення елементів масиву або витягати з них важливу інформацію. Дані перетворення досягаються маніпуляцією A [i] елементом масиву, де A — вихідний оголошений масив.

Кориснa порадa

Для обробки двовимірних масивів необхідно використовувати не один, а два цикли for. При цьому імена змінних циклів повинні бути різними, наприклад i та j. Звернення до елемента такого масиву досягається командою A [i] [j] -.

69. Принцип динамічної організації пям’яті полягає в тому,що для змінних надається пам’ять за необхідністю (за вказівкою програміста).Такі змінні називаються динамічними.Для роботи з динамічними змінними використовують вказівники. Для виділення динамічної пам’яті застосовується команда new так:

<тип вказівника>*<назва>=new<тип змінної>;

Дія команди new. Для відповідного типу змінної автоматично надається необхідна неперервна ділянка пам’яті. Команда повертає обсяг цієї ділянки,а вказівник вказує на її початок.

Дія команди delete. Після опрацювання динамічних змінних пам’ять необхідно вивільнити,а відповідний вказівник занулити. Якщо цього не зробити,то пам’ять можна вичерпати. Вивільняють її за допомогою команди:

Delete<назва вказівника>;

Щоб вказівник не вказував на жодну ділянку пам’яті, його необхідно занулити такою командою:

<назва вказівника>=NULL;

71. Для опрацювання файлу його необхідно відкрити, виконати потрібні дії та закрити.

Зчитування даних із файлу. Щоб зчитати вхідні дані з файлу, необхідно оголосити файлову змінну та відкрити файл читання так (розглянемо два способи):

бо так:

Ifstream<назва файлової змінної>; <назва файлової змінної>.(<зовнішня назва>);

Зчитати дані з файлу можна за допомогою команди:

<назва файлової змінної>>><змінна 1>>><змінна 2>>>... >><змінна N>

Після опрацювання файлу його потрібно закрити. Це роб­лять так:

<назва файлової змінної>.close()

Наприклад, MyFile.close (). Файл MyText.txt буде закрито. Після цього файлову змінну MyFile у разі потреби можна зв'язати з іншим файлом на диску.

Визначити кінець файлу можна за допомогою функції eof (eof – endoffile, кінець файлу) так:

<назва файлової змінної>.eof()

Ця функція повертає нульове значення, якщо досягнуто кінця файлу.

72. Виведення даних у файл. Відкрити файл для запи­тання у нього даних можна так:

iоsteram<назва файлової змінної> (<зовнішня назва>,ознака1 | ознака2 |... | ознака N)

або так:

iоsteram<назва файлової змінної>; <назва файлової змінної>.ореn(<зовнішня назва>);

Не нашли, что искали? Воспользуйтесь поиском: