Advanced ταξινόμηση πινάκων στη C

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Άβαταρ μέλους
Silverthan
Δημοσιεύσεις: 114
Εγγραφή: 13 Ιουν 2004 13:43
Τοποθεσία: McLaren Technology Center
Επικοινωνία:

Advanced ταξινόμηση πινάκων στη C

Δημοσίευση από Silverthan » 16 Σεπ 2012 13:03

Καλησπέρα παίδες,

Εστω ότι εχω 2 πίνακες με 10 τιμές τους οποίους εχω αρχικοποιήσει και σορτάρει με bubble.

Θέλω τώρα στους νέους πίνακες παίρνοντας με τη σειρά κάθε στοιχείο του Α, κοιταζω το αντίστοιχο του Β, δηλαδή για τον Α[0] το Β[0] κοκ.

Θέλω να βρω το επόμενο νούμερο από τον πίνακα Α με την σειρά, που είναι μεγαλύτερο ή ίσο από τον αυτόν τον αριθμό, τον Β[0] και να τουs τυπώσω :)

Προσπαθώ να το κάνω με αυτό το τρόπο.

Κώδικας: Επιλογή όλων

 
    for &#40;i=0; i<10; i++&#41; &#123;
        
        if &#40;tableB&#91;i&#93;>=tableA&#91;i+1&#93;&#41; &#123;
            
            if &#40;tableB&#91;i&#93;>=tableA&#91;i+2&#93;&#41; &#123;
                
                i++;
            &#125;
            
            else &#123;
            
            printf&#40; "%5d   | %5d\n", tableA&#91;i&#93;, tableB&#91;i&#93;&#41;;
                
            &#125;
        &#125;
        
        else &#123;
            
            tableA&#91;i&#93; = tableC&#91;i&#93;;
            tableB&#91;i&#93; = tableD&#91;i&#93;;
            k++;
      
Ευχαριστώ ΠΑΡΑ ΠΟΛΥ για κάθε βοήθεια εκ των προτέρων :)

nkast
Δημοσιεύσεις: 137
Εγγραφή: 15 Νοέμ 2009 20:31
Επικοινωνία:

Advanced ταξινόμηση πινάκων στη C

Δημοσίευση από nkast » 19 Σεπ 2012 05:19

Κώδικας: Επιλογή όλων

int aidx=0;
int bidx=0; 
for &#40;bidx=0; bidx<10; bidx++&#41; 
&#123; 
         if&#40;aidx<bidx&#41; aidx=bidx; 
         while&#40;tableB&#91;bidx&#93;>tableA&#91;aidx&#93; && aidx<10&#41; aidx++;
         if&#40;aidx>=10&#41; continue;
         printf&#40; "%5d   | %5d\n", tableA&#91;aidx&#93;, tableB&#91;bidx&#93;&#41;;               
&#125; 
Κατι σαν αυτο πιστευω θα δουλεψει.
Στον κωδικα σου εχεις και κατι ακομα που δεν κατάλαβα τι κατι και ποτε.

Άβαταρ μέλους
Silverthan
Δημοσιεύσεις: 114
Εγγραφή: 13 Ιουν 2004 13:43
Τοποθεσία: McLaren Technology Center
Επικοινωνία:

Advanced ταξινόμηση πινάκων στη C

Δημοσίευση από Silverthan » 20 Σεπ 2012 09:51

Ευχαριστώ πολύ nkast! :)

Δυστυχώς με την while πεφτει σε κάποια λούπα και μου βγάζει υπερβολικά πολλά αποτελέσματα.

Τώρα προσπαθώ με τον παρακάτω κώδικα


Κώδικας: Επιλογή όλων

   int m=0;
 
            for &#40;i=0; i<10; i++&#41; &#123;
        
                    if &#40;tableA&#91;i+1&#93;>=tableB&#91;m&#93;&#41; &#123;
                                
                            printf&#40; "%5d   | %5d\n", tableA&#91;i&#93;, tableB&#91;i&#93;&#41;;
                            m++;
                     &#125;
                
                    else &#123;
                        
                        printf&#40;"Den yparxei megalutero\n"&#41;;
                        
                    &#125;
                                                 
            &#125;
Ακόμα δε μου βγάζει βέβαια ακριβώς όπως το θέλω :(

nkast
Δημοσιεύσεις: 137
Εγγραφή: 15 Νοέμ 2009 20:31
Επικοινωνία:

Advanced ταξινόμηση πινάκων στη C

Δημοσίευση από nkast » 20 Σεπ 2012 13:48

Δεν καταλαβαίνω γιατι συγκρίνεις αρχικά την tableA[i+1] ενώ στην περιγραφη γράφεις πως ξεκινάς με tableA[0] και tableB[0].

Αν δωσεις τα στοιχεια που βαζεις στους πινακες θα μπορουσα να δοκιμασω την λυση πανω στον compiler να δω τι συμβαινει με την while.

Θα παραφράσω λιγο το προβλήμα για να σου εξηγίσω τι πρασπαθώ να κανω στον αλγόριθμό που σου εστειλα.

Για καθε στοιχείο Bindex του πινακαΒ, βρίσκουμε το στοιχείο Aindex (οπου Aindex>=Bindex ) του πινακαΑ που είναι μεγαλύτερο ή ίσο.

Αυτο θα μπορουσε να γραφεί

const int SIZE=10;
for (int Bindex=0; Bindex<SIZE; Bindex++)
{
int Aindex=Bindex;
while(tableA[Aindex]<tableB[Bindex] && Aindex<SIZE) Aindex++;
if(Aindex>=SIZE) {printf("No more results");break;}
printf( "%5d | %5d\n", tableA[aidx], tableB[bidx]);
}

Στην χειροτερη περιπτωση το παραπανω θα κάνει SIZE*SIZE συγκρίσεις και SIZE*SIZE*2 προσπεράσεις στους πινακες.

Ξέρουμε όμως πως οι πίνακες είναι ταξινομημένοι, οποτε καθε φορα το στοιχείο στον πινακα Α που ψαχνουμε αποκλείεται να βρίσκαται σε μικρότερη θεση απο το στοιχείο που βρηκαμε την προηγούμενη φορα.
Για αυτο το λογο στον αλγοριθμό που σου εστειλα διλώνω το Aindex εξω απο την λουπα ωστε να θυμάται την τελευταία θεση, και αντι για Aindex=Bindex; κανω απλα if(aidx<bidx) aidx=bidx;
Αυτός είναι και ο λογος που o index στην λοοπα κανει iterate πανω στα στοιχεία του πινακα Β. Εξού και η παραφρασή του προβλήματος ωστε ο πινακας Β να είναι αυτος που οδηγεί στην λύση.

Η διαφορα στην ταχυτητα αναμεσα στους δυο αλγοριθμούς θα γινεται εντυπωσιακή για μεγαλα SIZE.

:hammer:
~Know your DATA~

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης