Теоретични въпроси:
1. Рекурсия и рекурсивни функции в езика C++.
2. Динамична памет. Оператори new и delete.

Условие на задачата на C++:

зад.15. Да се състави програма за обработване на данни за служителите от дадена фирма. За всеки служител се въвежда следната информация: име, месечна заплата, служебен номер. Програмата да дава възможност за получаване на следните резултати:

1. Извеждане на списък на всички служители с въведените данни за тях;
2. Пресмятане и извеждане на средната заплата за фирмата;
3. Извеждане на списък на всички служители, които имат заплата по-голяма от средната заплата за фирмата;
4. Извеждане на списък на всички служители, чието име започва с дадена буква;
5. Извеждане на списък на всички служители, подреден в низходящ ред на месечните заплати.Ако има служители с една и съща заплата, по-напред в списъка да се изведе този, който има по-малък служебен номер.

 

 

Съдържание:

„Source“ код на програмата                    стр. 3 – 8

Алгоритъм                                            стр. 8 – 10

Развит теоретичен въпрос 1                   стр. 10 – 13

Развит теоретичен въпрос 2                   стр. 13 – 14

 

„Source“  код на програмата:

// string options.cpp : Defines the entry point for the console application.

//
#include “stdafx.h”
#include “iostream”
#include <string.h>
#include <iomanip>
#include <cctype>

using namespace std;

struct workers

{

int number;
char name[30];
double salary;

};

void read_workers(workers&);
void print_workers(workers&);
void sort_over_average(double, workers& );
int search_name(workers&, char*);
void sorttable(int, workers[]);
int d=0;

 

int main()

{

workers table[30];
int n;
int i;
int choice;
double s = 0;

cout << “Enter a number for employees between 1 and 30: “; // Въвеждане на брой работници.
cin >> n;

if (n < 1 || n > 30) // Проверка за въведения брой.
{

cout << “Number must be between 1 and 30! :”;
return 1;

}

for (i=0; i<=n-1; i++) // Извикване на функция за въвеждане на данните за всеки работник.

{

cout << “WORKER NUMBER[” << i+1 << “]: “;

read_workers(table[i]);

}

top:

cout << “\n =================================================================” << endl;
cout << “|Press:                                                                                                                              |” << endl;
cout << “|1 To view the information you entered                                                                              |” << endl;
cout << “|2 To view the average salary and workers with salary over average                            |” << endl;
cout << “|3 To search for a worker with the first letter of his name                                               |” << endl;
cout << “|4 To view the information sorted by salaries                                                                     |” << endl;
cout << “|5 To EXIT                                                                                                                                   |” << endl;
cout << “====================================================================” << endl;

cout << “\n Enter your choice: “;
cin >> choice;

if (choice < 1 || choice > 5) // Проверка на валидността на въведения избор.
{

cout << “Enter a number between 1 and 4!: “;
return 1;

}

switch (choice)        /* Чрез този оператор switch реализирам избора, като за всеки един избор се извиква     съответната функция, която да го реализира. */

{

case 1: {                                                        // Първи случай за извеждане на въведените данни в табличен вид.

for(i=0; i<n; i++)
{
print_workers(table[i]);     // Функция за извеждане на въведените дани.
}
goto top;

} break;

case 2:  // Втори случай за извеждане на средната заплата и на работниците, които са я надхвърлили.

{

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

{
s = s + table[i].salary;
}

double sum;
sum = (s/n);

cout << “\n” << “Average is: ” << sum << endl;
cout << “Workers with salary over average: ” << endl;

if(table[0].salary == sum)       // Проверка в случай, че няма заплати по-големи от средната.

cout << ” There are no workers!”;

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

{
sort_over_average(sum, table[i]);  // Функция за извеждане на работниците със заплата  над средната.
}

goto top;

} break;

case 3:  // Трети случай за търсенето на служител по първа буква от името му.

{

char search[2];

cout << “Enter a letter to search for worker: “;
cin >> search;

double q=0;

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

{

search_name(table[i], search);// Функция за търсене по име.
if (d == 3)
q = q++;
}

if (q == n)
cout << “There are no workers!”;
goto top;
}break;

case 4:  // Четвърти случай за сортировка на въведените заплати и извеждането на записите отново в табличен вид, но сортирани.

{

sorttable(n, table); // Функция за сортиране на работниците.
for(i=0; i<n; i++)
{
print_workers(table[i]); // Функция за принтиране на данните.
}

goto top;

} break;

case 5: return 0; break;
}

system(“PAUSE”);
return 0;

}

 

void read_workers(workers& w)  // Реализация на функцията за въвеждане на данните на служител.

{

cout << ‘\n’ << “Enter name: “;
cin >> w.name;

cout << ‘\n’ << “Enter salary: “;
cin >> w.salary;

cout << ‘\n’ << “Enter work number: “;
cin >> w.number;

cout << endl;

}

 

void print_workers(workers& wor) // Реализация на функцията за извеждане на въведените данни.

{

cout << endl << setw(20) << “Name: “<< wor.name << setw(10) << “Salary: ” << wor.salary << setw(10) << “Number: ” << wor.number ;

}

 

void sort_over_average(double sum, workers& work) // Реализация на функция за извеждане на служителите със заплата над средната.

{
if (work.salary > sum)
cout << work.name << endl;
}

int search_name(workers& work, char* search) // Реализация на функцията за търсене на служител по първа буква от името му.

{

if (strncmp(work.name, search,1)==0) // Проверка дали символът се среща

{

cout << work.name << setw(6) << work.salary << setw(10) << work.number << endl;

return d=0;

}

else // В случай, че не се среща

{

if(islower(search[0])) // Проверка дали буквата е малка

{

search[0] = toupper(search[0]); // Буквата се увеличава. Т.е. става главна.

if (strncmp(work.name, search,1)==0) // Ако се среща, резултатът се отпечатва
{

cout << work.name << setw(6) << work.salary << setw(10) << work.number << endl;
return d=0;

}

else return d= 3;
}

else //ако буквата е главна се изпълнява това.

{

search[0] = tolower(search[0]); // буквата се намалява
if (strncmp(work.name, search,1)==0) // резултатът се отпечатва

{

cout << work.name << setw(6) << work.salary << setw(10) << work.number << endl;
return d=0;

}

else return d= 3;

}

}

}

 

void sorttable(int n, workers table[]) // Реализация на функцията за сортиране по въведена заплата на служител.

{

workers tmp[30];
for (int i=0; i<n-1; i++)
{
for (int j=0; j<n-i-1; j++)
{
if (table[j].salary > table[j+1].salary)  // Първа сортировка за сравнение на заплатите и сортирането им в низходящ ред. Метод на мехурчето.
{

tmp[j] = table[j];
table[j] = table[j+1];
table[j+1] = tmp[j];

}

if (table[j].salary == table[j+1].salary) // Втора сортировка в случай, че заплатите са равни.

{

if (table[j].number > table[j+1].number) // Сортиране според служебния номер, в случай, че заплатите са равни.

{

tmp[j] = table[j];
table[j] = table[j+1];
table[j+1] = tmp[j];

 

}

}

}

}

}

Алгоритъм на програмната реализация:

Интерфейс на програмата – реших да създам едно простичко меню,  чрез което при въведено число да се извършва определено действие. По този начин дадох малка свобода на потребителя в избора му и в зависимост от това какво иска да направи.

Оператор switch – използвах го за да реализирам идеята по-горе за менюто, в случай, че бъдат избрани числата: 1,2,3,4 или 5.

1,2,3,4,5 – действия с числата:
1 – Извеждане на данните в табличен вид.
2 – Извеждане на средната заплата и на работниците, които получават повече от нея.
3 – Търсене на служител по буква.
4 – Сортировка на въведените данни.
5 – Изход.

Променливи, масиви и структури в задачата – В задачата използвам точно една структура  с име работници (workers).  Тя има следните полета:  Служебен номер (number),  Име на служителя (name[30]) и заплата (salary). Ползвам и един масив от 30 елемента от типа на структурата. Една от по-важните променливи е n, която служи за вкарване на броя на работниците (той трябва да бъде между 1 и 30, затова и масивът е от 30 елемента). Друга важна променлива е choice, в която се съхранява изборът на потребителя за това какво действие иска да се извърши (т.е. въведеното число).

Функциите в задачата –  за мое улеснение разбих задачата на едни малки подзадачи, всяка една от които, бива решаване от отделна функция. Така получих следните функции: Вход на данните,  Отпечатване на данните,  Намирането на работниците със заплата над средната, Търсенето на името на работник по буква и Сортиране на заплатите.  Тук ще обърна внимание на някои от по-интересните функции.

Някои по-важни функции :
– Намиране на работниците със заплата над средната (sort_over_average) –  самата функция е доста простичка. Обработва се целия масив като средната заплата се запазва в една променлива (sum), която събира заплатите на всички работници(salary) и ги дели на броя им (n). След това се обхожда масивът с въведеният брой работници и се сравнява заплатата на всеки работник със средната. Ако заплатата е по-голяма, то името на работника се изписва. Но ако заплатите на всички работници са равни, как да изпише функцията, че няма работници ? Тук се досетих за следното нещо. Ако заплатите на всичките работници са равни, то която и заплата на вземем , на който и да е работник, трябва да бъде равна на средната заплата. Т.е. равенството на заплатите на работниците помежду им, ни позволява да си изберем една заплата и да я сравним със средната и ако тя се окаже, че е равна на средната, тогава да се изпише, че няма работници с по-голяма от средната заплата. В случая аз взехм заплатата на първия работник и я сравнявах дали не е равна на средната заплата.
– Търсене на служител по името му (search_name) – тук се възползвах от една малка хитринка, която C++ ни позволява, чрез библиотеката cctype. Да речем, че въведем имената на работниците с главни букви, а когато изберем да ги търсим по първата буква от името им, въведем малка буква и резултат не излиза. Тук се намесва и cctype. Първото, което правя е да обходя всяко име на работник и да проверя дали първата буква на името му съответства на въведената буква. Ако да – извежда се. Ако не – тук идва хитрината. Ако не – сравнява се каква е буквата (дали малка е първо) чрез функцията islower. Ако е малка се увеличава (т.е. става главна) чрез функцията toupper и се проверява дали има резултат.  В случай, че не е малка са отива директно на else условието, без да има нужда от функция. Там, чрез функцията tolower, буквата се смалява (т.е. става малка) и се проверява дали се среща резултат. Ако да – отпечатва се. Това е малката особеност тук.  Другата особеност е как да изписва, че няма намерен резултат. Това става, чрез една променлива d=0, която я направих глобална. В случай, че при сравнение с всяко име не открива резултат, правя променливата да бъде d=3, и при всяко проверяване на всяко име, се задейства и един if оператор в цикъла, който проверява дали d=3 и ако е да, използвам една променлива p като брояч (почва от 0 и се увеличава с 1.) В случай, че променливата стане равна на броя на служителите, се изписва, че няма такива служители.
– Сортиране на служителите по заплатите (а при еднакви заплати, по служебен номер) – използвах метода на мехурчето за сортиране на заплатите на работниците в комбинация с условен оператор if, който проверява дали заплатите на служителите не са равни. В такъв случай се задейства пак сортировка, която сравнява служебните номера на служителите и извежда този с по-малък служебен номер.
Теоретични въпроси:

Рекурсия и рекурсивни функции в езика C++.
Динамична памет. Оператори new и delete.

Изготвил: Георги Мирчев                           Фак. Номер: 0901261023

 

Здравейте!  Казвам се Георги Мирчев и смятам днес да Ви изнеса две лекции на следните теми: Рекурсия и рекурсивни функции в C++ и Динамична памет. Оператори new и delete.
Избрал съм един, според мен поне, интересен начин да представя уроците пред Вас с надеждата, че ще привлека Вашето внимание и интерес.
Въпрос 1:
Рекурсия и рекурсивни функции в езика C++.

Нека направо да започнем с първата тема, която е: Рекурсия и рекурсивни функции в C++.
За пръв път като чух думата рекурсия и в мен изникна въпросът: Какво аджеба изобщо означава тази дума ? . Затова нека започнем от там. Думата има английски произход  и означава „повтарям се, случвам се отново“ .
А сега за рекурсията в информатиката.  Това е програмна техника, чиято правилна употреба може да Ви донесе много бонус точки както пред Вашите шефове, така и пред тези, на които я представяте. Рекурсия наричаме тогава, когато даден метод извиква себе си, за да реши даден проблем. Всъщност тези методи наричаме рекурсивни.
Предполагам, че все още не Ви е много ясно какво представлява точно рекурсията, затова нека видим два примера.
Числата на Фибоначи:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

F₁ = F₂ = 1
F_i = F_i-1 + F_i-2 (за i > 2)

Факториел на n или n! :

f(1)! = 1                f(2)! = 1*2           f(3)! = 1*2*3
f(n)! = n * f(n-1)!

Първият пример, който виждате, са числата на Фибоначи. При тях какво забелязвате ? Аз забелязвам, че всеки член на редицата е равен на сбора на предишните два.
Извели сме и една формула за общия член на редицата. Сега следващия пример. Той е за факториел n. Мисля, че всички знаят  какво представлява факториелът. Извел съм също една формула за общия член.  Ще оставя реализацията на двата примера за след малко. Сега нека погледнем видовете рекурсия.

Когато в тялото на метод се извършва обръщение към същия метод, казваме, че методът е пряко рекурсивен или тогава имаме пряка рекурсия.  А ако метод A се обръща към метод B, B към C, а С отново към А, казваме, че методът А, както и методите В и C са непряко (косвено) рекур сивни или взаимно-рекурсивни.

А->В, В ->С, С->А;

Сега нека погледнем реализацията на примера за числата на Фибоначи. Тя изглежда така:

double fib(int n) {
if (n <= 2)
return 1;
else
return fib(n – 1) + fib(n – 2);
}
Тя е пример за пряка рекурсия. Както виждате накрая методът извиква себе си. Имаме и едно условие, което виждате в началото. Условието n<=2 се нарича дъно на рекурсията. А какво значи дъно ? За да реализираме рекурсия трябва да сме сигурни, че ще получим резултат след краен брой стъпки. Затова трябва да имаме поне един случай, чието решение можем да намерим директно, без рекурсивно извикване. Тези случаи наричаме дъно на рекурсията.  Такъв е и случаят, когато n<=2. При него можем директно да върнем резултат, без да извършваме рекурсивни извиквания, тъй като по дефиниция първите два члена на редицата на Фибоначи са равни на 1.

Не съм сигурен, но мисля, че повечето от вас до сега би трябвало да се запитат дали това е най-ефективният начин за решение на дадена задача. Разбира се има и друг начин на решение на двата примера. И това е итерацията (т.е. циклите). И тук идва големият въпрос: Кога да ползваме рекурсия и кога да ползваме итерация ?

Когато алгоритъмът за решаване на даден проблем е рекурсивен, реализирането на рекурсивно решение, може да бъде много по-четливо и елегантно от реализирането на итеративно решение на същия проблем. Понякога дефинирането на еквивалентен итеративен алгоритъм е значително по-трудно и не е лесно да се докаже, че двата алгоритъма са еквивалентни. В определени случаи, чрез използването на рекурсия, можем да постигнем много по-прости, кратки и лесни за разбиране решения. От друга страна, рекурсивните извиквания, може да консумират много повече ресурси и памет. При всяко рекурсивно извикване, в стека се заделя нова памет за аргументите, локалните променливи и връщаните резултати. Рекурсията е мощна програмна техника, но трябва внимателно да преценяваме, преди да я използваме. При неправилна употреба, тя може да доведе до неефективни и трудни за разбиране и поддръжка решения.

А как да създадем рекурсивен метод? Има три основни принципа.

Когато създаваме рекурсивни методи, трябва разбием задачата, която решаваме на подзадачи, за чието решение можем да използваме същия алгоритъм (рекурсивно).
Комбинирането на решенията на всички подзадачи, трябва да води до решение на изходната задача.
При всяко рекурсивно извикване, проблемната област трябва да се ограничава така, че в даден момент да достигнем дъното на рекурсията, т.е. всички подзадачи трябва да се стремят да достигнат дъното на рекурсията.

А сега дойде време и за реализацията на n!.  Написал съм ви няколко члена на редицата. Би трябвало да виждате връзката между тях, ако не, съм ви я извел. Нулата е нашето дъно, тъй като при нея можем да върнем направо резултат.  Ето я и как изглежда разписана на C++.
Намиране на рекурентна зависимост:

0! = 1
1! = 1*1*0!  = 1
2! = 2*1 = 2*1!
3! = 3*2*1 = 3*2!
4! = 4*3*2*1 = 4*3!
5! = 5*4*3*2*1  = 5*4!

n = n*(n-1)!

Реализация:
– Дъно – при n = 0
– C++
double factorial(int n) {
// Дъно на рекурсията
if (n == 0)
return 1;
// Рекурсивно извикване: Методът извиква себе си
else
return n * factorial(n – 1);
}

Сега ви връщам пак малко назад. На примера с числата на Фибоначи. Видяхте, че рекурсията става за решаването им. Но дали тя е най-ефективното решение? Отговорът е: Не. Представете си, че напишем за n =  100. Първо погледнете примера за n=5.
Имаме толкова много повтарящи се изчисления.  За пример само пресмятаме fib(1) близо 5 пъти. Тук имам един въпрос? Сеща ли се някой за начин на оптимизация на тази задача? Да работи пак ефективно чрез рекурсията. Ако не се сещате, ще ви кажа. Един добър начин е пресметнатите числа да се запазват в масив и да не се пресмятат наново числа, които вече са били изпълнени.  Но ще оставя вие да разработите тази реализация. Аз само давам идеи.

И какви изводи можем да си направим накрая за рекурсията?  Ако все още не сте сигурни как работи, избягвайте я. Видяхте колко неефективна може да бъде тя. Търсете итеративни решения. Не е лошо човек да има повече от едно неща за сравнение. Ако постигате желания резултати това не е за сметка на ефективността и паметта, то тогава се чувствайте свободни да използвате рекурсията. Примерът тук..е достатъчно ясен. Благодаря за изслушването!

Въпрос 2:
Динамична памет. Оператори new и delete.

Та успяхме да стигнем  и до втория въпрос.  Представете си една катеричка. А сега да ви демонстрирам действието на операторите new и delete.  В първия случай new намира дом на катеричката, а във втория..без коментар. Това разбира се в кръга на шегата. Мисля, че е най-разумно да започнем от това, какво е това динамична памет (или от английски „хийп“). Хийпът е област за съхранение на данни, която е по-постоянна от стека. Това е един вид дълготрайна памет. Особеност е, че тази памет не се свързва с променливи.  Работи се главно с указатели и се използва обикновено при т.нар. динамични структури от данни.
А какво са динамичните данни?
Това са такива обекти, чиито брой не е известен в момента на проектирането на програмата. Те се създават и рушат по време на изпълнението ѝ. След разрушаването заетата памет се освобождава и може да се използва наново. Така паметта се използва по-ефективно.
Създаването и разрушаването на динамични обекти в C++ се осъществява чрез операторите new и delete. Нека разгледаме сега оператор new. Синтаксисът му е :
new <име_на_тип> [[size]]опц |
new <име_на_тип> (<инициализация>)

size – показва броя на компонентите от тип <име_на_тип>, за който да се задели памет

А семантиката:
Заделя в хийпа
sizeof(<име_на_тип>) байта ако не са зададени size и <инициализация>
sizeof(<име_на_тип>)*size байта, ако е явно указан size
sizeof(<име_на_тип>) ако е специфицирана <инициализация>, която памет се инициализира с нея и връща указател.
Може да разгледате и няколко примери:
int* q = new int(2+5*5); – 4B  памет -> 27 и свързва q  с адреса на паметта.
int* p = new int[10]; – 40B за 10 ел-та и свъзва p с адреса на паметта.
rat* r = new rat; – за обект от тип rat, записва адреса в r, извиква конструктора по default.

Тъй като в тези примери навсякъде се заделя памет нека поговорим и малко за заделянето на памет. То бива два вида. По време на компилация (статично заделяне) и по време на изпълнение на програмата(динамично заделяне).
И да поговорим и малко за променливите.  Период на активност на една променлива се нарича частта от време за изпълнението на програмата, през което променливата е свързана с конкретно място в паметта. Паметта за глобалните променливи се заделя в началото и остава свързана с тях до завършването на изпълнението на програмата. Паметта за локалните променливи се заделя при влизане в локалната област и се освобождава при напускането ѝ. За динамичните обекти тази памет се заделя с помощта на оператор new. Заделената по този начин памет остава свързана със съответната променлива докато не се освободи явно от програмиста.

За това служи и оператор delete.
Синтаксис
delete <указател_към_динам_обект>;
Разрушава обекта, адресиран от указателя, като паметта, която заема този обект, се освобождава.
Ако обектът е обект на клас, то първо се извиква деструкторът и след това се освобождава паметта.
Можете да разгледате и някои примери за използването му. Ето ги:
int* arr = new int[5];
delete [] arr;

Когато трябва да се унищожи единичен обект се използва само delete, а за масив  – delete [].
Операторът се използва само за памет заделена с new.
И последна примерна програма:
Да се напише програма, която създава динамичен масив от естествени числа, след което го извежда.

int main(){
int size; //дължина на масива
do
{
cout << „size of array:“;
cin >> size;
} while (size < 1);
int* arr = new int[size]; // дин. масив arr от size ел-та от тип int
int i;
for(i=0 i<= size-1, i++)
arr[i]=i;
for(i=0 i<= size-1, i++) // извеждане на ел-тите на масива
cout << arr[i] << „ “ ;
cout << endl;
delete [] arr; // освобождаване на заетата памет
return 0;
}