Lecture "Algorithms", exercise 3
essepuntato opened this issue · 19 comments
The previous chapter, entitled “Introduction to Computational Thinking”, illustrates two different algorithms, expressed in natural language, for implementing the Fibonacci function. Create two distinct flowcharts to implement both of them.
I hope I managed to correctly translate the two algorithms in these two flowcharts.
This flowchart represents the first algorithm:
This flowchart represents the second one:
This is the flowchart for the first algorithm
I tried to represent the second agorithm through a flowchart too, but I'm not sure at all about the result
This is only for the first algorithm since I didn't really understand how to represent second algorithm in a flowchart
I was able to create the flowchart just for the first algorithm.
The first natural language instructions of Fibonacci function:
The function for calculating the nth Fibonacci number takes as input an integer “n”. If “n” is
less than or equal to 0, then 0 is returned as a result. Otherwise, if “n” is less than or equal
to 2, then 1 is returned. Otherwise, in all the other cases, associate the value “1” to two distinct
variables “a” and “b”. Then, repeat the following operations indefinitely until a value is returned.
Set the variable “c” as the sum of “a” plus “b”. If “n” is less than or equal to “3” then return “c”,
otherwise assign the value of “b” to “a” and the value of “c” to “b”, and finally decrease the
value of “n” by 1 before repeating.
Flowchart version :
The second natural language instructions of Fibonacci function :
The function for calculating the nth Fibonacci number takes as input
an integer “n”. If “n” is less than or equal to 0, then 0 is returned
as a result. Otherwise, if “n” is equal to 1, then 1 is returned.
Otherwise,
> return the sum of the same function with “n-1” as input
> and still the same function with “n-2” as input.
As I have mentioned earlier I couldn't actually understand the quoted part of the instructions in the second version still trying.
I tried to put the second algorithm in a flowchart but at the end I got in an infinite loop of 13s
Then, when I saw the answers from my colleagues I realized I put an extra "if" that was making the loop infinite, so the end diagram is
representation of the first description in natural language of the Fibonacci's algorithm
representation of the second description in natural language of the Fibonacci's algorithm
Representation of the first description in natural language of the Fibonacci's algorithm
Representation of the second description (probably wrong)
first definition:
second definition
:
Flowchart 1
Flowchart 2
First Flowchart
Second Flowchart
The recursive style algorithm is on the right. Not 100% sure about it though.
Flow chart 1
(I realised it was necessary, I think, to split up the assignments of a and b, and c into two separate widgets)
Flowchart 2
First flowchart:
Second flowchart:
First flowchart (without recursion)
Second flowchart (with recursion)
Made the second one after the suggestion given during last class
