Αποστολέας Θέμα: Άσκηση [Δύσκολη]  (Αναγνώστηκε 2106 φορές)

DaKnOb

  • Software Developer. Vulnerability Researcher.
  • Θαμώνας
  • ***
  • Μηνύματα: 38
  • Software Developer. Vulnerability Researcher.
    • DaKnOb
Άσκηση [Δύσκολη]
« στις: 25 Ιαν 2013, 09:48:39 μμ »
Γειά σας! Πριν λίγες ώρες σκέφτηκα μια ενδιαφέρουσα άσκηση (που δύσκολο να μπει, αλλά δεν πειράζει) και μου πήρε 30' - 1 ώρα να την λύσω. Είναι λίγο μεγάλη η εκφώνηση, αλλά αξίζει.

Euler's Phi
Το Φ είναι μια ιδιότητα ακέραιων θετικών αριθμών που υπολογίζεται βάση των πόσων θετικών ακέραιων αριθμών, μικρότερων του ίδιου του ακέραιου δεν έχουν κανέναν κοινό παράγοντα με αυτόν τον αριθμό.

Π.Χ.: Φ(12) = 4
Πως βγήκε αυτό;

[1]  -> Προσμετράται στον υπολογισμό
(2)  -> Παράγοντας του 12, άρα δεν προσμετράται
(3)  -> Παράγοντας του 12, άρα δεν προσμετράται
(4)  -> Παράγοντας του 12, άρα δεν προσμετράται
[5]  -> Παράγοντες: 1,5 (Κανένας κοινός με του 12, άρα προσμετράται)
(6)  -> Παράγοντας του 12, άρα δεν προσμετράται
[7]  -> Παράγοντες: 1,7 (Κανένας κοινός με του 12, άρα προσμετράται)
(8 )  -> Παράγοντες: 1,2,4,8 (Τα 2 και 4 είναι κοινά με του 12, άρα δεν προσμετράται)
(9)  -> Παράγοντες: 1,3,9 (Το 3 είναι κοινό με το 12, άρα δεν προσμετράται)
(10) ->Παράγοντες: 1,2,5,10 (Το 2 είναι κοινό με το 12, άρα δεν προσμετράται)
[11] ->Παράγοντες: 1,11 (Κανένας κοινός με του 12, άρα προσμετράται)
(12) ->Ο ίδιος ο αριθμός δεν προσμετράται

Καταλήξαμε λοιπόν πως 4 αριθμοί προσμετρώνται. Οι 1,5,7,11. Άρα το Φ(12) = 4.

Να γίνει αλγόριθμος που θα υπολογίζει το Φ() ενός ακέραιου θετικού αριθμού.

Enjoy. :P
« Τελευταία τροποποίηση: 25 Ιαν 2013, 10:37:46 μμ από DaKnOb »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3147
  • to Iterate is human to Recurse divine
Απ: Άσκηση [Δύσκολη]
« Απάντηση #1 στις: 25 Ιαν 2013, 10:13:21 μμ »
Το παρακάτω υπολογίζει τη συνάρτηση του Euler φ(ν) σχετικά γρήγορα, τουλάχιστον στα πλαίσια του μαθήματος της Ανάπτυξης
ίσως να μου ξέφυγε κάτι αλλά η γενική ιδέα φαίνεται νομίζω

Κώδικας: [Επιλογή]
ι <- 2
φ <- ν
Όσο   ι*ι <= ν    Επανάλαβε
    Αν ν mod ι = 0   Τότε   φ <- φ – φ div ι
    Όσο ν mod ι = 0 Επανάλαβε
        ν <-- ν div ι
   Τέλος_Επανάληψης
   ι <- ι + 1
Τέλος_Επανάληψης
Αν (ν > 1)  Τότε  φ <-  φ – φ div ν

edit: διορθώσεις μετά από παρατηρήσεις του gthal
« Τελευταία τροποποίηση: 27 Ιαν 2013, 02:10:34 μμ από evry »
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

DaKnOb

  • Software Developer. Vulnerability Researcher.
  • Θαμώνας
  • ***
  • Μηνύματα: 38
  • Software Developer. Vulnerability Researcher.
    • DaKnOb
Απ: Άσκηση [Δύσκολη]
« Απάντηση #2 στις: 25 Ιαν 2013, 10:37:23 μμ »
Να πω την αλήθεια αρκετά λείπουν, όπως μερικά τότε, τι είναι εκείνο το 2 και τι εκείνο το ν. Θα το κοιτάξω καλύτερα και θα προσπαθήσω να καταλάβω τι παίζει..

Υ.Γ.: Ξέχασα να πω πως εδώ έχει ένα script εύρεσης του Φι

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3147
  • to Iterate is human to Recurse divine
Απ: Άσκηση [Δύσκολη]
« Απάντηση #3 στις: 25 Ιαν 2013, 10:49:58 μμ »
Κάποια hints:

1. Όταν ψάχνουμε για πρώτους αρκεί να ψάξουμε μέχρι τη ρίζα του αριθμού ν. Αποδεικνύεται σχετικά εύκολα και μπορεί να δειχτεί στους μαθητές και εμπειρικά. π.χ. αν εξετάσεις όλα τα ζευγάρια διαιρετών του 100 θα δεις γιατί αρκεί να ελέγξουμε μέχρι το 10.
2.  Χρησιμοποιώ ι*ι για να αποφύγω τη ρίζα
3. Ουσιαστικά ο αλγόριθμος κάνει κάποιου είδους ας πούμε ανάλυση πρώτων παραγόντων

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

DaKnOb

  • Software Developer. Vulnerability Researcher.
  • Θαμώνας
  • ***
  • Μηνύματα: 38
  • Software Developer. Vulnerability Researcher.
    • DaKnOb
Απ: Άσκηση [Δύσκολη]
« Απάντηση #4 στις: 25 Ιαν 2013, 10:55:05 μμ »
Κάποια hints:

1. Όταν ψάχνουμε για πρώτους αρκεί να ψάξουμε μέχρι τη ρίζα του αριθμού ν. Αποδεικνύεται σχετικά εύκολα και μπορεί να δειχτεί στους μαθητές και εμπειρικά. π.χ. αν εξετάσεις όλα τα ζευγάρια διαιρετών του 100 θα δεις γιατί αρκεί να ελέγξουμε μέχρι το 10.
2.  Χρησιμοποιώ ι*ι για να αποφύγω τη ρίζα
3. Ουσιαστικά ο αλγόριθμος κάνει κάποιου είδους ας πούμε ανάλυση πρώτων παραγόντων

Αν τον τρέξεις με το χέρι για κάποιον μικρό αριθμό θα καταλάβεις πως δουλεύει

Για τους πρώτους αριθμούς ισχύει ο παρακάτω τύπος (παρεπιπτόντως):
Φ(Ν) = Ν - 1
Ν: Πρώτος Αριθμός
Το θέμα είναι τι γίνεται με αριθμούς που δεν είναι πρώτοι. Αν πχ ελεγχαμε μέχρι την ρίζα του αριθμού, τότε το 8 και το 9 δεν θα αποκλείονταν, ενώ στην πραγματικότητα πρέπει. Το Φ() δεν είναι οι παράγοντες ενός αριθμού αλλά όλοι οι αριθμοί που όσο και να τους παραγοντοποιήσεις δεν θα βρεις ποτέ έναν παράγοντα που ανήκει στο Ν.

DaKnOb

  • Software Developer. Vulnerability Researcher.
  • Θαμώνας
  • ***
  • Μηνύματα: 38
  • Software Developer. Vulnerability Researcher.
    • DaKnOb
Απ: Άσκηση [Δύσκολη]
« Απάντηση #5 στις: 25 Ιαν 2013, 11:07:45 μμ »
ακριβώς, όταν λέω πρώτοι εννοούσα πρώτοι ως προς το Ν. Ένας αριθμός M είναι πρώτος ως προς το Ν αν ΜΚΔ(Μ, Ν) = 1

Τα παραπάνω που είπα είναι κάποιες γενικές υποδείξεις που έχουν σχέση με τη λογική του αλγορίθμου και θεώρησα ότι ίσως να βοηθήσουν για να καταλάβει κάποιος τη λογική του

Ακριβώς. Ένας τρόπος είναι να κοιτάμε το ΜΚΔ με κάθε αριθμό και στο τέλος να κρατάμε αυτούς που είχαν αποτέλεσμα 1. Ο άλλος είναι αυτός που έκανα εγώ σε 24 γραμμούλες:

Εδώ

Αν η γλώσσα είχε καλό float precision θα μπορούσαμε να πάρουμε έναν πιο αποδοτικό τύπο, αλλά δεν.. :P

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3147
  • to Iterate is human to Recurse divine
Απ: Άσκηση [Δύσκολη]
« Απάντηση #6 στις: 25 Ιαν 2013, 11:10:46 μμ »
αυτό το Αν ι=1 που έχεις μέσα στην επανάληψη νομίζω ότι δημιουργεί πολλούς περιττούς ελέγχους.
όπως και το Φ <- Φ δεν χρειάζεται
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

DaKnOb

  • Software Developer. Vulnerability Researcher.
  • Θαμώνας
  • ***
  • Μηνύματα: 38
  • Software Developer. Vulnerability Researcher.
    • DaKnOb
Απ: Άσκηση [Δύσκολη]
« Απάντηση #7 στις: 25 Ιαν 2013, 11:20:06 μμ »
αυτό το Αν ι=1 που έχεις μέσα στην επανάληψη νομίζω ότι δημιουργεί πολλούς περιττούς ελέγχους.
όπως και το Φ <- Φ δεν χρειάζεται

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

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

Γενικά, σαν ιδέα (η άσκηση) πως σου φάνηκε;

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 541
  • There can be only one...may it be AEPP.
Απ: Άσκηση [Δύσκολη]
« Απάντηση #8 στις: 26 Ιαν 2013, 01:46:04 πμ »
Πολύ καλή DaKnOb. Μου άρεσε υπερβολικά. :)
Η απάντησή σου είναι πολύ καλή.
 
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 541
  • There can be only one...may it be AEPP.
Απ: Άσκηση [Δύσκολη]
« Απάντηση #9 στις: 26 Ιαν 2013, 01:50:39 πμ »
Εγώ το σκέφτηκα κάπως έτσι:

Αρχή_επανάληψης
Εμφάνισε "Δώσε αριθμό για Euler"
  Διάβασε χ
Μέχρις_ότου Α_Μ(χ) = χ και χ > 0
μ ← 1
Για i από 2 μέχρι χ - 1
  Αν χ mod i ≠ 0 τότε
    flag ← Ψευδής
    j ← 2
    Όσο j ≤ i - 1 και flag = Ψευδής επανάλαβε
      Αν i mod j = 0 και χ mod j = 0 τότε
        flag ← Αληθής
      Τέλος_αν
      j ← j + 1
    Τέλος_επανάληψης
    Αν flag = Ψευδής τότε
      μ ← μ + 1
    Τέλος_αν
  Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε "Φ(", χ, ")=", μ

Φυσικά χωλαίνει αρκετά, από την λύση που έδωσε ο evry του οποίου τη θεωρώ άριστη.
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

DaKnOb

  • Software Developer. Vulnerability Researcher.
  • Θαμώνας
  • ***
  • Μηνύματα: 38
  • Software Developer. Vulnerability Researcher.
    • DaKnOb
Απ: Άσκηση [Δύσκολη]
« Απάντηση #10 στις: 26 Ιαν 2013, 01:09:17 μμ »
Και εδώ η λύση που έδωσε ο καθηγητής μου (στο φροντιστήριο) που επίσης λειτουργεί και βασίζεται αρκετά στα πρότυτπα του σχολικού βιβλίου:

Κώδικας: [Επιλογή]
Αλγόριθμος myway
Αρχή_επανάληψης
    Εμφάνισε "Δώστε ακέραιο"
    Διάβασε Ν
Μέχρις_ότου Ν >0 ΚΑΙ Α_Μ(Ν) = Ν

Κ← 0
Για i από 2 μέχρι Ν-1
    Αν Ν mod i = 0 τότε ! το i είναι παράγοντας του Ν και το αποθηκεύω σε πίνακα
         Κ← Κ + 1
         Α[Κ] ← i
    Τέλος_αν
Τέλος_επανάληψης
!εμφανίζω τους παράγοντες του Ν
Για λ από 1 μέχρι Κ
    Εμφάνισε " παράγοντας του ",Ν, " είναι ο "  ,Α[λ]
Τέλος_επανάληψης

! Για κάθε αριθμό από Ν-1 μέχρι 2 δοκιμάζω αν διαιρείται με έναν από τους παράγοντες του Ν
Φ← 1
Για h από Ν-1 μέχρι 2 με_βήμα -1
    done ← Αληθής
    ρ ← 1
    Όσο ρ ≤ Κ ΚΑΙ done = Αληθής επανάλαβε
        Αν h mod Α[ρ] = 0 τότε
            done ← Ψευδής
        αλλιώς
            ρ← ρ +1
        Τέλος_αν
    Τέλος_επανάληψης
    Αν done = Αληθής τότε
            Φ← Φ+1
    Τέλος_αν
Τέλος_επανάληψης   

Εμφάνισε Φ
Τέλος myway

gthal

  • Ομάδα διαγωνισμάτων 2017
  • *
  • Μηνύματα: 891
Απ: Άσκηση [Δύσκολη]
« Απάντηση #11 στις: 27 Ιαν 2013, 11:09:53 πμ »
Μας τρέλανες πάλι Ευριπίδη!
Ο μάγος των ακεραίων διαιρέσεων!!  ;)
Φαίνεται ότι υπάρχουν υπέροχες ιδέες εδώ μέσα και θέλω λίγη ακόμα βοήθεια για να τον καταλάβω:
(καλά, φαντάζομαι λείπει μια    ι<-ι+1   και το τέλος_επανάληψης - το προσπερνάμε)
Υποψιάζομαι (σχεδόν) τι κάνεις με την Όσο ν mod ι = 0 ...
αλλά δεν μπορώ καθόλου να καταλάβω τι κάνει η Αν (ν > 1)  Τότε  φ <--  φ – φ div ν
(εντύπωση ακόμα μου κάνει που δεν ξεκινάς με φ <- ν-1  και δε βρίσκω πώς αυτό διορθώνεται στην πορεία)

Επίσης να πω ότι κάτι μάλλον πάει στραβά για μεγαλύτερους αριθμούς αφού πχ για ν=100 μας δίνει φ=37 αντι 40
Για δες το ...
Φιλικά,
Γιώργος Θαλασσινός

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3147
  • to Iterate is human to Recurse divine
Απ: Άσκηση [Δύσκολη]
« Απάντηση #12 στις: 27 Ιαν 2013, 02:07:47 μμ »
Γιώργο έχεις δίκιο, μάλλον μου ξέφυγαν πολλά τελικά.
Προφανώς δεν σκέφτηκα αυτή τη λύση τώρα. Είχα αντιμετωπίσει το πρόβλημα παλιά και με αρκετό ψάξιμο και διάβασμα κατέληξα στον παραπάνω αλγόριθμο.
Εκμεταλλεύτηκα τις παρακάτω ιδιότητες της συνάρτησης:

Φ(α*β) = Φ(α)*Φ(β)

και το γεγονός ότι αν θεωρήσουμε ότι οι πρώτοι παράγοντες του ν είναι οι p1, p2, ..., pk
τότε ισχύει
Φ(ν) = ν*(1 - 1/p1 ) * (1 - 1/p2 ) * ... * (1 - 1/pk)

αν θυμάμαι καλά.

Αν βρω λίγο χρόνο θα δώσω και τις αναφορές μου.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

noname

  • Ομάδα διαγωνισμάτων 2013
  • *
  • Μηνύματα: 190
Απ: Άσκηση [Δύσκολη]
« Απάντηση #13 στις: 27 Ιαν 2013, 03:10:40 μμ »
Για δες και αυτό:

Κώδικας: [Επιλογή]
Αλγόριθμος ΦΦ
Αρχή_επανάληψης
  Διάβασε Χ
Μέχρις_ότου Χ > 0 και Α_Μ(Χ) = Χ
Φ ← 0
Για ι από 1 μέχρι Χ
  Α ← Χ
  Β ← ι
  Γ ← Β
!Εύρεση  Α=ΜΚΔ(Χ, ι)
 Όσο Γ ≠ 0 επανάλαβε
    Γ ← Α mod Β
    Α ← Β
    Β ← Γ
  Τέλος_επανάληψης
  Αν Α = 1 τότε Φ ← Φ + 1
Τέλος_επανάληψης
Εμφάνισε Φ
Τέλος ΦΦ

DaKnOb

  • Software Developer. Vulnerability Researcher.
  • Θαμώνας
  • ***
  • Μηνύματα: 38
  • Software Developer. Vulnerability Researcher.
    • DaKnOb
Απ: Άσκηση [Δύσκολη]
« Απάντηση #14 στις: 27 Ιαν 2013, 06:48:15 μμ »
Για δες και αυτό:

Κώδικας: [Επιλογή]
Αλγόριθμος ΦΦ
Αρχή_επανάληψης
  Διάβασε Χ
Μέχρις_ότου Χ > 0 και Α_Μ(Χ) = Χ
Φ ← 0
Για ι από 1 μέχρι Χ
  Α ← Χ
  Β ← ι
  Γ ← Β
!Εύρεση  Α=ΜΚΔ(Χ, ι)
 Όσο Γ ≠ 0 επανάλαβε
    Γ ← Α mod Β
    Α ← Β
    Β ← Γ
  Τέλος_επανάληψης
  Αν Α = 1 τότε Φ ← Φ + 1
Τέλος_επανάληψης
Εμφάνισε Φ
Τέλος ΦΦ

Μια χαρά. Και μόλις παρατήρησα πως όλες οι δυνάμεις του δύο έχουν σαν Φ() την αμέσως προηγούμενη δύναμη.. :P