3 Διάλεξη Τρίτη - 9 Δεκεμβρίου 2011

3.1 Ταξινόμηση (sorting) μιας λίστας

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

   1 ' This program reads a list of numbers
   2 ' from the user and orders it (sorts it)
   3 ' in ascending order
   4 CLS
   5 
   6 ' Declare variables
   7 DIM n, i, j AS INTEGER
   8 DIM t AS SINGLE
   9 
  10 ' Data input
  11 PRINT "Give n: ";
  12 INPUT n
  13 DIM dat(n) AS SINGLE
  14 FOR i = 1 TO n
  15  PRINT "Give No "; i
  16  INPUT dat(i)
  17 NEXT
  18 
  19 ' sort the elements
  20 FOR i = 1 TO n - 1
  21  ' the inner for loop below ensures that, after it finishes,
  22  ' the contents of dat(i) are correct and they will not change from then on
  23  FOR j = i + 1 TO n
  24   IF dat(i) > dat(j) THEN
  25    t = dat(i)
  26    dat(i) = dat(j)
  27    dat(j) = t
  28   END IF
  29  NEXT
  30 NEXT
  31 
  32 ' print the results
  33 FOR i = 1 TO n
  34  PRINT dat(i)
  35 NEXT

Το αρχείο l3/sort.bas

Στις γραμμές 7 και 8 έχουμε τις δηλώσεις των μεταβλητών που χρησιμοποιούμε εκτός του πίνακα όπου θα αποθηκεύσουμε τη λίστα. Ο πίνακας δηλώνεται στη γραμμή 13 αφού πρώτα ο χρήστης μας πει ποιο θα είναι το μήκος της λίστας στις γραμμές 11 και 12. Ο πίνακας dat δηλώνεται ως SINGLE αφού θα περιέχει πραγματικούς αριθμούς. Το ίδιο και η μεταβλητή t παραπάνω που χρησιμοποιείται στις γραμμές 25-27 για την ανταλλαγή των περιεχομένων δύο θέσεων του πίνακα dat και άρα οφείλει να είναι ίδιου τύπου (SINGLE) με τον πίνακα dat.

Τα στοιχεία του πίνακα τα διαβάζουμε από το χρήστη με μια ανακύκλωση FOR στις γραμμές 14-17.

Διπλή ανακύκλωση (nested loop)
Η ουσιαστική δουλειά της ταξινόμησης των περιεχομένων του πίνακα dat γίνεται στις γραμμές 20-30. Εκεί βλέπουμε μια ανακύκλωση FOR (η εξωτερική ανακύκλωση, που αρχίζει στη γραμμή 20 και τελειώνει με το NEXT της γραμμής 30) η οποία έχει μέσα της μια άλλη ανακύκλωση FOR (η εσωτερική ανακύκλωση, που αρχίζει στη γραμμή 23 και τελειώνει με το NEXT της γραμμής 29).

Στην εξωτερική ανακύκλωση η μεταβλητή i παίρνει διαδοχικά τιμές από 1 έως n-1. Σκοπός της εξωτερικής ανακύκλωσης είναι, μετά το τέλος του i-οστού κύκλου,

να έχει τοποθετήσει στις θέσεις dat(1), dat(2), ..., dat(i) τα σωστά στοιχεία της λίστας, χωρίς να καταστρέψει τα περιεχόμενα του πίνακα dat αλλά απλά αναδιατάσσοντάς τα μέσα στον πίνακα.

Μετά το τέλος δηλ. της πρώτης φοράς που εκτελείται η ανακύκλωση (για i=1 δηλαδή) αυτό που έχει επιτευχθεί είναι ότι στη θέση dat(1) βρίσκεται το μικρότερο στοιχείο της λίστας dat. Μετά το τέλος της 2ης εκτέλεσης (για i=2) η θέση dat(1) εξακολουθεί να έχει μέσα το σωστό στοιχείο αλλά τώρα και η dat(2) έχει μέσα της το σωστό αριθμό, δηλ. το δεύτερο πιο μικρό στοιχείο, κλπ. Μετά την τελευταία εκτέλεση του εξωτερικού FOR, για i=n-1, όλα τα στοιχεία

dat(1), dat(2), ..., dat(n-1)

έχουν μέσα τους τα σωστά περιεχόμενα. Για παράδειγμα στη θέση dat(n-1) βρίσκεται το 2ο μεγαλύτερο στοιχείο της λίστας, στη θέση dat(n-2) το 3ο μεγαλύτερο στοιχείο κλπ. Έτσι, αναγκαστικά, στη θέση dat(n) βρίσκεται το μεγαλύτερο στοιχείο της λίστας (το σωστό δηλ.).

Για να επιτευχθεί αυτό το αποτέλεσμα σε κάθε εκτέλεση του εξωτερικού FOR τρέχει (γραμμές 23-29) ένα άλλο εσωτερικό FOR, με δείκτη τη μεταβλητή j, η οποία διανύει διαδοχικά τις τιμές από i+1 έως n. Σε κάθε εκτέλεση του εσωτερικού FOR οι τιμές των μεταβλητών i και j δεν αλλάζουν και εκτελούνται οι γραμμές 24-28.

Στο IF που εκτείνεται από τη γραμμή 24 έως τη γραμμή 28 εκτελούνται οι γραμμές 25-27 μόνο στην περίπτωση που τα περιεχόμενα των θέσεων dat(i) και dat(j) δεν είναι στη σωστή σειρά. Αυτό συμβαίνει αν dat(i) > dat(j) μια και πάντα στο εσωτερικό FOR ισχύει i<j. Αν λοιπόν αυτό συμβαίνει τότε τα περιεχόμενα των dat(i) και dat(j) εναλλάσσονται στις γραμμές 25-27, με τη βοήθεια της προσωρινής μεταβλητής t. (Βεβαιωθείτε ότι καταλαβαίνετε πώς ακριβώς γίνεται αυτή η εναλλαγή στις γραμμές 25-27.)

Τέλος στις γραμμές 33-35 τυπώνεται η διατεταγμένη λίστα.

Άσκηση 31.
Στο παραπάνω πρόγραμμα sort.bas εισάγετε ανάμεσα στις γραμμές 23 και 24 τη γραμμή

PRINT "Cheking pair (" ; i ; ", " ; j ; ")"

Η εντολή αυτή δεν επηρεάζει τη λειτουργία του προγράμματος παρά μόνο όσον αφορά το τι τυπώνει στην οθόνη. Τι υποτίθεται ότι τυπώνει αυτή η γραμμή; Βεβαιωθείτε ότι καταλαβαίνετε το με ποια σειρά τυπώνονται τα ζεύγη.
$\surd$

Άσκηση 32.
Αποδείξτε ότι οι γραμμές 24-28 εκτελούνται το πολύ $n^2$ φορές κατά την εκτέλεση του προγράμματος sort.bas.
$\surd$

Το παρακάτω πρόγραμμα αποτελεί μια μικρή παραλλαγή του προγράμματος ταξινόμησης sort.bas.

   1 ' This program reads a list of strings (words)
   2 ' from the user and orders it (sorts it)
   3 ' in ascending order
   4 CLS
   5 
   6 ' Declare variables
   7 DIM n, i, j AS INTEGER
   8 DIM t AS STRING
   9 
  10 ' Data input
  11 PRINT "Give n: ";
  12 INPUT n
  13 DIM dat(n) AS STRING
  14 FOR i = 1 TO n
  15  PRINT "Give No "; i
  16  INPUT dat(i)
  17 NEXT
  18 
  19 ' sort the elements
  20 FOR i = 1 TO n - 1
  21  ' the inner for loop below ensures that, after it finishes,
  22  ' the contents of dat(i) are correct and they will not change from then on
  23  FOR j = i + 1 TO n
  24   IF dat(i) > dat(j) THEN
  25    t = dat(i)
  26    dat(i) = dat(j)
  27    dat(j) = t
  28   END IF
  29  NEXT
  30 NEXT
  31 
  32 ' print the results
  33 FOR i = 1 TO n
  34  PRINT dat(i)
  35 NEXT

Το αρχείο l3/sort1.bas

Το μόνο που έχει αλλάξει είναι οι τύποι των μεταβλητών t και dat που τώρα είναι STRING αντί για SINGLE που ήταν πριν.

Με STRING δηλώνουμε μεταβλητές που οι τιμές τους είναι ολόκληρα κομμάτια κειμένου.

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

DIM s AS STRING
s = "ABCD EFG abcd efg 12345"
PRINT s

Το άλλο πράγμα που έχει αλλάξει σε αυτό το πρόγραμμα από το sort.bas, χωρίς όμως να χρειαστεί εμείς να κάνουμε την αλλαγή, είναι το νόημα που αποδίδει η υπολογιστής στη συνθήκη που εμφανίζεται στο IF, δηλ. στη συνθήκη dat(i) > dat(j). Εφ' όσον τα δεδομένα που συγκρίνονται τώρα είναι τύπου STRING ο υπολογιστής τα συγκρίνει λεξικογραφικά. (Λεξικογραφική είναι η διάταξη των λέξεων σύμφωνα με την οποία είναι π.χ. ταξινομημένα τα επώνυμα στον τηλεφωνικό κατάλογο.)

3.2 Έλεγχος του αν ένας ακέραιος είναι πρώτος αριθμός

   1 ' This program decides if a number given by
   2 ' the user is prime
   3 CLS
   4 
   5 'Declare variables
   6 DIM n, k, r, found AS INTEGER
   7 
   8 
   9 ' Read n from user
  10 PRINT "Give N: "
  11 INPUT n
  12 
  13 
  14 ' Variable found=1 means that we have found a divisor
  15 ' of n, so n is not prime
  16 found = 0
  17 
  18 ' Check if n is divisible by k, for k
  19 ' as large as the square root of n
  20 FOR k = 2 TO SQR(n)
  21  IF found=1 THEN EXIT FOR
  22  r = n MOD k
  23  ' if (n mod k)=0 then k divides n
  24  IF r = 0 THEN
  25   PRINT "Found divisor: "; k
  26   found = 1
  27  END IF
  28 NEXT
  29 
  30 ' If no divisor found then n is prime
  31 IF found = 0 THEN
  32  PRINT n; " is prime"
  33 END IF

Το αρχείο l3/isprime.bas

Το παραπάνω πρόγραμμα isprime.bas ελέγχει αν ένας θεικός ακέραιος που δίνει ο χρήστης είναι πρώτος αριθμός ή όχι. Πρώτος λέγεται ένας φυσικός αριθμός αν οι μόνοι διαιρέτες του είναι ο εαυτός του και ο αριθμός 1, οι τετριμμένοι δηλ. διαιρέτες.

Το πρόγραμμά μας ψάχνει για διαιρέτες του n (που έχει δώσει ο χρήστης) κοιτώντας διαδοχικά τους ακεραίους 2, 3, 4, ..., έως και τον αριθμό $\sqrt{n}$. Δε χρειάζεται να ελέγξουμε πιθανούς διαιρέτες μεγαλύτερους του $\sqrt{n}$, γιατί ισχύει το εξής:

Θεώρημα 3.1   Αν ο φυσικός αριθμός $n$ έχει κάποιο μη τετριμμένο (διάφορο δηλ. των 1, $n$) διαιρέτη $k > \sqrt{n}$ τότε έχει και κάποιο μη τετριμμένο διαιρέτη $\ell < \sqrt{n}$.

Ο λόγος γι' αυτό είναι ότι αν $k$ διαιρεί το $n$ τότε ο $\ell = \frac{n}{k}$ είναι ακέραιος και αν υποθέσουμε ότι $\sqrt{n}<k<n$ έπεται εύκολα ότι $1 < \ell < \sqrt{n}$. Αν λοιπόν φτάσουμε μέχρι το $\sqrt{n}$ και δεν έχουμε βρει διαιρέτη του $n$ τότε είμαστε σίγουροι ότι δε θα βρούμε διαιρέτη ούτε μεγαλύτερο του $\sqrt{n}$, κάνοντας έτσι το πρόγραμμά μας σημαντικά πιο γρήγορο απ' ό,τι αν ήλεγχε όλους τους ακεραίους έως το $n$.

Η βασική μας ανακύκλωση είναι το FOR στις γραμμές 20-28, όπου η μεταβλητή k διανύει όλες τις ακέραιες τιμές από 2 έως $\sqrt{n}$. (Η τιμή $\sqrt{n}$ δεν είναι κατ' ανάγκη ακέραια, αλλά η BASIC την αντικαθιστά με το ακέραιο μέρος της πριν αρχίσει να τρέχει η ανακύκλωση.

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

Η μεταβλητή found χρησιμοποιείται για να μαρκάρουμε αν έχουμε βρεί κάποιο μη τετριμμένο διαιρέτη του n (found=0 σημαίνει ότι δεν έχουμε βρεί ακόμη και found=1 ότι έχουμε βρεί-γι'αυτό τη θέτουμε ίση με 0 πριν μπούμε στην ανακύκλωση στη γραμμή 16).

Μέσα στην ανακύκλωση ελέγχουμε πρώτ' απ' όλα αν έχουμε βρεί ήδη κάποιο διαιρέτη (IF found=1 THEN ...). Αν αυτό συμβαίνει τότε εκτελώντας την εντολή EXIT FOR (την οποία βλέπουμε για πρώτη φορά) σταματάει η εκτέλεση της ανακύκλωσης (ο έλεγχος μεταφέρεται στη θέση μετά το NEXT του FOR). Επίσης για πρώτη φορά βλέπουμε τη σύνταξη του IF σε μια γραμμή μόνο, χωρίς το END IF.

Αν τώρα found = 0, δεν έχουμε δηλ. μέχρι στιγμής βρει κάποιο διαιρέτη, τότε ελέγχουμε αν το k διαιρεί το n. Στη γραμμή 22 υπολογίζουμε το υπόλοιπο της διαίρεσης n δια k με την πράξη

r = n MOD k

Το k είναι διαιρέτης του n αν και μόνο αν το υπόλοιπο r είναι 0. Αυτό ελέγχεται στη γραμμή 24 και αν αυτό συμβαίνει τότε τυπώνουμε ένα μήνυμα στο χρήστη ότι βρήκαμε ένα διαιρέτη (γραμμή 25) και σημειώνουμε το γεγονός θέτοντας τη μεταβλητη found = 1 στη γραμμή 26. Την επόμενη φορά που θα μπούμε στην ανακύκλωση FOR το found θα είναι 1 και άρα η ανακύκλωση θα τελειώσει και ο έλεγχος θα βρεθεί στη γραμμή 31.

Έχοντας φτάσει στη γραμμή 31 ο τρόπος που έχουμε για να δούμε αν φτάσαμε έχοντας βρει ένα διαιρέτη ή έχοντας τρέξει όλη την ανακύκλωση χωρίς να βρούμε διαιρέτη είναι να ελέγξουμε τη μεταβλητή found Αν αυτή δεν είναι 0 (έχουμε ήδη βρεί διαιρέτη και τον έχουμε τυπώσει στο χρήστη) τότε δεν τυπώνουμε κάποιο μήνυμα αλλά αν είναι 0, που σημαίνει ότι δεν έχουμε βρει διαιρέτη στην ανακύκλωση, τότε τυπώνουμε ένα μήνυμα ότι το n είναι πρώτος αριθμός (prime).

Άσκηση 33.
Τροποποιείστε το πρόγραμμα isprime.bas ώστε να βρίσκει όλους τους διαιρέτες ενός αριθμού και όχι απλά να λέει αν υπάρχουν διαιρέτες ή όχι.
$\surd$

Άσκηση 34.
Όπως είπαμε παραπάνω στο FOR της γραμμής 20 ο υπολογιστής, για να βρεί το άνω όριο της ανακύκλωσης, υπολογίζει με το SQR(n) την τετραγωνική ρίζα του n και παίρνει το ακέραιο μέρος της, το μέγιστο δηλ. ακέραιο που είναι $\le \sqrt{n}$.

Όμως οι υπολογισμοί πραγματικών δε γίνονται ακριβώς στον υπολογιστή. Χονδρικά, όταν υπολογίζουμε μια πραγματική ποσότητα όπως η τετραγωνική ρίζα μόνο μερικά από τα ψηφία του αποτελέσματος είναι σωστά. Αυτό είναι αναπόφευκτο: αριθμοί όπως ο $\sqrt{2}$ έχουν άπειρα μη μηδενικά ψηφία και ο υπολογιστής έχει πεπερασμένη, άρα δε μπορεί να τα αποθηκεύσει όλα. Στην πράξη για ένα υπολογισμό όπως ο SQR(n) μπορούμε να υπολογίζουμε σε 5-6 σωστά δεκαδικά ψηφία, το πολύ.

Ας πάρουμε τώρα την περίπτωση που ο αριθμός $n$ είναι τετράγωνο κάποιου μεγάλου πρώτου αριθμού $p$. Ο υπολογισμός SQR(n) πρέπει να μας δώσει το $p$ και το πρόγραμμα θα βρεί το μοναδικό μη τετριμμένο διαιρέτη του $n$ στην τελευταία εκτέλεση της ανακύκλωσης.

Αυτό στη θεωρία γιατί στην πράξη, λόγω ακριβώς της έλλειψης ακρίβειας που μπορεί να υπάρχει σ' ένα τέτοιο υπολογισμό, μπορεί το αποτέλεσμα της SQR(n) να υπολλείπεται του ακεραίου $p$ σε ένα δεκαδικό ψηφίο. Για παράδειγμα αν $p=997$ (ο μεγαλύτερος πρώτος πριν το 1000) και $n = p^2 = 994009$ τότε ενδέχεται ο υπολογισμός SQR(n) να δώσει ως αποτέλεσμα ένα αριθμό όπως 996.9997, για παράδειγμα.

Εξηγείστε γιατί σε μια τέτοια περίπτωση το αποτέλεσμα του προγράμματος isprime.bas είναι λανθασμένο. Προτείνετε τροποποιήσεις στο πρόγραμμα, όσο γίνεται πιο απλές, που αποφεύγουν αυτό το πρόβλημα.
$\surd$

3.3 Εύρεση όλων των πρώτων αριθμών μέχρι κάποιο όριο

Το επόμενο πρόγραμμα βρίσκει όλους τους πρώτους αριθμούς από το 2 (το 1 δε θεωρείται πρώτος) έως και ένα αριθμό n που δίνει ο χρήστης.

   1 ' This program finds all primes up to n
   2 CLS
   3 DIM n, i, j, rt AS INTEGER
   4 
   5 ' Ask user
   6 PRINT "Until which number: ";
   7 INPUT n
   8 
   9 ' cross(i) = 1 if and only if i has been crossed out
  10 DIM cross(n) AS INTEGER
  11 
  12 ' Initially, nothing is crossed out
  13 FOR i = 1 TO n
  14  cross(i) = 0
  15 NEXT
  16 
  17 ' Sieve of Eratosthenes
  18 rt = SQR(n)
  19 FOR i = 2 TO rt
  20  ' If not crossed out
  21  IF cross(i) = 0 THEN
  22   ' cross out all multiples
  23   PRINT "Now crossing out multiples of "; i
  24   FOR k = 2 TO (n / i)
  25    cross(k * i) = 1
  26   NEXT
  27  END IF
  28 NEXT
  29 
  30 PRINT "The primes are: ",
  31 ' i is prime if not crossed out
  32 FOR i = 2 TO n
  33  IF cross(i) = 0 THEN
  34   PRINT i,
  35  END IF
  36 NEXT

Το αρχείο l3/sieve.bas

Η μέθοδος που ακολουθούμε είναι το λεγόμενο «κόσκινο του Ερατοσθένη»:

ξεκινάμε με μια λίστα με όλους τους ακεραίους από το 2 έως το n. Έπειτα παίρνουμε κάθε ακέραιο από τους $2, 3, \ldots, {\left\lfloor{\sqrt{n}}\right\rfloor}$ και διαγράφουμε όλα τα πολλαπλάσιά τους από τη λίστα. Οι αριθμοί που έχουν μείνει στο τέλος είναι ακριβώς οι πρώτοι αριθμοί από το 2 έως το n.

Ο λόγος γι' αυτό είναι ότι κάθε σύνθετος αριθμός μικρότερος ή ίσος από n έχει αναγκαστικά κάποιο μη τετριμμένο διαιρέτη που είναι μικρότερος ή ίσος του $\sqrt{n}$ (δείτε το Θεώρημα 3.1). Άρα, διαγράφοντας όλα τα πολλαπλάσια των αριθμών $2, 3, \ldots, {\left\lfloor{\sqrt{n}}\right\rfloor}$ έχουμε διαγράψει όλους τους σύνθετους αριθμούς και μόνο αυτούς. Αυτοί που απομένουν είναι οι πρώτοι.

Μάλιστα, για να επισπεύσουμε λίγο τη διαδικασία, δε διαγράφουμε τα πολλαπλάσια ενός αριθμού από τους $2, 3, \ldots, {\left\lfloor{\sqrt{n}}\right\rfloor}$ αν αυτός ο αριθμός έχει ήδη διαγραφεί. Αυτό το κάνουμε γιατί, αφού έχει αυτός ήδη διαγραφεί, ξέρουμε ότι είναι σύνθετος και άρα όλα τα πολλαπλάσιά του έχουν ήδη διαγραφεί προηγούμένως ως πολλαπλάσια κάποιου διαιρέτη του και δε χρειάζεται να τα διαγράψουμε ξανά.

Αφού ο χρήστης μας δώσει το n (γραμμές 6-7) δηλώνουμε ένα ακέραιο πίνακα cross(n) και του δίνουμε αρχικές τιμές ίσες με το 0 σε όλα τα στοιχεία του (γραμμές 13-15). Τον πίνακα αυτό τον χρησιμοποιούμε για να μαρκάρουμε τους ακεραίος από 2 έως n που έχουμε διαγράψει από τη λίστα (το στοιχείο cross(1) δεν το χρησιμοποιούμε ποτέ). Η τιμή cross(i) = 0 σημαίνει ότι ο ακέραιος i δεν έχει διαγραφεί ακόμη (γι' αυτό και οι μηδενικές αρχικές τιμές) ενώ θέτουμε cross(i) = 1 για να μαρκάρουμε τον ακέραιο i ως διαγραμμένο από τη λίστα. Στο τέλος του προγράμματος (γραμμές 30-36) απλά διανύουμε τους ακεραίους 2 έως n με μια ανακύκλωση FOR και τυπώνουμε όσα i έχουν cross(i) = 0, δεν έχουν δηλ. διαγραφεί από τον αλγόριθμο.

Στη γραμμή 18 υπολογίζουμε την τετραγωνική ρίζα του n, που εν γένει δεν είναι ακέραια ποσότητα, και την αναθέτουμε στην ακέραια μεταβλητή rt. Το αποτέλεσμα είναι ότι στη μεταβλητή rt ανατίθεται το ακέραιο μέρος (στρογγύλεμα σε ακέραιο προς τα κάτω) της τετραγωνικής ρίζας του n.

Το κόσκινο του Ερατοσθένη τρέχει στη διπλή (βάθους δύο) ανακύκλωση στις γραμμές 19-28. Στη εξωτερική ανακύκλωση FOR ο δείκτης i διανύει τις τιμές 2 έως rt, διανύει δηλ. όλες τις ακέραιες τιμές από το 2 έως το $\sqrt{n}$ (αν το $\sqrt{n}$ είναι ακέραιος τότε αυτή θα είναι η τελευταία τιμή που θα πάρει το i στην ανακύκλωση, αλλιώς η τελευταία τιμή του i θα είναι το ακέραιο μέρος του $\sqrt{n}$).

Για κάθε μια από αυτές τις τιμές του i ελέγχουμε κατ' αρχήν στη γραμμή 21 αν έχει διαγραφεί. Αν όχι (cross(i) = 0) τότε διαγράφουμε από τον πίνακα όλα τα πολλαπλάσιά του (εκτός τον εαυτό του). Αυτό γίνεται με την εσωτερική ανακύκλωση FOR, στις γραμμές 24-26 (έχει προηγηθεί ένα πληροφοριακό μήνυμα στο χρήστη στη γραμμή 23). Το εσωτερικό FOR λοιπόν διαγράφει όλα τα πολλαπλάσια $ki$ για $2 \le k \le \frac{n}{i}$ θέτοντας την τιμή cross(k*i) = 1.

Άσκηση 35.
Το πολύ πόσες φορές (ως συνάρτηση του $n$) εκτελείται η γραμμή 25 του προγράμματος sieve.bas;
$\surd$

Άσκηση 36.
Γράψτε ένα πρόγραμμα που να τυπώνει, μια φορά το καθένα και σε αύξουσα σειρά, όλα τα πολλαπλάσια του 3 ή του 5 που είναι $\le n$ (τον αριθμό $n$ τον δίνει ο χρήστης).
$\surd$

Άσκηση 37.
Γράψτε ένα πρόγραμμα που να τυπώνει όλους τους ακεραίους $k$, τ.ώ. $1 \le k \le n$ και ο $k$ γράφεται σαν άθροισμα δύο τετραγώνων, υπάρχουν δηλ. ακέραιοι $r, s$ τ.ώ. $k=r^2+s^2$.

Υπόδειξη: Χρησιμοποιείστε ένα πίνακα αντίστοιχο του cross στο πρόγραμμα sieve.bas ο οποίος να είναι αρχικά μηδενισμένος και πάνω στον οποίο θα μαρκάρετε όλα τα αθροίσματα δύο τετραγώνων πριν τα τυπώσετε. Για να τα μαρκάρετε θα χρειαστείτε μια διπλή ανακύκλωση FOR.
$\surd$

Άσκηση 38.
Η ακολουθία Fibonacci $F_n$ ορίζεται ως εξής: $F_1 = F_2 = 1$ και για $n \ge 3$ ορίζουμε $F_n = F_{n-1}+F_{n-2}$. Φτιάξτε ένα πρόγραμμα που να τυπώνει τον αριθμό $F_n$ (τον αριθμό $n$ τον δίνει ο χρήστης).
$\surd$