Бағдарламасы бойынша практикум ( пәннің атауы) Тақырып: С++ тілінде массивтерді сұрыптау және іздеуді ұйымдастыру

Жұп-тақ сұрыптау

2.5 Екілік ағаш әдісі арқылы сұрыптау

Ағаш құрылымын жадқа физикалық орналастыру кезінде кем дегенде {\қасиеттері дисплей мәнінің мәні 4Н}{\қасиеттері дисплей мәнінің мәні 4Н} қосымша жад ұяшықтары қажет (әр түйінде бастапқы массив элементіне, ата-ана элементіне, сол және оң жақ параққа сілтемелер болуы керек), алайда қажетті қосымша жадты азайтудың жолдары бар.мәліметтер ағаш = жапырақ | түйін (ағаш)а (ағаш)

кірістіру:: Ord a => a - > ағаш A - > ағаш A

x парағын кірістіру = түйін парағы x парағы

кірістіру x (түйін t y t') / x <= y = түйін (кірістіру x t) y t'

кірістіру x (түйін t y t') | x > y = түйін T y (кірістіру x t')

тегістеу:: ағаш a - > [a]

парақты тегістеу = []

2.6 Бинарлы іздеу алгоритмі
Екілік іздеу реттелген массивте жасалады.
Екілік іздеу кезінде қажетті кілт массивтегі орташа элементтің кілтімен салыстырылады. Егер олар тең болса, онда іздеу сәтті болады. Әйтпесе, іздеу массивтің сол немесе оң жағында да жүзеге асырылады.

Алгоритмді рекурсивті және рекурсивті емес формаларда анықтауға болады.

Екілік іздеуді сегментті екіге бөлу немесе дихотомия әдісі деп те атайды.

Іздеу қадамдарының саны келесідей анықталады

log2n↑,

мұндағы n-элементтер саны,

↑ - ең жақын бүтін санға дейін дөңгелектеу.

Әр қадамда сегменттің ортасын формула бойынша іздеу жүзеге асырылады

mid = (left + right)/2

Егер қалаған элемент mid индексі бар элементке тең болса, іздеу аяқталады.

Егер қажетті элемент mid индексі бар элементтен аз болса, қарастырылып отырған кесіндінің оң шекарасы mid орнына, әйтпесе сол жақ шекара жылжиды.

Екілік іздеу

Дайындау. Іздеуді бастамас бұрын массивтің сол және оң шекараларын орнатыңыз:

left = 0, right = 19

Қадам 1. Біз массивтің ортаңғы индексін іздейміз (төменгі жағына дөңгелектейміз):

mid = (19+0)/2=9

Біз осы индекстегі мәнді қалаған мәнмен салыстырамыз:

69 < 82

left = mid = 9

Қадам 2. Біз массивтің ортаңғы индексін іздейміз (төменгі жағына дөңгелектейміз):

mid = (9+19)/2=14

Біз осы индекстегі мәнді қалаған мәнмен салыстырамыз:

84 > 82

right = mid = 14

Қадам 3. Біз массивтің ортаңғы индексін іздейміз (төменгі жағына дөңгелектейміз):

mid = (9+14)/2=11

Біз осы индекстегі мәнді қалаған мәнмен салыстырамыз:

78 < 82

left = mid = 11

Қадам 4. Біз массивтің ортаңғы индексін іздейміз (төменгі жағына дөңгелектейміз):

mid = (11+14)/2=12

Біз осы индекстегі мәнді қалаған мәнмен салыстырамыз:

80 < 82

left = mid = 12

Қадам 5. Біз массивтің ортаңғы индексін іздейміз (төменгі жағына дөңгелектейміз):

mid = (12+14)/2=13

Біз осы индекстегі мәнді қалаған мәнмен салыстырамыз:

82 = 82

Іздеу қадамдарының санын азайту үшін іздеу шекараларын бірден сегменттің ортасынан кейінгі элементке ауыстыруға болады:

right = mid — 1

# define _crt_secure_no_warnings / / scanf дұрыс жұмыс істеуі үшін()

#include

#include // system()функцияларын пайдалану үшін

int main()

{

int k[20]; / / негізгі кестенің кілттер массиві

int key, i;

system("chcp 1251"); // орыс тілін консольге аудару

system ("cls"); / / консоль терезесін тазалау

// Негізгі өрістерді реттелген мәндермен баптандыру

k[0] = 8; k[1] = 14;

k[2] = 26; k[3] = 28;

k[4] = 38; k[5] = 47;

k[6] = 56; k[7] = 60;

k[8] = 64; k[9] = 69;

k[10] = 70; k[11] = 78;

k[12] = 80; k[13] = 82;

k[14] = 84; k[15] = 87;

k[16] = 90; k[17] = 92;

k[18] = 98; k[19] = 108;

// Жазбаларды енгізу

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

{

printf("%2d. k[%2d]=%3d: r[%2d]= ", i, i, k[i], i);

}

printf ("кілтті енгізіңіз:"); / / қажетті кілт өрісін енгізіңіз

int left = 0; / / іздеудің сол және оң жиектерін орнатыңыз

int right = 19;

int search = -1; / / табылған элемент индексі -1 (элемент табылмады)

while (сол жақ <= оң) / / сол жақ шекара оң жаққа "секіргенше"

{

int mid = (сол + оң) / 2; / / сегменттің ортасын іздеңіз

іздеу = орта; / / біз қажетті элементті таптық,

break; / / циклден шығыңыз

}

егер (key < k[mid]) // егер қажетті кілт өрісі табылған ортадан аз болса

басқа / / басқа

сол жақ = mid + 1; // сол жақ шекараны жылжытамыз, оң жақта іздеуді жалғастырамыз

}

if (search == -1) // егер элемент индексі әлі де -1 болса, элемент табылмады

else / / әйтпесе біз элементті, оның кілті мен мәнін көрсетеміз

printf("%d. key= %d. r[%d]=%d", search, k[search], search, r[search]);

getchar(); getchar();

return 0;

}

int interpolationSearch (a : int[], кілт : int) // a сұрыпталуы керек

сол жақ = 0 // іздеудің сол жақ шекарасы (массив элементтері нөлден нөмірленеді деп санаймыз)

оң жақ = а.ұзындығы-1 / / оң жақ іздеу шекарасы

a [сол жақта] < пернесі және < A пернесі [оң жақта]

ортаңғы = сол жақ + (кілт - a[сол жақта]) * (оң жақта - сол жақта) / (a[оң жақта] - a[сол жақта]) // біз салыстыратын элемент индексі

Егер a [mid] < кілт

сол жақта = mid + 1

әйтпесе, егер a [mid] > кілт

оңға = mid - 1

тағы

ортасында оралу

солға оралу

әйтпесе, егер [оң] == кілт

құқықты қайтарады

тағы

қайтару -1 / / егер массивте мұндай элемент болмаса

2.8 Решето Эратостен іздеу алгоритмі

P айнымалысына 2 мәнін тағайындаңыз (бірінші жай Сан).

P2-ден n-ге дейінгі сандарды p қадамымен алып тастаңыз (бұл p: P2, p2+p, p2+2p және т.б. сандар болады).

Массивтегі алғашқы сәтсіз санды табыңыз, үлкенірек Р, және айнымалы мәнге тағайындаңыз p бұл сан.

Мүмкіндігінше алдыңғы екі қадамды қайталаңыз.

Массивте қалған барлық сандар 2-ден N-ге дейінгі жай сандар

3. Бағдарламалық қамтаманы жүзеге асыру
Компоненттер жиынтығы ретінде c++ қолданумен байланысты мәселелерді түсіну үшін 1980 жылдардың аяғында C++ кітапханаларының қалай таралғанын бақылау пайдалы. O(1) кезінде ішкі жолдарды іздеу алгоритмін жасаған кітапхана жасаушыны елестетіп көріңіз (яғни іздеу уақыты жолдың ұзындығына пропорционалды емес, тұрақты). Бұл тривиалды емес міндет екені белгілі. Пайдаланушы үшін алгоритмді мүмкіндігінше қарапайым ету үшін әзірлеуші кез-келген клиент бағдарламасына мәтіндік жолдарды (fast text strings) жылдам жіберетін алгоритмге негізделген жолдар класын жасауы керек. Мұны істеу үшін әзірлеуші сынып анықтамасын қамтитын тақырып файлын дайындауы керек:

// faststring.h

class FastString

{

char *mpsz;

FastString(const char *psz);

~FastString(void);

int Length(void) const;

// returns # of characters

// таңбалар санын қайтарады

int Find(const char *psz) const;

// returns offset

// офсетті қайтарады

};

Сынып анықталғаннан кейін әзірлеуші оның мүше функцияларын бөлек файлда орындауы керек:

#include «faststring.h»

#include

FastString::FastString(const char *psz) : mpsz(new char [strlen(psz) + 1])

{ strcpy(mpsz, psz); }

FastString::~FastString(void)

{ delete[] mpsz; }

int FastString::Length(void) const

{ return strlen(mpsz); }

int FastString::Find(const char *psz) const

{

//O(1) lookup code deleted for> clarity

// 0(1) іздеу коды түсінікті болу үшін жойылды

C++ кітапханалары дәстүрлі түрде бастапқы код түрінде таратылды. Кітапхана пайдаланушылары Бастапқы файлдардың орындалуын және олар жасаған жүйені қосып, C++компиляторын қолдана отырып, кітапхананың бастапқы файлдарын қайта құрастырады деп күтілді. Егер кітапхана C++ тілінің ең көп қолданылатын нұсқасында жазылған деп болжасақ, онда бұл тәсіл өте тиімді болар еді. Бұл схеманың басты себебі-бұл кітапхананың орындалатын коды Барлық клиенттік қосымшаларға қосылуы керек еді.

3.1 Қолданушыға нұсқаулық

Талап ұғымына анықтама беру

Л.Новиков RUP белгісінің [15] орыс тіліндегі нұсқасында келесідей анықтама береді: «Талап – бұл жүйе қанағаттандыруға тиісті шарт немесе мүмкіндік».

IEEE стандартты Глоссарийде Software Engineering Terminology (1990) [7] бұл ұғым кеңірек түсіндіріледі. Талап мынада:

1. проблемаларды шешу немесе мақсаттарға жету үшін пайдаланушы талап ететін шарттар немесе мүмкіндіктер;

2. келісім-шартты орындау немесе стандарттарға, техникалық шарттарға немесе басқа ресми құжаттарға сәйкес келу үшін жүйенің немесе жүйе құрамдастарының болуы қажет шарттар немесе мүмкіндіктер;

3. 1 және 2 тармақтар үшін шарттар немесе мүмкіндіктердің құжатталған көрінісі (дәйексөздің соңы).

Талаптардың классификациясы

Талаптарды жіктеудің әртүрлі әдістерінің айтарлықтай саны бар, олардың ең маңыздысы лекцияда талқыланады.

Жобаға қойылатын талаптар. Жобаға қойылатын талаптарды тұжырымдау мәселелері, яғни. Әзірлеуші мақсатты жүйені құру бойынша жұмысты қалай орындайтыны Тапсырыс берушінің құзыретіне кірмейтін сияқты. Барлық жобалар әрқашан дәл және уақытында орындалса, Тапсырыс беруші процесті реттемей-ақ істеу оңай болар еді. Алайда, өкінішке орай, бағдарламалық жобалардың нәтижелерінің әлемдік статистикасы басқаша айтады. Тапсырыс беруші Әзірлеушімен шарттық қарым-қатынасқа түсе отырып, әр түрлі тәуекелдерді көтереді, олардың негізгісі өнімді кешіктіру немесе сапасыз алу қаупі болып табылады. Тәуекелді бақылау және азайтудың негізгі шаралары бағдарламалық қамтамасыз етуді құру процесін реттеу және оның аудиті болып табылады.

Тапсырыс беруші жобаға қойылатын талаптарды қаншалықты егжей-тегжейлі реттеуі керек - бұл риторикалық сұрақ. Оған жауап көптеген факторларға байланысты, мысалы, Тапсырыс беруші үшін түпкілікті өнімнің құны, Тапсырыс берушінің Әзірлеушіге деген сенімінің дәрежесі, қол қойылған келісім-шарт сомасы, өнімді пайдалануға беру мерзімін Тапсырыс берушімен байланыстыру. бизнес-жоспарлар және т.б. Дегенмен, толық сенімділікпен мынаны айта аламыз: 1) Тапсырыс берушінің процесті реттеуі оның тәуекелдерін азайтуға мүмкіндік береді; 2) Тапсырыс берушінің процесті реттеу шаралары қосымша үстеме шығындарға әкеледі. Тәуекелді бақылау дәрежесі мен шығындар сомасы арасында ақылға қонымды ымыраға келу талап етіледі.

3.2 Тестілеу нәтижелері

Бақытымызға орай, адамзат бұрыннан күрделі объектілерді модельдеуде кеңінен қолданылатын күрделілікпен күресу әдістерін ойлап тапты - абстракция және декомпозиция. Бағдарламалық жүйелерге қойылатын талаптарды талдау пәніне қолданылғанда бұл принциптер келесідей жұмыс істейді. Талаптар деңгейлерге бөлінеді. Талаптардың деңгейлері, бір жағынан, жүйенің абстракциялық деңгейімен, екінші жағынан, кәсіпорындағы басқару деңгейімен байланысты.

Жалпы талаптардың үш деңгейі бар.

Жоғарғы деңгейде бизнес талаптары деп аталады. Іскерлік талаптардың мысалдары: жүйе кәсіпорында өңделген тапсырыстарды орындау уақытын үш есе қысқарту керек. Іскерлік талаптарды әдетте кәсіпорынның топ-менеджерлері немесе акционерлері тұжырымдайды.

Келесі деңгей - пайдаланушы талаптарының деңгейі. Пайдаланушы талабының мысалы: жүйе тапсырыс туралы жан-жақты ақпаратты енгізу үшін интерактивті құралдарды қамтамасыз етуі керек, содан кейін мәліметтер базасында ақпаратты бекіту және тапсырыс туралы ақпаратты оны жоспарлауға және орындауға жауапты қызметкерге бағыттау керек. Пайдаланушы талаптары көбінесе нашар құрылымдалған, қайталанатын және қарама-қайшы. Сондықтан жүйені құру үшін талаптарды ресімдеу жүзеге асырылатын үшінші деңгей маңызды.

Үшінші деңгей – функционалдық (функционалдық талаптар). Электрондық тапсырыспен жұмыс істеуге арналған функционалдық талаптардың мысалы: тапсырысты жасауға, өңдеуге, жоюға және сайттан сайтқа жылжытуға болады.

Әртүрлі деңгейдегі талаптар арасында объективті қарама-қайшылықтар бар. Осылайша, бизнестің айқын талабы – пайдаланушылардың жұмыс орындарында бірыңғай дерекқорға жиналған ақпараттың толықтығына қойылатын талап. Ақпарат неғұрлым толық болса, әрекетті талдау және шешім қабылдау үшін негіз соғұрлым терең болады. Екінші жағынан, жүйенің белгілі бір пайдаланушысы үшін оның негізгі функцияларының орындалуына әсер ететін ақпараттың бір бөлігін ғана пайдалану жеткілікті болуы мүмкін.

Кәсіпорында ААЖ енгізу және пайдаланудың маңызды ережелері «Бір жинау нүктесі», «Деректер пайда болған жерде жиналады». Осы ережелерді пайдалану ақпаратты негізсіз қайталау шығындарын және одан да маңыздысы, кіріс нүктелерін қайталау кезінде сөзсіз туындайтын бухгалтерлік қателерден шығындарды болдырмауға мүмкіндік береді.

Кәсіпорында ААЖ енгізу барлық ақпаратты енгізу пункттерін автоматтандырылған жұмыс станцияларымен (ААЖ) жабдықтау, персоналды оқыту және көбінесе персонал орындайтын жұмыс процестерін ресімдеу деңгейін оңтайландыру және арттыру қажеттілігіне әкеледі. Сондықтан, AIS енгізу оңай процесс емес, көбінесе «адам материалын қайта құруды» және дайын емес немесе жаңа әдіспен жұмыс істегісі келмейтін пайдаланушылардың қарсылығын қанағаттандыруды талап етеді.

Қорытынды

 Сыртқы интерфейстер (Сыртқы интерфейстер),

 Сапа атрибуттары,

 Шектеулер.

Көптеген заманауи AIS-тегі сыртқы интерфейстердің ішінде ең маңыздысы пайдаланушы интерфейсі (User Interface, UI). Сонымен қатар, сыртқы құрылғылармен интерфейстер (аппараттық интерфейстер), бағдарламалық интерфейстер және ақпаратты беру интерфейстері (коммуникациялық интерфейстер) ерекшеленеді.

Сапаның негізгі белгілері:

 Қолдану мүмкіндігі,

 Сенімділік,

 Өнімділік,

 қызмет көрсету қабілеттілігі,

FURPS үлгісінде өте жақсы ашылған (төменде қараңыз).

Шектеулер - талаптарды немесе талаптар жиынтығын өзгертетін, оларды жүзеге асырудың мүмкін шешімдерін таңдауды тарылтатын шарттар тұжырымдары. іске асыруды және/немесе орналастыру платформасын таңдау (хаттамалар, қолданбалы серверлер, дерекқорлар, ...), бұл өз кезегінде, мысалы, сыртқы интерфейстерге қатысты болуы мүмкін (дәйексөздің соңы).

Сондай-ақ бұл тұжырымдаманың2 жалпы көрінісі бар: «мүмкіндіктер функционалды немесе функционалды емес талаптарға қатысты болуы мүмкін және өнімнің нұсқасынан нұсқасына өзгеруі мүмкін».

С.Өрли еңбегінде «Талаптарды инженерия тұрғысынан алғанда ерекшеліктер функционалдық талаптармен де, функционалдық еместермен де корреляциялануы мүмкін тәуелсіз артефакт болып табылады» деп атап көрсетеді.

Сипаттамалардың рөлі ең алдымен маркетинг саласында көрінеді: өнімнің әрбір әлеуетті тұтынушысы оның функционалдық сипаттамаларын оқи бермейді, ал бәсекелестік артықшылықтарды сипаттайтын негізгі сипаттамалардың жиынтығы қысқаша және флайердің бір бетіне сәйкес келуі мүмкін немесе ықшам дискіде басып шығарылады.

Қолданылған әдебитеттер тізімі

1. Макарова Н.В. Информатика: Оқулық. – М.: Қаржы және статистика, 2012. – 768 б.

2. ERP жүйелері. Қазіргі жоспарлау және кәсіпорын ресурстарын басқару. Таңдау, іске асыру, пайдалану / Дэниел О'Лири; [Транс. ағылшын тілінен. Ю.И.Водопянова].

3. Меняев М.Ф. Басқарудың ақпараттық технологиялары: Оқулық: 3 кітапта: 3-кітап: Ұйымды басқару жүйелері. – М.: Омега-Л, 2010. – 464 б.

4. Автоматтандырылған ақпараттық жүйелер, мәліметтер базасы және деректер банкі. Кіріспе курс: Оқу құралы. - М.: Гелиос АРВ, 2011. - 368 б., сырқат.

5. Б.Н. Гайфуллин, И.А. Обухов. ERP/MRPII стандартының кәсіпорынды басқарудың автоматтандырылған жүйелері. Өндірістік басылым. – М.

«Богородский принтері», 2012, 104 б.

6. Петров В.Н. Ақпараттық жүйелер. – Петербург: Петр, 2010. – 688 б.

7. IEEE стандартты глоссарий бағдарламалық қамтамасыз ету инженериясы терминологиясы/IEEE Std 610.12

8. Vigers Carl Бағдарламалық қамтамасыз ету талаптарын әзірлеу / Per, ағылшын тілінен. —

М .: «Орыс редакциясы» баспасы және сауда үйі, 2010. -576б.: ауру.

9. Леффингвелл Д., Видриг Д. Бағдарламалық қамтамасыз ету талаптарымен жұмыс істеу принциптері. М.: ID «Уильямс», 2002 ж.

10. Алистер Коберн. Жүйеге қойылатын функционалдық талаптарды сипаттаудың заманауи әдістері. М.: «Лори» баспасы, 2012. – 263 б.

11. Мацяшек Лешек. Талаптарды талдау және жүйелерді жобалау. Ақпаратты дамыту: Диалектика-Вильямспен

12. Орлик С., Булуй Ю. Бағдарламалық қамтамасыз ету инженериясына кіріспе және бағдарламалық қамтамасыз етудің өмірлік циклін басқару Бағдарламалық жасақтама инженериясы. Бағдарламалық қамтамасыз ету талаптары. Авторлық құқық © Сергей Орлик, 2004-2005.

http://www.sorlik.ru/swebok/3-1-software_engineering_requirements.pdf

13. Л.Новиков. Рационалды біртұтас процесске кіріспе.

http://www.interface.ru/rational/interface/151199/rup/main.htm

14. MSF ақ беттері.http://www.microsoft.com/rus/msdn/msf

15. Талаптарды талдау және Microsoft .Net шешім архитектурасын анықтау 2011 491

бет Microsoft Press.