Προβλημα σε ασκηση C

[jimisvog]

Εχω ενα προβλημα σε μια ασκηση σε ενα προβλημα.. Καθως το προβλημα ειναι λογικο και δεν θελω να δημοσιευσω ολη την ασκηση γιατι δεν ψαχνω την λυση αυτη καθ'εαυτη αλλα τι εχω λαθος στον τροπο σκεψης μου οποιος εχει ενδιαφερον να βοηθησει ας στειλει ενα πμ.. Ευχαριστω..

[migf1]

Μπορείς να εξηγήσεις με λόγια το πρόβλημά σου, και να δούμε αν μπορούμε να βοηθήσουμε. Μπορείς προαιρετικά να τα συνοδεύσεις και με μικρά αποσπάσματα κώδικα αν θεωρείς πως διευκολύνουν στην εξήγηση.

 

Δημόσια συζήτηση για την λογική θα είναι πιστεύω ιδιαίτερα εποικοδομητική για όλους

 

[jimisvog]

Καλως.. Λοιπον.. πρεπει να φτιαξω μια συναρτηση η οποια θα εμφανιζει την τομη 3 πινακων των οποιων το μεγεθος και το περιεχομενο θα δινεται απο πριν απο τον χρηστη στο προγραμμα.. Η συναρτηση τωρα σκεφτηκα να κανει μια επαναληψη ολο το περιεχομενο του πινακα Α και να ελεγχει π.χ αν το 1ο στοιχειο ταιριαζει με καποιο απο τον πινακα Β και αν ναι τοτε θα μπαινει και θα ελεγχει και αν υπαρχει στον πινακα Γ, αν οχι θα πηγαινει στο επομενο στοιχειο του Α αντιστοιχα.. Εχω προβλημα ομως γιατι ετσι οπως το εφτιαξα εμφανιζει παντα ολο το περιεχομενο του Α..

Παραθετω παρακατω το κωδικα..

 

>
for (i=0;i<=(n1-1);i++){
j=0;
do{
cond1='f';
if(A[i]==B[j]){
cond1='t';
}
j++;
}while ((cond1=='f')||(j<=(n2-1)));
 cond2='f';
if(cond1=='t'){
 k=0;
 do{
 if(A[i]==C[k]){
 cond2='t';
 numb==C[k];
}
 k++;
 }while ((cond2=='f')||(k<=(n3-1)));
 }
 if (cond2=='t')
		 printf("%d\n",numb);

[migf1]

Αν υποθέσουμε πως υλοποιείς τον έλεγχο σε μια συνάρτηση, π.χ.

 

>
??? get_intersection( arr1, arr2, arr3, ??? );

 

τι θέλεις να σου επιστρέφει η συνάρτηση αυτή;

 

Σου αρκεί δηλαδή απλώς να επιστρέφει true (αν υπάρχει τομή και στους 3 πίνακες) ή false (αν δεν υπάρχει τομή σε 2 από τους 3);

 

Χρειάζεται δηλαδή ή όχι να επιστρέψει και στο ποια σημεία τέμνονται (αν τέμνονται).

 

Επίσης, για να μη ψάχνω μιας και δεν το θυμάμαι, πως ορίζεται επίσημα η τομή μονοδιάστατων πινάκων?

 

Πρέπει να υπάρχει μια κοινή συνεχόμενη περιοχή ίδιων στοιχείων; Αν ναι, τότε τι θεωρείται τομή αν έχουν περισσότερες από 1 ίδιες συνεχόμενες περιοχές στοιχείων (π.χ. αν έχουν ίδιες τις περιοχές στοιχείων, από 1 έως 3 και από 7 έως 12);

[jimisvog]

η συναρτηση παιρνει ως παραμετρο τους 3 πινακες γεμισμενους με ακαιρεους αριθμους και θελω να επιστρεφει τα κοινα στοιχεια.. π.χ

 

Α{3,4,5,6}

Β{5,6,7}

Γ{1,2,5,6}

 

πρεπει να εμφανιζει το {5,6}

[migf1]

Ωραία, οπότε θες να σου επιστρέφει μια δομή (π.χ. έναν 4ο array, ή μια λίστα ή οτιδήποτε άλλο, με τα κοινά στοιχεία και στους 3 πίνακες).

 

Μια χαρά, το κάνει πιο ενδιαφέρον

 

Βασικά την κάνω για σπίτι τώρα, αλλά να σου δώσω 2 ιδέες για την επίσπευση της αναζήτησης κοινών στοιχείων σε 2 πίνακες.

 

Όταν δεν είναι ταξινομημένοι οι πίνακες (ή δεν συμφέρει να τους ταξινομήσεις) τότε μπορείς να χρησιμοποιήσεις hash-table (αν δεν ξέρεις τι είναι αυτό, google: "what is hash table").

 

Αν είναι ήδη ταξινομημένοι (ή συμφέρει να τους ταξινομήσεις) τότε είναι πιο memory-friendly και μάλλον πιο απλό σαν κώδικας να τους συγκρίνεις in-place, ως εξής:

 

Ξεκινάς με 2 indexers που δείχνουν στην αρχή των 2 πινάκων (ας πούμε i = 0 και j = 0) και...

 

>
while ( !endof(arr1) && !endof(arr2) ) {
   if ( arr1[i] > arr2[j] )
       j++;
   else if ( arr1[i] < arr2[j] )
       i++;
   else
       // insert arr1[i] ( or arr2[j] ) into the structure holding common elems
}

[jimisvog]

Φιλε μου ειμαι πρωτοετης και μου φαινονται πιο πρωχορημενα αυτα που μου λες.. :/

 

Σε αυτο που εχω εγω πανω τι ειναι λαθος..?

Αφου ξεκιναει απο το Α[0] και ελεγχει αν ειναι ισο με το Β[0] και αν ειναι προχοραει στον αλλο πινακα και αν υπαρχει το εμφανιζει αλλιως ελεγχει με το Β[1], B[2] κ.λ.π.. Μου φαινεται απλο και στα λογια σωστο αλλα δεν βγαζει σωστο αποτελεσμα..

[ZAKKWYLDE]

Αυτό που πρέπει να κάνεις είναι το εξής

 

1. Ελέγχεις να δεις αν το στοιχείο υπάρχει στο Α και Β

2. Αν υπάρχει κοιτάς να δεις αν είναι και στο Γ

3. Αν υπάρχει και στο Γ τότε:

3α. Πας στον πίνακα Δ και κοιτάς αν έχει ήδη βρεθεί το στοιχείο, αν υπάρχει συνεχίζεις

3β. Αν δεν υπάρχει ήδη το στοιχείο στον πίνακα Δ τον παίρνεις πάλι απο την αρχή και όπου είναι κενός

γράφεις το στοιχείο.

 

Ο κώδικας έτσι όπως τον έχεις βλέπω τα εξής προβλήματα:

1. Στους ελέγχους cond1/cond2 στα while θέλει && και όχι ||

2. numb = C[k] και όχι numb == C[k];

 

Με αυτές τις διορθώσεις θα σου παίξει, αλλά δεν προβλέπεις τι γίνεται αν το στοιχείο βρίσκεται 2 φορες σε έναν πίνακα. Ο αλγόριθμός σου θα τον εκτυπώσει 2 φορές.

[jimisvog]

Αυτό που πρέπει να κάνεις είναι το εξής

 

1. Ελέγχεις να δεις αν το στοιχείο υπάρχει στο Α και Β

2. Αν υπάρχει κοιτάς να δεις αν είναι και στο Γ

3. Αν υπάρχει και στο Γ τότε:

3α. Πας στον πίνακα Δ και κοιτάς αν έχει ήδη βρεθεί το στοιχείο, αν υπάρχει συνεχίζεις

3β. Αν δεν υπάρχει ήδη το στοιχείο στον πίνακα Δ τον παίρνεις πάλι απο την αρχή και όπου είναι κενός

γράφεις το στοιχείο.

 

Ο κώδικας έτσι όπως τον έχεις βλέπω τα εξής προβλήματα:

1. Στους ελέγχους cond1/cond2 στα while θέλει && και όχι ||

2. numb = C[k] και όχι numb == C[k];

 

Με αυτές τις διορθώσεις θα σου παίξει, αλλά δεν προβλέπεις τι γίνεται αν το στοιχείο βρίσκεται 2 φορες σε έναν πίνακα. Ο αλγόριθμός σου θα τον εκτυπώσει 2 φορές.

Σωστα.. Με τις διορθωσεις που προτεινες δουλεψε.. Απλα εγω μπερδευομαι και μεταφραζω μεσα μου το while=Μεχρις_οτου απο την ΓΛΩΣΣΑ και εξου και οι λαθος συνθηκες.. Τωρα οσο αναφορα την εκτυπωση που λες.. Θα το προσπαθησω να βαζει την τομη σε εναν πινακα Δ ετσι ωστε να μην υπαρχουν επαναληψεις.. Ευχαριστω ΠΟΛΥ...

 

 

3. Αν υπάρχει και στο Γ τότε:

3α. Πας στον πίνακα Δ και κοιτάς αν έχει ήδη βρεθεί το στοιχείο, αν υπάρχει συνεχίζεις

3β. Αν δεν υπάρχει ήδη το στοιχείο στον πίνακα Δ τον παίρνεις πάλι απο την αρχή και όπου είναι κενός

γράφεις το στοιχείο.

 

Το προβλημα ομως που προκυπτει ειναι το μεγεθος του πινακα Δ.. Νωριτερα στο προγραμμα ο χρηστης καθοριζει το μεγεθος των τριων πινακων.. Δεν ξερεις ποσα ειναι τα κοινα στοιχεια ετσι ωστε να φτιαξεις αναλογο πινακα.. Μπορει να ειναι 3 μπορει ομως να ειναι και 200

[migf1]

Φιλε μου ειμαι πρωτοετης και μου φαινονται πιο πρωχορημενα αυτα που μου λες.. :/

...

 

To hash-table ίσως είναι όντως προχωρημένο αν είστε πριν τη μέση του εξαμήνου, ο 2ος τρόπος όμως δεν είναι.

 

...

Το προβλημα ομως που προκυπτει ειναι το μεγεθος του πινακα Δ.. Νωριτερα στο προγραμμα ο χρηστης καθοριζει το μεγεθος των τριων πινακων.. Δεν ξερεις ποσα ειναι τα κοινα στοιχεια ετσι ωστε να φτιαξεις αναλογο πινακα.. Μπορει να ειναι 3 μπορει ομως να ειναι και 200

 

Πρέπει να ξέρουμε τι έχετε καλύψει στην ύλη σας.

 

Αν έχετε κάνει δείκτες και απλές δομές που στηρίζονται σε αυτούς (π.χ. απλά συνδεδεμένες λίστες) τότε το Δ μπορείς να μην το κάνεις πίνακα, αλλά μια απλά συνδεδεμένη λίστα.

 

Κρίνοντας από την άσκηση, θεωρώ αυτονόητο πως έχετε ήδη κάνει δείκτες και δυναμικούς πίνακες (διότι αμφιβάλλω αν σας έχουν μιλήσει για VLA), οπότε αν θες το Δ να το κάνεις πίνακα, τότε μια speed-efficient πρόταση είναι να δεσμεύσεις για τον Δ lengthof( A ) + lenghtof( Β ) + length( Γ ) στοιχεία EDIT το σωστό εδώ είναι o Δ να έχει τόσα στοιχεία όσα ο μικρότερος από τους 3 πίνακες, όπως πολύ σωστά παρατήρησε ο imitheos στο ποστ #19.

 

Όταν τελειώσει το loop σου, θα τον κάνεις resize σε τόσα στοιχεία όσα δηλώνει ο μετρητής του loop που αντιστοιχεί στον πίνακα Δ (το resize το κάνεις με realloc() ).

 

Αν το κάνεις έτσι, τότε υπάρχει ένα tricky σημείο. Επειδή ο μετρητής του πίνακα Δ στο loop ξεκινάει από 0, στο τέλος του loop μπορεί να δείχνει 0 σε δυο περιπτώσεις:

 

α) όταν δεν έχει βρεθεί κανένα κοινό στοιχείο

β) όταν έχει βρεθεί μονάχα ένα κοινό σημείο

 

Για να διευκρινήσεις σε ποια από τις παραπάνω περιπτώσεις αντιστοιχεί πιθανή μηδενική τιμή του μετρητή μετά το loop, μπορείς να χρησιμοποιήσεις μια boolean μεταβλητή ειδικά για αυτό το σκοπό.

 

 

ΥΓ. Η εκφώνηση απαιτεί να περνιούνται και οι 3 πίνακες στη συνάρτηση ή έχετε ελευθερία να το υλοποιήσετε και αλλιώς; Π.χ. μια συνάρτηση που συγκρίνει 2 πίνακες, και μετά να την ξανακαλείς με ορίσματα τον 3ο πίνακα και το αποτέλεσμα της προηγούμενης κλήσης της.

 

Επίσης, σας διευκρινίζει η εκφώνηση αν οι πίνακες θα είναι ήδη ταξινομημένοι από πριν ή όχι;

Επεξ/σία 24 Νοεμβρίου 2012 από migf1

[jimisvog]

ΥΓ. Η εκφώνηση απαιτεί να περνιούνται και οι 3 πίνακες στη συνάρτηση ή έχετε ελευθερία να το υλοποιήσετε και αλλιώς; Π.χ. μια συνάρτηση που συγκρίνει 2 πίνακες, και μετά να την ξανακαλείς με ορίσματα τον 3ο πίνακα και το αποτέλεσμα της προηγούμενης κλήσης της.

 

Επίσης, σας διευκρινίζει η εκφώνηση αν οι πίνακες θα είναι ήδη ταξινομημένοι από πριν ή όχι;

Η εκφωνηση της ασκησης ειναι η εξης:

Γράψτε μια συνάρτηση που να δέχεται σαν παράμετρο 3 πίνακες με ακεραίους και να τυπώνει στην οθόνη την τομή μεταξύ των τριών πινάκων (δλδ, τα στοιχεία που είναι κοινά και στους 3 πίνακες). Για παράδειγμα, για τους πίνακες Α={1, 5, 12, 3}, Β={3, 5, 7, 1, 23} και Γ={5, 23, 3, 12}, η τομή είναι οι αριθμοί {3, 5}. Γράψτε και ένα πρόγραμμα που θα προτρέπει τον χρήστη να εισάγει τα στοιχεία των 3 πινάκων και εν συνεχεία να καλεί τη συνάρτηση και παρουσιάζει το αποτέλεσμα.

 

Το θεμα ειναι οτι ο τροπος που προτεινεις δεν εχει διδαχτει ακομα.. οι εντολες.. ετσι θα φανει οτι την ασκηση την πηρα απο αλλου και δεν το εχω κανει.. Θα ηθελα να εφαρμοσω τον δικο μου τροπο σκεψης οπως τα εχω αντιληφθει μεχρι τωρα.. Απλα ρωταω εδω για να διαπιστωσω τυχον λαθη...

[migf1]

 

Η εκφωνηση της ασκησης ειναι η εξης:

Γράψτε μια συνάρτηση που να δέχεται σαν παράμετρο 3 πίνακες με ακεραίους και να τυπώνει στην οθόνη την τομή μεταξύ των τριών πινάκων (δλδ, τα στοιχεία που είναι κοινά και στους 3 πίνακες). Για παράδειγμα, για τους πίνακες Α={1, 5, 12, 3}, Β={3, 5, 7, 1, 23} και Γ={5, 23, 3, 12}, η τομή είναι οι αριθμοί {3, 5}. Γράψτε και ένα πρόγραμμα που θα προτρέπει τον χρήστη να εισάγει τα στοιχεία των 3 πινάκων και εν συνεχεία να καλεί τη συνάρτηση και παρουσιάζει το αποτέλεσμα.

 

Το θεμα ειναι οτι ο τροπος που προτεινεις δεν εχει διδαχτει ακομα.. οι εντολες.. ετσι θα φανει οτι την ασκηση την πηρα απο αλλου και δεν το εχω κανει.. Θα ηθελα να εφαρμοσω τον δικο μου τροπο σκεψης οπως τα εχω αντιληφθει μεχρι τωρα.. Απλα ρωταω εδω για να διαπιστωσω τυχον λαθη...

 

Τότε είναι πολύ πιο απλό από ότι είπαμε αρχικά. Διότι αρχικά μου είχες πει πως η συνάρτηση πρέπει να επιστρέφει τα κοινά σημεία των πινάκων, ενώ η εκφώνηση δεν έχει τέτοια απαίτηση. Η εκφώνηση λέει πως η συνάρτηση απλώς τα τυπώνει και όχι ότι τα επιστρέφει

 

Οπότε, πλέον δεν χρειάζεται να ξέρεις εκ των προτέρων το πλήθος των κοινών στοιχείων και δε χρειάζεσαι καν πίνακα Δ. Τύπωνέ τα απευθείας μέσα από το loop.

 

EDIT

 

Άσχετο, η εκφώνηση απαιτεί επίσης εμμέσως πλην σαφώς (μέσω των παραδειγμάτων που δίνει) οι πίνακες να μην είναι εξαρχής ταξινομημένοι.

 

[jimisvog]

Τότε είναι πολύ πιο απλό από ότι είπαμε αρχικά. Διότι αρχικά μου είχες πει πως η συνάρτηση πρέπει να επιστρέφει τα κοινά σημεία των πινάκων, ενώ η εκφώνηση δεν έχει τέτοια απαίτηση. Η εκφώνηση λέει πως η συνάρτηση απλώς τα τυπώνει και όχι ότι τα επιστρέφει

Οπότε, πλέον δεν χρειάζεται να ξέρεις εκ των προτέρων το πλήθος των κοινών στοιχείων και δε χρειάζεσαι καν πίνακα Δ. Τύπωνέ τα απευθείας μέσα από το loop.

Αυτο κανω, και απο την αρχη ειπα πως πρεπει να εμφανιζει τα κοινα στοιχεια .. Το προβλημα μου ομως ειναι π.χ

Α {1,2,3,4,3]

Β {1,3,4,5,2}

Γ {3,4,7,89,12}

 

Τοτε θα εμφανιζει {3,4,3} δηλαδη 2 φορες το 3 γιατι 2 φορες το συνανταει στο πινακα Α

[migf1]

Αυτο κανω, και απο την αρχη ειπα πως πρεπει να εμφανιζει τα κοινα στοιχεια ..

 

Εγώ πάντως στο ποστ #5 βλέπω να απαντάς επιστρέφει όταν σε ρώτησα

 

 

 

Post #5

 

η συναρτηση παιρνει ως παραμετρο τους 3 πινακες γεμισμενους με ακαιρεους αριθμους και θελω να επιστρεφει τα κοινα στοιχεια

...

 

 

 

Το προβλημα μου ομως ειναι π.χ

Α {1,2,3,4,3]

Β {1,3,4,5,2}

Γ {3,4,7,89,12}

 

Τοτε θα εμφανιζει {3,4,3} δηλαδη 2 φορες το 3 γιατι 2 φορες το συνανταει στο πινακα Α

 

Για να το κάνεις αυτό χρειάζεσαι νέα δομή Δ (πίνακας, λίστα ή οτιδήποτε) όπως σου εξήγησα παραπάνω, αλλά είπες πως δεν τα έχετε διδαχτεί.

[imitheos]

Disclaimer: Με μπέρδεψε το παρόν νήμα οπότε μάλλον θα πω χαζομάρες. Γενικά δεν πολύ κατάλαβα τι έχετε διδαχθεί και τι όχι.

 

1) Από που καταλαβαίνουμε πως η εκφώνηση προϋποθέτει πως οι πίνακες θα είναι ταξινομημένοι ? Στο παράδειγμα μάλιστα κανένας δεν είναι ταξινομημένος (πχ 1, 5, 12, 3).

Edit: Ό,τι να ναι διαβάζω. Να μην είναι έγραψε ο migf1.

 

2) Η τελευταία προτροπή του migf1 είναι να χρησιμοποιηθεί μια δομή Δ (πίνακας, λίστα ή οτιδήποτε) αλλά δεν έχει διδαχθεί. Για λίστα, hash table, κτλ το καταλαβαίνω αλλά πίνακας γιατί δεν μπορεί να χρησιμοποιηθεί ? Δεν θα μπορούσε να χρησιμοποιηθεί ένα απλός πίνακας Δ πχ υπό μορφή ιστογράμματος ?

 

Αν ο κώδικας σου με τα loop και τα cond1, cond2 παίζει σωστά και το μόνο πρόβλημά σου είναι ότι εμφανίζει πάνω από μία φορά κοινά στοιχεία που υπάρχουν πολλές φορές στον πίνακα Α, μπορείς πριν αρχίσεις να ελέγχεις το στοιχείο να προσθέσεις ακόμη ένα for το οποίο θα ελέγχει τα στοιχεία του πίνακα Α από το 1ο μέχρι αυτό που ελέγχεις ώστε αν το έχεις ξαναελέγξει να το πηδάει. Ο κώδικας βέβαια δεν θα είναι βέλτιστος αλλά θα είναι στο ίδιο επίπεδο με τον υπόλοιπο που έγραψες και δεν θα χρησιμοποιεί κάτι που δεν έχετε διδαχθεί.

 

>
   for (i=0;i<=(n1-1);i++){
/* arxh */
       same = 0;
       for (k=0;k<i;k++) {
           if (A[k] == A[i]) {
               same = 1;
               break;
           }
       }
       if (same)
           continue;
/* telos */
       j=0;
       do{

 

Αν πάρουμε τον κώδικά σου μετά τις διορθώσεις που έκανε ο ZAKKWYLDE και προσθέσουμε το παραπάνω κομμάτι, τότε το αποτέλεσμα είναι μόνο 3 4 αντί για 3 4 3 που ήταν αρχικά. Ελέγχεις σειριακά ένα-ένα τα στοιχεία του πίνακα και αν κάποιο είναι ίσο με το παρόν στοιχείο σημαίνει ότι το έχεις ελέγξει στο παρελθόν (και είτε είναι κοινό με τους άλλους είτε όχι) οπότε δεν χρειάζεται να ξαναελεγχθεί για αυτό θέτεις τιμή 1 στη ακέραια μεταβλητή same. Αν η μεταβλητή έχει τιμή 1 τότε τρέχεις continue δηλαδή πηδάς το παρόν i και πας στο επόμενο στοιχείο.