Άσκηση [Δύσκολη]

[DaKnOb]

Γειά σας! Πριν λίγες ώρες σκέφτηκα μια ενδιαφέρουσα άσκηση (που δύσκολο να μπει, αλλά δεν πειράζει) και μου πήρε 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.

[evry]

Το παρακάτω υπολογίζει τη συνάρτηση του Euler φ(ν) σχετικά γρήγορα, τουλάχιστον στα πλαίσια του μαθήματος της Ανάπτυξης
ίσως να μου ξέφυγε κάτι αλλά η γενική ιδέα φαίνεται νομίζω

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

edit: διορθώσεις μετά από παρατηρήσεις του gthal

[DaKnOb]

Να πω την αλήθεια αρκετά λείπουν, όπως μερικά τότε, τι είναι εκείνο το 2 και τι εκείνο το ν. Θα το κοιτάξω καλύτερα και θα προσπαθήσω να καταλάβω τι παίζει..

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

[evry]

Κάποια hints:

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

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

[DaKnOb]

Κάποια hints:

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

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

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

[DaKnOb]

ακριβώς, όταν λέω πρώτοι εννοούσα πρώτοι ως προς το Ν. Ένας αριθμός M είναι πρώτος ως προς το Ν αν ΜΚΔ(Μ, Ν) = 1

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

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

Εδώ

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

[evry]

αυτό το Αν ι=1 που έχεις μέσα στην επανάληψη νομίζω ότι δημιουργεί πολλούς περιττούς ελέγχους.
όπως και το Φ <- Φ δεν χρειάζεται

[DaKnOb]

αυτό το Αν ι=1 που έχεις μέσα στην επανάληψη νομίζω ότι δημιουργεί πολλούς περιττούς ελέγχους.
όπως και το Φ <- Φ δεν χρειάζεται

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

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

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

[nikolasmer]

Πολύ καλή DaKnOb. Μου άρεσε υπερβολικά.
Η απάντησή σου είναι πολύ καλή.

[nikolasmer]

Εγώ το σκέφτηκα κάπως έτσι:

Αρχή_επανάληψης
Εμφάνισε "Δώσε αριθμό για 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]

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

Αλγόριθμος 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]

Μας τρέλανες πάλι Ευριπίδη!
Ο μάγος των ακεραίων διαιρέσεων!! 
Φαίνεται ότι υπάρχουν υπέροχες ιδέες εδώ μέσα και θέλω λίγη ακόμα βοήθεια για να τον καταλάβω:
(καλά, φαντάζομαι λείπει μια    ι<-ι+1   και το τέλος_επανάληψης - το προσπερνάμε)
Υποψιάζομαι (σχεδόν) τι κάνεις με την Όσο ν mod ι = 0 ...
αλλά δεν μπορώ καθόλου να καταλάβω τι κάνει η Αν (ν > 1)  Τότε  φ <--  φ – φ div ν
(εντύπωση ακόμα μου κάνει που δεν ξεκινάς με φ <- ν-1  και δε βρίσκω πώς αυτό διορθώνεται στην πορεία)

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

[evry]

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

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

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

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

Αν βρω λίγο χρόνο θα δώσω και τις αναφορές μου.

[noname]

Για δες και αυτό:

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

[DaKnOb]

Για δες και αυτό:

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

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