Anˆptuxh K dika se Antikeimenostrafèc Peribˆllon ProgrammatismoÔ - PDF

Description
Anˆptuxh K dika se Antikeimenostrafèc Peribˆllon ProgrammatismoÔ NÐkoc Pojhtìc 8/5/ Anˆptuxh K dika se Antikeimenostrafèc Peribˆllon ProgrammatismoÔ Oi antikeimenostrafeðc gl ssec

Please download to get full document.

View again

of 40
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Nature & Wildlife

Publish on:

Views: 18 | Pages: 40

Extension: PDF | Download: 0

Share
Transcript
Anˆptuxh K dika se Antikeimenostrafèc Peribˆllon ProgrammatismoÔ NÐkoc Pojhtìc 8/5/ Anˆptuxh K dika se Antikeimenostrafèc Peribˆllon ProgrammatismoÔ Oi antikeimenostrafeðc gl ssec programmatismoô dieukolônoun sthn kalôterh orgˆnwsh tou k dika. Sth C++ mporoôme na sqediˆzoume me antikeimenostraf trìpo apodotikèc efarmogèc. Gia na grˆyoume k dika C++ pou epilôei èna sugkekrimèno prìblhma, qreiˆzetai prohgoumènwc na doôme prosektikˆ thn perigraf tou probl matoc autoô. Ja prèpei na diakrðnoume tic ontìthtec pou upˆrqoun sto prìblhma, tic idiìthtèc touc kai tic metaxô touc sqèseic. Ja skeftoôme epðshc touc algorðjmouc epðlushc tou probl matoc. SÔsthma Katˆrtishc WrologÐou Progrˆmmatoc S mera, ta megˆla probl mata qronoprogrammatismoô epilôontai me th bo jeia upologist. Tètoia probl mata eðnai p.q. oi bˆrdiec tou proswpikoô miac aeroporik c etaireðac, o kajorismìc hmeromhni n gia tic epaggelmatikèc sunant seic, to wrolìgio prìgramma enìc ekpaideutikoô idrômatoc k.ˆ. O bèltistoc qronoprogrammatismìc kai h apodotik katˆrtish wrologðwn programmˆtwn eðnai èna prìblhma (kai) thc Teqnht c NohmosÔnhc. Ektìc apì efarmogèc pou epilôoun tètoia probl mata, èqoun anaptuqjeð kai arketèc, emporikèc kurðwc, biblioj kec epðlushc. 3 Perigraf tou probl matoc Gia arq, ja asqolhjoôme me mða apl ekdoq tou probl matoc katˆrtishc wrologðou progrˆmmatoc: 'Estw ìti mac èqei anatejeð h dhmiourgða tou wrologðou progrˆmmatoc gia èna gumnˆsio. To prìgramma aforˆ mìno mða hmèra thc ebdomˆdac. GnwrÐzoume poiec tˆxeic kalôtera poia tm mata upˆrqoun sto sqoleðo autì. Se kˆje tˆxh didˆskontai sugkekrimèna maj mata apì ènan/mða didˆskonta/ousa to kajèna. Kˆje mˆjhma diarkeð mða ra. Perigraf tou probl matoc: Sqìlia H parapˆnw perigraf eðnai sqetikˆ saf c. Wstìso den anafèrontai se aut n kˆpoiec profaneðc parˆmetroi tou pragmatikoô kìsmou pou ja prèpei na lhfjoôn upìyh katˆ th montelopoðhsh tou probl matoc. P.q. ènac kajhght c den mporeð na brðsketai tautìqrona se dôo aðjousec. Akìma, se mða tˆxh den mporoôn na gðnontai tautìqrona dôo diaforetikˆ maj mata! 5 Anadromikìc algìrijmoc epðlushc se yeudok dika Schedule(l, nlesson) if l == nlesson return true // epituqða for h = 0 to nhours 1 if o kajhght c kai h aðjousa tou maj matoc eðnai diajèsima thn ra h Dèsmeuse ton kajhght kai thn aðjousa gia thn h. Programmˆtise to l na gðnetai thn h. if Schedule(l + 1, nlesson) == true return true AkÔrwse thn anˆjesh thc h gia to l. AkÔrwse th dèsmeush kajhght kai aðjousac. return false // apotuqða eôreshc rac gia to mˆjhma l Aplìc Diadikastikìc Programmatismìc Sth sunèqeia parousiˆzetai to arqeðo k dika only main.cpp, to opoðo kˆje ˆllo parˆ to drìmo thc antikeimenostrafoôc montelopoðhshc akoloujeð. GÐnetai apìpeira na strimwqtoôn mèsa se mða main() ìlec oi ontìthtec tou probl matoc. O k dikac autìc ja mporoôse kˆllista na grafeð kai me apl C. 7 only main.cpp (1/6) #include iostream #include string using namespace std; // A constant for declaring an empty hour for a classroom const int EMPTY = -1; // How many hours exist in a day const int nhours = 3; inline bool solve_rec (int course_room[], int course_prof[], int course_hour[], int ncourse, bool room_unavail[][nhours], bool prof_unavail[][nhours]); only main.cpp (2/6) int main (void) // The following names could be used for printing // the timetable on the screen. string room_name[] = C1 , C2 ; string prof_name[] = Einstein , Godel , Eco ; string course_name[] = Physics , Physics , Maths , Maths , Philosophy , Philosophy , Literature ; // Availabilities of our resources bool room_unavail[][nhours] = false, false, false, false, false, false ; bool prof_unavail[][nhours] = false, false, false, false, false, false, false, false, false ; 9 only main.cpp (3/6) // Indexes of the corresponding classroom and professor // for each course, and the hour it is scheduled at // (currently EMPTY). int course_room[] = 0, 1, 0, 1, 0, 1, 0; int course_prof[] = 0, 0, 1, 1, 2, 2, 2; int course_hour[] = EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY; // If we change ncourse to 7, the scheduler // will not find any solution. int ncourse = 6; if (solve_rec(course_room,course_prof,course_hour,ncourse, room_unavail,prof_unavail) == true) cout Found a solution\n ; else cout Couldn t find a solution\n ; only main.cpp (4/6) bool solve_rec_body (int course_room[], int course_prof[], int course_hour[], int curr_course, int ncourse, bool room_unavail[][nhours], bool prof_unavail[][nhours]) // Renaming (for better readability) int l = curr_course; // Check if all the courses have been scheduled if (l == ncourse) return true; for (int h=0; h nhours; ++h) if (!room_unavail[course_room[l]][h] &&!prof_unavail[course_prof[l]][h] ) // Assign resources and hour room_unavail[course_room[l]][h] = true; prof_unavail[course_prof[l]][h] = true; course_hour[l] = h; 11 only main.cpp (5/6) // Continue with scheduling the next course if (solve_rec_body(course_room,course_prof,course_hour, l+1,ncourse,room_unavail,prof_unavail) == true) return true; // Free resources room_unavail[course_room[l]][h] = false; prof_unavail[course_prof[l]][h] = false; course_hour[l] = EMPTY; // Couldn t find an hour, for course l return false; only main.cpp (6/6) inline bool solve_rec (int course_room[], int course_prof[], int course_hour[], int ncourse, bool room_unavail[][nhours], bool prof_unavail[][nhours]) return solve_rec_body(course_room,course_prof,course_hour, 0,ncourse,room_unavail,prof_unavail); 13 only main.cpp: Apotelèsmata % g++ -o only_main only_main.cpp %./only_main Found a solution % Gia aplìthta, to only main.cpp den ektup nei to wrolìgio prìgramma; anafèrei mìno an upˆrqei kˆpoia lôsh sto prìblhma. ParathroÔme ìti qwrðc th qr sh klˆsewn den eðnai xekˆjaro to poiec eðnai telikˆ oi ontìthtec tou probl matoc. Upˆrqei mða isopèdwsh twn dedomènwn, afoô h anaparˆstas touc peristrèfetai gôrw apì touc algorðjmouc mìno. Antikeimenostraf c MontelopoÐhsh (1/2) Gia na proqwr soume sthn antikeimenostraf montelopoðhsh, ja prèpei na entopðsoume tic ontìthtec tou probl matoc, kaj c kai tic metaxô touc sqèseic. 'Oson aforˆ to prìblhmˆ mac, ja dhmiourg soume mða klˆsh gia ta maj mata, mða gia touc kajhghtèc kai ˆllh mða gia tic tˆxeic. Kˆje mˆjhma perièqei anaforˆ (reference) ston/sthn kajhght /tria pou to didˆskei kai sthn tˆxh sthn opoða ja gðnei. 15 Antikeimenostraf c MontelopoÐhsh (2/2) Ston qronoprogrammatismì, ènac pìroc (resource) eðnai kˆti to opoðo anˆ pìsa qronik stigm mporeð na anatejeð se to polô mða drasthriìthta. 'Enac kajhght c mporeð na jewrhjeð ìti eðnai-ènac (is-a) pìroc: kajemða ra mporeð na didˆskei èna mìno mˆjhma. 'Omoia, se mða aðjousa mporeð na lambˆnei q ra èna to polô mˆjhma thn ra, opìte kai h aðjousa klhronomeð tic idiìthtec enìc pìrou CResource is-a is-a CClassroom CProfessor 'Oson aforˆ ton algìrijmo epðlushc, mporoôme na ulopoi soume dôo enallaktikèc teqnikèc anaz thshc: a) me anadrom (èmmesh qr sh stoðbac) kai b) me emfan qr sh stoðbac. timetable.h (1/8) #ifndef TIMETABLE_H #define TIMETABLE_H #include string #include iostream namespace timetable class CResource private: bool *slot; int nhours; // slot[h]==true means that the resource is unavailable at // hour h. The length of the array slot is nhours. 17 timetable.h (2/8) public: CResource (int nhours_init) : nhours(nhours_init) slot = new bool[nhours]; for (int h=0; h nhours; ++h) slot[h] = false; // initially the resource is always available ~CResource (void) delete [] slot; timetable.h (3/8) void reserve (int hour) slot[hour] = true; void release (int hour) slot[hour] = false; ; bool is_free (int hour) const return (!slot[hour] ); 19 timetable.h (4/8) class CClassroom : public CResource private: const int id; static int count; std::string name; public: CClassroom (std::string name_init, int nhours_init) : CResource(nhours_init), id(++count), name(name_init) friend std::ostream& operator (std::ostream& os, const CClassroom& room); ; int get_id (void) const return id; timetable.h (5/8) class CProfessor : public CResource private: const int id; static int count; std::string name; public: CProfessor (std::string name_init, int nhours_init) : CResource(nhours_init), id(++count), name(name_init) friend std::ostream& operator (std::ostream& os, const CProfessor& prof); ; int get_id (void) const return id; 21 timetable.h (6/8) class CCourse private: std::string name; int hour_scheduled; static const int EMPTY = -1; // hour_scheduled==empty means that // the course has not been scheduled. CClassroom& classroom; CProfessor& professor; public: CCourse (std::string name_init, CClassroom& cl_init, CProfessor& pr_init) : name(name_init), hour_scheduled(empty), classroom(cl_init), professor(pr_init) friend std::ostream& operator (std::ostream& os, const CCourse& les); 23 timetable.h (7/8) CClassroom& get_class (void) const return classroom; CProfessor& get_prof (void) const return professor; int get_hour (void) const return hour_scheduled; bool schedule (int hour) if (classroom.is_free(hour) && professor.is_free(hour)) classroom.reserve(hour); professor.reserve(hour); hour_scheduled = hour; return true; else return false; timetable.h (8/8) ; void cancel_schedule (void) classroom.release(hour_scheduled); professor.release(hour_scheduled); hour_scheduled = EMPTY; bool solve_rec (CCourse course[], int ncourse, int nhours); void print_timetable (CCourse course[], int ncourse, CClassroom room[], int nroom, int nhours); // end namespace #endif // TIMETABLE_H timetable.cpp (1/6) #include timetable.h using namespace timetable; using namespace std; // Initializations of the counters of the instances // of the classes int CClassroom::count = 0; int CProfessor::count = 0; 25 timetable.cpp (2/6) // Overloaded operators for printing ostream& timetable::operator (ostream& os, const CClassroom& room) os room.name; return os; ostream& timetable::operator (ostream& os, const CProfessor& prof) os prof.name; return os; ostream& timetable::operator (ostream& os, const CCourse& c) os c.name; return os; 27 timetable.cpp (3/6) namespace bool solve_rec_body (CCourse course[], int ncourse, int curr_course, int nhours) if (curr_course == ncourse) return true; // success: every course has been scheduled // variable renaming (for readability) CCourse& c = course[curr_course]; for (int h=0; h nhours; ++h) if (c.schedule(h) == true) if (solve_rec_body(course,ncourse, curr_course+1,nhours) == true) return true; c.cancel_schedule(); return false; // failed to find an appropriate hour // end namespace timetable.cpp (4/6) // Recursive search for a solution (timetable) bool timetable::solve_rec (CCourse course[], int ncourse, int nhours) return solve_rec_body(course,ncourse,0,nhours); #include iostream #include iomanip 29 timetable.cpp (5/6) namespace // Serial search for the course scheduled to take place // in room room at hour hour int search_course (CCourse course[], int ncourse, CClassroom& room, int hour) for (int c=0; c ncourse; ++c) if (course[c].get_class().get_id() == room.get_id() && course[c].get_hour() == hour) return c; return -1; inline void print_bar (int columns) for (int i=0; i columns; ++i) cout ; cout +\n ; // end namespace timetable.cpp (6/6) void timetable::print_timetable (CCourse course[], int ncourse, CClassroom room[], int nroom, int nhours) int h, r, c; print_bar(nroom); for (r=0; r nroom; ++r) cout ; cout setiosflags(ios::left) setw(10) room[r] ; cout \n ; print_bar(nroom); for (h=0; h nhours; ++h) for (r=0; r nroom; ++r) c = search_course(course,ncourse,room[r],h); cout ; cout setiosflags(ios::left) setw(10) course[c] ; cout \n ; print_bar(nroom); 31 main.cpp (1/2) #include timetable.h using namespace timetable; #include iostream using namespace std; int main (void) int nhours = 3; // hours of the timetable CClassroom room[] = CClassroom( C1 , nhours), CClassroom( C2 , nhours) ; CProfessor prof[] = CProfessor( Einstein , nhours), CProfessor( Godel , nhours), CProfessor( Eco , nhours) ; CCourse course[] = CCourse( Physics , room[0], prof[0]), CCourse( Physics , room[1], prof[0]), CCourse( Maths , room[0], prof[1]), CCourse( Maths , room[1], prof[1]), CCourse( Philosophy , room[0], prof[2]), CCourse( Philosophy , room[1], prof[2]), CCourse( Literature , room[0], prof[2]) ; main.cpp (2/2) cout First case, with 6 courses:\n ; if (solve_rec(course,6,nhours) == true) cout Found a solution\n\n ; print_timetable(course, 6, room, 2, nhours); else cout Couldn t find a solution\n ; //cout Second case, with 7 courses:\n ; //if (solve_rec(course,7,nhours) == true) // cout Found a solution\n\n ; // print_timetable(course, 7, room, 2, nhours); // else // cout Couldn t find a solution\n ; // Apotelèsmata % g++ -o timetable timetable.cpp main.cpp %./timetable First case, with 6 courses: Found a solution C1 C Physics Philosophy Maths Physics Philosophy Maths % ShmeÐwsh: An metaglwttisteð o k dikac sta mhqan mata Sun tou Tm matoc me thn prokajorismènh èkdosh tou g++, ta apotelèsmata ja emfanistoôn kanonikˆ, allˆ qwrðc stoðqish. An qrhsimopoi soume thn pio kainoôrgia èkdosh tou g++, den ja upˆrqei autì to prìblhma. To mìno pou qreiˆzetai gia na gðnei autì, eðnai na trèxoume, prin tic entolèc tou parapˆnw plaisðou, thn entol alias g++ /usr/sfw/bin/g++ 33 Anaz thsh lôshc me stoðba An antð thc sunˆrthshc solve rec() (anaz thsh me anadrom ), qrhsimopoi soume thn solve with stack() (anaz thsh me emfan qr sh stoðbac) tou solve stack.h, ja pˆroume ta Ðdia akrib c apotelèsmata. Exˆllou, oi dôo autèc sunart seic ulopoioôn ton Ðdio algìrijmo, pou lègetai anaz thsh lôshc me opisjodrìmhsh (backtracking). solve stack.h #ifndef SOLVE_STACK_H #define SOLVE_STACK_H #include timetable.h namespace timetable bool solve_with_stack (CCourse course[], int ncourse, int nhours); // end namespace #endif // SOLVE_STACK_H 35 solve stack.cpp (1/3) #include solve_stack.h using namespace timetable; #include my_stack.h bool timetable::solve_with_stack(ccourse course[],int ncourse,int nhours) my_stack stack_choices; solve stack.cpp (2/3) int c=0, h=0; while (c ncourse) while (h nhours) if (course[c].schedule(h) == true) // Course No c has been scheduled at hour h stack_choices.push(h); ++c; h = 0; break; else ++h; if (h == 0) continue; // Search for course No c failed if (c == 0) return false; 37 solve stack.cpp (3/3) // Canceling previous assignment for course No c-1 --c; course[c].cancel_schedule(); h = stack_choices.top() + 1; // proceed to the next hour stack_choices.pop(); return true; // success: every course has been scheduled Ulopoi seic stoðbac 'Eqoume treic enallaktikèc ulopoi seic tou tôpou dedomènwn stoðba: 1. Sta arqeða my stack.h kai my stack.cpp ulopoieðtai mða apl stoðba akeraðwn (klˆsh my stack). 2. Sto arqeðo my stack templ.h ulopoieðtai mða template stoðba (klˆsh my stack templ), dhlad mða stoðba thc opoðac o tôpoc twn stoiqeðwn mporeð na eðnai o opoiosd pote opìte mporeð na eðnai mða stoðba akeraðwn, mia stoðba sumboloseir n, mia stoðba stoib n k.o.k. 3. Tèloc upˆrqei h ètoimh lôsh thc STL (klˆsh stack tou om numou arqeðou epikefalðdac thc prìtuphc biblioj khc). 39 my stack.h (1/2) #ifndef MY_STACK_H #define MY_STACK_H class my_stack private: struct stacknode int thedata; struct stacknode ; *next; stacknode *stack; public: my_stack (void) : stack(0) my stack.h (2/2) ~my_stack (void) while (stack!= 0) pop(); int top (void) const return stack- thedata; ; void void pop (void); push (int newdata); #endif // MY_STACK_H 41 my stack.cpp #include my_stack.h void my_stack::pop (void) stacknode *current = stack; stack = current- next; delete current; void my_stack::push (int newdata) stacknode *newnode = new stacknode; newnode- thedata = newdata; newnode- next = stack; stack = newnode; my stack templ.h (1/3) #ifndef MY_STACK_TEMPL_H #define MY_STACK_TEMPL_H template class TemplType class my_stack_templ private: struct stacknode TemplType thedata; struct stacknode *next; ; stacknode *stack; public: my_stack_templ (void) : stack(0) 43 my stack templ.h (2/3) ~my_stack_templ (void) while (stack!= 0) pop(); TemplType& return top (void) stack- thedata; ; void void pop (void); push (TemplType& newdata); my stack templ.h (3/3) template class TemplType void my_stack_templ templtype ::pop (void) stacknode *current = stack; stack = current- next; delete current; template class TemplType void my_stack_templ templtype ::push (TemplType& newdata) stacknode *newnode = new stacknode; newnode- thedata = newdata; newnode- next = stack; stack = newnode; #endif // MY_STACK_TEMPL_H 45 Ulopoi seic stoðbac: Sqìlia (1/2) To s ma mðac template sunˆrthshc mporeð na orisjeð kai se èna arqeðo epikefalðdac. O lìgoc eðnai ìti o metaglwttist c qreiˆzetai na gnwrðzei ìqi mìno th d lwsh, allˆ kai ton orismì miac tètoiac sunˆrthshc, gia na ftiˆqnei kˆje forˆ diaforetikèc ekdìseic thc (se gl ssa mhqan c), anˆloga me ton tôpo dedomènwn gia ton opoðo kaleðtai. MporoÔme na orðzoume domèc (p.q. thn struct stacknode) akìma kai ˆllec klˆseic entìc enìc orismoô miac klˆshc. Autì gðnetai gia thn kalôterh orgˆnwsh tou k dika, dhlad gia na dhl netai kai na orðzetai kajetð sto epðpedo pou qreiˆzetai kai gia na mhn upˆrqei (aqreðasth) kajolik prìsbash sthn opoiad pote d lwsh. Ulopoi seic stoðbac: Sqìlia (2/2) AntÐjeta apì thn my stack::top(), h my stack templ::top() epistrèfei anaforˆ (reference) sto antikeðmeno pou brðsketai sthn koruf thc stoðbac. O lìgoc pou gðnetai autì eðnai gia na mhn kaleðtai o copy-constructor tou tôpou dedomènwn pou perièqetai sth stoðba. Gia thn klˆsh my stack den upˆrqei antðstoiqo prìblhma, afoô gnwrðzoume ek twn protèrwn ìti o tôpoc dedomènwn pou perièqetai se aut n th stoðba eðnai akèraioc (int). H anˆjesh enìc akeraðou se ènan ˆllo eðnai profan c mða prˆxh pou den kostðzei. 47 Nèa perigraf probl matoc (me perissìtera zhtoômena) Se autì to shmeðo, ja kˆnoume allagèc kai prosj kec ston k dika pou èqei dh parousiasjeð, ètsi ste metaxô twn ˆllwn na kalufjoôn kai ta ex c zhtoômena: Katˆrtish wrologðou progrˆmmatoc gia ebdomˆda. 'Ena mˆjhma t ra ja mporeð na apoteleðtai apì pollèc paradìseic. DÔo paradìseic tou idðou maj matoc den mporoôn na gðnontai thn Ðdia hmèra. Kˆje parˆdosh èqei sugkekrimènh diˆrkeia se rec. Apomìnwsh twn ontot twn ekeðnwn pou aforoôn kajarˆ to algorijmikì kommˆti thc katˆrtishc wrologðou progrˆmmatoc. Parakˆtw ja doôme p c ja antimetwpðsoume autì to zhtoômeno, anaforikˆ me thn klˆsh gia touc kajhghtèc/riec. Apomìnwsh klˆsewn wrologðou progrˆmmatoc (1/2) H klˆsh CProfessor analôetai se CProfessor kai CProfessorSched. Sth CProfessorSched perièqontai ta gnwrðsmata ekeðna enìc kajhght, pou qreiˆzetai na xèrei èna sôsthma katˆrtishc wrologðou progrˆmmatoc ìpwc to qarakthristikì MaxHoursPerDay, pou eðnai oi rec anˆ hmèra pou mporeð to polô na kˆnei mˆjhma ènac kajhght c. 1 Apì thn ˆllh, sth CProfessor (h opoða klhronomeð ta qarakthristikˆ thc CProfessorSched) perièqontai gnwrðsmata enìc kajhght ìpwc to ìnomˆ tou, pou den eðnai aparaðthto na ta xèrei ènac algìrijmoc katˆrtishc wrologðou progrˆmmatoc. 1 P.q. sth main() pou akoloujeð orðzetai ìti o Einstein mporeð na didˆxei 49 to polô 2 rec/hmèra, lìgw p.q. sômbashc. Apomìnwsh klˆsewn wrologðou progrˆmmatoc (2/2) AfoÔ analôsame thn arqik klˆsh, se CProfessor kai CProfessorSched, gðnetai t ra na proqwrˆme se allagèc sthn ulopoðhsh thc CProfessorSched, qwrðc na mac end
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks