EECE Problem Set 1 Solution

ΥΠΟΛΟΓΙΣΤΩΝ ΤΟΜΕΑΣ ΤΕΧΝΟΛΟΓΙΑΣ ΠΛΗΡΟΦΟΡΙΚΗΣ ΚΑΙ ΥΠΟΛΟΓΙΣΤΩΝ

Άσκηση 1
Δυνάμεις του δύο (0.25+0.25 = 0.5 βαθμοί)
Όπως γνωρίζουμε, οι δυνάμεις του δύο είναι οι θετικοί ακέραιοι αριθμοί 1, 2, 4, 8, 16, ...
Μπορούμε να γράψουμε κάθε θετικό ακέραιο ώς άθροισμα δυνάμεων του δύο. Για παράδειγμα, ο αριθμός 42 μπορεί να γραφεί ως 2+8+32. Αλλά προσέξτε ότι υπάρχουν και άλλοι τρόποι να γράψουμε τον 42 ως άθροισμα δυνάμεων του δύο, π.χ. ως 2+2+2+4+16+16, ως 2+8+8+8+8+8, ή ακόμα και προσθέτοντας 42 φορές τον ακέραιο 1.
Αυτό που θέλουμε να κάνουμε είναι να βρούμε αν ένας ακέραιος Ν (1 ≤ Ν ≤ 1.000.000.000) μπορεί να γραφεί ως το άθροισμα ακριβώς Κ (1 ≤ Κ ≤ 200.000) δυνάμεων του δύο ή όχι και, σε περίπτωση που μπορεί να γραφεί, να βρούμε το λεξικογραφικά μικρότερο τρόπο που αυτό μπορεί να γίνει. Για παράδειγμα, ο λεξικογραφικά μικρότερος τρόπος που ο ακέραιος 9 μπορεί να γραφεί ως άθροισμα 5 δυνάμεων του δύο είναι ο 1+1+1+2+4 και ο λεξικογραφικά μικρότερος τρόπος που ο 42 μπορεί να γραφεί με 6 δυνάμεις του δύο είναι ο 1+1+2+2+4+32. Για να αποφύγουμε το πολύ output σε περιπτώσεις με πολλές επαναλήψεις, οι δύο παραπάνω τρόποι μπορούν να συμπτυχθούν ως [3,1,1] (δηλαδή τρεις φορές το 1, μία το 2, μία το 4) και [2,2,1,0,0,1], αντίστοιχα. Αλλά, φυσικά, δεν υπάρχει κάποιος τρόπος να γράψουμε τον ακέραιο 9 με 10 δυνάμεις του δύο, ούτε κάποιος τρόπος να γράφουμε τον 42 με 2 δυνάμεις του δύο, οπότε σε αυτές τις περιπτώσεις το πρόγραμμά σας θα πρέπει να τυπώνει μία κενή λίστα [].
Η άσκηση σάς ζητάει να γράψετε δύο προγράμματα (ένα σε C/C++ και ένα σε ML) τα οποία να διαβάζουν Τ ζεύγη ακειραίων Ν και Κ και, για κάθε ζεύγος με τη σειρά, να τυπώνουν τον λεξικογραφικά μικρότερο τρόπο που ο Ν μπορεί να γραφεί ως άθροισμα ακριβώς Κ δυνάμεων του δύο στη μορφή που περιγράφηκε παραπάνω, ή [] αν δεν μπορεί.
Τα στοιχεία εισόδου θα διαβάζονται από ένα αρχείο όπως φαίνεται στο παράδειγμα που ακολουθεί. Η πρώτη γραμμή του αρχείου περιέχει έναν ακέραιο αριθμό T (1 ≤ Τ ≤ 10): το πλήθος των ζευγών που ακολουθούν. Στη συνέχεια ακολουθούν Τ γραμμές, κάθε μία από τις οποίες περιέχει δύο ακέραιους αριθμούς Ν και Κ, χωρισμένους μεταξύ τους με ένα κενό διάστημα. Παρακάτω δίνεται κάποιο παράδειγμα σε C/C++ και σε ML.

Σε C/C++, MLton, ή σε OCaml Σε SML/NJ
$ ./powers2 f.txt - powers2 "f.txt";
[1,2,1] [1,2,1]
[3,1,1] [3,1,1]
[] []
[2,2,1,0,0,1] [2,2,1,0,0,1]
val it = () : unit
όπου το αρχείο με τα δεδομένα εισόδου είναι το εξής (η εντολή cat είναι εντολή του Unix):
$ cat f.txt
4
9 4
9 5
42 2
42 6
<-- τέσσερα ζεύγη ακεραίων ακολουθούν



Κορωνογράφοι (0.25+0.25 = 0.5 βαθμοί)
Ο φίλος σας ο Σωτήρης είναι λοιμωξιολόγος και έχει αναλάβει μια πολύ σημαντική δουλειά: να μελετήσει τη δομή του κορωνοϊού. Ο ιός αυτός όμως, εκτός από επικίνδυνος για την υγεία μας, είναι και αρκετά πολύπλοκος στη δομή του, κι έτσι ο φίλος σας χρειάζεται τη βοήθειά σας. Ο Σωτήρης μάς τον έδειξε στο ηλεκτρονικό μικροσκόπιο και έμοιαζε όπως στο σχήμα δεξιά πάνω.
Σύμφωνα με το φίλο σας, το γενετικό υλικό του κορωνοϊού αποτελείται από Ν κορωνονουκλεοτίδια (κάπως έτσι τα είπε ο Σωτήρης, ας τα ονομάσουμε «κόμβους») τα οποία συνδέονται μεταξύ τους με Μ κορωνοσυνάψεις (ας τις ονομάσουμε «ακμές»). Σε μια αφαιρετική μορφή, η δομή του κορωνοϊού μοιάζει όπως στο σχήμα δεξιά κάτω.
Αν λοιπόν το φανταστούμε σαν ένα μη κατευθυνόμενο γράφο, το γενετικό υλικό του κορωνοϊού έχει την εξής μορφή: Αποτελείται από ένα σύνολο από δένδρα, οι ρίζες των οποίων είναι συνδεδεμένες σε έναν κύκλο. Στο διπλανό σχήμα, τα δένδρα αυτά έχουν τις ρίζες τους στους κόμβους 1, 4 και 5. Προσέξτε ότι τα δένδρα αυτά δεν είναι απαραίτητα δυαδικά και ότι ένα δένδρο μπορεί να αποτελείται και μόνο από τη ρίζα του.
Ο Σωτήρης θέλει, δεδομένου ενός γράφου να μπορεί να βρίσκει αν όντως έχει αυτή τη μορφή. Αν ναι, θέλει επίσης να γνωρίζει από πόσα δένδρα αποτελείται και το πλήθος των κόμβων κάθε δένδρου.
Η άσκηση σας ζητάει να γράψετε δύο προγράμματα (ένα σε C/C++ και ένα σε ML) τα οποία να διαβάζουν αρκετούς γράφους και για κάθε έναν με τη σειρά να απαντούν στα παραπάνω.
Τα στοιχεία εισόδου θα διαβάζονται από ένα αρχείο όπως φαίνεται στο παράδειγμα που ακολουθεί. Η πρώτη γραμμή του αρχείου περιέχει έναν ακέραιο αριθμό T (1 ≤ Τ ≤ 10): το πλήθος των γράφων που ακολουθούν. Στη συνέχεια ακολουθούν Τ περιγραφές γράφων, που κάθε μία έχει την εξής μορφή. Η πρώτη γραμμή της περιέχει δύο ακέραιους αριθμούς χωρισμένους μεταξύ τους με ένα κενό διάστημα: το πλήθος των κόμβων Ν (1 ≤ Ν ≤ 1.000.000) και το πλήθος των ακμών Μ (1 ≤ Μ ≤ 1.000.000). Κάθε μία από τις επόμενες Μ γραμμές περιγράφει μία ακμή του γράφου και περιέχει δύο ακέραιους αριθμούς, χωρισμένους μεταξύ τους με ένα κενό διάστημα. Οι αριθμοί αυτοί είναι οι αριθμοί των κόμβων που βρίσκονται στα άκρα της εν λόγω ακμής. Θεωρήστε ότι οι κόμβοι είναι αριθμημένοι από 1 έως και Ν, ότι τα άκρα της ακμής είναι πάντα διαφορετικοί μεταξύ τους κόμβοι, και ότι δε θα δίνεται δύο φορές η ίδια ακμή.
Το πρόγραμμά σας πρέπει να ελέγχει κάθε γράφο με τη σειρά που δίνονται. Σε περίπτωση που ο γράφος έχει τη μορφή του κορωνοϊού, το πρόγραμμά σας πρέπει να εκτυπώνει δύο γραμμές. Η πρώτη θα περιέχει τη λέξη «CORONA», ένα κενό διάστημα και έναν ακέραιο αριθμό: το πλήθος C των δένδρων που εμφανίζονται στον κύκλο στο κέντρο του γράφου. (Φυσικά θα είναι C ≥ 3 για να υπάρχει κύκλος). Η δεύτερη γραμμή θα περιέχει ακριβώς C ακέραιους αριθμούς χωρισμένους ανά δύο με ένα κενό διάστημα: τα πλήθη των κόμβων σε κάθε ένα από τα C δένδρα. Οι αριθμοί αυτοί θα πρέπει να εμφανίζονται σε αύξουσα σειρά. Αντίθετα, αν ο γράφος δεν έχει τη μορφή κορωνοΐού, το πρόγραμμά σας θα πρέπει να εκτυπώνει μία γραμμή που να περιέχει το μήνυμα «NO CORONA» (και φυσικά δεν εννοούμε την μπύρα).

Παρακάτω δίνεται κάποιο παράδειγμα σε C/C++ και σε ML.

Σε C/C++, MLton, ή σε OCaml Σε SML/NJ
$ ./coronograph graphs.txt - coronograph "graphs.txt";
CORONA 3 CORONA 3
2 3 4 2 3 4
NO CORONA NO CORONA
val it = () : unit
όπου το αρχείο με τα δεδομένα εισόδου είναι το εξής:
$ cat graphs.txt
2 <-- δύο γράφοι
9 9 <-- αρχίζει ο πρώτος, με Ν=9 και Μ=9
6 3 <-- οι 9 ακμές του, με τη σειρά...
7 1
8 9
6 4
5 1
1 9

2 5
1 4
5 4
9 9
4 6 <-- αρχίζει ο δεύτερος, πάλι με Ν=9 και Μ=9
8 1 <-- οι 9 ακμές του, με τη σειρά...
3 4
2 8
6 7
9 3
4 7
1 5
4 9
Ο πρώτος γράφος του αρχείου εισόδου αντιστοιχεί στο παραπάνω σχήμα. Ο δεύτερος γράφος δεν έχει τη ζητούμενη μορφή — ζωγραφίστε τον!

Περαιτέρω οδηγίες για τις ασκήσεις

• Μπορείτε να δουλέψετε σε ομάδες το πολύ δύο ατόμων, τόσο σε αυτή όσο και στις επόμενες σειρές ασκήσεων. Όμως, έχετε υπ’ όψη σας ότι, αν δεν περάσετε το μάθημα φέτος, οι βαθμοί των προγραμματιστικών ασκήσεων κρατούνται μόνο για όσους δεν τις έκαναν σε ομάδα αλλά τις έκαναν μόνοι τους.

• Δεν επιτρέπεται να μοιράζεστε τα προγράμματά σας με συμφοιτητές εκτός της ομάδας σας ή να τα βάλετε σε μέρος που άλλοι μπορούν να τα βρουν (π.χ. σε κάποια σελίδα στο διαδίκτυο, σε ιστοσελίδες συζητήσεων, …). Σε περίπτωση που παρατηρηθούν «περίεργες» ομοιότητες σε προγράμματα, ο βαθμός των εμπλεκόμενων φοιτητών σε όλες τις σειρές ασκήσεων γίνεται αυτόματα μηδέν ανεξάρτητα από το ποια ομάδα... «εμπνεύστηκε» από την άλλη.

• Μπορείτε να χρησιμοποιήσετε «βοηθητικό» κώδικα (π.χ. κώδικα ταξινόμησης, κάποιο κώδικα που διαχειρίζεται κάποια δομή δεδομένων) που βρήκατε στο διαδίκτυο στα προγράμματά σας, με την προϋπόθεση ότι το πρόγραμμά σας περιέχει σε σχόλια την παραδοχή για την προέλευση αυτού του κώδικα και ένα σύνδεσμο σε αυτόν.

• Τα προγράμματα σε C/C++ πρέπει να είναι σε ένα αρχείο και να μπορούν να μεταγλωττιστούν χωρίς warnings με gcc/g++ (version ≥ 8.3.2) με εντολές της μορφής, π.χ.

gcc –std=c99 -Wall –Werror -O3 –o powers2 powers2.c g++ –std=c++11 -Wall –Werror -O3 –o powers2 powers2.cpp
• Τα προγράμματα σε ML πρέπει επίσης να είναι σε ένα αρχείο και να δουλεύουν σε SML/NJ ≥ v110.79 ή σε MLton ≥ 20130715 ή σε Objective Caml version ≥ 4.05.0. Το σύστημα ηλεκτρονικής υποβολής σας επιτρέπει να επιλέξετε μεταξύ αυτών των διαλέκτων της ML.

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