[Ανάλυση Αλγορίθμων] Απορίες στις ασκησεις 2014

[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 με προσοχή στα ονόματα των αρχείων!

Για οποιοδήποτε πρόβλημα με register/login, στείλτε email στο contact@thmmy.gr.

[princess_of_the_dawn]

ε τον κοίταξα πάλι τον ορισμό,δεν καταλαβαίνωωωω   

βασικά αυτό με το όριο δεν το είχα σκεφτεί,εγώ απλά στην ανίσωση έβαλα νιοστές ρίζες και μετά έβαλα δυο τυχαίες τιμές για n kai c

[Exomag]

ε τον κοίταξα πάλι τον ορισμό,δεν καταλαβαίνωωωω   

βασικά αυτό με το όριο δεν το είχα σκεφτεί,εγώ απλά στην ανίσωση έβαλα νιοστές ρίζες και μετά έβαλα δυο τυχαίες τιμές για n kai c

Ο ορισμός λέει:


Στο συγκεκριμένο θέμα, ικανοποιούνται όλες οι προϋποθέσεις αυτές, άρα είναι το γ.

[princess_of_the_dawn]

Κοίτα να δεις ρε παιδί μου.Ενώ το βιβλίο το διάβασα αυτό με το όριο πρώτη φορά το είδα!
Ευχαριστώ!!

[pentium4]

Κοίτα να δεις ρε παιδί μου.Ενώ το βιβλίο το διάβασα αυτό με το όριο πρώτη φορά το είδα!
Ευχαριστώ!!

οκ σβήστηκα διορθώθηκα βασικά θα αυτοσβηστώ και σε λίγο ΔΙΑΦΑΝΕΙΕΣ

[xameno kormi]

δεν καταλαβαινω απο την ασκηση 16-1 ασκ 7 στο φυλλαδιο με τις ασκησεις του κεφ 16 το τελευταιο ερωτημα...στα d ειναι μεσα και το μονολεπτο ? αυτο το c[j - di] πως υπολογιζεται ? κι η μοναδα που εχει στο 1+ c[..] ειναι στην ουσια το μονολεπτο ? αν καταλαβε κανεις ας βοηθησει...! τνξ

[et3rn1ty]

δεν καταλαβαινω απο την ασκηση 16-1 ασκ 7 στο φυλλαδιο με τις ασκησεις του κεφ 16 το τελευταιο ερωτημα...στα d ειναι μεσα και το μονολεπτο ? αυτο το c[j - di] πως υπολογιζεται ? κι η μοναδα που εχει στο 1+ c[..] ειναι στην ουσια το μονολεπτο ? αν καταλαβε κανεις ας βοηθησει...! τνξ

Τα κέρματά σου έχουν πάντα μονόλεπτο, αλλιώς δεν λύνεται η άσκηση για κάθε ποσό. Κάποιο από τα d₁ ...  d_k είναι μονόλεπτο.

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

Το c είναι λοιπόν ο πίνακας που κουβαλάει τις λύσεις σου. Το κελί c[1] έχει τη λύση για ρέστα 1, το c[2] για ρέστα 2 κλπ... και το c[n] για ρέστα n, δηλαδή αυτό που θες.

Οπότε, ξεκινάς από κάτω προς τα πάνω (δηλαδή από το μικρότερό σου πρόβλημα, για ρέστα 0):
Προφανώς, το c[0] είναι 0, αφού τότε δίνεις 0 κέρματα για ρέστα.
Το c[1] είναι 1 κέρμα (αξίας 1 λεπτού) + την λύση για c[1-1] = 0... κλπ

Αν είχαμε μόνο μονόλεπτα θα ήταν εύκολη η ζωή μας (said no one ever), αλλά πες έχεις και δίλεπτα. Οπότε έχεις δύο επιλογές για το c[2]:
-Ή να δώσεις 1x1cent +{ την λύση για c[2-1] = c[1]=1 } (δύο κέρματα, άρα c[2] = 2)
-Ή να δώσεις 1x2cent + { την λύση για c[2-2] = c[0]=0 } (ένα κέρμα, άρα c[2]=1)
Ε, από αυτές τις λύσεις πάρε το minimum c.
Αυτό που έχω σε αγκύλες είναι το c[j-d_i] ουσιαστικά.


Έτσι προκύπτει το c[j] = 1 + min{c[j-d_i]}. d_i είναι η αξία του κέρματος.

[xameno kormi]

να σαι καλα ρε φιλε γτ εχω μπερδευτει λιγο..

[et3rn1ty]

Η αλήθεια είναι ότι είναι λίγο περίεργος ο Δυναμικός. Εμένα με βοήθησαν τα

• http://people.cs.clemson.edu/~bcdean/dp_practice/
• http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static
• http://www.codechef.com/wiki/tutorial-dynamic-programming
  

[princess_of_the_dawn]

στα θέματα 2007β(όχι ότι υπάρχουν και άλλα ) στο 1ο Θέμα τί βρήκατε;
επίσης αυτό δεν είναι ύλη α' προόδου;

[c0ndemn3d]

στα θέματα 2007β(όχι ότι υπάρχουν και άλλα ) στο 1ο Θέμα τί βρήκατε;
επίσης αυτό δεν είναι ύλη α' προόδου;

Όλη η ύλη είναι μέσα και πιστεύω πως είναι το d

[princess_of_the_dawn]

A!Στην αρχή νόμιζα ότι ήταν το β αλλά με μια δευτερη ματιά θαρρώ πως έχεις δίκιο.Θένκιου ε!

[MG9S]

παιδια για το 3ο 8εμα που καναμε σημερα στο μαθημα ποια ηταν η λυση για το α ερωτημα τελικα??

[Αλντεμπαράν]

'Ασκηση 15.2 "καλαισθητη εκτύπωση"

προφανώς δεν μπορεί να κοπεί μια λέξη στα δύο αν δεν χωράει ολοκληρη στην γραμμή έτσι ?

[c0ndemn3d]

Δεν κόβονται οι λέξεις

[princess_of_the_dawn]

Στο θέμα 1 β πρόοδος στο α ερώτημα που ζητάει αλγόριθμο του Prim: θέλει να γράψουμε τον αλγόριθμο ή να πούμε ότι από το α με μια τομή S βλέπουμε ότι η γραμμή με το ελάχιστο κόστος είναι  η τάδε,οπότε πάμε στο β πχ κλπ;;;