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
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 2
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 3
A copy shop charges 2 euros for the first ten photocopies, 1.50 euros for the next twenty and 1 euro beyond. Write an algorithm that asks the user for the number of photocopies made and then displays the corresponding amount.
It is possible to put the branches in sequential, but that is less efficient in calculation time.
Exercise 4
Write an algorithm to display the season by introducing the number of the month.
Exercise 5
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.
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).
EN 
FR 
ES