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

Ξεκίνησε από olga_ath, 13 Οκτ 2010, 02:47:27 ΜΜ

« προηγούμενο - επόμενο »

nikolasmer

Παράθεση από: pgrontas στις 21 Ιαν 2013, 10:42:42 ΜΜ
Πάντως η δυσκολία σε αυτή την άσκηση δεν είναι αλγοριθμική.
Η δυσκολία είναι στο ότι οι μαθητές δεν κατανοούν τι σημαίνει αναπαράσταση και αξία ενός αριθμού.

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

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

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

ofilos13

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

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

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

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

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


Παράθεση από: ofilos13 στις 27 Νοε 2014, 01:11:45 ΜΜ
Θα μπουρουσε καποιος να μου δωσει την ακριβης λυση του παρακατω αλγοριθμου.

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

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


nikolasmer

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

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

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

Καμία ιδέα για μικρότερη πολυπλοκότητα;  :-\   
Μερεντίτης Νικόλαος
Πληροφορικός

evry

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

Αν θες κάτι πολύ γρήγορο δοκίμασε το κόσκινο του Ερατοσθένη. Αν η απαραίτητη μνήμη που διαθέτεις αρκεί είναι εξαιρετικά γρήγορο
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

sstergou

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

nikolasmer

Παράθεση από: sstergou στις 17 Δεκ 2014, 03:46:00 ΜΜ
...... υλοποιείται και με πίνακα λογικών μεταβλητών.

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

sstergou

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

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

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

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

nikolasmer

Παράθεση από: sstergou στις 17 Δεκ 2014, 04:44:20 ΜΜ
Αλγόριθμος Ερατοσθένης
Δεδομένα //Ν//
Για i από 1 μέχρι Ν 
	Είναι_Πρώτος[i] ← Αληθής
Τέλος_επανάληψης

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

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

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

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

petrosp13

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

itt

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

pstasinos

Παράθεση από: sstergou στις 17 Δεκ 2014, 04:44:20 ΜΜ
Αλγόριθμος Ερατοσθένης
Δεδομένα //Ν//
Για i από 1 μέχρι Ν 
	Είναι_Πρώτος[i] ← Αληθής
Τέλος_επανάληψης

όριο ← Τ_Ρ(Ν)

[/quote]


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


Ευχαριστώ

sstergou

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

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


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

pstasinos

Παράθεση από: sstergou στις 27 Φεβ 2015, 10:24:03 ΠΜ
Δεν υπάρχει πρόβλημα.
Κάποια στιγμή το ι θα ξεπεράσει τον πραγματικό. Δεν είναι απαραίτητο για το όριο να είναι ακέραιος. Δεν ξέρω αν αυτό εννοούσες.

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

Ευχαριστώ

nikolasmer

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

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

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