Copy-Paste....Γρίφος

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[height=400]

  Όταν ανεβάζουμε φωτογραφίες στις Ανακοινώσεις και Έκτακτα νέα, βάζουμε τη μεγαλύτερη πλευρά 400 (width=400 ή height=400 ). π.χ. [img height=400 (κλείνει η αγκύλη) 

[fugiFOX]

Το πρόβλημα είναι απλό, αλλά σίγουρα θα έχει απασχολήσει τους χρήστες Η/Υ τουλάχιστον 1 φορα:

Θα το διατυπώσω στην πιο απλή μορφή του.
Θέλω να γεμίσω ένα κείμενο με έναν χαρακτήρα. Π.χ. κατι σαν αυτό:

ggggggggggggggggggggggggg
ggggggggggggggggggggggggg
ggggggggggggggggggggggggg
κτλ κτλ.

Ο απλός (μη βέλτιστος) τρόπος είναι να κρατώ συνεχώς πατημένο το αντίστοιχο πλήκτρο. Αυτό ισχύει για έναν μικρό αριθμό χαρακτήρων.
ΑΝ θέλω όμως έναν μεγάλο αριθμό Ν, έστω Ν=10^6, τότε συμφέρει να αρχίσω το copy-paste.
Δηλαδή έχοντας συμπληρώσει έναν αριθμό m1  χαρακτήρων ξεκινώ και κάνω copy-paste αυτούς.
Κατόπιν  έχοντας συμπληρώσει έναν αριθμό m2 χαρακτήρων m2>>m1 (?) ξεκινώ και κάνω copy-paste αυτούς.
κτλ κτλ.

Όλοι θα έχουμε δοκιμάσει να βρούμε τους βέλτιστους αριθμούς m1,m2,m3 διαισθητικά.
έχει σκεφτεί κανείς να βρει την ακριβή λύση του προβλήματος μαθηματικά;
Καμιά ιδέα;

Θεωρούμε το "κόστος" του copy-paste =2 χαρακτήρες ή και 3 αν προτιμάτε.
Η λύση του προβλήματος έχει ενδιαφέρον και μπορεί εύκολα να επεκταθεί και για κάποια φράση,pattern σε σχεδιαστικό πρόγραμμα και πολλές ακόμη εφαρμογές.

[~Michelle~]

Πάρα πολύ ενδιαφέρον! Αν βρω λίγο χρόνο θα προσπαθήσω να το λύσω!

[Junior]

Μια διευκρίνηση... επιτρέπεται να ξεπεράσουμε τον αριθμό Ν ή να κάνουμε copy ένα τμήμα του κειμένου ώστε να φτάσουμε ακριβώς το Ν;

Αν επιτρέπεται να ξεπεράσουμε το Ν νομίζω βρήκα τη λύση (για κόστος 2 των copy-paste), αλλά είναι πολύπλοκη και έχει διάφορες περιπτώσεις. Αν μιλούσαμε για κάποια φράση ή κάποιο pattern το οποίο θέλουμε να αναπαράγουμε τότε είναι απλούστερο. Όμως με τους απλούς χαρακτήρες μπλέκεται και το πόσους χαρακτήρες θα πληκτρολογήσεις στην αρχή χωρίς copy-paste, που "κοστίζουν" το 1/2 ή το 1/3 από το κάθε copy ή paste.
Θέλω αρκετή ώρα να διατυπώσω τη λύση, μάλλον θα κάτσω αύριο. Να τη στείλω σε κάποιο mail σου fugitive για να μην τη δημοσιεύσω εδώ;

Αλέξης Γελαστόπουλος, υποψήφιος συμφοιτητής σας

[cmichaelides]

Ωραίο το πρόβλημά σου fugitive, προτείνω όμως αντί μαθηματικής λύσης λαμβάνοντας υπόψιν το κόστος που ανέφερες, να ψάξουμε για την καλύτερη δυνατή προγραμματιστική λύση με κριτήριο το χρόνο εκτέλεσης του προγράμματος.

ΥΓ: Χαιρετίσματα στον υποψήφιο συμφοιτητή

[Καλλισθένης]

Ψάξε μήπως βγάλεις άκρη με την εντολή του word: =rand(a,b) όπου α ο αριθμός παραγράφων και όπου b ο αριθμός των σειρών ανά παράγραφο.

Τώρα πως θα αλλάξει το κείμενο της παρουσίασης των γραμματοσειρών σε κάτι άλλο ... είναι ένας "γρίφος"

Εξάλλου θέλει αρετή και τόλμη η Ελευθερία!!!

Αποποίηση ευθύνης:
δεν είμαι υπεύθυνος αν κάποιος γράψει =rand(200,99) ή περισσότερο και κολήσει το pc του... 

[fugiFOX]

Μια διευκρίνηση... επιτρέπεται να ξεπεράσουμε τον αριθμό Ν ή να κάνουμε copy ένα τμήμα του κειμένου ώστε να φτάσουμε ακριβώς το Ν;

Ναι μπορείς να το ξεπεράσεις. Μετά θα χρειαστείς απλώς 1-2 εντολές Delete.

Αλέξης Γελαστόπουλος, υποψήφιος συμφοιτητής σας

Καλως ήρθες στην κοινότητα του ΤΗΜΜΥ.gr

ΥΓ: Πώς μας ανακάλυψες;

[Junior]

Έστειλα τη λύση στο email σου fugitive

Καλως ήρθες στην κοινότητα του ΤΗΜΜΥ.gr

ΥΓ: Πώς μας ανακάλυψες;

Έψαχνα πληροφορίες για τη σχολή, πριν και μετά το μηχανογραφικό. Δε θυμάμαι που βρήκα το link, αλλά αμέσως έκανα bookmark τη σελίδα.

[Καλλισθένης]

Έστειλα τη λύση στο email σου fugitive

Εμείς δεν θα μάθουμε? 

Κ.Ι.Σ.

[~Michelle~]

Kallis καλύτερα τώρα?

[Καλλισθένης]

Ευτυχώς που υπάρχει και η νοικοκυρά μας (ή μήπως e-κοκυρά) εδώ πέρα και τακτοποιεί αμέσως τις συζητήσεις "εντός θέματος"...     

Κ.Ι.Σ.

[fugiFOX]

Επειδή το ζήτησε ο Καλ.
και για να μη χαρακτηριστώ "μοναχοφάης" κάνω....
copy-paste απο το μαιλ μου

Γεια χαρά,
Ορίστε η λύση του γρίφου. Εϊναι λίγο δύσκολο να την παρακολουθήσεις, δεν
μπορούσα να τα γράψω πιο απλά... Ελπίζω να τα καταφέρεις!

Έστω ότι αρχικά γράφουμε ακριβώς α χαρακτήρες χωρίς copy-paste. Το κόστος
μέχρι εδώ είναι α χαρακτήρες.
Κάθε φορά για να διπλασιάσουμε το κείμενο που έχουμε γράψει πρέπει να
κάνουμε μία φορά copy και μία φορά paste. Αυτό θα μας κοστίσει συνολικά 4
χαρακτήρες. Αν θέλαμε να τριπλασιάσουμε το κείμενο θα κάναμε μία φορά copy
και 2 φορές paste, που θα κόστιζε 6 χαρακτήρες. Γενικά για να
πολλαπλασιάσουμε το κείμενο που έχουμε γράψει με τον αριθμό n, μας κοστίζει
2n χαρακτήρες: 2 για το copy και 2n-2 για τα paste. Θα αποδείξουμε ότι το
μόνο που συμφέρει να κάνουμε είναι να διπλασιάζουμε ή να τριπλασιάζουμε
(κατά περίσταση) το κείμενό μας.
Πράγματι, για να τετραπλασιάσουμε το κείμενο απαιτούνται 8 χαρακτήρες. Αλλά
με το ίδιο κόστος μπορούμε να το διπλασιάσουμε δύο φορές και έτσι να έχουμε
το ίδιο αποτέλεσμα. ʼρα δε θα χρειαστεί ποτέ να τετραπλασιάσουμε. Για να
πενταπλασιάσουμε κοστίζει 10 χαρακτήρες, αλλά με τους ίδιους χαρακτήρες
μπορούμε να διπλασιάσουμε και να τριπλασιάσουμε οπότε έχουμε 6 φορές το
κείμενο. ʼρα δε συμφέρει να πενταπλασιάσουμε. Κάθε αριθμός μεγαλύτερος του 5
γράφεται στη μορφή 3κ, 3κ+1 ή 3κ+2, με κ μεγαλύτερο ή ίσο του 2. Για να
πολλαπλασιάσουμε το κείμενό μας με τον αριθμό 3κ ή 3κ+1 ή 3κ+2 μας κοστίζει
2*(3κ) ή 2*(3κ+1) ή 2*(3κ+2) χαρακτήρες. Όμως, με 2*3 χαρακτήρες μπορούμε να
τριπλασιάσουμε το κείμενο και αν επαναλάβουμε κ φορές θα έχουμε 3^κ φορές το
κείμενο με κόστος 2*3*κ χαρακτήρες. Με μαθηματική επαγωγή εύκολα
αποδεικνύεται ότι για κ μεγαλύτερο ή ίσο του 2 ισχύει 3^κ > 3κ+2 > 3κ+1 >
3κ. ʼρα με ίδιο ή μικρότερο κόστος μπορούμε να έχουμε περισσότερες φορές το
κείμενο τριπλασιάζοντας διαδοχικά αντί να πολλαπλασιάσουμε με 3κ ή 3κ+1 ή
3κ+2, κ μεγαλύτερο ή ίσο του 2.
ʼρα δε συμφέρει να τετραπλασιάσουμε, να πενταπλασιάσουμε, να εξαπλασιάσουμε
κλπ το κείμενο. Αυτό πρακτικά σημαίνει ότι μεταξύ δύο copy θα κάνουμε μόνο
ένα ή δύο paste.
Έστω ότι τους αρχικούς α χαρακτήρες τους διπλασιάσαμε λ φορές και τους
τριπλασιάσαμε μ φορές. Το συνολικό κόστος σε χαρακτήρες είναι α + 4*λ + 6*μ
και τελικά έχουμε α*2^λ*3^μ χαρακτήρες. Θα προσπαθήσουμε να βρούμε το
ελάχιστο κόστος που μπορεί να δώσει Ν ή περισσότερους χαρακτήρες, δηλαδή τα
α, λ, μ για τα οποία α*2^λ*3^μ μεγαλύτερο ή ίσο του Ν και α + 4*λ + 6*μ
ελάχιστο. Για να το βρούμε αυτό θα βρούμε πρώτα το μέγιστο α*2^λ*3^μ που
μπορεί να δώσει κάθε σταθερό άθροισμα α + 4*λ + 6*μ, και στη συνέχεια από τα
μέγιστα που ξεπερνάν το Ν θα πάρουμε αυτό που έχει το ελάχιστο άθροισμα α +
4*λ + 6*μ.

Έστω ότι για κάποια α, λ, μ έχουμε κόστος α + 4*λ + 6*μ. Θα προσπαθήσουμε να
βρούμε άλλους α, λ, μ ώστε το κόστος να είναι ίδιο και οι χαρακτήρες που
γράφουμε περισσότεροι.
Αν λ > 2, τότε ελαττώνοντας το λ κατά 3 και αυξάνοντας το μ κατά 2, το
κόστος παραμένει το ίδιο, αφού α + 4*(λ-3) + 6*(μ+2) = α + 4*λ � 12 + 6*μ +
12 = α + 4*λ + 6*μ, ενώ οι χαρακτήρες που παίρνουμε αυξάνονται, αφού
α*2^(λ-3)*3^(μ+2) = α*2^λ*3^μ*9/8. ʼρα, κάθε φορά που λ > 2 μπορούμε να
ελαττώσουμε το λ κατά 3 και να αυξήσουμε το μ κατά 2 και να έχουμε
περισσότερους χαρακτήρες με το ίδιο κόστος. Επομένως για κάθε κόστος ο
μέγιστος αριθμός χαρακτήρων που μπορούμε να γράψουμε είναι για λ=0 ή λ=1 ή
λ=2.

Τώρα θα προσπαθήσουμε να περιορίσουμε τις τιμές του α.
Θα πάρουμε αρχικά την περίπτωση που μ > 0. Αν ελαττώσουμε το μ κατά 1, για
να διατηρηθεί το άθροισμα α + 4*λ + 6*μ πρέπει το α να αυξηθεί κατά 6. Όμως
επειδή με τη μείωση του μ, το α*2^λ*3^μ διαιρείται με το 3, για να μας
συμφέρει η ελάττωση του γ και η αύξηση του α θα πρέπει η αύξηση του α να
συνεπάγεται πολλαπλασιασμό του α*2^λ*3^μ με αριθμό μεγαλύτερο του 3, δηλαδή
(α+6) > 3α ή α < 3. Έτσι, αν α < 3 αυξάνουμε το α κατά 6 και ελαττώνουμε το
μ κατά 1. Βλέπουμε ότι το α δε χρειάζεται να αυξηθεί αν είναι μεγαλύτερο ή
ίσο του 3. Την περίπτωση που α < 3 και μ = 0 θα την εξετάσουμε ξεχωριστά στο
τέλος.
Εδώ μπορούμε να θεωρήσουμε το α μεγαλύτερο ή ίσο του 3 (αφού αν α < 3 το
αυξάνουμε κατά 6 και ελαττώνουμε το μ κατά 1)

Θα δοκιμάσουμε τώρα πότε μας συμφέρει να αυξήσουμε το μ κατά 1 και να
ελαττώσουμε το α κατά 6, ώστε το α + 4*λ + 6*μ να διατηρηθεί σταθερό. Η
αύξηση του μ συνεπάγεται πολλαπλασιασμό του α*2^λ*3^μ με το 3. ʼρα αυτή η
κίνηση μας συμφέρει αν α-6>α/3 δηλαδή α>9, ενώ είναι ουδέτερη αν α=9, οπότε
γίνεται α=3. Αφού η κίνηση μας συμφέρει (ή είναι ουδέτερη) για α >= 9
μπορούμε να θεωρήσουμε α <= 8.
Επομένως α=3 ή α=4 ή α=5 ή α=6 ή α=7 ή α=8.
Στην περίπτωση που α=8, μπορούμε να κάνουμε το α ίσο με 4 και να αυξήσουμε
το β κατά 1, οπότε το άθροισμα α + 4*λ + 6*μ και το γινόμενο α*2^λ*3^μ
παραμένουν σταθερά. Οπότε για κάθε κόστος ο μέγιστος αριθμός χαρακτήρων που
μπορούμε να γράψουμε είναι για α=3 ή α=4 ή α=5 ή α=6 ή α=7.

Έστω τώρα ότι 3^γ<Ν<=3^(γ+1). Για κάθε ζεύγος α, λ υπάρχει μοναδικός αριθμός
μ που εξαρτάται από το γ τέτοιος ώστε 3^γ < α*2^λ*3^μ <= 3^(γ+1). Οι τριάδες
α, λ, μ δίνουν ένα άθροισμα α + 4*λ + 6*μ. Από τις τριάδες που έχουν ίδιο
άθροισμα α + 4*λ + 6*μ θα επιλέξουμε εκείνη με το μεγαλύτερο γινόμενο
α*2^λ*3^μ, για την οποία γνωρίζουμε ότι θα είναι μία από αυτές που 0 <= λ <=
2 και 3 <= α <= 7 και έτσι θα έχουμε βρει το μεγαλύτερο αριθμό χαρακτήρων
(γινόμενο α*2^λ*3^μ) που μπορούμε να γράψουμε για κάθε συγκεκριμένο κόστος,
ξεκινώντας από το κόστος που μόλις μπορεί να ξεπεράσει τους 3^γ χαρακτήρες
και σταματώντας σε αυτό που φτάνει ή ξεπερνάει τους 3^(γ+1) χαρακτήρες.
Έπειτα θα επιλέξουμε το ελάχιστο κόστος που δίνει χαρακτήρες που φτάνουν ή
ξεπερνούν το Ν.
Στον παρακάτω πίνακα για κάθε δυνατό ζεύγος α, λ βρίσκουμε το μ, το κόστος
(α + 4*λ + 6*μ) και τους χαρακτήρες (α*2^λ*3^μ) συναρτήσει του γ.

α   λ   μ      κόστος   χαρακτήρες (*3^(γ-2))
3   0   γ      6γ+3       27   *
3   1   γ-1   6γ+1      18
3   2   γ-2   6γ-1       12
4   0   γ-1   6γ-2       12   *
4   1   γ-1   6γ+2      24   *
4   2   γ-2   6γ          16   *
5   0   γ-1   6γ-1      15    *
5   1   γ-2   6γ-3      10    *
5   2   γ-2   6γ+1      20
6   0   γ-1   6γ          15
6   1   γ-2   6γ-2      12
6   2   γ-2   6γ+2      24
7   0   γ-1   6γ+1      21   *
7   1   γ-2   6γ-1       14
7   2   γ-3   6γ-3      28/3

Οι μόνοι τρόποι για να έχουμε κάποιο κόστος από τα 6γ-2, 6γ-1,�, 6γ+2 με 0
<= λ <= 2 και 3 <= α <= 7 είναι αυτοί που εμφανίζονται στον πίνακα, αφού σε
οποιοδήποτε ζεύγος α, λ αν αυξήσουμε το μ κατά 1 το κόστος γίνεται 6γ+3 ή
παραπάνω, ενώ αν το μειώσουμε κατά 1 το κόστος γίνεται 6γ-3 ή λιγότερο. ʼρα
ο μέγιστος αριθμός χαρακτήρων που μπορούμε να γράψουμε με κάθε κόστος από
6γ-2 έως 6γ+2 είναι ο μεγαλύτερος από αυτούς που εμφανίζονται στον πίνακα
για το συγκεκριμένο
 κόστος.

Για να έχουμε κόστος 6γ-3 με 0 <= λ <= 2 και 3 <= α <= 7 οι μόνοι τρόποι
είναι αυτοί που εμφανίζονται στον πίνακα καθώς και αν α = 3, λ = 0 και μ =
γ-1, που προκύπτει αν στην πρώτη γραμμή του πίνακα ελαττώσουμε το μ κατά 1.
Όμως σε αυτή την περίπτωση οι χαρακτήρες δεν ξεπερνούν το 10*3^(γ-2) που
δίνονται από την 8η γραμμή του πίνακα. ʼρα με κόστος 6γ-3 μπορούμε να έχουμε
μέχρι 10*3^(γ-2) χαρακτήρες.

Έστω ότι υπάρχει κόστος μικρότερο από 6γ-3 τέτοιο ώστε να δίνει
περισσότερους από 3^γ χαρακτήρες. Τότε με το ίδιο κόστος μπορούμε να έχουμε
τους ίδιους ή περισσότερους χαρακτήρες για 0 <= λ <= 2 και 3 <= α <= 7. Αφού
το κόστος είναι μικρότερο από 6γ-3 και τα α, λ είναι ίδια με κάποιο ζεύγος
στον πίνακα, συμπεραίνουμε ότι το μ είναι μικρότερο από το αντίστοιχο στον
πίνακα. Αν αυξήσουμε το μ κατά 1, τότε το μ θα είναι μικρότερο ή ίσο με αυτό
του πίνακα και θα δίνει περισσότερους από 3^(γ+1) χαρακτήρες, δηλαδή με ίδια
α, λ και μικρότερο ή ίσο μ θα έχουμε μεγαλύτερο γινόμενο α*2^λ*3^μ, που
είναι άτοπο.
ʼρα για 3^γ χαρακτήρες το κόστος είναι τουλάχιστον 6γ-3.

3^(γ+1) χαρακτήρες μπορούμε να έχουμε με κόστος 6γ+3 και όχι μικρότερο, όπως
προκύπτει από τον πίνακα.

Οπότε για κάθε κόστος ο μέγιστος αριθμός χαρακτήρων είναι ο εξής (αστερίσκος
στον πίνακα):
<6γ-3:    < 3^γ
6γ-3:      10*3^(γ-2)
6γ-2:      12*3^(γ-2)
6γ-1:      15*3^(γ-2)
6γ:         16*3^(γ-2)
6γ+1:     21*3^(γ-2)
6γ+2:     24*3^(γ-2)
6γ+3:     >= 27*3^(γ-2) = 3^(γ+1)


Επομένως,
αν 3^γ             < Ν <= 10*3^(γ-2)  τότε α=5, λ=1, μ=γ-2
αν 10*3^(γ-2)  < Ν <= 12*3^(γ-2)  τότε α=4, λ=0, μ=γ-1
αν 12*3^(γ-2)  < Ν <= 15*3^(γ-2)  τότε α=5, λ=0, μ=γ-1
αν 15*3^(γ-2)  < Ν <= 16*3^(γ-2)  τότε α=4, λ=2, μ=γ-2
αν 16*3^(γ-2)  < Ν <= 21*3^(γ-2)  τότε α=5, λ=2, μ=γ-2
αν 21*3^(γ-2)  < Ν <= 24*3^(γ-2)  τότε α=4, λ=1, μ=γ-1
αν 24*3^(γ-2)  < Ν <= 3^(γ+1)      τότε α=3, λ=0, μ=γ

Τώρα θα εξετάσουμε την περίπτωση που μ = 0 και α < 3.
Επειδή λ <= 2, α <=2 και μ = 0, ισχύει α*2^λ*3^μ <= 8. Δηλαδή μας ενδιαφέρει
η περίπτωση που Ν <= 8. Αλλά για Ν <= 8 εύκολα βρίσκεται ότι έχουμε το
μικρότερο κόστος όταν δεν κάνουμε κανένα copy-paste, δηλαδή όταν α = Ν.

Τα προηγούμενα επομένως ισχύουν αν Ν > 8.

Βρίσκουμε τα Μ1, Μ2, Μ3 κλπ
Μ1 = α

Αν λ = 0,               Μ2 = 3*Μ1
Αν λ = 1 ή λ = 2,   Μ2 = 2*Μ1

Αν λ = 0 ή λ = 1,    Μ3 = 3*Μ2
Αν λ = 2,                Μ3 = 2*Μ2

Για ν >= 4 Μν = 3*Μ(ν-1)

Σταματάμε στον ελάχιστο αριθμό ν για τον οποίο Μν >= Ν

Αλέξης Γελαστόπουλος

[fugiFOX]

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

Το μόνο που μου φαίνεται λίγο παράδοξο θα έλεγα είναι το

Άρα δε συμφέρει να τετραπλασιάσουμε, να πενταπλασιάσουμε, να εξαπλασιάσουμε
κλπ το κείμενο. Αυτό πρακτικά σημαίνει ότι μεταξύ δύο copy θα κάνουμε μόνο
ένα ή δύο paste.

[cmichaelides]

Εκφράζοντας τον δεκαδικό αριθμό των ζητούμενων χαρακτήρων στο δυαδικό σύστημα παρατήρησα πως μπορούμε εύκολα να δούμε πόσα copy-paste θα χρειαστούμε για να τον εκφράσουμε ακριβώς εισάγοντας μόνο ένα χαρακτήρα. Έγραψα μια εκδοχή της λύσης αυτού του προβλήματος σε κώδικα και σας το παραθέτω. Αν και δεν έχει πολλή σχέση με το αρχικό πρόβλημα που έθεσε ο fugitive, είναι αρκετά ενδιαφέρον. Είναι λίγο πρόχειρος ο κώδικας, αλλά δίνει μια εικόνα του συλλογισμού χωρίς πολλά λόγια.

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

[fugiFOX]

Λοιπόν παραθέτω και τη δική μου "λύση" ή καλύτερα προσπάθεια επίλυσης.
Είναι γενική ώστε να μην περιλαμβάνει μόνο χαρακτήρες αλλά και οποιοδήποτε pattern.
Έχουμε λοιπόν:
Αρχικά γράφουμε Κ1 χαρακτήρες (ή patterns στο εξής θα αναφέρονται με την κοινή ονομασία χαρακτήρες).
Κατόπιν κάνουμε αυτούς copy-paste (CP) Κ2 φορές.
Επομένως τώρα έχουμε Κ1*Κ2 χαρακτήρες.
Κάνουμε αυτό το σύνολο τώρα CP Κ3 φορές οπότε και έχουμε τώρα Κ1*Κ2*Κ3 χαρακτήρες.
Κατά τον ίδιο τρόπο συνεχίζουμε φτάνοντας έναν αριθμό Μ>Ν=ζητούμενο,
όπου Μ ο αριθμός χαρακτήρων που για πρώτη φορά θα υπερβεί το Ν.
Επομένως έχουμε Μ=Κ1*Κ2*...*Κν
και ζητούμε τα Ki τέτοια ώστε
P=K1+K2+K3+....+Kn να είναι ελάχιστο.

Εάν θεωρήσουμε αρχικά αμελητέο το κόστος σε εντολές του CP τότε η λύση είναι μάλλον απλή
αφού αυτό το άθροισμα γίνεται ελάχιστο όταν κάθε όρος από αυτούς γίνει ελάχιστος
και μετά από λίγες πράξεις καταλήγουμε ότι K1=K2=...Kn=2.
(το ένα απορρίπτεται αυφού δεν αυξάνει το γινόμενο)
Π.χ. για Ν=100 έχουμε
P=K1+K2+...K7=2*7=14.
ενώ αν K1=K2=10 έχουμε P=20.


Λοιπόν παραθέτω και τη δική μου "λύση" ή καλύτερα προσπάθεια επίλυσης.
Είναι γενική ώστε να μην περιλαμβάνει μόνο χαρακτήρες αλλά και οποιοδήποτε pattern.
Έχουμε λοιπόν:
Αρχικά γράφουμε Κ1 χαρακτήρες (ή patterns, στο εξής θα αναφέρονται με την κοινή ονομασία χαρακτήρες).
Κατόπιν κάνουμε αυτούς copy-paste (CP) Κ2 φορές.
Επομένως τώρα έχουμε Κ1*Κ2 χαρακτήρες.
Κάνουμε αυτό το σύνολο τώρα CP Κ3 φορές οπότε και έχουμε τώρα Κ1*Κ2*Κ3 χαρακτήρες.
Κατά τον ίδιο τρόπο συνεχίζουμε φτάνοντας έναν αριθμό Μ>Ν=ζητούμενο,
όπου Μ ο αριθμός χαρακτήρων που για πρώτη φορά θα υπερβεί το Ν.
Επομένως έχουμε Μ=Κ1*Κ2*...*Κν
και ζητούμε τα Ki τέτοια ώστε
P=K1+K2+K3+....+Kn να είναι ελάχιστο.

το άθροισμα γίνεται ελάχιστο όταν κάθε όρος από αυτούς γίνει ελάχιστος
και μετά από λίγες πράξεις καταλήγουμε ότι K1=K2=...Kn=2.
(το ένα απορρίπτεται αυφού δεν αυξάνει το γινόμενο)

Π.χ. για Ν=100 έχουμε
P=K1+K2+...K7=2*7=14.
ενώ αν K1=K2=10 έχουμε P=20.

Μέχρι τώρα, σιωπηρά υποθέσαμε ότι το κόστος σε εντολές του CP είναι αμελητέρο κάτι όμως που δεν ισχύει στην πραγματικότητα. Αυτό που πραγματικά συμβαίνει, είναι ότι σε κάθε copy θα μπορούσαμε να γράφαμε άλλον έναν χαρακτήρα, ομοίως και σε κάθε paste.
Εδ'ω μπλέκεται λίγο το θέμα.
Νέες ιδέες;

[Junior]

Το μόνο που μου φαίνεται λίγο παράδοξο θα έλεγα είναι το

Άρα δε συμφέρει να τετραπλασιάσουμε, να πενταπλασιάσουμε, να εξαπλασιάσουμε
κλπ το κείμενο. Αυτό πρακτικά σημαίνει ότι μεταξύ δύο copy θα κάνουμε μόνο
ένα ή δύο paste.

Πιο αναλυτικά θα έγραφα το εξής:

Άρα δε συμφέρει να τετραπλασιάσουμε, να πενταπλασιάσουμε, να εξαπλασιάσουμε
κλπ το κείμενο. Επομένως, το μόνο που θα κάνουμε είναι να διπλασιάζουμε ή να τριπλασιάζουμε το κείμενο που έχουμε κάθε φορά. Αυτό πρακτικά σημαίνει ότι μεταξύ δύο copy θα κάνουμε μόνο
ένα ή δύο paste.

Σημείωση: Για να διπλασιάσουμε το κείμενο κάνουμε copy, μετά μία φορά paste και μετά ξανακάνουμε copy όλο μαζί (εκτός αν έχουμε φτάσει το Ν). Για να τριπλασιάσουμε κάνουμε copy, δύο φορές paste και μετά πάλι copy όλο μαζί. Άρα μεταξύ δύο copy κάνουμε ένα ή δύο paste.

Αυτό που πραγματικά συμβαίνει, είναι ότι σε κάθε copy θα μπορούσαμε να γράφαμε άλλον έναν χαρακτήρα, ομοίως και σε κάθε paste.

  Ομολογώ πως αυτό δεν το έλαβα υπόψη. Έτσι όμως μπλέκεται πάάάάάρα πολύ το θέμα