5 Corrected exercises on algorithmic structures

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.

algorithmic structures

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.

Egyptian multiplication algorithm

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

Egyptian multiplication algorithm

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.

Egyptian multiplication algorithm

Which gives the following algorithm:

Egyptian multiplication

You don't have to use a temp variable to swap two values. Here is another version of the algorithm:

Egyptian multiplication

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!

permutation algorithm

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).

max algorithm

The idea would be to return the maximum without using additional variables.

maximum three variable algorithm

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!)

maximum optimized algorithm

vs- We just did it several times… for those who haven't followed.

permutation algorithm

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)

identical sign algorithm

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.

invoice algorithm

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.

sum algorithm

minimum maximum algorithm

algorithm rest of the quotient

product algorithm

divisor algorithm

divisor algorithm

prime number algorithm

sum of digits algorithm

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).

To share