Προβλήματα Μαθηματικών

Δεκέμβριος 12, 2008

Προγραμματισμός με τα χέρια δεμένα

Filed under: Λυμένα Προβλήματα — Mihalis Kolountzakis @ 2:24 μμ

hands

Γράψτε ένα πρόγραμμα (αν θέλετε σε ψευδοκώδικα ή και σε μια πραγματική γλώσσα προγραμματισμού) το οποίο να υπολογίζει το πηλίκο της διαίρεσης του x διά 2, με άλλα λόγια το ακέραιο μέρος του x/2, για x=1,2,3,\ldots.

Το πρόγραμμά σας επιτρέπεται να έχει (α) μόνο μια δομή ανακύκλωσης: ένα και μόνο for loop, μια ανακύκλωση δηλ. της μορφής

for i=1 to a do { εντολές ... },

και (β) να μη χρησιμοποιεί πολλαπλασιασμό (μόνο πρόσθεση).

Όλες οι άλλες μορφές προγραμματισμού που δε γυρίζουν τη ροή του προγράμματος προς τα πίσω επιτρέπονται, όπως  π.χ. εντολές της μορφής

  • x <- x + y
  • if( συνθήκη ) then { εντολές }
  • x <- x+2
Advertisements

17 Σχόλια »

  1. Μπορούμε να κάνουμε το εξής (σε C):

    p=0;
    for(i=1;i<x;i+=2) p++;

    και το ζητούμενο είναι το p.

    Ουσιαστικά δηλαδή μετράμε τους περιττούς που υπάρχουν μέχρι το x (χωρίς το x).

    Μου αρέσει!

    Σχόλιο από stedes — Δεκέμβριος 12, 2008 @ 7:07 μμ

  2. stedes:

    Το loop: for i=1 to a do { εντολές ... } εκτελείται ακριβώς a φορές. Είναι το πιο κλασικό for loop και δεν είναι τόσο flexible όσο της C. Προσπαθείστε λοιπόν να το κάνετε με τέτοιο for loop.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 12, 2008 @ 7:25 μμ

  3. Το υποπτευόμουν ότι δε θα είναι αποδεκτό αλλά είπα να κάνω μια δοκιμή. :p

    Ένας τρόπος με το κλασικό το for δηλαδή με βήμα 1 είναι ο παρακάτω:

    p=0;
    r=1;
    for(i=1;i<x;i++)
    { if(r==1)
    { p++;
    r=0;
    }
    else r=1;
    }

    Μου αρέσει!

    Σχόλιο από stedes — Δεκέμβριος 12, 2008 @ 8:04 μμ

  4. Ωραία. Τώρα ας σφίξω λίγο το σχοινί: κάντε το χωρίς if.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 12, 2008 @ 8:14 μμ

  5. Μια λύση χωρίς τη χρήση if:

    Ορίζουμε ένα πίνακα p με 2x+1 στοιχεία και εκτελούμε τον εξής αλγόριθμο

    p[0]=0;
    for(i=1;i<=x;i++)
    { p[i+i-1]=i;
    p[i+i]=i;
    }

    οπότε το ζητούμενο αποτέλεσμα είναι το στοιχείο p[x-1].

    Μου αρέσει!

    Σχόλιο από stedes — Δεκέμβριος 13, 2008 @ 3:31 πμ

  6. Σωστά.

    Ιδού και μια λύση που δε χρησιμοποιεί πίνακες:


    a = 0;
    for i=1 to x {
          a++; //Αυξάνουμε το a κατά 1
          t = a; a = b; b = t; // Εναλλάσσουμε τις τιμές των a, b
    }

    Αποτέλεσμα στη μεταβλητή a.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 13, 2008 @ 3:12 μμ

  7. Ωραία λύση με τη διαφορά ότι πρέπει να οριστεί και το b ίσο με 0 στην αρχή.
    Μπορεί να γίνει και λίγο πιο δύσκολο: να βρεθεί αλγόριθμος που ικανοποιεί όλες τις παραπάνω συνθήκες και χρησιμοποιεί μόνο 4 μεταβλητές (το x και 3 ακόμη).

    Μου αρέσει!

    Σχόλιο από stedes — Δεκέμβριος 14, 2008 @ 2:26 πμ

  8. Έχεις δίκιο, πρέπει να πάρει αρχική τιμή και το b.

    Ποια είναι η λύση σου με 3 μεταβλητές εκτός του x;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 14, 2008 @ 2:44 πμ

  9. Ένας αλγόριθμος με τη χρήση 3 μεταβλητών εκτός του x είναι ο εξής:

    a=0;
    b=0;
    for(i=1;i<=x;i++)
    {  a=a+b+1;
       b=a-b;
       a=a-b;
    }

    και το αποτέλεσμα είναι και πάλι στη μεταβλητή a.

    Μου αρέσει!

    Σχόλιο από stedes — Δεκέμβριος 14, 2008 @ 4:28 πμ

  10. Ωραίο κόλπο για την εναλλαγή δύο μεταβλητών χωρίς βοηθητική, δεν το ήξερα.

    Και ωραίο στοιχειώδες παράδειγμα του ότι ο χρόνος (πράξεις του αλγορίθμου) μπορεί να αυξηθεί σε βάρος του χώρου (πλήθος μεταβλητών) και ανάποδα (space-time trade off).

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 14, 2008 @ 9:48 πμ

  11. Η τεχνική αυτή της εναλλαγής αριθμητικών μεταβλητών χωρίς βοηθητική είναι σωστή υπολογιστικά – μαθηματικά, αλλά επικίνδυνη προγραμματιστικά.

    Καθένα από τα α και β μπορεί να «χωράνε» ως μέγεθος και ακρίβεια (αν ήταν floating point) στη μνήμη, όμως τα α+β ή/και α-β, παρότι απαιτούνται μόνο προσωρινά, μπορεί να υπολογιστούν λάθος, λόγω υπερχείλισης ή «side effect» των πράξεων στην ακρίβεια. Το αποτέλεσμα θα είναι η λανθασμένη εναλλαγή.

    Μου αρέσει!

    Σχόλιο από Stazybο Hοrn — Δεκέμβριος 17, 2008 @ 9:46 μμ

  12. Είναι σωστό ότι πρέπει κανείς να είναι προσεκτικός με τις αριθμητικές πράξεις.

    Όμως στο συγκεκριμένο πρόβλημα ο κίνδυνος είναι μάλλον μικρός αφού μιλάμε για ακεραίους, οπότε το να αναφερθούμε στο άθροισμα θα μας κοστίσει το πολύ ένα bit παραπάνω και οι πράξεις είναι ακριβείς.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 18, 2008 @ 12:15 πμ

  13. Εν προκειμένω, έχετε δίκιο.

    Γενικότερα, όμως, η εναλλαγή αυθαιρέτων αριθμητικών μεταβλητών α και β με αυτό τον τρόπο πρέπει να αποφεύγεται.

    π.χ. αν είναι ακέραιοι του ενός byte [-128..127] κι έχουν τιμές κοντά στο ίδιο άκρο το άθροισμά η σειρά εκχωρήσεων παραπάνω δεν θα επιφέρει την αντιμετάθεσή τους.

    Μου αρέσει!

    Σχόλιο από Stazybο Hοrn — Δεκέμβριος 18, 2008 @ 12:22 πμ

  14. Μόλις ανακάλυψα το blog σας και το βρίσκω πολύ ενδιαφέρον! Συγχαρητήρια!
    Σας δίνω και εγώ μία λύση με 3 μεταβλητές (εκτός του x), χωρίς τη χρήση if.

    even=0;
    half=0;
    for(i=1;i<=x;i++){
    half=half+even;
    even=1-even;
    }

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

    Μου αρέσει!

    Σχόλιο από peterpan8 — Δεκέμβριος 20, 2008 @ 5:28 πμ

  15. Ωραία. Σωστή κι αυτή η λύση.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Δεκέμβριος 20, 2008 @ 7:57 πμ

  16. Estw x akeraios. Tote (8ewrontas to x os binary) mia olis8isi kati mia 8esi deksia, dinei to zhtoumeno. P.x. 4 = 100 (binary) kai 4 / 2 = 10(binary)

    In C / C++ :

    #include

    int main(){

    float x;
    int y;

    printf(«Give a number :»);
    scanf(«%f», &x);

    % Shift right by 1
    y = (int)x >> 1;

    printf(«\n%d\n», y );

    }

    Μου αρέσει!

    Σχόλιο από zouzias — Ιανουαρίου 28, 2009 @ 5:44 πμ

  17. Το νόημα αυτού του προβλήματος είναι να μη χρησιμοποιηθούν πράξεις πέρα από την πρόσθεση. Αλλιώς γράφοντας απλά y=x/2; στη C (int x, y;) κάνει το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιανουαρίου 28, 2009 @ 8:43 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: