Final- LO01
Spring 2019
算法代考 One wants to design a computer system to sort the candidates, by increasing number of votes, during the vote period.
ID number :
Surname :
Name :
Signature :
No document is authorized during the exam except paper language dictionaries.
Important1: You must answer each question in the frame located below the question. If the frame is too small please use the additional pages at the end of the subject and mention very clearly the number of the question you are answering to. 算法代考
Important2: Write your answers with great care. In particular, to obtain a good grade, make the structure of the algorithms clear and easy to read and avoid crossing-out. A penalty u叩to 50% of the mark of a question can be applied if the examiner has difficulty to read the answer.
Outline:
1. Recursivity (15 pts)
2. Pointers (5 pts)
3. Data Structure (15 pts)
4. Sorting (10 pts)
5. Flowers (55 pts)
Additional page
1 Recursivity (15 pts) 算法代考
Write a recursive sub-algorithm R text. length to compute the number of characters of a text ended by character ‘\0’. Character “\0′ is not counted.
Sub- algorithm R_ text length
Input parameters :
position: integer
Output parameter :
length: integer
Variables:
2 Pointers (5 pts)
For the following algorithm, indicate on the left of each declaration and instruction if the declaration or instruction is correct or not. If it is not correct, propose a crrct version using the same variables and so that, at the end, the value ofn is 3.7.
Algorithm TestPointer
Variables :
p: pointer to real; n :-intcgct
Instructions :
n←2.7
pn←2.7@n
p←p+1
3 Data structure (15 pts) 算法代考
3.1 Question (5 pts)
We want to record information about classrooms in SHU. We want to memorize the building number (for example B), the room number (for example 104b), the capacity of the room (maximum number of students allowed) and the presence, or not, of a videoprojector. Define a type SHU_ Class to record these information
3.2 Question (10 pts)
Write a sub-algorithm that enables a user to enter all information about a room and to memorize them in a variable.The sub-algorithm must returm a variable of type SHU_ Class.
It is mandatory to use the type defined in previous question.
Sub-algorithm EnterRoom
Input parameters : none
output parameter : Room: SHU_ Class .
4 Sorting (10 pts) 算法代考
For a TV show, a singing contest is organized. A jury watching the contcst can vote for onc of the 15 candidates during a given period of time. Each jury member can vote for only one candidate. At the end, the candidate that obtained the largest number of votes wins a price.
One wants to design a computer system to sort the candidates, by increasing number of votes, during the vote period. The idea is to update the sort after each vote and to display each time the result.
Different sorting algorithms have been studied during the course. Give the name of the best one for this problem and explain your choice.
5 Flowers (55 pts)
Aim and context:
We want to simulate over years the evolution of a population of flowers in a field.
We consider a square field divided in 50 lines and 50 columns (so that we have 2500 small squares). 算法代考
At the beginning the field is empty.
The first year the owner plants 3 different species of flowers (we call them species ‘A’, species ‘B’ and species ‘C’). He plants 5 seeds of each species in different locations of the field (so 15 seeds in total). Each seed becomes a flower and spread new seeds around. The next year some of those seeds will become flowers and produce new seeds and so on…
Flower reproduction rules
For each species of flower the number of seeds produced by one flower is 8 and the locations where the seeds go for next year depend on the flower species as shown by figure 1. Read carefully the caption of the figure.
Figure 1: Character F indicates the position of the flower, Characters S indicate the location of the seeds produced by the flower the next year. On the left – species ‘A’, in the middle – species ‘B’, on the right – species ‘C’
A seed that falls out of the field dies. 算法代考
Seeds live only one year.
Each small square can contain either nothing, 1, 2, 3… seeds or 1 flower and no seed.
●if year Yk the square is empty, there will be no flower there the next year Yk+1.
●if year Yk the square contains a flower, it will be empty the next year Ye+1.
●if year Y%: only one seed falls in the square, there will be a flower in that square the following year Yk+1. The type of the flower corresponds to the type of the seed.
●if year Yx, 2, 3 or more seeds fall in the square (more than one seed of a species can fall in one small square),there will be a flower competition and only one flower of one seed species will grow in that small square the next year Yk+1.
Data Type 算法代考
Let define a type SMALL SQUARE : RECORD (speciesA : integer, speciesB : integer, speciesC : integer).
Specification of the algorithm
Role: Simulate the propagation of the s during a given number of years
Data: the number of years of the simulation, the coordinates of the seeds planted at the beginning. 2 coordinates per seed (integers). 5 seeds of species ‘A’, 5 seeds of species ‘ B’, 5 seeds of species ‘C’
Result: for cach year, the number of empty small squares, the number of small squares with ‘A’ flowers, the number of small squares with ‘B’ flowers, the number of small squares with ‘C’ flowers. All four numbers are integers.
Analysis 算法代考
Variables and codes for species representation
The field is represented using 2 variables. Variable SEEDS is used to memorize the location of seeds for a year and variable FLOWERS is used to memorize the location of flowers the same year.
SEEDS is a 2D array with 50 lines, 50 columns of type SMALL_ SQUARE.
FLOWERS is a 2D array with 50 lines, 50 columns of type character.
Flowers of species ‘A’ are coded with character ‘A’, flowers of species ‘B’ are coded with character ‘B’, flowers of species ‘C’ are coded with character ‘C’, empty zone are represented using character ‘E’.
The value of variable SEEDS at year Yk enables to compute variable FLOWERS at year Yk+1 which is used to compute SEEDS at year Yk+1 and so on. At the beginning SEEDS is empty.
Examples
Examples of values of attributes “speciesA”, “speciesB”, “speciesC” of a SMALL_ SQUARE in array SEEDS:
●”speciesA”, ‘ speciesB”, “speciesC” are 0 : means the corresponding small square is empty
●”speciesB” is 1 the others are 0: means the corresponding small square contains one seed of species ‘B’
●”speciesB” is 2, “speciesA” is 0 and “speciesC” is 3 : means the corresponding small square contains 2 seeds,one of species ‘B’ and 3 of species ‘C.
Processing Steps:
1. Initialize variables FLOWERS to empty. Initialize the year number to 0. 算法代考
2. Initialize variables SEEDS to empty.
3. Ask the user the number of years of the simulation (integer)
4. Ask the location of the first 15 seeds, and change array SEEDS accordingly
5. Increase year number and determine the value of array FLOWERS from SEEDS
6. Count the flowers of each type and the number of empty SMALL_ SQUARE and output the result
7. Propagate new seeds produced by the flowers to determine SEEDS from FLOWERS.
8. For all SMALL_ SQUARE of SEEDS with more than one seed, select randomly a single seed and remove seeds from small squares containing a flower.
9. Repeat 5, 6, 7, 8 until the ending year 算法代考
5.1 Question (20pts)
Write the main algorithm corresponding to this problem. Pay attention to variable definition, to sub-algorithms name and to input and output arguments.
You must use one sub-algorithm for steps 1, 2, and steps 4 to 8 of the algorithm. This is mandatory!
5.2 Question (5pts)
Write the sub-algorithm corresponding to the initialization of variable SEEDS for step 2.
5.3 Question (10pts)
Write the sub-algorithm corresponding to step 6 : counting the flowers.
5.4 Question (20pts)
Write the sub algorithm corresponding to step 7: propagating the seeds according to flowers position and species. At the beginning the seed field must be empty. Next, when propagating the seeds, if a seed falls in a small square that contains others seeds, it has to be added to those seeds. In case you add new sub-algorithms, you must write them.
更多代写：程式作业代写 线上考试作弊 Econ网课代考 essay代写北美 paper代写英国 essay plan写作
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
