Αλγόριθμοι, δεδομένα και διαδικασίες

Διομήδης Σπινέλλης
 Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Ορισμός

Αλγόριθμος (algorithm) είναι μια διαδικασία που επεξεργαζόμενη ορισμένα στοιχεία με πεπερασμένο αριθμό βημάτων παράγει ένα συγκεκριμένο επιθυμητό αποτέλεσμα. Κάθε βήμα της διαδικασίας αποτελείται από μονοσήμαντα εκτελέσιμες πράξεις.

Εύρεση ν!

Παραγοντικό του Ν στο Χ

Πριν: Ν: φυσικός αριθμός
Μετά: Χ = Ν! 
Είσοδος:
   Ν : Φυσικός αριθμός

Εξοδος:
   Χ : Φυσικός αριθμός

Κ : Φυσικός αριθμός

Χ <- 1
Κ <- Ν
Οσο Κ > 0
    Χ <- Χ * Κ
    Κ <- Κ - 1
Τέλος (όσο)

Ψευδοκώδικας

Ο ψευδοκώδικας (pseudocode) επιτρέπει την περιγραφή των αλγορίθμων.
Στοιχεία εισόδου, εξόδου και μεταβλητές
Είσοδος:
πλευρά_α, πλευρά_β, πλευρά_γ : Φυσικός αριθμός

Εξοδος:
εμβαδό : Φυσικός αριθμός

αριθμός_πλακών : Φυσικός αριθμός
συνολικό_βάρος : Πραγματικός αριθμός
είναι_ισοσκελές : Λογική τιμή
Προϋποθέσεις και μετά-συνθήκες
Πριν: Ν Φυσικός αριθμός
Μετά: Χ = Ν!
Εκχωρήσεις
ύψος <- συν(κλίση) * πλευρά
μέσο <- ύψος / 2
Βρόχοι 
Οσο υπόλοιπο_χρημάτων > 0
   δώσε_χαρτονόμισμα
Τέλος (όσο)

Επανάλαβε
  μείωσε_αέρα
Οσο στροφές_κινητήρα < 900

Για πάντα
  έλεγξε_παραμέτρους_λειτουργίας_εργοστασίου
Τέλος (για πάντα)
Αποφάσεις
Αν ζωές_παίκτη > 0 Τότε
  ξεκίνα_νέο_παιγνίδι
Αλλιώς
  εμφάνισε "Game Over"
Τέλος (Αν)

Αν στροφές > 8700 Τότε
  διάκοψε_την_τροφοδοσία
Τέλος (Αν)

Αν ομάδα ΠΑΟ Τότε
  χρώμα <- πράσινο
Αλλιώς Αν ομάδα Ολυμπιακός Τότε
  χρώμα <- κόκκινο
Αλλιώς Αν ομάδα ΑΕΚ Τότε
  χρώμα <- κίτρινο
Τέλος (Αν)

Γλώσσες προγραμματισμού

Γλώσσα μηχανής

89 D9 
B8 01 00 
83 F9 00 
74 05 
F7 E1 
49 
EB F6

Συμβολική γλώσσα

; Παραγοντικό του BX στο AX
        MOV  CX, BX             ; Μετρητής στο CX
        MOV  AX, 1              ; Αρχική τιμή 1
LOOP:   CMP  CX, 0              ; Τέλος;
        JZ   DONE               ; Ναι, έξοδος
        MUL  CX                 ; Όχι, πολλαπλασίασε ΑΧ με CX
        DEC  CX                 ; Επόμενη τιμή του CX
        JMP  LOOP               ; Πίσω στο βρόχο
DONE:

Fortran 77

C Return factorial of N
C
      FUNCTION IFACTORIAL(N)
      INTEGER N
      INTEGER IFACTORIAL
      INTEGER IRESULT, I

      IRESULT = 1
      DO I = 1, N
        IRESULT = IRESULT * I
      END DO
      IFACTORIAL = IRESULT

      END

Fortran 95

! Return factorial of n
function factorial(n) result (nfac)
        integer, intent(in) :: n
        integer :: factorial
        integer :: i

        nfac = 1
        do i = 1, n
                nfac = nfac * i
        end do
end function factorial

C

/* Παραγοντικό */
int
factorial(int n)
{
        int result;
        int count;

        count = n;
        result = 1;
        while (count > 0) {
                result = result * count;
                count = count - 1;
        }
        return (result);
}

/* Παραγοντικό (με λιγότερες εντολές) */
int
factorial(int n)
{
        int result = 1;

        for (; n; n--)
                result *= n;
        return (result);
}

Prolog

factorial(0, 1).

% To N_Factorial είναι ισοδύναμο με Ν!
factorial(N, N_Factorial) :-
        N > 0,
        M is N - 1,
        factorial(M, M_Factorial),
        N_Factorial is M_Factorial * N.

Lisp

;; Επιστρέφει το παραγοντικό του n
(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))

Basic

500 REM Return factorial of N in variable FACT
510 FACT = 1
520 FOR I = 1 TO N
530 FACT = FACT * I
540 NEXT I
550 RETURN

Visual Basic

' Παραγοντικό του Ν
FUNCTION Factorial(N AS INTEGER) AS INTEGER
        DIM Count AS INTEGER
        DIM Result AS INTEGER

        Count = N
        Result = 1
        WHILE Count > 0
                Result = Result * Count
                Count = Count - 1
        WEND

END FUNCTION

Pascal

(* Παραγοντικό του Ν *)
function factorial(N : Integer) : Integer;
var
  Count, Result : Integer;
begin
     Count := N;
     Result := 1;
     While Count > 0 Do
     begin
           Result := Result * Count;
           Count := Count - 1
     end;
     Factorial := Result
end (* Factorial *);

Java

// Υπολογισμός ν παραγοντικού
public int παραγοντικό(int ν) {
        int αποτέλεσμα;
        int μετρητής;

        μετρητής = ν;
        αποτέλεσμα = 1;
        while (μετρητής > 0) {
                αποτέλεσμα = αποτέλεσμα * μετρητής;
                μετρητής = μετρητής - 1;
        }
        return (αποτέλεσμα);
}

Πίνακες

Παράδειγμα

class Sum {
        static int sum(int a[]) {
                int i, sum = 0;

                for (i = 0; i < a.length; i++)
                        sum += a[i];
                return sum;
        }

        static int testdata[] = {1, 2, 3, 4, 5};

        public static void main(String args[]) {
                System.out.println(sum(testdata));
        }
}

Εγγραφές

Παράδειγμα

struct point {
        double x;       /* X coordinate */
        double y;       /* Y coordinate */
};

struct customer {
        char name[50];  /* Customer name */
        int balance;    /* Account balance */
};

struct customer customer_list[100];

main()
{
        struct point a, b;

        a.x = 5;
        a.y = 9;
        b.x = 12;
        b.y = 19;
}

Δομές με δείκτη

Παράδειγμα (C)

struct s_int_list {
	int val;
	struct s_int_list *next;
};

Διαδικασίες, συναρτήσεις και τάξεις

Παράδειγμα συνάρτησης και διαδικασίας σε Pascal

program fun;

(* Παραγοντικό του Ν *)
function factorial(N : Integer) : Integer;
var
  Count, Result : Integer;
begin
     Count := N;
     Result := 1;
     While Count > 0 Do
     begin
           Result := Result * Count;
           Count := Count - 1
     end;
     Factorial := Result
end (* Factorial *);

procedure clear_screen;
const number_of_lines = 24;
var i : integer;

begin
  for i := 0 to number_of_lines do
      writeln('');
end (*clear_screen*);

begin
  clear_screen;
  writeln(factorial(5));
end.

Παράδειγμα κλάσης σε Java

class Point extends Object {
   private int x;
   private int y;

   public void MoveTo(int x, int y) {
     this.x = x;
     this.y = y;
  }

  public int GetX() {
    return (x);
  }
}

Αναδρομικές τεχνικές

Παράδειγμα

class Recurse {
        static void russian_doll(int size) {
                int i;

                System.out.print("[");
                for (i = 0; i < size; i++)
                        System.out.print("-");
                System.out.println("]");
                if (size > 1)
                        russian_doll(size - 1);
        }

        static int factorial(int n) {
                if (n == 0)
                        return (1);
                else
                        return (n * factorial(n - 1));
        }

        public static void main(String args[]) {
                System.out.println(factorial(5));
                russian_doll(10);
        }
}

Αποτελέσματα

120
[----------]
[---------]
[--------]
[-------]
[------]
[-----]
[----]
[---]
[--]
[-]

Βιβλιογραφία

Ασκήσεις

Creative Commons License  Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:27 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».