2

I have a problem: i need to find an average of the list using this scheme:

First of all, we find an average of two elements, three elements..... len(list) elements and form a new list using averages. The use .pop() and find all averages again. Function should stop when len(list) == 2. Recursion should be used.

Example: list: [-1, 4, 8, 1]

1 step:

  • find an average of [-1, 4], [-1, 4, 8], [-1, 4, 8, 1]
  • Then we form a new list: [1.5, 3.66..., 3] (averages)
  • Then find averages of new list: [1.5, 3.66...], [1.5, 3.66..., 3]
  • Then we form a new list: [2.5833.., 7.222...] (averages)
  • When len(list) == 2, find an average of this two elements.

Answer is 2.652777.

What should i write:

jada = []

while True:    
    print 'Lst elements:'    
    a = input()
    if (a == ''):    
        break    
    jada.append(a)

print 'Lst is:' + str(Jada)

def keskmine(Jada):
    for i in range(len(Jada) - 1):
        ...

    jada.pop()
    return keskmine(Jada)

Actually, this is a part of a homework, but i don't know how to solve it.

Improve this question

4 Answers 4

Reset to default
3

Accept the list as the function argument. If the list has one item, return that. Create two iterators from the list. Pop one item off one of the lists, zip them together, then find the averages of the zip results. Recurse.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

please, could you explain that more in a more datailed way.
Make an attempt first, and we'll guide you.
2

In short, you're finding the "running average" from a list of numbers.

Using recursion would be helpful here. Return the only element when "len(lst) == 1" otherwise, compute the running average and recurse.

There are two parts in this assignment. First, you need to transform lists like [-1, 4, 8, 1] to lists like [1.5, 3.66, 3] (find the running averages). Second, you need to repeat this process with the result of the running averages until your list's length is 2 (or 1).

You can tackle the first problem (find the running averages) independently from the second. Finding the running average is simple, you first keep track of the running sum (e.g. if the list is [-1, 4, 8, 1] the running sum is [-1, 3, 11, 12]) and divide each elements by their respective running index (i.e. just [1, 2, 3, 4]), to get [-1/1, 3/2, 11/3, 12/4] = [-1, 1.5, 3.66, 3]. Then you can discard the first element to get [1.5, 3.66, 3].

The second problem can be easily solved using recursion. Recursion is just another form of looping, all recursive code can be transformed to a regular for/while-loops code and all looping code can be transformed to recursive code. However, some problems have a tendency towards a more "natural" solution in either recursion or looping. In my opinion, the second problem (repeating the process of taking running averages) is more naturally solved using recursion. Let's assume you have solved the first problem (of finding the running average) and we have a function runavg(lst) to solve the first problem. We want to write a function which repeatedly find the running average of lst, or return the average when the lst's length is 2.

Improve this answer

5 Comments

.....first keep track of the running sum (e.g. if the list is [-1, 4, 8, 1] the running sum is [-1, 3, 11, 12]) and divide each elements by their respective running index (i.e. just [1, 2, 3, 4]), to get [-1/1, 3/2, 11/3, 12/4] = [-1, 1.5, 3.66, 3]..... how did you calculated that? I'd be very pleased if you could explain.
@user465137: the first element in the real list is -1, so you append -1 to the result list; then take the second element 4, add it to -1, to get 3, append 3 to the result list; then take the third element 8, add it to 3, to get 11, append 11 to the result list; then take the fourth element 1, add it to 11 to get 12, append 12 to the result list. Now the result list contains [-1, 3, 11, 12].
i tried to write the code for: [-1 + 4], [-1 + 4 + 8], [-1 + 4 +8 +1] but all my attempts end with nothing. please, help if you can
@user465137: Copy and paste your question so it includes what you have attempted, even if it is mistaken. We will help point out where your mistake is.
Hello @user465137 (oh please find an alias), take a look at my answer below, I believe it will help you out... Your problem is trying to compute the sum from the beginning for every element. Instead, add the next element to the sum so far after you've saved it into the array. If you think of it this way, the first element contains the sum of elements 1 to 1. If you add this to the 2nd element, it now contains the sum of elements 1-2 of the input list, add that to the 3rd element, and it contains the sum of elements 1-3 of the input list, and so on and so forth.
0

First I'll give you an explanation, and then some pseudo code, which you'll have to rewrite in Python. The main idea is to have one function that calls itself passing a lesser problem with each iteration. In this case you would like to decrease the number of items by 1.

You can either make a new list with every call, or reuse the same one if you'd like. Before passing on the list to the next iteration, you will need to calculate the averages thus creating a shorter list.

The idea is that you sum the numbers in a parameter and divide by the number of items you've added so far into the appropriate index in the list. Once you are done, you can pop the last item out.

The code should look something like this: (indexes in sample are zero based)

average(list[])
    if(list.length == 0)  // Check input and handle errors
        exit
    if(list.length == 1)  // Recursion should stop
        return list[0]    // The one item is it's own average!
    // calculate the averages into the list in indices 0 to length - 2
    list.pop()                       // remove the last value
    return average(list)             // the recursion happens here
Improve this answer

1 Comment

I initially wrote a complete answer but figured that you wouldn't learn much by it. The comment that says "calculate the averages into the list in indices 0 to length - 2" is for you to fill in. If you get stuck let me know and I'll hint it to you. Good luck.
0

This is also an opportunity to use python 3.x itertools.accumulate:

From docs:

>>> list(accumulate(8, 2, 50))

[8, 10, 60]

Then, you only need to divide each item by its index increased by 1, eliminate the first element and repeat until finished

For example, this works for any list of any length, doing most of the above-indicated steps inside a list comprehension:

>>> from itertools import accumulate
>>> a = [-1, 4, 8, 1]
>>> while len(a) > 1:
    a = [item / (index + 1) for (index, item) in enumerate(accumulate(a)) if index > 0]

>>> print(a)
[2.6527777777777777]
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.