Προγραμματιστική πρόκληση python

έχουμε την γεννήτρια φιμπονάτσι:

def fib():
    x_old = 0
    x = 1
    while True:
        yield x
        x, x_old = x + x_old, x

Το ερώτημα είναι πώς θα φτιάξουμε μια λίστα f με τούς πρώτους ας πούμε 100000 αριθμούς.

βάζω χρόνο στην υποβολή μέχρι την δευτέρα. :stuck_out_tongue:

Σημείωση: μόνο Python3

2 Likes

Με λεξικό μπορούμε :stuck_out_tongue: ;;;

coroutines στα Ελληνικά άσχετε :stuck_out_tongue:

ο καθένας είναι ελεύθερος να κάνει ό,τι καταλαβαίνει. :stuck_out_tongue:

αν μηλαμε για υπορουτινες εννοουμε subroutines :slight_smile: οχι coroutines :slight_smile:

O @lucinos έβαλε την άσκηση για να μας φέρει σε επαφή με κάποια πράγματα που ξεφεύγουν από την έννοια της υπορουτίνας μιας γλώσσας προγραμματισμού. Μια κλασική υπορουτίνα έχει ένα σημείο εισόδου και ένα σημείο εξόδου. (Μπορεί να πέφτει σε ατέρμνονο βρόγχο ή να έχει πολλαπλά σημεία εξόδου, αλλά δεν αλλάζει πολύ η κατάσταση). Τυπικά η μια υπορουτίνα καλεί μια άλλη και χρησιμοποιείτε μια στοίβα για διαχείρηση.

Ο κώδικάς που παρουσίασε ο @lucinos δεν έχει ένα σημείο εξόδου, είναι κάτι που μπορεί να θεωρηθεί πως τρέχει συνεχώς και παράγει τιμές όταν χρειαστεί. Αλλιώς μπορείς να το δεις σαν ενα GOTO με αναβολικά. Ποιο τεχνικά είναι μια γεννήτρια συνάρτηση, κάτι που παράγει τιμές κατά ζήτηση, και μπορεί να χρησιμοποιηθεί για να δεις άπειρες δομές δεδομένων όπως μια άπειρη ακολουθία όπως αυτή την περίπτωση.

Είμαι σίγουρος πως ο @lucinos θα τα εξηγήσει καλύτερα και λιγότερα θεωρητικά, αλλά από το γενικό προς το ειδικό κάποιες έννοιες για όποιον θέλει να το ψάξει παραπέρα. Να προειδοποιήσω πως οι έννοιες αυτές τις τελευταία δεκαετία έχουν γίνει κοινό κτήμα στις γλώσσες προγραμματισμού της πιάτσας, και είναι κάπως δύσπευπτες σε άδεια στομάχια


Μπορείτε να το δείτε σαν τον καταχωρήτη Programm Counter μαζί με ένα Stack Register (ή μια κλειστότητα) για να το πω όσο ποιο μπακάλικα μπορώ


Σαν να κάνεις GOTO ανάμεσα σε δυο διαφορετικά προγράμματα, ώστε να μοιάζει πως δυο πράγματα τρέχουν μαζί, πάλι με μια μπακάλικη λογική


Μπακάλικα ένα GOTO που να αποσυμπλέκει την έννοια της διάσχισης (for loop) κάποιων δεδομένων και της επεξεργασίας τους.


Εδώ είμαστε σε ποιο γνώριμα μονοπάτια είναι ενα αντικείμενο που μας βοηθά να διασχίσουμε μια δομή δεδομένων.

Αλλά όπως είπα αυτά είναι ψιλά γράμματα. Αν τα ξέρεις και τα υποστηρίζει η γλώσσα προγραμματισμού που χρησιμοποιείς μπορείς να γράψεις ποιο εκφραστικά προγράμματα. Κάποια στιγμή θα γίνουν κοινό κτήμα, αλλά αυτό θα πάρει καμία δεκαετία ακόμα :stuck_out_tongue:

Ακόμα κανείς δεν έχει προσπαθήσει :frowning:

Έχω σκεφτεί διαφόρους τρόπους προσέγγισης, έδωσα και ονόματα :stuck_out_tongue:

  1. ο αντικανονικός
  2. ο ωμός
  3. ο έξυπνος
  4. ο απλός
  5. ο έτοιμος
  6. ο γκουρού

Δεδομένου και ότι δεν γνωρίζω όλες τις λεπτομέρειες για το θέμα, δεν αποκλείω καθόλου να υπάρξουν και άλλες προσεγγίσεις!

Όποιος δίνει λύσεις ας προσπαθήσει να μαντέψει αν ανήκει και σε ποια από τις παραπάνω κατηγορίες! Αν σκεφτείτε διαφορετικούς τρόπους λύσης δώστε όσους σκέφτεστε.

Σκοπεύω αργότερα σήμερα να δώσω την «αντικανονική» λύση, για να βοηθήσω να μπούμε στην λογική τής yield, και λέω αύριο να δώσω την «ωμή» λύση. Την δευτέρα σιγά-σιγά τις υπόλοιπες.

1 Like

Θα δημιουργήσω δικιά μου κατηγορία.
Ο κάφρος! (Μάλλον ανήκει η λύση είτε στο 4 είτε στο 2)

def fib():
    x_old = 0
    x = 1
    while True:
        yield x
        x, x_old = x + x_old, x
# Αύξησε το n με δικιά σου ευθύνη!!!
def main(n=1000):
	x=fib()
	j=0
	file=open("fibo.txt","w")
	for i in x:
		if (j<=n):
			file.write("%s %s\n" % (j,i))
		else:
			break
		j+=1
	file.close()

if __name__ == '__main__':
    import sys
    try:
        n = int(sys.argv[1])
        main(n)
    except IndexError:
        main()
    except ValueError:
        print(':P')
1 Like

Είναι ανάμεσα στον ωμό και στον έξυπνο :stuck_out_tongue:

Καμμία σχέση με τον απλό.

1 Like

Εγώ αυτό που ξέρω είναι ότι πρέπει να πάμε για καινούριο μηχάνημα…:rofl:

Ποιο καθαρά

def printFib(n=1000):
    file=open("fibo.txt","w")
    for i in range(n-1):
         file.write("%s %s\n" % (i+1,fib()))
    file.close()
1 Like

Θα δώσω για αρχή, για να βλέπουμε σιγά-σιγά πώς λειτουργεί η yield την «αντικανονική» λύση.

Κατ, αρχήν το προφανές πρόβλημα είναι ότι ο βρόχος στην fib δεν φαίνεται να τερματίζει. Εμείς θέλουμε να εκτελεστεί n φορές οπότε ας αλλάξουμε την fib :stuck_out_tongue:

 def fibs(n):
    x_old = 0
    x = 1
    for i in range(n):
        yield x
        x, x_old = x + x_old, x

η fib και η fibs αυτό που κάνουν είναι να ορίζουν μια ακολουθία. Για την fibs που τερματίζει είναι εύκολο να την μετατρέψουμε σε λίστα.

f = list(fibs(10))

έχουμε λίστα με τούς πρώτους 10 αριθμούς και

f = list(fibs(100000))

έχουμε λίστα με τούς πρώτους 100000 αριθμούς.

Φυσικά η «λύση» αυτή παραβιάζει την εκφώνηση αφού δεν χρησιμοποιήσαμε την fib όπως δόθηκε.

Οπότε είναι κακά ορισμένη η fib;

Στην δική μου άποψη οι συναρτήσεις και γενικά οι ορισμοί μας θα πρέπει να κάνουν τα λιγότερα δυνατά. Οπότε μια έξτρα λειτουργία όπως η καταμέτρηση τών όρων δεν θα πρέπει να είναι ενσωματωμένη στον ορισμό. Η ακολουθία φιμπονάτσι είναι μια άπειρη ακολουθία άρα για μένα είναι λογικό να οριστεί ως μια άπειρη ακολουθία.

Υπάρχουν βέβαια και αντεπιχειρήματα σε αυτήν την λογική, σε κάθε περίπτωση η ιδέα είναι να δούμε κάποια πράγματα για τις ακολουθίες στην python.

Ως τώρα έχει δοθεί μία λύση πολύ κοντινή σε αυτήν που εννοούσα ως ωμή.

1 Like

Η «ωμή» λύση.

n = 100
f = []
i = 0
for x in fib():
    f.append(x)
    i += 1
    if i == n: break

οπότε δημιουργείται διαδοχικά η λίστα.

μπορούμε επίσης καλύτερα να την συμμαζέψουμε σε μια συνάρτηση

def fibs(n):
    f = []
    i = 0
    for x in fib():
        f.append(x)
        i += 1
        if i == n: return f

και να δημιουργήσουμε την λίστα με την εντολή

f = fibs(10)

Ένα πρόβλημα με αυτήν την λύση είναι ότι θέλουμε να αποφύγουμε την διαδοχική δημιουργία τής λίστας μέσα από εντολές append, κάτι που δεν είχαμε χρειαστεί στην «αντικανονική» λύση. Αυτό για να κατευθύνω προς τις υπόλοιπες λύσεις.

Αρχικά, εγώ μόνο με το append μπόρεσα μόνη μου να καταφέρω κάτι:

    f = []
for y in fib():
f.append(y)
if y > 200:
    break
print(f)

Αφού όμως το είχε πάρει το ποτάμι, και μίλησες για άλλες λύσεις, σκέφτηκα μήπως αυτή έχει να κάνει με συνοπτική λίστα. Αφού έφαγα καμιά-100σταριά ώρες στο ίντερνετ διαβάζοντας τι είναι αυτό το yield και τί κάνει και αφού έμαθα και για την next, με πολλή βοήθεια γενικά, έχω να καταθέσω αυτό:

y = fib()
f = [next(y) for _ in range(30)]
print(f) 

Δεν ξέρω εάν είναι ανάμεσα στις λύσεις που ζητήθηκαν, πάντως θα ήθελα να μάθω ποιες είναι τελικά αυτές γιατί πραγματικά είναι τόσο ενδιαφέρον όλο αυτό… Ερώτηση: εάν αυτό με το append είναι η ωμή λύση, η απλή ποιά είναι;;

3 Likes

Καταρχήν δεν «έχω ζητήσει» συγκεκριμένες λύσεις. Έχω σκεφτεί κάποιες λύσεις και θα είναι ενδιαφέρον αν κάποιος σκεφτεί και κάποια έξω από αυτές.

Η λύση σου είναι ακριβώς η «απλή».

Αυτός είναι ακριβώς ο σκοπός τής «πρόκλησης». Δεν είναι να εξεταστεί η γνώση, είναι το ίδιο το ψάξιμο.