Τετάρτη, 10 Φεβρουαρίου 2016

Παράδειγμα με Γρήγορη Ταξινόμηση (ανανέωση)

Αυτή είναι η δεύτερη έκδοση υπολογισμού υποσυνόλων για ένα σύνολο αριθμών, όπου θέλουμε να βρούμε τους δυνατούς συνδυασμούς που δίνουν ένα άθροισμα. Επειδή ο αλγόριθμος βρίσκει καμία φορά τα ίδια νούμερα με άλλη σειρά, τα ταξινομούμε και μετά κοιτάμε αν υπάρχουν στο έγγραφο που τα αποθηκεύουμε. Μάλιστα με μια εντολή Πρόχειρο Α$ τα γράφω στο πρόχειρο.

Η ταξινόμηση γίνεται σε σωρό. Ο σωρός τιμών της Μ2000 μπορεί να πάρει οτιδήποτε τιμές, αριθμητικές, αλφαριθμητικές, ακόμα και ένα πίνακα ή ένα αντικείμενο (με ότι θέλουμε μέσα), μπορεί να είναι σε ένα στοιχείο του σωρού. Μπορούμε επίσης να ανοίξουμε νέο σωρό. Ο νέος γίνεται τρέχων σωρός και όταν κλείνει το μπλοκ, ότι έχει μέσα  διαγράφεται. Με το κλείσιμο έρχεται στο προσκήνιο ο προηγούμενος σωρός! Μπορούμε να σηκώνουμε τιμές με την Διάβασε μόνο, που διαβάζει από την κορυφή του. Αν δείτε άλλα παραδείγματα, με συναρτήσεις και τμήματα, η διάβασε συνδέει και αναφορές. Όλα αυτά τα βρίσκει στο σωρό τιμών. (δεν έχει σχέση με return stack).
Μπορούμε να κάνουμε όμως μερικά ωραία πράγματα όπως, να δούμε τις τιμές (για αλφαριθμητικά και για αριθμούς) σαν να διαβάζουμε πίνακα (δεν μπορούμε όμως να γράψουμε όπως γράφουμε πίνακα). Αυτό γίνεται με την ΤιμήΣωρού() και ΤιμήΣωρού$(), και να δούμε τι τύπο έχει πριν διαβάσουμε με την ΣωρούΤύπος$(). Η αρίθμηση ξεκινάει από το 1, που είναι η κορυφή. Επίσης όμως έχουμε μερικά στοιχεία από την Forth. όπως η Πάνω που βγάζει αντίγραφο πάνω από Ν άλλα (χωρίς νούμερο διπλασιάζει την κορυφή), την Φέρε που φέρνει από το Ν στοιχείο στη κορυφή, τη ΦέρεΠίσω που στέλνει την κορυφή στη Ν θέση. Μπορούμε να πετάξουμε στοιχεία χωρίς να τα διαβάσουμε με την Πέτα. (Over, Shift, ShiftBack, Drop)
Επίσης εκτός από τη Βάλε που βάζει πάντα στη θέση 1 και ότι είχε αυτή γίνεται 2 κ.ο.κ, έχουμε και την Σειρά η οποία βάζει στο τέλος, μετά το τελευταίο στοιχείο. Ξέρουμε πόσα στοιχεία έχει ο σωρός, με την Κενό αν δεν έχει τίποτα και την Μέγεθος.Σωρού που μας δίνει ακριβώς το νούμερο.

Ορισμένες εντολές που μπορεί να επιστρέψουν διαφορετικό αριθμό αποτελεσμάτων χρησιμοποιούν τον σωρό. Η Εύρεση δίνει 0 αν δεν βρει στο έγγραφο αυτό που ψάχνουμε ή δίνει θέση στο όλο έγγραφο, παράγραφο και θέση στη παράγραφο.. Εδώ στο πρόγραμμα μας ενδιαφέρει το 0, να μην βρει δηλαδή για να καταχωρήσουμε τα νούμερα.

Η ρουτίνα ταξινόμησης είναι η Quick Sort, η οποία δουλεύει με κλήση στον εαυτό της. με Όριο.Αναδρομής 100000 μπορούμε να φτάσουμε χωρίς πρόβλημα τις 100 χιλιάδες κλήσεις.
Και οι συναρτήσεις και τα τμήματα (αυτά με κλήση με την Κάλεσε) έχουν αναδρομή αλλά περιορίζονται από τον stack  του exe αρχείου που το έχω αυξήσει για περίπου 14300 κλήσεις. Τα τμήματα και οι συναρτήσεις είναι "βαριά" αντικείμενα εκτέλεσης. Οι ρουτίνες είναι μέρη τμημάτων/συναρτήσεων. δεν έχουν αντικείμενο εκτέλεσης, και βλέπουν ότι βλέπει το τμήμα που τρέχουν. Έτσι εδώ στη πάρε_ένα() έχουμε μίξη μεταβλητών. από το τμήμα. (δεν είναι γενικές του τμήματος), όπως το έγγραφο A$.

Ο αλγόριθμος που εκτελείται είναι απλός, για Ν αριθμούς καλούμε μια διαδικασία (Ν-κ) επί Ν-1 φορές, όπου κ τα στοιχεία που είναι μεγαλύτερα από το 9. Σε κάθε επανάληψηκάνουμε μια ανίχνευση από το σημείο όπου σίγουρα είναι ένας αριθμός μικρότερος του 9 (αν είναι ίσος βγαίνει άμεσα) και μετακινούμαστε με το βήμα που μας δίνει η επανάληψη. Στην ουσία μας κάνει μια περιστροφή στα νούμερα με αυξανόμενο βήμα αλλά στο τελείωμα πέφτει σε βήμα συν ένα. Δεν έχω υπολογίσει μαθηματικά την λύση, αλλά έχω κάνει δοκιμές και δουλεύει (τα μαθηματικά είναι φαντασία. και κάπως έτσι σκέφτηκα...Άλλο πράγμα η απόδειξη...). Το σημείο πάντως με το οποίο "κέρδισε" η ρουτίνα είναι σε αυτό   αν κ+άσε_τόσα >μεγ1 τότε άσε_τόσα=1 όπου ελέγχουμε πριν υπερβούμε και χάσουμε τα τελευταία στοιχεία, κατά ένα. Έτσι ουσιαστικά αφού δίνουμε και το Ν-1  θα σαρώσουμε και κατά ένα το φάκελο και ίσως για το λόγο αυτό να γλιτώσουμε μια επανάληψη αν ξεκινήσουμε από το 2 και όχι το 1. (το δοκίμασα δίνει 10% λιγότερο χρόνο εκτέλεσης, δηλαδή το   για τόσα=1 έως μεγ1... να γίνει   για τόσα=2 έως μεγ1  


Εδώ έχουμε ορίσει το 9 ως το ζητούμενο αποτέλεσμα. Αναβάθμισα το πρόγραμμα, έβγαλα μια Αν από τη ταξινόμηση και έβαλα μια Ενώ στο πάρε_ένα()  (προσοχή στις ρουτίνες τα ονόματα πρέπει να δίνονται ως έχουν μικρά - μεγάλα και τόνοι είναι σημαντικά - αυτό γίνεται επειδή δεν γράφονται σε λίστα και κάθε φορά που τις καλούμε αναζητούνται από το τέλος..ώς έχουν, και για το λόγο αυτό βάζουμε τις ρουτίνες στο τέλος). Όλα τα άλλα αναγνωριστικά γίνονται κεφαλαία και βρίσκονται γρήγορα με χρήση εσωτερικά πίνακα κατακερματισμού (εκτός από αναγνωριστικά εντολών που αναζητούνται ξεχωριστά σε κάθε εντολή)

Αποτελέσματα:
Σύνολο  1, 3, 4, 6, 5, 4,12, 13, 7, 8
001.   1,   4,   4 
002.   1,   8 
003.   3,   6 
004.   1,   3,   5 
005.   4,   5 


Αποτελέσματα:
Σύνολο 1, 1, 1, 3, 3, 3, 4, 5, 1, 2
001.   1,   1,   1,   3,   3 
002.   1,   2,   3,   3 
003.   1,   3,   5 
004.   1,   1,   2,   5 
005.   1,   1,   3,   4 
006.   1,   1,   1,   2,   4 
007.   3,   3,   3 
008.   4,   5 
009.   2,   3,   4 


\\ ετοιμασία οθόνης
Οθόνη 5 : Φορμα 80,50 : Πένα 14
\\ ετοιμασία πίνακα
μεγ=10
μεγ1=μεγ-1
Πίνακας Α(μεγ)
Α(0) = 1, 1, 1, 3, 3, 3, 4, 5, 1, 2
'Α(0) = 1, 3, 4, 6, 5, 4,12, 13, 7,8
\\ μεταβλητές


Τοπικές σκοπός=9, συνολο, μισό=μεγ Δια 2
\\Ετοιμασία Εξαγωγής
Κάνε φόρμα4$(Χ)=Δεξι$("    "+Γραφή$(Χ,"##0"),4)
Έγγραφο Α$={Αποτελέσματα:
                        Σύνολο 1, 1, 1, 3, 3, 3, 4, 5, 1, 2
                        }
\\ κύρια επανάληψη
Για κ=0 Έως μεγ1 {
      Αν α(κ)<σκοπός Τότε {
            Για τόσα=1 Έως μεγ1 { \\ δοκίμασε με τόσα=2
                        πάρε_ένα(κ, σκοπός, τόσα)
                 }
       }
}
Διόρθωσε Α$ \\ ανοίγει τον διορθωτή Για να συμπληρώσουμε κάτι
Πρόχειρο Α$ \\ εξαγωγή στο πρόχειρο
Σώσε.Έγγραφο Α$, "Αποτελέσματα.txt"
Αναφορά Α$ \\ στην οθόνη
\\ εδώ τερματίζει ο διερμηνευτής.
Ρουτίνα πάρε_ένα(χ, ν, άσε_τόσα)
      Τοπικές κ=1, σουμα, κκ, μμ, προχ$
      \\ αναβαθμίζουμε σε Έγγραφο την τοπική
      Έγγραφο προχ$=""
      μμ=χ
      Σωρός Νέος {
            \\ ανοίγουμε ένα σωρό τιμών
            \\ βάζουμε τιμές με την βάλε και τις δαβάζουμε με την Διάβασε
            \\ καθαρίζει στο πέρας του μπλοκ    
            Ενώ ν>0 {
                        χ=(μεγ+χ ) Υπολ μεγ
                        Αν Α(χ)<=ν Τότε ν-=Α(χ) : σουμα+=Α(χ) : Βαλε Α(χ )
                        Αν κ+άσε_τόσα >μεγ1 Τότε άσε_τόσα=1
                        κ+=άσε_τόσα
                        Αν κ>μεγ1 Τότε Έξοδος
                        χ=μμ+κ
            }
            Αν σούμα=σκοπός Τότε {
                  Αν όχι κενό Τότε ταξινόμηση(1,Μέγεθος.Σωρού)
                  Προχ$="."
                  Ενώ όχι κενό {
                        Διάβασε κκ
                        Αν Εγγράφου.Μήκος(Προχ$)>1 Τότε Προχ$ = ","
                        Προχ$ = φόρμα4$(κκ)
                  }
                  Προχ$ = {
                  }
                  Εύρεση Α$, Προχ$
                  Αν Αριθμός=0 Τότε {
                        συνολο++
                        Α$ =Γραφή$(σύνολο, "000")+Προχ$
                  }
            }  
      }
Τέλος Ρουτίνας
Ρουτίνα ταξινόμηση(αρχικό, τελικό)
      Τοπικές πράγμα, ι=αρχικό, όριο=τελικό+1
      Αν όριο >2 Τότε Φέρε (όριο+ι) Δια 2
      Διάβασε πράγμα
      όριο--
      Ενώ ι<όριο {
            Αν πράγμα<ΤιμήΣωρού(ι) Τότε {
                  όριο--
                  Αν ι>1 Τότε Φέρε ι
                  ΦέρεΠίσω όριο
            }  Αλλιώς ι++
      }
      Αν ι>όριο Τότε ι=όριο
      Βάλε πράγμα : ΦέρεΠίσω ι
      Αν ι>αρχικό Τότε ταξινόμηση(αρχικό,ι-1)
      Αν τελικό>ι Τότε ταξινόμηση(ι,τελικό)
Τέλος Ρουτίνας








Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου