Υπάρχει μαθηματικός τύπος ταυτοποίησης αριθμών με αναγραμματισμένα ψηφία;

[migf1]

Καλησπέρα,

 

υπάρχει κάποιος μαθηματικός τύπος που να βρίσκει αν 2 (ή περισσότεροι) θετικοί ακέραιοι είναι ο ένας αναγραμματισμός ψηφίων του άλλου;

 

Έχω λύσει το 52ο πρόβλημα του Project Euler...

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

 

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

αλλά θέλω να βελτιώσω την ταχύτητα εκτέλεσης, γιατί τώρα μετατρέπω τους αριθμούς σε c-strings και κατόπιν χρησιμοποιώ ένα ιστόγραμμα με βάση τον πίνακα ASCII για τη συχνότητα εμφάνισης του κάθε ψηφίου στους αριθμούς.

 

Αν υπήρχε κάποιος σχετικά απλός μαθηματικός τύπος που θα δούλευε απευθείας πάνω στα νούμερα θα ήταν καλύτερα.

 

Γνωρίζει κανείς κάτι;

[Technology fan]

Δεν ξέρω αν σε βοηθά αλλα μπορείς να βρείς πολύ εύκολα οτι δύο αριθμοί ΔΕΝ είναι αναγραμματισμοί ο ένας του άλλου, πχ προσθέτοντας/πολλαπλασιάζοντας τα επιμέρους ψηφία τους, αν είναι αναγραμματισμοί τότε τα έχουν ίδιο άθροισμα/γινόμενο, αλλα αυτό δουλεύει μονόδρομα,

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

 

edit :

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

Θα χρησιμοποιήσω ένα πίνακα ας τον πω Α μεγέθους όσο και το πλήθος των αριθμών.. (ελπίζω να μην είναι πρόβλημα αυτό). Θα προσπαθήσω να περιγράψω τι θα κάνει ο πίνακας με βάση τα περιεχόμενα του

 

Α[0]=0

Α[1]=1

.

.

.

Α[9]=9

Α[10]=01

Α[11]=11

Α[12]=12

.

.

.

Α[19]=19

Α[20]=02

Α[21]=12

Α[22]=22

Α[23]=23

 

Δηλαδή θα μετατρέπεις τον κάθε αριθμό σε string και θα τον ταξινομέις πρίν τον βάλεις στον πίνακα,

και θα περιέχει αυτά

 

Α[125874]=124578

Α[251748]=124578

 

Οπότε κάνεις έλεγχο αν τα strings τους συμπίπτουν, Αν σου φαίνεται πολύς χρόνος η ταξινόμηση σκέψου οτι το κάνεις μία φορά και μόνο, και μετά θα χρησιμοποιείς τον πίνακα σου.

 

και κόστος γραμμής "if (strcmp(A[x],A[2x]))" είναι O(1)

[PCharon]

Μαθηματικός τύπος με κάποιες αριθμητικές πράξεις όπως το εννοείς δε ξέρω και δε νομίζω κιόλας να υπάρχει.

 

τώρα μετατρέπω τους αριθμούς σε c-strings

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

 

 

Άλλη μέθοδος είναι: int > μετατροπή int σε char string > sorting κατά char > μετατροπή char string σε int > απλή σύγριση νέων integers (δηλαδή σε χώρο αν το προπαρασκευάσεις χρειάζεσαι δύο int για κάθε αριθμό, ένα με τον αριθμό κι ένα που προέκυψε ως παραπάνω). Αν κατάλαβα καλά τί κάνεις, τότε αυτό θα πρέπει να είναι πολύ πιο γρήγορο και πιο «οικονομικό» αν το υλοποιήσεις καλά.

[migf1]

@PCharon: δυστυχώς η ταξινόμηση και κατόπιν σύγκριση ψηφίων ένα προς ένα είναι πιο χρονοβόρα από το ιστόγραμμα που χρησιμοποιώ τώρα.

 

@Techonology fan: ναι, πεπερασμένοι είναι. 5 αριθμοί είναι όλοι κι όλοι κάθε φορά για κάθε i του loop (2x, 3x, 4x, 5x και 6x). Τους βάζω ήδη σε πίνακα). Το άθροισμα και το γινόμενο δεν ισχύουν σαν κριτήρια, διότι π.χ. οι 24 και 15 δίνουν και οι δυο άθροισμα 6 χωρίς να είναι αναγραμματισμοί (όπως επίσης οι 16 και 32 δίνουν και οι 2 γινόμενο 6, αλλά δεν είναι αναγραμματισμοί. Εκτός αν δεν έχω καταλάβει τι ακριβώς εννοείς, ιδιαίτερα όταν λες "μονόδρομα". Για εξήγησέ το λίγο παραπάνω αν θέλεις.

 

Όσο για την τρέχουσα υλοποίηση, αφού μετατρέψω πρώτα το καθένα από τα 5 νούμερα σε c-strings και τα βάλω σε ένα array, εξετάζω το 1ο με όλα τα υπόλοιπα, ανά ζεύγη δηλαδή... 1 με 2, 1 με 3, 1 με 4 και 1 με 5. Αν έστω και σε ένα από τα ζεύγη τα strings του δεν είναι αναγραμματισμοί, τότε διακόπτω την διαδικασία με επιστροφή FALSE.

 

Όσο για τον έλεγχο για το αν 2 c-strings είναι το ένα αναγραμματισμός του άλλου, βάζω ENA loop να τρέχει μέχρι να τελειώσουν οι χαρακτήρες του μακρύτερου από τα 2 c-strings (ΧΩΡΙΣ ΧΡΗΣΗ ΤΗΣ strlen). Mέσα στο loop για κάθε χαρακτήρα του 1ου string αυξάνω κατά 1 την τιμή που του αντιστοιχεί στο ιστόγραμμα ( histogram[ *s ]++; ), ενώ για κάθε χαρακτήρα του 2ου string αφαιρώ κατά 1 την τιμή που του αντιστοιχεί στο ιστόγραμμα ( histogram[ *t ]--; ) .

 

Οπότε, πιάνοντας μετά το ιστόγραμμα από την αρχή η πρώτη μη-μηδενική τιμή σηματοδοτεί πως ΔΕΝ ισχύει αναγραμματισμός. Αυτή η διαδικασία κοστίζει σε χρόνο το μήκος του μακρύτερου string + το μήκος του ιστογράμματος βλέπε EDIT παρακάτω.

 

Πολύ λιγότερο δηλαδή από την ταξινόμηση των 2 strings και την κατόπιν σύγκρισή τους.

 

Στον κώδικα που έχω γράψει τώρα υπάρχουν 2 σημεία που θέλουν βελτιστοποίηση. Καταρχήν τη μετατροπή των αριθμών σε c-strings τώρα την κάνω με snprintf αντί για χειροκίνητα με / και %, γιατί δεν ξέρω ποιος από τους 2 τρόπους είναι ο πιο expensive, οπότε για αρχή πήρα την εύκολη λύση ) Έπειτα, επειδή τη συνάρτηση για τον έλεγχο αναγραμματισμών ανάμεσα σε 2 strings την χρησιμοποίησα ατόφια από άλλο project μου, ιστογραφεί όλο τον extended πίνακα ASCII (256 χαρακτήρες), ενώ για το συγκεκριμένο πρόβλημα χρειάζεται να ιστογραφηθούν μονάχα οι 10 χαρακτήρες, από τον '0' έως και τον '9'.

 

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

 

Τον μέχρι τώρα κώδικα (σε C) τον έχω ανεβάσει στο ideone.com για όποιον θέλει να δει λεπτομέρειες: https://ideone.com/Zmum3 (αλλάζοντας το NMULS μπορείτε να αλλάξετε το πλήθος των πολλαπλάσιων, αλλά μέχρι 5 πάει καλά... όταν βάζω 6 το "σκοτώνω" μετά από κανά 5λεπτο γιατί βαριέμαι να το περιμένω... ).

 

ΥΓ. Προσπαθώ να αποφύγω υλοποίηση με anagram trees

 

EDIT: Μια μικρή διόρθωση, ήδη ΔΕΝ εξετάζω όλο το ιστόγραμμα στο 2ο στάδιο της s_isanagram(char *s, char *t), αλλά μόνο τους χαρακτήρες του κοντύτερου από τα 2 strings, άρα ναι μεν το ιστόγραμμα είναι πίνακας 256 χαρακτήρων, αλλά ουσιαστικά εξετάζονται μόνο οι χαρακτήρες του κοντύτερου string.

 

Άρα ο συνολικός χρόνος είναι: μήκος μακρύτερου string + μήκος κοντύτερου string (μιλάω για τη συνάρτηση που εξετάζει 2 strings)... O(m+n)

[PCharon]

@PCharon: δυστυχώς η ταξινόμηση και κατόπιν σύγκριση ψηφίων έναν προς ένα είναι πιο χρονοβόρα από το ιστόγραμμα που χρησιμοποιώ τώρα.

Η σύγκριση δε θα γίνεται ως ψηφία, μάλλον λάθος κατάλαβες, αλλά ως int. Δηλαδή έχω πχ τους int 1258714 και 8514721 που γίνονται αντίστοιχα οι int 1124578 και 1124578 και απλά συγκρίνω int (αν 1124578 == 1124578 τότε ισχύει αναγραμματισμός).

 

[edit] αυτό που είπα είναι σαν αυτό που έγραψε μετά το edit o Technology fan αλλά πολύ πιο γρήγορο διότι συγκρίνεις int (ένα απλό if) και όχι char strings.

[migf1]

Η σύγκριση δε θα γίνεται ως ψηφία, μάλλον λάθος κατάλαβες, αλλά ως int. Δηλαδή έχω πχ τους int 1258714 και 8514721 που γίνονται αντίστοιχα οι int 1124578 και 1124578 και απλά συγκρίνω int (αν 1124578 == 1124578 τότε ισχύει αναγραμματισμός).

Ωραίο!

(αν και προϋποθέτει και 2η μετατροπή: int->string και string->int).

 

ΥΓ. Διαβάζω τώρα και το edit του Technology fan.

[Technology fan]

Απλά αν γίνει η σύγκριση ως int , πιθανόν να υπάρχει πρόβλημα στη περίπτωση όπου ο αριθμός περιέχει μηδέν, πχ 102365 -> 012356

όμως λύση στο πρόβλημα αυτό δίνεται αν ταξινομηθούν ανάποδα δηλαδή 102365 -> 653210

οπότε τα μηδενικά να μαζεύονται στο τέλος και όχι στην αρχή...

[migf1]

...

Δηλαδή θα μετατρέπεις τον κάθε αριθμό σε string και θα τον ταξινομέις πρίν τον βάλεις στον πίνακα,

και θα περιέχει αυτά

 

Α[125874]=124578

Α[251748]=124578

 

Οπότε κάνεις έλεγχο αν τα strings τους συμπίπτουν, Αν σου φαίνεται πολύς χρόνος η ταξινόμηση σκέψου οτι το κάνεις μία φορά και μόνο, και μετά θα χρησιμοποιείς τον πίνακα σου.

 

και κόστος γραμμής "if (strcmp(A[x],A[2x]))" είναι O(1)

Λοιπόν κάτσε να τα πάρουμε με τη σειρά, μπας και τα ταξινομήσω κι εγώ σωστά στο μυαλό μου (το οποίο το έχω ταλαιπωρήσει αρκετά από το πρωί ).

 

Καταρχήν για κάθε αριθμό θέλουμε μια μετατροπή σε string και μια ταξινόμηση ψηφίων πριν το βάλουμε στον πίνακα (ως strings τα βάζουμε, αν κατάλαβα σωστά). Υποθέτοντας πως ταξινομούμε τα ψηφία με quick-sort, έχουμε μέσο χρόνο: Ο( n + n*log(n) )... θεωρώ πως η μετατροπή από int σε string στοιχίζει n (όσα δηλαδή τα ψηφία του αριθμού).

 

Αν το πλήθος των παραγόμενων αριθμών είναι k, τότε για να γεμίσουμε τον πίνακα θέλουμε: O( k * (n + n*log(n)) ).

 

Αυτό σαν προεργασία, η οποία μας έχει στοιχίσει και πάρα πολύ σε μνήμη λόγω του πίνακα, ο οποίος μπορεί να γίνει πραγματικά τεράστιος, συν ότι δεν μπορούμε να προϋπολογίσουμε το μήκος του, άρα μάλλον θα χρειαστεί συν τοις άλλοις να δουλέψουμε με linked-list αντί για array. Μετά, η γραμμή: "if (strcmp(A[x],A[2x]))" δεν έχει κόστος O(1) όπως αναφέρεις παραπάνω. Κόστος O(1) έχει μόνο αν τα strings A[x] και A[2x] έχουν διαφορετικό τον 1ο τους χαρακτήρα... αλλιώς αν είναι ίδια, έχει κόστος O(n), όπου n το πλήθος των χαρακτήρων τους

 

Με την υλοποίηση του ιστογράμματος που έχω κάνει τώρα η μόνη προεργασία που γίνεται είναι η μετατροπή του αριθμού σε string πριν τον αποθηκεύσουμε στον πίνακα, και κοστίζει O(n) συν ότι ο πίνακας είναι δραματικά μικρότερος (ίσος με το πλήθος των πολλαπλάσιων... 5 στην περίπτωσή μας, και κυρίως με προβλέψιμο μήκος εξαρχής, μέσω της σταθεράς NMULS).

 

Θα μπορούσαμε να βάλουμε στο στάδιο της προεργασίας και την ιστογράφηση των ψηφίων του κάθε αριθμού, που στοιχίζει O(n) (άρα συνολικά O(2*n) που εξακολουθεί να είναι μικρότερο του O(n + n *logn) που χρειάζεται ο τρόπος που περιγράφεις). Αλλά στην τρέχουσα υλοποίηση μου δουλεύω απευθείας με ζεύγη αριθμών με την ταυτόχρονη ιστογράφηση ΚΑΙ ΤΩΝ 2 (ένα loop) να στοιχίζει Ο( max(n,m) ), με n και m να είναι τα πλήθη των ψηφίων τους. Μπορούμε να γενικεύσουμε όμως λέγοντας πως η ιστογράφηση ενός αριθμού στοιχίζει O(n/2) αφού στη συντριπτική πλειοψηφία των περιπτώσεων ισχύει: n ~= m.

 

Οπότε η ιστογράφηση ενός αριθμού μας στοιχίζει: O(n+n/2), ενώ δυο αριθμών μας στοιχίζει: O(2*n) και μάλιστα έχουμε διανύσει ήδη τον περισσότερο δρόμο, αφού το μόνο που μας μένει είναι να κάνουμε το πολύ άλλες O(n) συγκρίσεις ακεραίων (και όχι strings) για να βρούμε αν έχουμε αναγραμματισμό μεταξύ 2 αριθμών. Συνολικά δηλαδή, η πλήρης διαδικασία για 2 αριθμούς μας στοιχίζει: Ο(3*n)

 

Στο δικό σου τρόπο, πριν καν βάλεις τον αριθμό στον (έτσι κι αλλιώς τεράστιο) πίνακα, χρειάζεσαι: O( n + n*log(n) ) για ένα μόλις αριθμό χωρίς καν να τον έχεις βάλει στον πίνακα. Το κόστος αυτό υπολείπεται πολύ λίγο από το ήδη τελειωμένο O(3*n) δυο μάλιστα αριθμών με την υλοποίηση του ιστογράμματος.

 

Νομίζω πως το ιστόγραμμα είναι ήδη ο ταχύτερος τρόπος από τους 3 γνωστούς δημοφιλείς (sort & compare, brute with strchr οι άλλοι δυο). Μετά υπάρχουν και τα anagram trees, αλλά προσπαθώ να τα αποφύγω. Μακάρι να υπήρχε μαθηματικός τύπος και να μη μπαίναμε καν στη διαδικασία των strings.

 

Πάντως είναι παραπάνω από πιθανό να έχω κάνει λάθος ανάλυση παραπάνω, γιατί είμαι σερί από το πρωί και έχω κουρκουτιάσει. Διορθώστε αν έχω γράψει καμιά... λαλακία.

[Technology fan]

Λοιπόν κάτσε να τα πάρουμε με τη σειρά, μπας και τα ταξινομήσω κι εγώ σωστά στο μυαλό μου (το οποίο το έχω ταλαιπωρήσει αρκετά από το πρωί ).

 

Καταρχήν για κάθε αριθμό θέλουμε μια μετατροπή σε string και μια ταξινόμηση ψηφίων πριν το βάλουμε στον πίνακα (ως strings τα βάζουμε, αν κατάλαβα σωστά). Υποθέτοντας πως ταξινομούμε τα ψηφία με quick-sort, έχουμε μέσο χρόνο: Ο( n + n*log(n) )... θεωρώ πως η μετατροπή από int σε string στοιχίζει n (όσα δηλαδή τα ψηφία του αριθμού).

 

Αν το πλήθος των παραγόμενων αριθμών είναι k, τότε για να γεμίσουμε τον πίνακα θέλουμε: O( k * (n + n*log(n)) ).

 

Αυτό σαν προεργασία, η οποία μας έχει στοιχίσει και πάρα πολύ σε μνήμη λόγω του πίνακα, ο οποίος μπορεί να γίνει πραγματικά τεράστιος, συν ότι δεν μπορούμε να προϋπολογίσουμε το μήκος του, άρα μάλλον θα χρειαστεί συν τοις άλλοις να δουλέψουμε με linked-list αντί για array. Μετά, η γραμμή: "if (strcmp(A[x],A[2x]))" δεν έχει κόστος O(1) όπως αναφέρεις παραπάνω. Κόστος O(1) έχει μόνο αν τα strings A[x] και A[2x] έχουν διαφορετικό τον 1ο τους χαρακτήρα... αλλιώς αν είναι ίδια, έχει κόστος O(n), όπου n το πλήθος των χαρακτήρων τους

 

 

Λοιπόν, σωστά είναι όλα αυτά που λες, με κάποιες βελτιώσεις όμως μπορούν να γίνουν καλύτεροι οι χρόνοι. Καταρχήν για την ταξινόμηση αν και γενικά είναι αδύνατον να ξεπεράσεις το (n+nlogn) στη πράξη όμως δεν θα κάνεις με τους συνηθισμένους τρόπους ταξινόμηση, θα εκμεταλλευτείς οτι τα πιθανά σύμβολα είναι 0-9, επομένως φτιάχνοντας ένα πίνακα 10 θέσεων (αρχικοποιημένος με μηδέν) θα φτιάξεις το ιστόγραμμα του κάθε αριθμού

 

πχ 59874811

Hist[0]=0

Hist[1]=2

Hist[2]=0

Hist[3]=0

Hist[4]=1

Hist[5]=1

Hist[6]=0

Hist[7]=1

Hist[8]=2

Hist[9]=1

 

Και τώρα η παραγωγή του ταξινομημένου αριθμού θα γίνει διασχύζοντας τον πίνακα και παράγοντας Hist[x] φορές το ψηφίο x,

δηλάδή 11 4 5 7 88 9

 

Συνολικό κόστος Ο(2*n),

 

Όμως αν το κάνεις για πολλούς αριθμούς, δεν χρειάζεται να ξαναυπολογίσεις τον πίνακα Hist,

 

πχ 59874812 (τον επόμενο δηλαδή απλά αλλαζει το 1 σε 2)

και η αλλαγή του Hist είναι εύκολη αφαιρώ ενα απο το 1 προσθέτω ένα στο 2.

 

Οπότε πηγαίνουμε σε επιμερισμένο κόστος που είναι σαφώς μικρότερο κόστος του Ο(2*n) αλλα αδυνατω να το υπολογίσω αναλυτικά,

 

Ύστερα για την αποθήκευση αυτού του θηρίου θα πήγαινα σε heap (όχι σε linked list) έχοντας εύκολη μετάβαση απο το x στο 2*x.

 

Και όσο για το κόστος σύγκρισης, όντως είναι O(n) ,όπου n το πλήθος των χαρακτήρων τους, αλλα αν το μετατρέψεις σε αριθμό (δεν ξέρω το κόστος αυτό) και συκρίνεις μετά τον αριθμό O(1) , και αν ο αριθμός είναι τέτοιος που δεν μπορείς να τον χειριστείς ως integer , θα σπάσεις το string σε substring μεγέθους όσο και το μέγιστο πλήθος που μπορείς να χειριστείς και θα κάνεις ύστερα την μετατροπή των substrings σε integers και την επιμέρους σύγκριση (βέβαια έχω μία μικρή αμφιβολία για το αν συμφερει το τελευταίο).

[Red_Phantom]

Cyclic number:

https://secure.wikimedia.org/wikipedia/en/wiki/Cyclic_number

 

Έχει και τρόπο κατασκευής τους.

[migf1]

 

...

Και τώρα η παραγωγή του ταξινομημένου αριθμού θα γίνει διασχύζοντας τον πίνακα και παράγοντας Hist[x] φορές το ψηφίο x,

δηλάδή 11 4 5 7 88 9

 

Συνολικό κόστος Ο(2*n),

 

Όμως αν το κάνεις για πολλούς αριθμούς, δεν χρειάζεται να ξαναυπολογίσεις τον πίνακα Hist,

 

πχ 59874812 (τον επόμενο δηλαδή απλά αλλαζει το 1 σε 2)

και η αλλαγή του Hist είναι εύκολη αφαιρώ ενα απο το 1 προσθέτω ένα στο 2.

 

Οπότε πηγαίνουμε σε επιμερισμένο κόστος που είναι σαφώς μικρότερο κόστος του Ο(2*n) αλλα αδυνατω να το υπολογίσω αναλυτικά

Δεν χρειάζεται να ξανά υπολογίσεις τον Hist, αλλά χρειάζεται ένα επιπρόσθετο complexity για να υπολογίζεις σε ποια ψηφία θα προσθαφαιρείς μονάδες στις τιμές του Hist, το οποίο μάλιστα είναι και αυξητικά κλιμακούμενο. Π.χ. από το 8 στο 9 αλλάζεις 2 τιμές του Hist, από το 9 στο 10 αλλάζεις 3 τιμές του Hist, από 19 στο 20 αλλάζεις 4 τιμές του Hist. Συν ότι θα χρειαστεί να ελέγχεις και περιπτώσεις ίδιων ψηφίων. π.χ. από το 999 στο 1000 θα πρέπει να μετρήσεις πόσα 9 υπάρχουν στο 999 και πόσα 0 στο 1000 για να δεις τι ακριβώς θα προσθαφαιρέσεις στις τιμές που αντιστοιχούν στα ψηφία 0,1 και 9 μέσα στον Hist.

 

Και όλα αυτά για κάθε αριθμό και πριν καν ξεκινήσεις να κάνεις συγκρίσεις μεταξύ 2 αριθμών. Για δυο λοιπόν αριθμούς ξεκινάς με το καλημέρα με complexity O(2*n + 2*αυξητικά κλιμακούμενο complexity) κι ακόμα δεν έχεις μπει καν σε διαδικασία αναζήτησης και σύγκρισης των αριθμών που σε ενδιαφέρουν.

 

Ύστερα για την αποθήκευση αυτού του θηρίου θα πήγαινα σε heap (όχι σε linked list) έχοντας εύκολη μετάβαση απο το x στο 2*x.

Όποια δομή και να επιλέξεις, το πρόβλημα με αυτόν τον τρόπο προσέγγισης είναι πως έχεις ένα δραματικό αυξανόμενο πλήθος στοιχείων μέσα στη δομή σου, οπότε το να βρεις και να συγκρίνεις δυο αριθμούς μέσα σε αυτήν εκτοξεύει την πολυπλοκότητα στον... Θεό, σε πλήρη δλδ αναλογία με το ραγδαία αυξανόμενο πλήθος των στοιχείων της δομής (πόσο μάλλον όταν θες να αναζητήσεις και να συγκρίνεις 5 νούμερα).

 

Κι αυτό αγνοώντας πλήρως το θέμα μνήμη.

 

Cyclic number:

https://secure.wikimedia.org/wikipedia/en/wiki/Cyclic_number

 

Έχει και τρόπο κατασκευής τους.

Ωραίο link! Αλλά θέλει μελέτη και εγώ είμαι ήδη τερματισμένος για σήμερα. Παρατήρησα όμως πως έλεγε ότι στη βάση του 10 ο μόνος κυκλικός αριθμός που υπάρχει είναι ο 142857 (για αυτό όταν βάζω το NMULS = 6 στο πρόγραμμα τρέχει μέχρι να το "σκοτώσω" )