Γράψτε ένα πρόγραμμα (αν θέλετε σε ψευδοκώδικα ή και σε μια πραγματική γλώσσα προγραμματισμού) το οποίο να υπολογίζει το πηλίκο της διαίρεσης του 
Το πρόγραμμά σας επιτρέπεται να έχει (α) μόνο μια δομή ανακύκλωσης: ένα και μόνο for loop, μια ανακύκλωση δηλ. της μορφής
for i=1 to a do { εντολές ... },
και (β) να μη χρησιμοποιεί πολλαπλασιασμό (μόνο πρόσθεση).
Όλες οι άλλες μορφές προγραμματισμού που δε γυρίζουν τη ροή του προγράμματος προς τα πίσω επιτρέπονται, όπως π.χ. εντολές της μορφής
x <- x + yif( συνθήκη ) then { εντολές }x <- x+2
Προβλήματα Μαθηματικών 
Μπορούμε να κάνουμε το εξής (σε C):
p=0;
for(i=1;i<x;i+=2) p++;
και το ζητούμενο είναι το p.
Ουσιαστικά δηλαδή μετράμε τους περιττούς που υπάρχουν μέχρι το x (χωρίς το x).
Μου αρέσει!Μου αρέσει!
Σχόλιο από stedes — 12 Δεκεμβρίου, 2008 @ 7:07 μμ
stedes:
Το loop:
for i=1 to a do { εντολές ... }εκτελείται ακριβώςaφορές. Είναι το πιο κλασικό for loop και δεν είναι τόσο flexible όσο της C. Προσπαθείστε λοιπόν να το κάνετε με τέτοιο for loop.Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 12 Δεκεμβρίου, 2008 @ 7:25 μμ
Το υποπτευόμουν ότι δε θα είναι αποδεκτό αλλά είπα να κάνω μια δοκιμή. :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 μμ
Ωραία. Τώρα ας σφίξω λίγο το σχοινί: κάντε το χωρίς
if.Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 12 Δεκεμβρίου, 2008 @ 8:14 μμ
Μια λύση χωρίς τη χρήση 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 πμ
Σωστά.
Ιδού και μια λύση που δε χρησιμοποιεί πίνακες:
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 μμ
Ωραία λύση με τη διαφορά ότι πρέπει να οριστεί και το b ίσο με 0 στην αρχή.
Μπορεί να γίνει και λίγο πιο δύσκολο: να βρεθεί αλγόριθμος που ικανοποιεί όλες τις παραπάνω συνθήκες και χρησιμοποιεί μόνο 4 μεταβλητές (το x και 3 ακόμη).
Μου αρέσει!Μου αρέσει!
Σχόλιο από stedes — 14 Δεκεμβρίου, 2008 @ 2:26 πμ
Έχεις δίκιο, πρέπει να πάρει αρχική τιμή και το b.
Ποια είναι η λύση σου με 3 μεταβλητές εκτός του x;
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 14 Δεκεμβρίου, 2008 @ 2:44 πμ
Ένας αλγόριθμος με τη χρήση 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 πμ
Ωραίο κόλπο για την εναλλαγή δύο μεταβλητών χωρίς βοηθητική, δεν το ήξερα.
Και ωραίο στοιχειώδες παράδειγμα του ότι ο χρόνος (πράξεις του αλγορίθμου) μπορεί να αυξηθεί σε βάρος του χώρου (πλήθος μεταβλητών) και ανάποδα (space-time trade off).
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 14 Δεκεμβρίου, 2008 @ 9:48 πμ
Η τεχνική αυτή της εναλλαγής αριθμητικών μεταβλητών χωρίς βοηθητική είναι σωστή υπολογιστικά – μαθηματικά, αλλά επικίνδυνη προγραμματιστικά.
Καθένα από τα α και β μπορεί να «χωράνε» ως μέγεθος και ακρίβεια (αν ήταν floating point) στη μνήμη, όμως τα α+β ή/και α-β, παρότι απαιτούνται μόνο προσωρινά, μπορεί να υπολογιστούν λάθος, λόγω υπερχείλισης ή «side effect» των πράξεων στην ακρίβεια. Το αποτέλεσμα θα είναι η λανθασμένη εναλλαγή.
Μου αρέσει!Μου αρέσει!
Σχόλιο από Stazybο Hοrn — 17 Δεκεμβρίου, 2008 @ 9:46 μμ
Είναι σωστό ότι πρέπει κανείς να είναι προσεκτικός με τις αριθμητικές πράξεις.
Όμως στο συγκεκριμένο πρόβλημα ο κίνδυνος είναι μάλλον μικρός αφού μιλάμε για ακεραίους, οπότε το να αναφερθούμε στο άθροισμα θα μας κοστίσει το πολύ ένα bit παραπάνω και οι πράξεις είναι ακριβείς.
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 18 Δεκεμβρίου, 2008 @ 12:15 πμ
Εν προκειμένω, έχετε δίκιο.
Γενικότερα, όμως, η εναλλαγή αυθαιρέτων αριθμητικών μεταβλητών α και β με αυτό τον τρόπο πρέπει να αποφεύγεται.
π.χ. αν είναι ακέραιοι του ενός byte [-128..127] κι έχουν τιμές κοντά στο ίδιο άκρο το άθροισμά η σειρά εκχωρήσεων παραπάνω δεν θα επιφέρει την αντιμετάθεσή τους.
Μου αρέσει!Μου αρέσει!
Σχόλιο από Stazybο Hοrn — 18 Δεκεμβρίου, 2008 @ 12:22 πμ
Μόλις ανακάλυψα το 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 πμ
Ωραία. Σωστή κι αυτή η λύση.
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 20 Δεκεμβρίου, 2008 @ 7:57 πμ
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 πμ
Το νόημα αυτού του προβλήματος είναι να μη χρησιμοποιηθούν πράξεις πέρα από την πρόσθεση. Αλλιώς γράφοντας απλά
y=x/2;στη C (int x, y;) κάνει το ζητούμενο.Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 28 Ιανουαρίου, 2009 @ 8:43 πμ