α) Πόσες φορές επαναλαμβάνεται ο αριθμός 3, σαν ψηφίο, στους
αριθμούς από το 1 έως το 1000;
(π.χ. O αριθμός 333 περιέχει τρεις φορές το ψηφίο 3, ο αριθμός 133
περιέχει 2 φορές το ψηφίο 3, ενώ ο αριθμός 321 ή ο αριθμός 23
περιέχουν από μια φορά το ψηφίο 3.)
β) Εάν θελήσουμε να γενικεύσουμε τον ανωτέρω συλλογισμό, ποιος
είναι ο τύπος που μπορεί να μας υπολογίσει πόσα ίδια, συνολικά ως
ψηφία, περιέχονται σε «n» διαδοχικούς ακέραιους αριθμούς;
(Κατ.27/Πρβ.Νο.298)
είναι ο τύπος που μπορεί να μας υπολογίσει πόσα ίδια, συνολικά ως
ψηφία, περιέχονται σε «n» διαδοχικούς ακέραιους αριθμούς;
(Κατ.27/Πρβ.Νο.298)
Αναρτήσεις
13 σχόλια:
Απαντώ το α) ερώτημα:
Από το 1 έως το 1000, κανείς συναντά 300 φορές τον αριθμό 3.
Ως τελευταίο ψηφίο (μονάδες) το 3 απαντάται 100 φορές, ως προτελευταίο (δεκάδες) επίσης 100 φορές και ώς τρίτο από το τέλος (εκατοντάδες) και πάλι 100 φορές, άρα σύνολο 300 φορές.
Αναφορικά με το β) ερώτημα, σίγουρα δεν είναι σωστά διατυπωμένο. Υποθέτω ότι λείπει η λέξη "διαδοχικοί" μπροστά από το "ακέραιοι", αλλά αυτό δεν είναι το μόνο πρόβλημα στην εκφώνηση.
@ΧΑΡΗΣ
Σωστή η λύση. Η διόρθωση έγινε. Σ' ευχαριστώ για την πρέμβαση. Τώρα μένει ο γενικός τύπος.
@papaveri
Το να αλλάζεις τις συνθήκες ενός προβλήματος ενίοτε είναι "άδικο" για όσους έχουν απαντήσει ήδη. (Μη με ρωτήσεις, μπορώ να σου βρω παράδειγμα με δική μου απάντηση).
Εγώ δεν ασχολήθηκα αρχικά γιατί ήταν εξαιρετικά άστοχη η διατύπωση. Μετά όμως από την επέμβαση του αναγνώστη Χάρη σου δόθηκε η ευκαιρία να ξαναδείς το πρόβλημα. Έβαλες "διαδοχικοί", εντάξει, αλλά σου λέει ότι δεν είναι το μόνο μειονέκτημα στην εκφώνηση.
Ψάχνουμε για συγκεκριμένο ψηφίο; Μας δίνουν πεδίο ορισμού; Τα όρια είναι ανοικτά ή κλειστά;
Ας πούμε ότι οι διαδοχικοί ακέραιοι είναι οι [ -2, -1, 0, 1, 2, 3, 4, 5 ). Δεν πιστεύω ότι υπάρχει γενικός τύπος που δίνει και πόσα δυάρια υπάρχουν και πόσα πεντάρια υπάρχουν στο αριθμοσύνολο αυτό. Μακάρι να κάνω λάθος.
Μήπως το ερώτημα είναι διαφορετικό;
Λίγο αργότερα θα δημοσιεύσω αλγόριθμο ο οποίος υπολογίζει τον αριθμό των εμφανίσεων ενός ψηφίου (0 ως 9) στο διάστημα [1..n]
Θέλω να τον ελέγξω λίγο ακόμα...
Αν έχουμε αυτόν τον αλγόριθμο μπορούμε νομίζω σχετικά εύκολα να υπολογίσουμε τις εμφανίσεις ενός ψηφίου σε ένα διάστημα (ανοιχτό ή κλειστό) διαδοχικών ακεραίων.
@alkinoos
Ζήτώντας το γενικό τύπο για τον υπολογισμό των τριαριών είχα την εντύπωση πως ήταν εμφανές ότι πρόκειτε για διαδοχικούς ακέραιους αριθμούς. Ίσως έπρεπε να γράψω απο το 1...n.
Όχι, το ερώτημα του δευτέρου σκέλους ζητάει το γενικό τύπο. Το έψαξα, αλλά δεν μπόρεσα να βρω κάτι.
Να και ο αλγόριθμος. Υπολογίζει τις εμφανίσεις ενός ψηφίου (0 έως 9) στους διαδοχικούς αριθμούς [1..n] Οι δοκιμές μου έδειξαν πως δουλεύει. Ελπίζω να μη μου έχει ξεφύγει κάποια ειδική περίπτωση.
Γενικά αναλύοντας το πρόβλημα ανακάλυψα αρκετές διαφορετικές περιπτώσεις. Με δυσκόλεψε π.χ. η περίπτωση του 0 (μηδέν)
Η γενική ιδέα είναι να εξετάσει σε πόσες 10αδες, 100αδες, 1000αδες κτλ μπορεί να χωριστεί ο αριθμός n. Για κάθε δεκάδα προστίθεται μία εμφάνιση του ψηφίου, για κάθε 100άδα 10 εμφανίσεις, για κάθε 1000αδα 100 εμφανίσεις κτλ. Τα δύσκολα ξεκινούν με τα υπόλοιπα. Τι γίνεται δηλ. όταν το n δεν είναι πολλαπλάσιο του 10, 100, 1000 κτλ.
Δείτε τον αλγόριθμο. θα προσπαθήσω κάποια άλλη στιγμή να δώσω αναλυτικότερες εξηγήσεις. Να πω μόνο ότι αν π.χ. θέλουμε τις εμφανίσεις του 3 στο διάστημα π.χ. [153..567] τότε υπολογίζουμε τις εμφανίσεις του τρία στο διάστημα [1..567] και στο διάστημα [1..152] και αφαιρούμε το δεύτερο αποτέλεσμα από το πρώτο.
Για λόγους απλότητας δεν υπάρχει φυσικά έλεγχος της ορθότητας εισόδου. Ο αλγόριθμος είναι γραμμένος σε ΓΛΩΣΣΑ
ΠΡΟΓΡΑΜΜΑ ΜΕΤΡΗΤΗΣ_ΨΗΦΙΩΝ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: n, ψηφίο, μετρητής, διαιρέτης
ΑΡΧΗ
ΓΡΑΨΕ 'Δώσε το ψηφίο που σε ενδιαφέρει να μετρήσεις:'
ΔΙΑΒΑΣΕ ψηφίο
ΓΡΑΨΕ 'Δώσε το n:'
ΔΙΑΒΑΣΕ n
μετρητής <- 0
διαιρέτης <- 10
ΟΣΟ (n DIV διαιρέτης > 0) ΕΠΑΝΑΛΑΒΕ
μετρητής <- μετρητής + (n DIV διαιρέτης)*(διαιρέτης DIV 10)
ΑΝ (n MOD διαιρέτης - διαιρέτης DIV 10* ψηφίο >= διαιρέτης DIV 10) ΤΟΤΕ
μετρητής <- μετρητής + διαιρέτης DIV 10
ΑΛΛΙΩΣ_ΑΝ (n MOD διαιρέτης - διαιρέτης DIV 10* ψηφίο >= 0) ΤΟΤΕ
μετρητής <- μετρητής + n MOD διαιρέτης - διαιρέτης DIV 10* ψηφίο + 1
ΤΕΛΟΣ_ΑΝ
ΑΝ ψηφίο = 0 ΤΟΤΕ
μετρητής <- μετρητής - διαιρέτης DIV 10
ΤΕΛΟΣ_ΑΝ
διαιρέτης <- διαιρέτης* 10
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΑΝ (n MOD διαιρέτης - διαιρέτης DIV 10* ψηφίο >= διαιρέτης DIV 10) ΤΟΤΕ
μετρητής <- μετρητής + διαιρέτης DIV 10
ΑΛΛΙΩΣ_ΑΝ (n MOD διαιρέτης - διαιρέτης DIV 10* ψηφίο >= 0) ΤΟΤΕ
μετρητής <- μετρητής + n MOD διαιρέτης - διαιρέτης DIV 10* ψηφίο + 1
ΤΕΛΟΣ_ΑΝ
ΑΝ ψηφίο = 0 ΤΟΤΕ
μετρητής <- μετρητής - διαιρέτης DIV 10
ΤΕΛΟΣ_ΑΝ
ΓΡΑΨΕ 'Το ψηφίο ', ψηφίο, ' εμφανίζεται ', μετρητής, ' φορές στους αριθμούς από 1 έως ', n
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
@Δημήτρης Σκυριανόγλου
Καλέ μου φίλε Δημήτρη, δεν ζητάει αλγόριθμο, αλλά έναν Γενικό Τύπο. Εσύ λύνεις (με επιτυχία!) ένα άλλο πρόβλημα.
@alkinoos
Ευχαριστώ για τη διευκρίνιση. Τελικά, θυμάμαι ότι κάπου είχα δει το τύπο. Δεν θυμάμαι όμως που.
@Δημήτρης Σκυριανόγλου
με πρόλαβε ο Alkinoos για τη διευκρίνιση. Μήπως μπορείς να με βοηθήσεις. Το ζήτησα και απο κάποιο γνωστό μου. Περιμένω απάντηση. Είμαι σίγουρος ότι υπάρχει, αλλά δεν θυμάμαι που τον είδα.
Η εύρεση τύπου μου φαίνεται αρκετά δύσκολη... Οι διαφορετικές ειδικές περιπτώσεις είναι αρκετές και αν πράγματι υπάρχει ο τύπος δηλώνω εκ των προτέρων εντυπωσιασμένος :-)
κ. Papaveri μήπως ο τύπος που είχατε δει ίσχυε για τις περιπτώσεις που το n είναι δύναμη του 10 (10, 100, 1000 κοκ)? Τότε πράγματι τα πράγματα είναι απλούστερα. Σε διαφορετική περίπτωση μου φαίνεται δύσκολο...
@alkinoos
Να μια ενδιαφέρουσα άσκηση (στην απλουστευμένη μορφή που ανέφερα πιο πάνω) για την ΑΕΠΠ. Καθαρή αλγοριθμική σκέψη, ούτε πίνακες ούτε τίποτα :-) Συμφωνείτε?
Δημήτρης Σκυριανόγλου
Νομίζω ότι δεν έκανε διάκριση για τις περιπτώσεις που το n είναι δύναμη του 10. Αλλά σε κάθε περίπτωση, πριν ανακαλυφθούν οι γλώσσες προγραμματισμού με τους αλγόριθμους, νομίζω ότι τέτοια προβλήματα πρέπει να λύνονταν με κάποιο μαθηματικό τύπο και όχι μετρώντας ανά εκατοντάδα για να βρεις πόσα ίδια ψηφία περιέχονται του "χ" αριθμού σε μία σειρά διαδοχικών ακεραίων αριθμών. Τι γνώμη έχετε;
@Δημήτρης Σκυριανόγλου
Όντως είναι ένα θέμα πολύ ενδιαφέρον
που "σηκώνει" πολύ συζήτηση σε βάθος,
για να λυθεί διεξοδικά.
@Δημήτρης Σκυριανόγλου
Έστω ότι το πρόβλημα είναι να βρώ έναν τύπο που δίνει το πλήθος m εμφανίσεων ενός ψηφίου σε μια πλήρη σειρά ισομήκων διαδοχικών ακεραίων αριθμών, από 00...000 μέχρι 99...999, όπου το μήκος είναι n.
Απάντηση : m = n*10^(n-1)
Μονοψήφιοι : m = 1*10^0 = 1
Διψήφιοι : m = 2*10^1 = 20
Τριψήφιοι : m = 3*10^2 = 300
κλπ.
Η διαφορά με το ερώτημα α) είναι ότι εκεί τα όρια είναι από το 1 έως το 1000, ενώ εγώ βρίσκω από το 000 μέχρι το 999, και δεν έχει σημασία για ποιό από τα δέκα ψηφία μιλάμε.
Δημοσίευση σχολίου