Παρασκευή, 26 Μαρτίου 2010

Οι πρώτοι 100 [πρώτοι αριθμοί]

Πρώτος, καλείται ένας φυσικός μεγαλύτερος του 1, που διαιρείται ακριβώς μόνο με την μονάδα και τον εαυτό του. Θα γνωρίζετε, υποθέτω, την μέθοδο εντοπισμού τους από τον Ερατοσθένη - το κόσκινο του Ερατοσθένη.

Παραδείγματα πρώτων αριθμών : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 ...

Ο αριθμός 2 είναι ο μόνος άρτιος (ζυγός) πρώτος αριθμός. Οι υπόλοιποι πρώτοι αριθμοί είναι περιττοί (μονοί).

Θέλουμε να φτιάξουμε ένα πρόγραμμα που θα υπολογίζει τους πρώτους 100 πρώτους αριθμούς. Ο έλεγχος για το αν κάποιος αριθμός είναι πρώτος θα γίνεται με μια λογική συνάρτηση.

Μέσα στην συνάρτηση θα προσπαθούμε να βρούμε αν ο δοθείς αριθμός Ξ διαιρείται με διαδοχικούς περιττούς αριθμούς, από 3 μέχρι Τετραγωνική_Ρίζα(Ξ). Δεν υπάρχει λόγος να ψάξουμε για μεγαλύτερους διαιρέτες, γιατί θα τους έχουμε ήδη συναντήσει ως πηλίκα, και θα έχουμε μάθει αν ο αριθμός Ξ διαιρείται.

Παραδείγματα :

16=2*8=4*4=8*2. Δεν ψάχνουμε για διαιρέτη πέρα από το 4.

60=2*30=3*20=4*15=5*12=6*10=10*6=12*5=15*4=20*3=30*2. Δεν ψάχνουμε για διαιρέτη πέρα από το Τ_Ρ(64)=7 κόμμα κάτι.

Η δική μου πρόταση φαίνεται παρακάτω. (Συμβουλή για ερευνητές : Αν η ταχύτητα υπολογισμού είναι σημαντική, για πολύ μεγάλα Ξ, δεν διαιρούμε με περιττούς από 3 μέχρι την ρίζα Ξ, αλλά διαιρούμε με πρώτους μέχρι την ρίζα Ξ).

ΠΡΟΓΡΑΜΜΑ πρωτοι
! πρώτος καλείται ο φυσικός αριθμός που διαιρείται ακριβώς
! μόνο με την μονάδα και τον εαυτό του.
! Εδώ θα βρούμε και θα γράψουμε τους πρώτους 100 πρώτους αριθμούς
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: ΠΡ[100], i, imax, Ξ
ΑΡΧΗ
imax <- 100
ΠΡ[1] <- 2
i <- 1 ! το i μετράει πόσους πρώτους έχουμε βρεί
Ξ <- 3 ! ελέγχουμε μόνο τους περιττούς από το 3 και μετά
ΟΣΟ i < imax ΕΠΑΝΑΛΑΒΕ
ΑΝ einaiprotos(Ξ) ΤΟΤΕ
i <- i + 1
ΠΡ[i] <- Ξ
ΤΕΛΟΣ_ΑΝ
Ξ <- Ξ + 2
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ imax ΜΕ_ΒΗΜΑ 10
ΓΡΑΨΕ ΠΡ[i], ΠΡ[i + 1], ΠΡ[i + 2], ΠΡ[i + 3], ΠΡ[i + 4], ΠΡ[i + 5], ΠΡ[i + 6], ΠΡ[i + 7], ΠΡ[i + 8], ΠΡ[i + 9]
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
!
ΣΥΝΑΡΤΗΣΗ einaiprotos(Ξ): ΛΟΓΙΚΗ
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Ξ, Σ
ΠΡΑΓΜΑΤΙΚΕΣ: ΡΙΖΑΞ
ΛΟΓΙΚΕΣ: διαιρείται
ΑΡΧΗ
ΡΙΖΑΞ <- Α_Μ(Τ_Ρ(Ξ))
Σ <- 3 ! οι διαιρέτες θα είναι περιττοί, από το 3 και μετά
διαιρείται <- ΨΕΥΔΗΣ
ΟΣΟ (Σ <= ΡΙΖΑΞ) ΚΑΙ (διαιρείται = ΨΕΥΔΗΣ) ΕΠΑΝΑΛΑΒΕ
ΑΝ Ξ MOD Σ = 0 ΤΟΤΕ
διαιρείται <- ΑΛΗΘΗΣ
ΤΕΛΟΣ_ΑΝ
Σ <- Σ + 2
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
einaiprotos <- ΑΛΗΘΗΣ
ΑΝ διαιρείται ΤΟΤΕ
einaiprotos <- ΨΕΥΔΗΣ
ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ


Το εξαγόμενο είναι το ακόλουθο :
  2   3   5   7  11  13  17  19  23  29
 31  37  41  43  47  53  59  61  67  71
 73  79  83  89  97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541

Τετάρτη, 24 Μαρτίου 2010

Γρίφος Kasparov

Σε ένα ιστολόγιο για γρίφους έγινε μια ανάρτηση που ζητούσε να αποδείξουμε ότι

 YUSUPOV +
 SOKOLOV +
 2KARPOV =
KASPAROV

παίζοντας με τα ονόματα διάσημων παικτών σκακιού.

Σε γρίφους αυτού του είδους κάθε γράμμα αντιστοιχεί σε έναν αριθμό.
Συνήθως δεν είναι 0 το πρώτο γράμμα της λέξης, άρα υποθέτουμε ότι τα Y S K δεν είναι μηδενικά.
Στο ψηφίο των μονάδων V + V + V δίνει αριθμό που λήγει σε V, άρα μπορεί να είναι 0 ή 5. Άν είναι V=0, τότε στο ψηφίο των δεκάδων O + O + O δίνει O, άρα O=5.
Το K στο άθροισμα μπορεί να είναι 1 ή 2.

Μπορείτε να γράψετε ένα πρόγραμμα που να λύνει τον γρίφο;

Η δική μου προσπάθεια ακολουθεί παρακάτω :

ΠΡΟΓΡΑΜΜΑ KASPAROV
! YUSUPOV + SOKOLOV + 2KARPOV = KASPAROV
ΜΕΤΑΒΛΗΤΕΣ
ΑΚΕΡΑΙΕΣ: Y, U, S, P, O, V, K, L, A, R, X1, X2, X3, X4, MANY
ΑΡΧΗ
MANY <- 0
ΓΙΑ Y ΑΠΟ 1 ΜΕΧΡΙ 9
_ΓΙΑ U ΑΠΟ 0 ΜΕΧΡΙ 9
__ΑΝ U<>Y ΤΟΤΕ
___ΓΙΑ S ΑΠΟ 1 ΜΕΧΡΙ 9
____ΑΝ S<>Y ΚΑΙ S<>U ΤΟΤΕ
_____ΓΙΑ P ΑΠΟ 0 ΜΕΧΡΙ 9
______ΑΝ P<>Y ΚΑΙ P<>U ΚΑΙ P<>S ΤΟΤΕ
_______ΓΙΑ O ΑΠΟ 0 ΜΕΧΡΙ 9
________ΑΝ O<>Y ΚΑΙ O<>U ΚΑΙ O<>S ΚΑΙ O<>P ΤΟΤΕ
_________ΓΙΑ V ΑΠΟ 0 ΜΕΧΡΙ 5 ΜΕ ΒΗΜΑ 5
__________ΑΝ V<>Y ΚΑΙ V<>U ΚΑΙ V<>S ΚΑΙ V<>P ΚΑΙ V<>O ΤΟΤΕ
___________ΓΙΑ K ΑΠΟ 1 ΜΕΧΡΙ 2
____________ΑΝ K<>Y ΚΑΙ K<>U ΚΑΙ K<>S ΚΑΙ K<>P ΚΑΙ K<>O ΤΟΤΕ
____________ΑΝ K<>V ΤΟΤΕ
_____________ΓΙΑ L ΑΠΟ 0 ΜΕΧΡΙ 9
______________ΑΝ L<>Y ΚΑΙ L<>U ΚΑΙ L<>S ΚΑΙ L<>P ΚΑΙ L<>O ΤΟΤΕ
______________ΑΝ L<>V ΚΑΙ L<>K ΤΟΤΕ
_______________ΓΙΑ A ΑΠΟ 0 ΜΕΧΡΙ 9
________________ΑΝ A<>Y ΚΑΙ A<>U ΚΑΙ A<>S ΚΑΙ A<>P ΚΑΙ A<>O ΤΟΤΕ
________________ΑΝ A<>V ΚΑΙ A<>K ΚΑΙ A<>L ΤΟΤΕ
_________________ΓΙΑ R ΑΠΟ 0 ΜΕΧΡΙ 9
__________________ΑΝ R<>Y ΚΑΙ R<>U ΚΑΙ R<>S ΚΑΙ R<>P ΚΑΙ R<>O ΤΟΤΕ
__________________ΑΝ R<>V ΚΑΙ R<>K ΚΑΙ R<>L ΚΑΙ R<>A ΤΟΤΕ
_________X1 <- (((((Y*10 + U)*10 + S)*10 + U)*10 + P)*10 + O)*10 + V
_________X2 <- (((((S*10 + O)*10 + K)*10 + O)*10 + L)*10 + O)*10 + V
_________X3 <- (((((20 + K)*10 + A)*10 + R)*10 + P)*10 + O)*10 + V
_________X4 <- ((((((K*10 + A)*10 + S)*10 + P)*10 + A)*10 + R)*10 + O)*10 + V
___________________MANY <- MANY + 1
___________________ΑΝ X1 + X2 + X3 = X4 ΤΟΤΕ
____________________ΓΡΑΨΕ MANY, ' RESULT ', Y, U, S, P, O, V, K, L, A, R
___________________ΤΕΛΟΣ_ΑΝ
__________________ΤΕΛΟΣ_ΑΝ
__________________ΤΕΛΟΣ_ΑΝ
_________________ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
________________ΤΕΛΟΣ_ΑΝ
________________ΤΕΛΟΣ_ΑΝ
_______________ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
______________ΤΕΛΟΣ_ΑΝ
______________ΤΕΛΟΣ_ΑΝ
_____________ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
____________ΤΕΛΟΣ_ΑΝ
____________ΤΕΛΟΣ_ΑΝ
___________ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
__________ΤΕΛΟΣ_ΑΝ
_________ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
________ΤΕΛΟΣ_ΑΝ
_______ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
______ΤΕΛΟΣ_ΑΝ
_____ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
____ΤΕΛΟΣ_ΑΝ
___ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
__ΤΕΛΟΣ_ΑΝ
_ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

Η εντολή
ΓΡΑΨΕ MANY, ' RESULT ', Y, U, S, P, O, V, K, L, A, R
δίνει αποτέλεσμα
136920 RESULT 9 7 4 2 5 0 1 8 6 3

άρα η πρόσθεση είναι
 9747250+
 4515850+
 2163250=
16426350

Δευτέρα, 22 Μαρτίου 2010

Ημερομηνία του Πάσχα

Πλησιάζει το Πάσχα (των Ορθοδόξων) και θέλουμε να μάθουμε πότε ακριβώς "πέφτει".
Θα χρησιμοποιήσουμε την μέθοδο Gauss.
Στο σημερινό πρόγραμμα διαβάζουμε το τετραψήφιο έτος και με ένα υποπρόγραμμα βρίσκουμε την ημερομηνία του Πάσχα και ένα λεκτικό για τον μήνα (στην γενική πτώση).
Το υποπρόγραμμα Βρες_Πάσχα θα παίρνει μία παράμετρο εισόδου [έτος] και θα επιστρέφει δύο παραμέτρους εξόδου [ημερομηνία, μηνός], άρα θα είναι διαδικασία. (Για μία παράμετρο εξόδου, αρκούσε ένα υποπρόγραμμα συνάρτηση).

ΠΡΟΓΡΑΜΜΑ πασχα
! υπολογίζουμε την ημερομηνία του Πάσχα για δεδομένο έτος
__ΜΕΤΑΒΛΗΤΕΣ
____ΑΚΕΡΑΙΕΣ: έτος, ημερομηνία
____ΧΑΡΑΚΤΗΡΕΣ: μηνός
ΑΡΧΗ
__ΑΡΧΗ_ΕΠΑΝΑΛΗΨΗΣ
____ΓΡΑΨΕ 'Δώσε έτος τετραψήφιο : '
____ΔΙΑΒΑΣΕ έτος
__ΜΕΧΡΙΣ_ΟΤΟΥ έτος > 1900
__ΚΑΛΕΣΕ ΒρεςΠάσχα(έτος, ημερομηνία, μηνός)
__ΓΡΑΨΕ 'Το έτος ', έτος, ' έχει το πάσχα στις ', ημερομηνία, μηνός
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ
!
ΔΙΑΔΙΚΑΣΙΑ ΒρεςΠάσχα(ετο, ημε, μην)
__ΜΕΤΑΒΛΗΤΕΣ
____ΑΚΕΡΑΙΕΣ: αα, ββ, γγ, δδ, ετο, ζζ, ημε
____ΧΑΡΑΚΤΗΡΕΣ: μην
ΑΡΧΗ
__αα <- ετο MOD 19
__ββ <- ετο MOD 4
__γγ <- ετο MOD 7
__δδ <- (19*αα + 16) MOD 30
__ζζ <- (2*ββ + 4*γγ + 6*δδ) MOD 7
__ημε <- 3 + δδ + ζζ
__μην <- ' Απριλίου'
__ΑΝ ημε > 30 ΤΟΤΕ
____ημε <- ημε - 30
____μην <- ' Μαΐου'
__ΤΕΛΟΣ_ΑΝ
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ

Η εκτέλεση του προγράμματος είναι κάπως έτσι :

Δώσε έτος τετραψήφιο:
2010
Το έτος 2010 έχει το πάσχα στις 4 Απριλίου