Το παρακάτω πρόγραμμα είναι μια διασκευή ενός προγράμματος που υπάρχει στο info ως eertree.
Σκοπός του προγράμματος είναι να δείξει πως παράγουμε όλα τα παλίνδρομα μέρη ενός αλφαριθμητικού. Παλίνδρομο είναι το αλφαριθμητικό που διαβάζεται το ίδιο και από τις δυο πλευρές. Ενός χαρακτήρα αλφαριθμητικό είναι παλίνδρομο.
Η ιδέα του EERTREE είναι των Mikhail Rubinchik, Arseny M. Shur του 2015, όπου ο αλγόριθμος εκτελείτε πολύ γρήγορα,
Σε αυτή τη διασκευή έχουμε μια κλάση που λέγεται ΦτιάξεΔένδρο.
Η κλάση έχει ένα τμήμα που ορίζεται μετά το Κλάση: και έχει ίδιο όνομα με τη κλάση. Αυτό το τμήμα καλείται μέσα από μια κρυφή συνάρτηση που μεταφέρει το σωρό τιμών, δηλαδή μεταφέρει παραμέτρους αν τους χρειαζόμαστε (όχι σε αυτή τη κλάση) και με την εκτέλεση εντολών διαμορφώνουμε το αντικείμενο πριν αυτό παραδοθεί κατά τη κατασκευή. Δείτε ότι και η εσωτερική κλάση έχει έναν "κατασκευαστή" που παίρνει μια ή δυο τιμές (η δεύτερη είναι προαιρετική).
Το αντικείμενο που μας δίνει η ΦτιάξεΔένδρο() έχει τρία μέλη δημόσια, δηλαδή μπορούν να κληθούν έξω από το αντικείμενο. Βάζουμε πάντα το όνομα του αντικειμένου, τη τελεία και το όνομα του μέλους. Αν το μέλος είναι τμήμα και έχει παραμέτρους απλά βάζουμε τις παραμέτρους (χωρίς παρενθέσεις γύρω από τη λίστα παραμέτρων. Αν έχουμε συνάρτηση καλούμε τη συνάρτηση αλλά εδώ έχουμε παρενθέσεις ακόμα και αν δεν έχουμε παραμέτρους.
Το τμήμα ΠάρεΈνα με παράμετρο ένα αλφαριθμητικό. Εδώ καλούμε το τμήμα κάθε φορά που δίνουμε ένα χαρακτήρα. Πριν τη διασκευή μια αντίστοιχη λειτουργία γίνονταν για όλο το αλφαριθμητικό, και έμπαινε η παράμετρος το αλφαριθμητικό με όλα τα στοιχεία. Τώρα μπορούμε να προσθέτουμε χαρακτήρες και όποτε θέλουμε παίρνουμε το αποτέλεσμα (μια τη συνάρτηση Μάζεψε_τα_παιδιά()).
Το τμήμα ΔείξεΤηΔομή που παίρνει με αναφορά ένα αντικείμενο τύπου έγγραφο (έχει κατάληξη $ και γυρίζει αλφαριθμητικό, επίσης το = του κάνει πρόσθεση στο τέλος)
Αυτό που βλέπουμε στη δομή είναι ο αριθμός του κόμβου, ως το κλειδί σε μια λίστα κόμβων (εδώ φαίνονται οι αριθμοί με 0 στην αρχή του αριθμού και πλάτος τριών αριθμών). Μετά είναι το ΜήκοςΤμήματος, όπου έχουμε το -1 στο πρώτο κόμβο. Μετά έχουμε τη κατάληξη (suffix), που έχει σχέση με με μέγεθος του παλίνδρομου, Δείτε ότι στην αρχή είναι 0 και κάποια στιγμή σε ορισμένους κόμβος αλλάζει. Αυτή χρειάζεται για να πάμε προς τα πίσω στο μάζεμα και να μεγαλώνουμε τα παλίνδρομα όταν πρέπει να μεγαλώσουν (πχ στο "t" έχουμε το 5 στο κόμβο 1, πάμε στο 005 και από εκεί βρίσκουμε το "r" και το 6, τυπώνουμε το rτr το οποίο γίνεται ρίζα$ και πάμε στο 006, όπου βρίσκουμε το "e" και το 7, τυπώνουμε το "ertre" και πάμε στο 007, όπου βρίσκουμε το "e" και το 8, τυπώνουμε το "eertree" και πάμε στο 008, όπου όμως δεν υπάρχει στοιχείο στη λίστα με τις άκρες!
Για εξάσκηση πρέπει να φτιάξετε ένα πινακάκι και να εκτελέσετε το πρόγραμμα του ΠάρεΈνα και κάθε φορά γράφουμε τι αλλάζει και γράφουμε τι αλλάζει στη δομή Δένδρο και στους κόμβους που βάζουμε εκεί.
Τη Συνάρτηση Μάζεψε_τα_παιδιά(). Αυτή η συνάρτηση δουλεύει με τη δομή που δείχνει το προηγούμενο τμήμα, και εμφανίζει όλα τα παλίνδρομα. Στη διασκευή αυτή έχει καταργηθεί η αναδρομή (κλήση στον εαυτό της). και έχει μπει ο χειρισμός του σωρού τιμών (που πάντα υπάρχει διαθέσιμος σε κάθε σημείο προγράμματος). Ο σωρός τιμών σε μια συνάρτηση είναι πάντα καθαρός, αν δεν υπάρχουν παράμετροι αλλιώς έχει τις παραμέτρους. Μαζεύουμε τα παλίνδρομα σε ένα αντικείμενο επίσης σωρό τιμών. Όμως αντί να γυρίσουμε το σωρό τιμών γυρνάμε ένα πίνακα μεταφέρουμε αυτόματα τα στοιχεία του σωρού σε ένα πίνακα. Μας βολεύει ο πίνακας για να δώσουμε μετά μια εντολή που πακετάρει τα στοιχεία σε αλφαριθμητικό, η #Γραφή$(). Αυτή η συνάρτηση πρέπει να γραφτεί αμέσως μετά από έναν πίνακα (χειρίζεται το πίνακα σαν μιας διάστασης πίνακα, εφόσον έχει διάσταση!).
Εσωτερικά στη κλάση ΦτιάξεΔενδρο υπάρχουν ιδιωτικά μέλη, ένα από αυτά είναι μια κλάση, η κλάση Κόμβος. Αυτή τη κλάση τη ξέρει μόνο η ΦτιάξεΔένδρο. Ακόμα και η Κλάση Κόμβος έχει ιδιωτικά μέλη! Η ιδιότητα ΜήκοςΤμήματος μόνο διαβάζεται επειδή έχουμε δώσει μόνο το Αξία. Η ιδιωτική [ΜήκοςΤμήματος] κρατάει την τιμή πίσω από την ιδιότητα, και μέσω αυτής βάζουμε αρχική τιμή.
Το πρόγραμμα (το αντιγράφουμε σε ένα τμήμα):
\\ https://rosettacode.org/wiki/eertree
Κλάση ΦτιάξεΔένδρο {
ιδιωτικο:
Δένδρο=Λίστα
α$, Κατάληξη=1
Κλάση Κόμβος {
Ιδιωτικό:
Οι_άκρες_μου=Λίστα
Δημόσιο:
Κατάληξη=0
ιδιοτητα ΜήκοςΤμήματος {Αξία}
Συνάρτηση άκρες(α$) {
=-1 : Αν Υπάρχει(.Οι_άκρες_μου, α$) Τότε =εκφρ(.Οι_άκρες_μου)
}
Συνάρτηση Κλειδί$(εδώ) {
=Εκφρ$(.Οι_άκρες_μου, εδώ)
}
Συνάρτηση Που(εδώ) {
=.Οι_άκρες_μου(εδώ!)
}
Συνάρτηση ΠόσεςΑκρες() {
=Μήκος(.Οι_άκρες_μου)
}
Τμήμα προσθήκη_άκρης (α$, που) {
Προσθήκη .Οι_άκρες_μου, α$:=που
}
Κλάση:
Τμήμα Κόμβος (.[ΜήκοςΤμήματος]) {
Διάβασε ? .Κατάληξη
}
}
Δημόσιο:
Τμήμα ΠάρεΈνα(χ$) {
.α$+=χ$
ι=μήκος(.α$)
ν=.Κατάληξη
Επανάλαβε {
κ=.Δένδρο(ν).ΜήκοςΤμήματος
β=ι-κ-1
Αν β>0 Τότε Αν Μεσ$(.α$,β,1)=χ$ Τότε Έξοδος
ν=.Δένδρο(ν).Κατάληξη
} Πάντα
ε=.Δένδρο(ν).άκρες(χ$)
Αν ε>=0 Τότε .Κατάληξη<=ε :Συνέχισε
.Κατάληξη<=Μήκος(.Δένδρο)
Προσθήκη .Δένδρο, .Κατάληξη:=.Κόμβος(κ+2)
.Δένδρο(ν).προσθήκη_άκρης χ$, .Κατάληξη
Αν .Δένδρο(.Κατάληξη).ΜήκοςΤμήματος=1 Τότε .Δένδρο(.Κατάληξη).Κατάληξη=0 : Συνέχισε
Επανέλαβε { ' ή Επανάλαβε (είναι το ίδιο εδώ)
ν=.Δένδρο(ν).Κατάληξη
β=ι-.Δένδρο(ν).ΜήκοςΤμήματος-1
Αν β>1 Τότε Αν Μεσ$(.α$, β,1)=χ$ Τότε Έξοδος
} Πάντα
ε=.Δένδρο(ν).άκρες(χ$)
Αν ε>=0 Τότε .Δένδρο(.Κατάληξη).Κατάληξη=ε
}
Τμήμα ΔείξεΤηΔομή (&εδώ$){
Για ι=0 έως Μήκος(.Δένδρο)-1
κλ$=Έκφρ$(.Δένδρο, ι)
Για .Δένδρο(ι!) {
εγγραφή$=Μορφη$("{0}{1::-3}{2::-3}",γραφη$(κλ$,"000 "),.ΜήκοςΤμήματος,.κατάληξη)
Αν .ΠόσεςΑκρες()>0 τότε
για κ=0 έως .ΠόσεςΑκρες()-1
εγγραφή$+=" {"+.Κλειδί$(κ)+"}:="+.Που(κ)
επόμενο
τέλος αν
εδώ$=χαρ$(9)+εγγραφή$+{
}
}
Επόμενο
}
Συνάρτηση Μάζεψε_τα_παιδιά() {
Σειρά 0, "", 1, ""
ο=Σωρός
Ενώ Όχι Κενό {
Διάβασε ν, ρίζα$
Για .Δενδρο(ν) {
Μ=.ΠόσεςΑκρες()
Αν Μ=0 Τότε Συνέχισε
Μ--
Για ι=0 Έως Μ {
χ$= .Κλειδί$(ι)
εκεί=.Που(ι)
ρ$ = Αν$(ν=1 -> χ$, χ$+ρίζα$+χ$)
Σωρος ο {Σειρά ρ$}
Βάλε ρ$, εκεί
}
}
}
= Πίνακας(ο)
}
Κλάση:
Τμήμα ΦτιάξεΔένδρο {
Προσθήκη .Δένδρο, 1:=.Κόμβος(-1,1),0:=.Κόμβος(0,1)
}
}
Παλίνδρομο=Λάμδα τόσα (α$) ->{
Εγγραφο εγγραφο$
Δένδρο=ΦτιάξεΔένδρο()
για ι=1 εως μήκος(α$)
Δένδρο.ΠάρεΈνα Μεσ$(α$,ι,1)
επόμενο
τόσα++
εγγραφο$= τόσα+". "+παράθεση$(α$)+{
}
εγγραφο$ = Παράθεση$(Δένδρο.Μάζεψε_τα_παιδιά()#Γραφή$(Παράθεση$(", ")))+{
Δομή:
}
Δένδρο.ΔείξεΤηΔομή &εγγραφο$
=εγγραφο$
}
Έγγραφο Τελικό$
Τελικό$ = Παλίνδρομο("eertree")
Τελικό$ = Παλίνδρομο("banana")
Τελικό$ = Παλίνδρομο("0123214bb5a7aaaa")
Τελικό$ = Παλίνδρομο(Αναπ$("0123214bb5a7aaaa"))
Αναφορά Τελικό$
Πρόχειρο Τελικό$
Εδώ είναι το αποτέλεσμα (που βγάλαμε στο πρόχειρο, έχω προσθέσει χρώμα)
1. "eertree"
"ee", "e", "r", "t", "rtr", "ertre", "eertree"
Δομή:
001 -1 1 {e}:=2 {r}:=4 {t}:=5
000 0 1 {e}:=3
002 1 0
003 2 2
004 1 0
005 1 0 {r}:=6
006 3 4 {e}:=7
007 5 2 {e}:=8
008 7 3
2. "banana"
"b", "a", "n", "ana", "nan", "anana"
Δομή:
001 -1 1 {b}:=2 {a}:=3 {n}:=4
000 0 1
002 1 0
003 1 0 {n}:=6
004 1 0 {a}:=5
005 3 3
006 3 4 {a}:=7
007 5 5
3. "0123214bb5a7aaaa"
"bb", "aa", "aaaa", "0", "1", "2", "3", "4", "b", "5", "a", "7", "a7a", "aaa", "232", "12321"
Δομή:
001 -1 1 {0}:=2 {1}:=3 {2}:=4 {3}:=5 {4}:=8 {b}:=9 {5}:=11 {a}:=12 {7}:=13
000 0 1 {b}:=10 {a}:=15
002 1 0
003 1 0
004 1 0
005 1 0 {2}:=6
006 3 4 {1}:=7
007 5 3
008 1 0
009 1 0
010 2 9
011 1 0
012 1 0 {a}:=16
013 1 0 {a}:=14
014 3 12
015 2 12 {a}:=17
016 3 15
017 4 16
4. "aaaa7a5bb4123210"
"aa", "bb", "aaaa", "a", "7", "5", "b", "4", "1", "2", "3", "0", "232", "12321", "a7a", "aaa"
Δομή:
001 -1 1 {a}:=2 {7}:=6 {5}:=8 {b}:=9 {4}:=11 {1}:=12 {2}:=13 {3}:=14 {0}:=17
000 0 1 {a}:=3 {b}:=10
002 1 0 {a}:=4
003 2 2 {a}:=5
004 3 3
005 4 4
006 1 0 {a}:=7
007 3 2
008 1 0
009 1 0
010 2 9
011 1 0
012 1 0
013 1 0
014 1 0 {2}:=15
015 3 13 {1}:=16
016 5 12
017 1 0
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου
You can feel free to write any suggestion, or idea on the subject.