Description
1. Some online mapping software has the capability of presenting street maps with certain landmarks (e.g., hotels, restaurants, etc.) displayed. All landmarks have a name. All types of landmarks have a distinctive icon. Most types of landmarks are displayed with a yellow colored icon, but a few are some other color. Declare and implement the classes named in the sample program below in such a way that the program compiles, executes, and produces exactly the output shown. (Real mapping software would have snazzy graphics, but for now we’ll stick to simple text output.)
You must not change the implementations of displayor main. #include #include usingnamespacestd; Yourdeclarationsandimplementationswouldgohere voiddisplay(constLandmark*lm) { cout<<“Displaya”<color()<<“”<icon()<<“iconfor” <name()<<“.”<<endl; } intmain() { Landmark*landmarks[4]; landmarks[0]=newHotel(“WestwoodRestGood”); //Restaurantshaveanameandseatingcapacity. Restaurantswitha //capacityunder40haveasmallknife/forkicon;thosewithacapacity //40oroverhavealargeknife/forkicon. landmarks[1]=newRestaurant(“BruinBite”,30); landmarks[2]=newRestaurant(“LaMorsuredel’Ours”,100); landmarks[3]=newHospital(“UCLAMedicalCenter”); cout<<“Herearethelandmarks.”<<endl; for(intk=0;k<4;k++) display(landmarks[k]); //Cleanupthelandmarksbeforeexiting cout<<“Cleaningup.”<<endl;
for(intk=0;k<4;k++) deletelandmarks[k]; } Output produced: Herearethelandmarks. DisplayayellowbediconforWestwoodRestGood. Displayayellowsmallknife/forkiconforBruinBite. Displayayellowlargeknife/forkiconforLaMorsuredel’Ours. DisplayablueHiconforUCLAMedicalCenter. Cleaningup. DestroyingthehotelWestwoodRestGood. DestroyingtherestaurantBruinBite. DestroyingtherestaurantLaMorsuredel’Ours. DestroyingthehospitalUCLAMedicalCenter.
Decide which function(s) should be pure virtual, which should be non-pure virtual, and which could be non-virtual. Experiment to see what output is produced if you mistakenly make a function non-virtual when it should be virtual instead. To force you to explore the issues we want you to, we’ll put some constraints on your solution: You must not declare any struct or class other than Landmark, Hotel, Restaurant, and Hospital.
The Landmark class must not have a default constructor. The only constructor you may declare for Landmark must have exactly one parameter. That parameter must be of a builtin type or of type string, and it must be a useful parameter. Although the expression newRestaurant(“BruinBite”,30)is fine, the expression newLandmark(“LaPicaduradelOso”)and new Landmark(0)must produce compilation errors. (A client can create a particular kind of landmark object, like a Restaurant, but is not allowed to create an object that is just a plain Landmark.)
Other than constructors and destructors (which can’t be const), all member functions must be const member functions. No two functions with non-empty bodies may have implementations that have the same effect for a caller. For example, there’s a better way to deal with the name()function than to have each kind of landmark declare and identically implement a name function. (Notice that {return”yellow”;}and {string s(“yell”);returns+”ow”;}have the same effect. And notice that {cout <<“shoppingcart”;}and {cout<<“purse”;}do not have the same effect.) No implementation of a name()function may call any other function. All data members must be declared private. You may declare member
functions publicor private. Your solution must not declare any protected members (which we’re not covering in this class). In a real program, you’d probably have separate Landmark.h, Landmark.cpp, Hotel.h, Hotel.cpp, etc., files. For simplicity for this problem, you may want to just put everything in one file. What you’ll turn in for this problem will be a file named landmark.cppcontaining the definitions and implementations of the four classes, and nothing more. (In other words, turn in only the program text that replaces Your declarations and implementations would go here.)
2. The following is a declaration of a function that takes a double and returns true if a particular property of that double is true, and false otherwise. (Such a function is called a predicate.) boolsomePredicate(doublex); Here is an example of an implementation of the predicate x is negative: boolsomePredicate(doublex) { returnx<0; } Here is an example of an implementation of the predicate sin e x is greater than cos x: boolsomePredicate(doublex) { returnsin(exp(x))>cos(x);//includeforstd::sin,etc. } Here are five functions, with descriptions of what they are supposed to do.
They are incorrectly implemented. The first four take an array of doubles and the number of doubles to examine in the array; the last takes two arrays of doubles and the number of doubles to examine in each: //ReturntrueifthesomePredicatefunctionreturnstrueforat //leastoneofthearrayelements,falseotherwise. boolanyTrue(constdoublea[],intn) { returnfalse; //Thisisnotalwayscorrect. } //Returnthenumberofelementsinthearrayforwhichthe //somePredicatefunctionreturnstrue. intcountTrue(constdoublea[],intn) { return-999; //Thisisincorrect.
//Returnthesubscriptofthefirstelementinthearrayforwhich //thesomePredicatefunctionreturnstrue. Ifthereisnosuch //element,return-1. intfirstTrue(constdoublea[],intn) { return-999; //Thisisincorrect. } //Returnthesubscriptofthesmallestelementinthearray(i.e., //theonewhosevalueis<=thevalueofallelements). Ifmore //thanoneelementhasthesamesmallestvalue,returnthesmallest //subscriptofsuchanelement. Ifthearrayhasnoelementsto //examine,return-1. intindexOfMin(constdoublea[],intn) { return-999; //Thisisincorrect. } //Ifalln2elementsofa2appearinthen1elementarraya1,in //thesameorder(thoughnotnecessarilyconsecutively),then //returntrue;otherwise(i.e.,ifthearraya1doesnotinclude //a2asanot-necessarily-contiguoussubsequence),returnfalse. //(Ofcourse,ifa2isempty(i.e.,n2is0),returntrue.) //Forexample,ifa1isthe7elementarray // 10504020504030 //thenthefunctionshouldreturntrueifa2is // 502030 //or // 504040 //anditshouldreturnfalseifa2is // 503020 //or // 102020 boolincludes(constdoublea1[],intn1,constdoublea2[],intn2) { returnfalse; //Thisisnotalwayscorrect. }
Your implementations of those first three functions must call the function named somePredicatewhere appropriate instead of hardcoding a particular expression like x<0or sin(exp(x))>cos(x). (When you test your code, we don’t care what predicate you have the function named somePredicateimplement: x < 0 or x == 42 or sqrt(log(x*x+1)) > 5 or whatever, is fine.)
Replace the incorrect implementations of these functions with correct ones that use recursion in a useful way; your solution must not use the keywords while, for, or goto. You must not use global variables or variables declared with the keyword static, and you must not modify the function parameter lists.
You must not use any references or pointers as parameters except for the parameters representing arrays. (Remember that a function parameter xdeclared Tx[]for any type Tmeans exactly the same thing as if it had been declared T*x.) If any of the parameters n, n1, or n2is negative, act as if it were zero. Here is an example of an implementation of anyTruethat does not satisfy these requirements because it doesn’t use recursion and it uses the keyword for: boolanyTrue(constdoublea[],intn) { for(intk=0;k<n;k++) { if(somePredicate(a[k])) returntrue; } returnfalse; } You will not receive full credit if the anyTrue, countTrue, or firstTruefunctions cause each value somePredicatereturns to be examined more than once. Consider all operations that a function performs that compares two doubles (e.g. <=, ==, etc.).
You will not receive full credit if for nonnegative n, the indexOfMinfunction causes operations like these to be performed more than ntimes, or the includesfunction causes them to be performed more than n1times. For example, this non-recursive (and thus unacceptable for this problem) implementation of indexOfMinperforms a <= comparison of two doubles many, many more than ntimes, which is also unacceptable: intindexOfMin(constdoublea[],intn) { for(intk1=0;k1<n;k1++) { intk2; for(k2=0;k2<n&&a[k1]<=a[k2];k2++) ; if(k2==n) returnk1; } return-1; } Each of these functions can be implemented in a way that meets the spec without
calling any of the other four functions. (If you implement a function so that it does call one of the other functions, then it will probably not meet the limit stated in the previous paragraph.) For this part of the homework, you will turn in one file named linear.cppthat contains the five functions and nothing more: no implementation of somePredicate and no main routine. (Our test framework will precede the functions with an implementation of a function named somePredicatethat takes a double and returns a bool.)
3. Replace the implementation of pathExistsfrom Homework 2 with one that does not use an auxiliary data structure like a stack or queue, but instead uses recursion in a useful way. Here is pseudocode for a solution: Ifthestartlocationisequaltotheendinglocation,thenwe’ve solvedthemaze,soreturntrue. Markthestartlocationasvisted. Foreachofthefourdirections, Ifthelocationonestepinthatdirection(fromthestart location)isunvisited, thencallpathExistsstartingfromthatlocation(and endingatthesameendinglocationasinthe currentcall). Ifthatreturnedtrue, thenreturntrue. Returnfalse. (If you wish, you can implement the pseudocode for loop with a series of four if statements instead of a loop.) You may make the same simplifying assumptions that we allowed you to make for Homework 2 (e.g., that the maze contains only Xs and dots). For this part of the homework, you will turn in one file named maze.cppthat contains the Coord class (if you use it) and the pathExistsfunction and nothing more.
4. Replace the incorrect implementations of the countIncludesand the order functions below with correct ones that use recursion in a useful way. Except in the code for the splitfunction that we give you below, your solution must not use the keywords while, for, or goto. You must not use global variables or variables declared with the keyword static, and you must not modify the function parameter lists. You must not use any references or pointers as parameters except for the parameters representing arrays and the parameters of the exchangefunction we provided. If any of the parameters n1, n2, or nis negative, act as if it were zero. //Returnthenumberofwaysthatalln2elementsofa2appear
//necessarilyconsecutively). Theemptysequenceappearsina //sequenceoflengthn1in1way,evenifn1is0. //Forexample,ifa1isthe7elementarray // 10504020504030 //thenforthisvalueofa2 thefunctionmustreturn // 102040 1 // 104030 2 // 201040 0 // 504030 3 intcountIncludes(constdoublea1[],intn1,constdoublea2[],intn2) { return-999; //Thisisincorrect. } //Exchangetwodoubles voidexchange(double&x,double&y) { doublet=x; x=y; y=t; } //Rearrangetheelementsofthearraysothatalltheelements //whosevalueis>splittercomebeforealltheotherelements, //andalltheelementswhosevalueissplitter // *forfirstNotGreater<=i<firstLess,a[i]==splitter // *forfirstLess<=i<n,a[i]splitterendupinnoparticularorder. //Alltheelementssplitter // EveryelementfrompositionfirstNotGreatertofirstUnknown-1is // ==splitter // EveryelementfromfirstUnknowntofirstLess-1isnotknownyet // EveryelementatpositionfirstLessorlaterissplitter) { exchange(a[firstNotGreater],a[firstUnknown]); firstNotGreater++; } firstUnknown++; } } } //Rearrangetheelementsofthearraysothat //a[0]>=a[1]>=a[2]>=…>=a[n-2]>=a[n-1] //Ifn<=1,donothing. voidorder(doublea[],intn) { return; //Thisisnotalwayscorrect. } (Hint: Using the splitfunction, the orderfunction can be written in fewer than eight short lines of code.) Consider all operations that a function performs that compares two doubles (e.g. <=, ==, etc.). You will not receive full credit if for nonnegative n1and n2, the countIncludesfunction causes operations like these to be called more than factorial(n1+1)/(factorial(n2)*factorial(n1+1-n2))times.
The countIncludesfunction can be implemented in a way that meets the spec without
calling any of the functions in problem 2. (If you implement it so that it does call one of those functions, then it will probably not meet the limit stated in this paragraph.) For this part of the homework, you will turn in one file named tree.cppthat contains the four functions above and nothing more.
Turn it in By Monday, February 8, there will be a link on the class webpage that will enable you to turn in this homework. Turn in one zip file that contains your solutions to the homework problems. The zip file must contain one to four of the four files landmark.cpp, linear.cpp, maze.cpp, and tree.cpp, depending on how many of the problems you solved. Your code must be such that if we insert it into a suitable test framework with a main routine and appropriate #include directives, it compiles. (In other words, it must have no missing semicolons, unbalanced parentheses, undeclared variables, etc.)
