Άσκηση σε python

[DIMITRISG]

Για να μην ανοίγω άλλο θέμα, είμαι στο recursion και έχω μια (...) ερώτηση.

Σε αυτήν την άσκηση:

 

By writing something similar to nestedListSum

 

def nestedListSum(NL):
    if isinstance(NL, int):     # case (a): NL is an integer
        return NL               # base case

    sum = 0                     # case (: NL is a list of nested lists
    for i in range(0, len(NL)): # add subsums from each part of the main list
        sum = sum + nestedListSum(NL[i])
    return sum                  # all done

, define a recursive function

 

nestedListContains(NL, target)

that takes a nested list NL of integers and an integer target, and indicates whether target is contained anywhere in the nested list. Your code should return the boolean value True when it is contained in the nested list, and False if it is not contained in it.
For example, nestedListContains([1, [2, [3], 4]], 3) should give True and nestedListContains([1, [2, [3], 4]], 5) should give False.

 

μετά από επίπονες προσπάθειες έφτασα στο επιθυμητό αποτέλεσμα με τον παρακάτω κώδικα:

def nestedListContains(NL, target):
   if isinstance(NL, int):
      return NL
      
   for i in range(0, len(NL)):
      a=nestedListContains(NL[i], target)
      if a==True: break
      if target==a:
         b=True
         break
         return True
      if a!=target:
         b=False
         continue  
    
   if a == True: return True
   return b
   

Με αυτά τα ορίσματα:

Running nestedListContains([2, 3, 5, 7, 9], 7) … its value True is correct!
Running nestedListContains([2, 3, 5, 7, 9], 8) … its value False is correct!
Running nestedListContains([[9, 4, 5], [3, 8]], 3) … its value True is correct!
Running nestedListContains([[9, 4, 5], [3, 8]], 6) … its value False is correct!
Running nestedListContains([[[[[[[5]]]], 4]]], 3) … its value False is correct!
Running nestedListContains([[[[[[[7]]]], 8]]], 7) … its value True is correct!

 

 

Είχα κολλήσει πάρα πολύ ειδικά πριν βάλω τη γραμμή:

if a==True: break

 

την οποία πρόσθεσα αφού είδα στο visualizer ότι εκείνη τη συγκεκριμένη στιγμή επέστρεφε μια τιμη a=True

 

-Γενικά η λογική του κώδικα είναι σωστή;

-Από που κι ως που εμφανίζεται αυτό το a=True;;;;

 

Γενικά το recursion μου είναι ακόμα κάπως δύσκολο να αναλύσω στη σκέψη μου αλλά μέσες άκρες προσανατολίζομαι.

 

 

 

 

[nilosgr]

def nestedListContains(NL, target):
   if isinstance(NL, int):
      return NL == targer

   retVal = False

   for i in range(len(NL)):
      retVal = retVal or nestedListContains(i, target)

   return retVal

Στο ποδι το γραψα, αν δεν καταλαβαινεις κατι πες μου

Edit: κάτι διόρθωσα αλλά πάλι δεν το έχω τρέξει. Ίσως την παρασκευή ασχοληθώ

Επεξ/σία 19 Δεκεμβρίου 2012 από nilosgr

[pmav99]

Γενικό import για όλα τα snippets

from collections import Sequence

Κώδικας για testing

def test(func):
    assert func([1, [2, [3], 4]], 3)
    assert not func([1, [2, [3], 4]], 5)
    assert func([2, 3, 5, 7, 9], 7)
    assert not func([2, 3, 5, 7, 9], 8)
    assert func([[9, 4, 5], [3, 8]], 3)
    assert func([[3, 8], [9, 4, 5]], 3)
    assert not func([[9, 4, 5], [3, 8]], 6)
    assert not func([[[[[[[5]]]], 4]]], 3)
    assert func([[[[[[[7]]]], 8]]], 7)
    assert func([3, 2, [4, 5]], 4)
    assert func([3, 2, [4, 5]], 2)
    assert func([[4, 5], 3, 2], 4)
    assert func([[4, 5], 3, 2], 2)
    assert not func([3, 2, [4, 5]], 7)
    print("%s : OK" % func.__name__)

Η συνάρτηση του nilosgr είναι λάθος. Είναι σωστή η λογική μεν, αλλά επειδή οι λίστες μπορούν να έχουν περίεργα περιεχόμενα, δεν μπορεί να τα πιάσει όλα. H δική σου συνάρτηση Δημήτρη δεν περνάει το δεύτερο assertion.

 

Αυτό που ζητάς μπορεί να γραφεί πολύ συνοπτικά ως εξής :

def nlc_oneliner(outer, target):
    if target in outer:
        return True
    return any([nlc_oneliner(inner, target) for inner in outer if isinstance(inner, Sequence)])

Λιγότερο ιδιωματικά μπορεί να γραφεί ως εξής:

def nlc_explained(outer, target):
    if target in outer:
        return True

    # if there are nested lists then call nlc function recursively
    # for each nested list.
    results = []
    for inner in outer:
        if isinstance(inner, Sequence):
            results.append(nlc_explained(inner, target))
    return any(results)

Και οι δύο συναρτήσεις, πρέπει να δουλεύουν με οποιοδήποτε τύπο (float, complex, string) και όχι μόνο με integers. Ακόμη πρέπει να δουλεύουν με οποιοδήποτε Sequence (πχ tuple). Μην βάλεις όμως κανά infinite iterator γιατί θα κρασάρει μόλις τελειώσει η μνήμη (ή μάλλον μόλις περάσει το Recursion Limit)

[nilosgr]

Ναι όντως λαλακια έγραψα... Μόνο το πρώτο στοιχείο ελέγχει... Θα προσπαθήσω να το διορθώσω (όταν βρω χρόνο θα γράψω σωστή λύση)

[pmav99]

@DimitrisG

Από που είναι τα παραδείγματα?

[DIMITRISG]

Από εδώ:

http://cscircles.cemc.uwaterloo.ca/16-recursion/