Δύσκολες Ασκήσεις στις Δομές Επανάληψης

[nikolasmer]

Πάντως η δυσκολία σε αυτή την άσκηση δεν είναι αλγοριθμική.
Η δυσκολία είναι στο ότι οι μαθητές δεν κατανοούν τι σημαίνει αναπαράσταση και αξία ενός αριθμού.

Πολύ ωραία και πολύ δυνατή άσκηση. Δεν μπορούσα να ξεκολήσω το μυαλό μου από το να μετρήσω με μετρητή τα ψηφία του αριθμού. Ένας φίλος ήρθε και με ξεκόλησε.
Μου άρεσε πολύ ο αθροιστής.

άθροισμα ← 10* άθροισμα + αριθμός mod 10

Όμως τί γίνεται με τον κατοπτρικό του 0001234;
Γίνεται να μου βγάλει 4321000;
Δεν βλέπω να τα καταφέρνω χωρίς πίνακα.

[ofilos13]

Θα μπουρουσε καποιος να μου δωσει την ακριβης λυση του παρακατω αλγοριθμου.

Σε ενα οινοπωλειο υπαρχει ενα βαρελι 500 κιλα με κοκκινο κρασι.Οι πελατες μπορουν να αγορασουν μπουκαλια του 1.5 κιλου προς 3.4 ευρω το μπουκαλι.Να γαψετε αλγοριθμο ο οποιος.

α)για καθε πελατη να ζητα ποσα μπουκαλια θελει να αγορασει
β)να εμφανιζει το κοστος της παραγγελιας
γ)να εμφανιζει τα συνολικα κιλα που απομενουν στο βαρελι μετα την αντληση καθε παραγγελιας κρασιου
δ)αν γινει καποια παραγγελια μεγαλυτερη απο το τρεχον περιεχομενο του βαρελιου τοτε να τερματιζει και να εμφανιζει
ε)τη μεγαλυτερη παραγγελια (σε μπουκαλια)που εγινε
στ)ποσα μπουκαλια πουληθηκαν
ζ) τα καθαρα εσοδα, αν ολο το κρασι ειχε αρχικο κοστος 120 ευρω

[Σπύρος Δουκάκης]

Μεθυστική άσκηση!!

Θα μπουρουσε καποιος να μου δωσει την ακριβης λυση του παρακατω αλγοριθμου.

Σε ενα οινοπωλειο υπαρχει ενα βαρελι 500 κιλα με κοκκινο κρασι.Οι πελατες μπορουν να αγορασουν μπουκαλια του 1.5 κιλου προς 3.4 ευρω το μπουκαλι.Να γαψετε αλγοριθμο ο οποιος.

α)για καθε πελατη να ζητα ποσα μπουκαλια θελει να αγορασει
β)να εμφανιζει το κοστος της παραγγελιας
γ)να εμφανιζει τα συνολικα κιλα που απομενουν στο βαρελι μετα την αντληση καθε παραγγελιας κρασιου
δ)αν γινει καποια παραγγελια μεγαλυτερη απο το τρεχον περιεχομενο του βαρελιου τοτε να τερματιζει και να εμφανιζει
ε)τη μεγαλυτερη παραγγελια (σε μπουκαλια)που εγινε
στ)ποσα μπουκαλια πουληθηκαν
ζ) τα καθαρα εσοδα, αν ολο το κρασι ειχε αρχικο κοστος 120 ευρω

[nikolasmer]

Για να ελέγξω αν ένας αριθμός, έστω Χ, είναι πρώτος, χρειάζομαι μια επανάληψη η οποία εξετάζει αν αυτός ο αριθμός έχει κάποιον διαιρέτη. Οπότε η επανάληψη που χρησιμοποιώ είναι

Για ι από 2 μέχρι χ div 2

Αν ο αριθμός είναι πρώτος τότε δεν θα υπάρχει κανένας διαιρέτης.

Το πρόβλημα είναι πως αν θέλω να βρω ποιοι αριθμοί στο διάστημα [1-500000], είναι πρώτοι, τότε βάζοντας ακόμη μια επανάληψη εξωτερικά ο χρόνος που απαιτείται για την εκτέλεση του αλγορίθμου, είναι τεράστιος. Δοκίμασα να απορρίψω αριθμούς οι οποίοι διαιρούνται με το 2, με το 3 με το 7 και με το 11 αλλά μάταια. Δεν έχει πέσει ο χρόνος εκτέλεσης.

Καμία ιδέα για μικρότερη πολυπλοκότητα;     

[evry]

Για κάθε αριθμό να ελέγξεις μέχρι τη ρίζα.
Είναι λίγο καλύτερα και μπορείς να το αποδείξεις και να το εξηγήσεις στα παιδιά σχετικά απλά
Δεν νομίζω όμως να δεις πάλι μεγάλη διαφορά.

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

[sstergou]

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

[nikolasmer]

...... υλοποιείται και με πίνακα λογικών μεταβλητών.

Δεν το καταλαβαίνω αυτό το κομμάτι.
Μια βοήθεια από που να ξεκινήσω;
Ευχαριστώ.

[sstergou]

Αλγόριθμος Ερατοσθένης
Δεδομένα //Ν//
Για i από 1 μέχρι Ν 
	Είναι_Πρώτος[i] ← Αληθής
Τέλος_επανάληψης

όριο ← Τ_Ρ(Ν)
Για i από 2 μέχρι όριο
	Αν Είναι_Πρώτος[i] τότε
		Για j από i * 2 μέχρι Ν με_βήμα i
			Είναι_Πρώτος[j] ← Ψευδής
		Τέλος_επανάληψης			
	Τέλος_αν
Τέλος_επανάληψης

Για i από 1 μέχρι Ν
	Αν Είναι_Πρώτος[i] τότε
		Εμφάνισε i
	Τέλος_αν
Τέλος_επανάληψης

Τέλος Ερατοσθένης

[nikolasmer]

Αλγόριθμος Ερατοσθένης
Δεδομένα //Ν//
Για i από 1 μέχρι Ν 
	Είναι_Πρώτος[i] ← Αληθής
Τέλος_επανάληψης

όριο ← Τ_Ρ(Ν)
Για i από 2 μέχρι όριο
	Αν Είναι_Πρώτος[i] τότε
		Για j από i * 2 μέχρι Ν με_βήμα i
			Είναι_Πρώτος[j] ← Ψευδής
		Τέλος_επανάληψης			
	Τέλος_αν
Τέλος_επανάληψης

Για i από 1 μέχρι Ν
	Αν Είναι_Πρώτος[i] τότε
		Εμφάνισε i
	Τέλος_αν
Τέλος_επανάληψης

Τέλος Ερατοσθένης

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

[petrosp13]

Θα πρέπει να αποθηκεύεται η πληροφορία των πολλαπλασίων του αριθμού που είναι πρώτος (ότι δεν είναι πρώτοι) οπότε είναι υποχρεωτικός ο πίνακας

[itt]

Θα μπορούσες επίσης να χρησιμοποιήσεις το θεώρημα του Fermat αν μπορούσαμε να παράγουμε τυχαίους αριθμούς. (Θα χάνεις βέβαια τους αριθμούς Carmichael)

[pstasinos]

Αλγόριθμος Ερατοσθένης
Δεδομένα //Ν//
Για i από 1 μέχρι Ν 
	Είναι_Πρώτος[i] ← Αληθής
Τέλος_επανάληψης

όριο ← Τ_Ρ(Ν)

[/quote]

Η απάντηση μου αρέσει πάρα πολύ.Πολύ όμορφη και απλή. Μόνο μια απορία.
Μήπως στη μεταβλητή όριο έπρεπε να μπει
όριο <- Α_Μ(Τ_Ρ(Ν))


Ευχαριστώ

[sstergou]

Δεν υπάρχει πρόβλημα.
Μεταφράζεται στην αντίστοιχη

ι <- 1
Όσο ι <= Κάποιος_πραγματικός επανάλαβε
    ι <- ι + 1
Τέλος_επανάληψης

Κάποια στιγμή το ι θα ξεπεράσει τον πραγματικό. Δεν είναι απαραίτητο για το όριο να είναι ακέραιος. Δεν ξέρω αν αυτό εννοούσες.

[pstasinos]

Δεν υπάρχει πρόβλημα.
Κάποια στιγμή το ι θα ξεπεράσει τον πραγματικό. Δεν είναι απαραίτητο για το όριο να είναι ακέραιος. Δεν ξέρω αν αυτό εννοούσες.

Ναι για αυτό το είπα , και έχεις δίκιο ισχύει.
Απλά στα παιδιά που το αναφέρω τους λέω πως διαγράφουμε με την γνωστή διαδικασία με το κόσκινο του Ερατοσθένη μέχρι και τον επόμενο ακέραιο του SQRT(N)
δηλαδή καλύτερα όριο <- Α_Μ(Τ_Ρ(Ν))+1
και σαφώς αυτό θα πρέπει να δίνεται ως παρατήρηση στην εκφώνηση. 

Ευχαριστώ

[nikolasmer]

Ωραία άσκηση από το διαδίκτυο, με μια μικρή τροποποίηση:
"Να βρεθεί το άθροισμα των 10 θετικών πρώτων αριθμών που θα συναντήσετε οι οποίοι μπορούν να διαιρεθούν ακριβώς ο καθένας τους, χωρίς να αφήνει υπόλοιπο, με όλους τους αριθμούς από το 1 μέχρι το 10."   

Αργώ να πάρω αποτέλεσμα στο διερμηνευτή.
Αν θέλαμε να την δυσκολέψουμε περισσότερο:
"Να υπολογιστεί και να εμφανιστεί 5ψήφιος  θετικός αριθμός ο οποίος να διαιρείται ακριβώς από τους 5 πρώτους πρώτους αριθμούς(primary). Αν δεν υπάρχει τέτοιος να βρεθεί το άθροισμα των 10 θετικών πρώτων αριθμών που θα συναντήσετε οι οποίοι μπορούν να διαιρεθούν ακριβώς ο καθένας τους, χωρίς να αφήνει υπόλοιπο, με όλους τους αριθμούς από το 1 μέχρι το 10. 

Χωρίς πίνακες εννοείται και με τη μικρότερη πολυπλοκότητα.