The following corrected exercises relate to algorithmic structures, control structures and data structures. The objective is to propose the structures most suited to the statement.
Exercise 1
Consider the algorithms below.
(a) What will be the contents of variables a, b and possibly c after their execution?
(b) In each of the above cases, are there any unnecessary lines, and if so which ones?
In most programming languages the last example (1.6) will not generate an error but the result will not often be '3'. Depending on the language, this will be the concatenation of these characters into a character string “ab” (case of Python or JavaScript languages), or even “a+b” (case of the shell) or the sum of the ASCII codes corresponding to the characters ' 1' and '2', i.e. 49 + 50 = 99: the character 'c' (case of C, C++ or Java languages). In very few languages, like PHP or perl, on the other hand, the result will be 3. Finally in other languages like pascal, which is a strongly typed language, the compilation will generate an error.
Exercise 2
This multiplication technique, used in ancient Egypt, does not require knowing all the multiplication tables up to 10 but only addition and multiplication by 2.
Here is for example the multiplication of 13 by 78. You must first write the table of powers of 2 less than or equal to 13. Then, write the table of doubles of the number 78.
Then, you have to tick the greatest powers of 2 breaking down the number 13 (that is to say that the binary bit is equal to 1). In other words, tick the powers of 2 entering the binary conversion of the number 13 = 1101
The sum is 78+312+624=1014.
a – Calculate the product of your choice using the Egyptian division algorithm.
b – Is it easier to calculate the product of 78 by 13? Why ?
c – Write the Egyptian multiplication algorithm (according to your answer of b!). Try to optimize it as best you can!
The easiest is to choose the smallest number for the power of 2 and therefore the largest number to be doubled. Indeed, the number of iteration is equal to the number of times that it is necessary to multiply 2 by itself to be greater than the number minus one iteration (we only keep what is strictly lower. We will therefore have a number d iteration n such that 2not > a (described number). We deduce that n>log2(a) hence the interest that a is the smallest.
We first recall the binary transformation of a decimal number.
Which gives the following algorithm:
You don't have to use a temp variable to swap two values. Here is another version of the algorithm:
Exercise 3
a – Write a algorithm whose parameters are three real variables and which circularly permutes their values.
b – Write an algorithm whose parameters are three real variables and returns the maximum value among these three values.
c – Write an algorithm that allows the values of two variables without using an additional variable.
d – Write an algorithm that returns true if two integers a and b have the same sign, otherwise false
has - The variables a, b and c are variables defined outside the algorithm. These values are modified even if nothing is returned. Pay attention to the order of your operations!
You can also do this without taking an additional variable. In this case we will have at the beginning (a,b,c). For example, a and b are swapped using the following operations:
a ← a + b
b ← a–b
a ← a–b
We therefore have the triple of values (b,a,c). It remains to swap a and c to obtain the tripled (b,c,a).
Or you can also swap the three values using a series of calculations.
a ← a + b + c;
c ← a–b–c;
b ← a–b–c;
a ← a–b–c;
b- Here the algorithm must return a value, so there are inputs and outputs. There are many ways to do things, it's up to you to find variants (with several conditions in the branch for example).
The idea would be to return the maximum without using additional variables.
It's not very pretty there either, so we'll try to return the maximum only once without using new variables. We will permute the values to store the maximum in x (be careful, depending on the languages you can have a real impact on the values in xy and z, so use with caution!)
vs- We just did it several times… for those who haven't followed.
d- We will think about a well-optimized algorithm to avoid making lots of branches. Two integers with the same sign will have their positive product! (0 is both positive and negative)
Exercise 4
Write an algorithm to solve each of the following problems: (try with different control structures FOR, WHILE, DO … WHILE, etc.).
1- Calculation of the sum of the first N integers.
2- Finding the minimum and the maximum in a set of N numbers.
3- Calculation of the quotient and remainder of the division of two integers A and B without using the division operation.
4- The calculation of the product of two integers using only the addition operation '+'.
5- Determination if A is divisible by B. With A and B positive integers.
6- Determine all the divisors of a given integer X.
7- Determine if an integer X is prime or not.
8- Calculate the sum of the digits that make up a natural number N.
9- A reprography store charges 2 euros for the first ten photocopies, 1.50 euros for the next twenty and 1 euro beyond that.
10- Write an algorithm to display the season by introducing the number of the month.
Erratum: at the beginning R = N, otherwise the algorithm does nothing (we say that it is not correct because it does not solve the problem posed).
9-
It is possible to put the branches in sequential, but that is less efficient in calculation time.
10-
Exercise 5
1. Write an algorithm that asks the user for an integer, tests whether that number is positive (0) or not, and displays “positive” or “negative”.
2. Write an algorithm that asks the user for an integer, tests whether that number is strictly positive, zero, or strictly negative, and displays that result.
3. Write an algorithm that asks the user for a real value and displays its absolute value (without using a predefined function obviously).
4. Write an algorithm that asks for a real number from the user and rounds it to the nearest integer (x.5 will be rounded up to the next integer).
5. Write an algorithm that asks for the number of a month and displays the number of days in that month (ignoring leap years).
6. Write an algorithm that checks if a year is a leap year. Remember that there are leap years every 4 years, but the first year of a century is not (1800, 1900 were not leap years) except every 400 years (2000 was a leap year) .
7. Write an algorithm that requests a date in the form of 2 integers (day number and month number) and displays the season (ex: 02/12; winter). It will be assumed that the first day of the season is always the 21st.
8. Write a program that asks for the coordinates (x, y) of the vertices A, B and C of a triangle and displays the nature of the triangle (isosceles, equilateral, rectangular or any).
Exercise 6
1. Write an algorithm that asks for a positive integer, and rejects it until the number entered does not match.
2. Write an algorithm that asks for 10 integers, counts the number of positive integers entered, and displays that result.
3. Write an algorithm that asks the user for positive integers, adds them, and stops displaying the
result as soon as a negative integer is entered.
4. Modify this last algorithm to display the average of the series of positive integers entered.
1-
2-
3-
4-
Exercise 7
Write an algorithm to display the first n terms of the following sequences (n requested from the user):
Exercise 8
Write an algorithm that calculates the first n prime numbers.
Exercise 9
Exercise 10
A positive integer is said Perfect if it is equal to the sum of its divisors (except itself). For example 6 is perfect, because 6 = 1 + 2 + 3; similarly 28 is perfect, because 28 = 1 + 2 + 4 + 7 + 14.
Write a perfect Boolean function for an integer n. To optimise.
Make a perfect_riddle procedure which searches for and displays, using a sieve, the perfect numbers on an interval from 1 to M .
We plan to store for each integer the sum of its divisors, a sum which will be calculated during the sift: the principle of the sift is, for each integer i of the interval, to go through the multiples of i to which we add the divisor i.
Here is a fairly simple algorithm to think of for finding a perfect number.
We can also initialize s to 1 and start the loop at 2, but be careful the function must return false for i = 1; we must then add a test to the initialization.
We can optimize the function by noting that if i split not, SO (not div i) is also a divisor since i (not div i) = not.
Just vary i from 2 to √not : if i is a divisor, then the divisor (not div i) is in the interval √not To not ; so we have all the divisors.
You have to think about starting at 2 so as not to add not. There is also a problem if not is a square: we will have added the divisor twice r = √not.
Here is an algorithm for perfect_screen:
The perfect numbers between 1 and 10,000,000 are 6, 28, 496, 8128.
Exercise 11
Write a function that returns the number of occurrences of the maximum value present in an unsorted array. Build the algorithm in 0(n).
It is possible to do it as a two-stroke, we will have a complexity of 2n=O(n)
Or to do everything in a single loop:
Exercise 12
We consider a square Q in which a large number of points are randomly positioned. The ratio between the number of points appearing in the circle inscribed in Q and the number of points drawn approaches the ratio between the surface of the disc inscribed in Q and the surface of the square Q. We deduce an approximate value of π. This method is called a Monte Carlo simulation (very useful in finance!).
That is r the radius of the circle. The area of the circle is πr2 and the area of the square is 4r2. To simplify we take r = 1, and we limit ourselves to the quarter plane R+ ×R+ .
random(m) provides an integer between 0 and m-1, while random without parameters provides a real between 0 and 1.
To know if a point (x,y) ∈ at the quarter circle we test if √(x² + y²) ≤ 1.
As calculating the square root is expensive, we simply do the equivalent test (x² + y²) ≤ 1. For this we can use the sqr function which is more optimized than x*x.
not is the total number of points drawn (all in the quarter square); vs is the number of these points that is in the quarter circle.
EN 
FR 
ES