Τα πάντα για την C

[stamatiou]

Πρώτα έχω υλοποιήσει τον πιο απλό αλγόριθμο: http://ideone.com/AlvqT. Να κάνω όλα τα πιθανά αθροίσματα και να κρατάω το μικρότερο. Από αύριο επανέρχομαι με ένα πιο γρήγορο

[simosx]

Πρώτα έχω υλοποιήσει τον πιο απλό αλγόριθμο: http://ideone.com/AlvqT. Να κάνω όλα τα πιθανά αθροίσματα και να κρατάω το μικρότερο. Από αύριο επανέρχομαι με ένα πιο γρήγορο

Πολύ ωραία. Μπορείς να δοκιμάσεις το πρόγραμμα αυτό και με μεγάλα αρχεία εισόδου, για να δεις πως ανταποκρίνεται.
Βλέποντας τον κώδικα, αυτό το for(for()) εκτελείτε γύρω στις n * n φορές. Δηλαδή, αν είχες 1000 στοιχεία στο αρχείο εισόδου, θα έτρεχε ο κώδικας μέσα στο for(for()) 1.000.000 φορές. Για 1.000.000, ο επεξεργαστής μπορεί να τις κάνει αρκετά γρήγορα. Θέλει βελτίωση όταν πας στο 1 εκ. αριθμούς, οπότε είναι 1.000.000 * 1.000.000 = 1.000.000.000.000 = 1τρις.

Αν θες να συζητήσεις και για καλύτερους αλγόριθμους, μπορείς να πεις εδώ.

[stamatiou]

Πρώτα έχω υλοποιήσει τον πιο απλό αλγόριθμο: http://ideone.com/AlvqT. Να κάνω όλα τα πιθανά αθροίσματα και να κρατάω το μικρότερο. Από αύριο επανέρχομαι με ένα πιο γρήγορο

Πολύ ωραία. Μπορείς να δοκιμάσεις το πρόγραμμα αυτό και με μεγάλα αρχεία εισόδου, για να δεις πως ανταποκρίνεται.
Βλέποντας τον κώδικα, αυτό το for(for()) εκτελείτε γύρω στις n * n φορές. Δηλαδή, αν είχες 1000 στοιχεία στο αρχείο εισόδου, θα έτρεχε ο κώδικας μέσα στο for(for()) 1.000.000 φορές. Για 1.000.000, ο επεξεργαστής μπορεί να τις κάνει αρκετά γρήγορα. Θέλει βελτίωση όταν πας στο 1 εκ. αριθμούς, οπότε είναι 1.000.000 * 1.000.000 = 1.000.000.000.000 = 1τρις.

Αν θες να συζητήσεις και για καλύτερους αλγόριθμους, μπορείς να πεις εδώ.

Δλδ τώρα τι να κάνω;

[stamatiou]

Εδώ:

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

for (i=0; !feof(fp) && 1 == fscanf(fp, "%ld", &(*buf)[i]); i++ )

γιατί γράφεις fscanf(fp, "%ld", &(*buf)[i]) και όχι fscanf(fp, "%ld", &buf[i]);

Διότι το buf το περνάω by-reference στην συνάρτηση (ως διπλό δείκτη δηλαδή ή ως *[] αν το καταλαβαίνεις καλύτερα). Οπότε μέσα στην συνάρτηση, το buffer μας είναι το *buf και όχι το buf. Δηλαδή ο πίνακάς μας είναι ο *buf και το σκέτο buf είναι η διεύθυνση του πίνακα (δεν είναι η διεύθυνση του 1ου στοιχείου του πίνακα)

Εδώ δεν καταλαβαίνω γιατί αν είναι αρνητικό πρέπει να αυξηθεί το istart ενώ αλλιώς πρέπει να μειωθεί το iend....

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

Off topic:
Να σε έχει ο Θεός καλά γιατί αν δεν με βοηθούσες στη C θα ήμουν αιώνες πίσω

Φίλε Γιώργο ευχαριστώ, αλλά πιστεύω δεν ακολουθείς σωστό δρόμο. Η γνώμη μου είναι πως πριν γραφτείς σε διαγωνισμούς προγραμματισμού και πριν διαβάσεις βιβλία για hacking, θα πρέπει να κάτσεις να διαβάσεις σωστά και με σύστημα ένα καλό εισαγωγικό βιβλίο στη γλώσσα, όπως αυτό που έχουμε αναφέρει στο νήμα.

Οκ, κατάλαβα τον αλγόριθμο και πως λειτουργεί, αλλά δεν καταλαβαίνω γιατί δουλεύει με τα istart++ και iend--.

[migf1]

Πήγα να κάνω μια υλοποίηση σε συνάρτηση αλλά κάποια χαζομάρα έχω κάνει με τους δείκτες:

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


#include <stdio.h>

int store_buffer(long int **buffer, long int n) {
FILE *input = fopen("operators.in","r");
int i;
for(i = 0; i < n; i++)
fscanf(input,"%ld",&(*buffer)[i]);
return 0;
}

int main(void) {
long int array[5],n;
FILE *input = fopen("operators.in","r");
fscanf(input,"%ld",&n);
store_buffer(&array,n);
for(n = 0; n < 5; n++)
printf("%ld",array[n]);
return 0;
}


Τι του λέω να κάνει και μου βγάζει ο compiler:

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


basic.c:15: warning: passing argument 1 of ‘store_buffer’ from incompatible pointer type
basic.c:3: note: expected ‘long int **’ but argument is of type ‘long int (*)[5]’


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

Αυτό δείχνει κι ο compiler, πως η συνάρτηση περιμένει έναν ** αλλά της περνάς έναν (*)[5]. Άλλαξε τη δήλωση του ορίσματος από...

Μορφοποιημένος Κώδικας: Επιλογή όλων

int store_buffer(long int **buffer, long int n)...

σε...

Μορφοποιημένος Κώδικας: Επιλογή όλων

int store_buffer(long int *buffer[5], long int n)...

και θα είσαι ok

ΥΓ. Τις παλιές μέρες, επί K&R μπορούσες να τα δηλώνεις και ως διπλούς δείκτες, από ANSI και μετά καταργήθηκε.

[migf1]

Οκ, κατάλαβα τον αλγόριθμο και πως λειτουργεί, αλλά δεν καταλαβαίνω γιατί δουλεύει με τα istart++ και iend--.

Το έκανες trace τον κώδικα στον gdb με 4 μόνο στοιχεία στον πίνακα, που σου είπα; Αν σε χαλάει ο gdb, κάνε το trace χειρκοκίνητα σε χαρτί: βάλε στον πίνακα 3-4 μόνο στοιχεία και ακολούθησε στο χαρτί τον κώδικα της συνάρτησης.

Όσο το άθροισμα είναι αρνητικό, μετακινεί τον istart μια θέση προς τα δεξιά για να συγκρίνει το στοιχείο του με το στοιχείο του iend, μόλις το sum γίνει θετικό αφήνει τον istart και πιάνει τον iend.

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

[stamatiou]

Οκ, κατάλαβα τον αλγόριθμο και πως λειτουργεί, αλλά δεν καταλαβαίνω γιατί δουλεύει με τα istart++ και iend--.

Το έκανες trace τον κώδικα στον gdb με 4 μόνο στοιχεία στον πίνακα, που σου είπα; Αν σε χαλάει ο gdb, κάνε το trace χειρκοκίνητα σε χαρτί: βάλε στον πίνακα 3-4 μόνο στοιχεία και ακολούθησε στο χαρτί τον κώδικα της συνάρτησης.

Όσο το άθροισμα είναι αρνητικό, μετακινεί τον istart μια θέση προς τα δεξιά για να συγκρίνει το στοιχείο του με το στοιχείο του iend, μόλις το sum γίνει θετικό αφήνει τον istart και πιάνει τον iend.

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

Το έκανα trace και με gdb και με χαρτί
Αυτό που δεν κατάλαβα είναι γιατί αν το sum είναι αρνητικό, τότε ο μικτρότερος δε χρειάζεται να συμμετέχει σε άλλο άθροισμα ενώ όταν είναι θετικός δεν χρειάζεται ο μεγαλύτερος να συμμετέχει...

[migf1]

Πρέπει να υπάρχει μια συνθήκη η οποία θα μετακινεί τους indexers στην επόμενη θέση, όταν έχει ολοκληρωθεί ο έλεγχος σε ένα ζευγάρι αριθμών.

Αν έχουμε π.χ. τους αριθμούς...

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

-100 -35 10 20

ξεκινάμε με istart=0, iend = 3, minsum = LONG_MAX και έχουμε...

Μορφοποιημένος Κώδικας: Επιλογή όλων

1η επανάληψη:
                 sum = buf[ istart ] + buf[ iend ]; // sum = -80
                if ( abs(sum) < abs(minsum) )    // 80 < LONG_MAX ? YES
                {
                        minsum = sum;    // minsum = -80
                }
                if ( sum < 0 )    // -80 < 0, get inside
                        istart++;   // istart = 1
                else
                        iend--;

2η επανάληψη:
                 sum = buf[ istart ] + buf[ iend ]; // sum = -15
                if ( abs(sum) < abs(minsum) )    // 15 < 80 ? YES
                {
                        minsum = sum;    // minsum = -15
                }
                if ( sum < 0 )    // -15 < 0, get inside
                        istart++;   // istart = 2
                else
                        iend--;

3η επανάληψη:
                 sum = buf[ istart ] + buf[ iend ]; // sum = 30
                if ( abs(sum) < abs(minsum) )    // 30 < -15 ? NO!
                {
                        minsum = sum;    // minsum = -15
                }
                if ( sum < 0 )    // 30 < 0 ? NO!
                        istart++;   // istart = 2
                else            // 30 >= 0 ? YES
                        iend--;    // iend = 2

[stamatiou]

Πρέπει να υπάρχει μια συνθήκη η οποία θα μετακινεί τους indexers στην επόμενη θέση, όταν έχει ολοκληρωθεί ο έλεγχος σε ένα ζευγάρι αριθμών.

Αν έχουμε π.χ. τους αριθμούς...

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

-100 -35 10 20

ξεκινάμε με istart=0, iend = 3, minsum = LONG_MAX και έχουμε...

Μορφοποιημένος Κώδικας: Επιλογή όλων

1η επανάληψη:
                 sum = buf[ istart ] + buf[ iend ]; // sum = -80
                if ( abs(sum) < abs(minsum) )    // 80 < LONG_MAX ? YES
                {
                        minsum = sum;    // minsum = -80
                }
                if ( sum < 0 )    // -80 < 0, get inside
                        istart++;   // istart = 1
                else
                        iend--;

2η επανάληψη:
                 sum = buf[ istart ] + buf[ iend ]; // sum = -15
                if ( abs(sum) < abs(minsum) )    // 15 < 80 ? YES
                {
                        minsum = sum;    // minsum = -15
                }
                if ( sum < 0 )    // -15 < 0, get inside
                        istart++;   // istart = 2
                else
                        iend--;

3η επανάληψη:
                 sum = buf[ istart ] + buf[ iend ]; // sum = 30
                if ( abs(sum) < abs(minsum) )    // 30 < -15 ? NO!
                {
                        minsum = sum;    // minsum = -15
                }
                if ( sum < 0 )    // 30 < 0 ? NO!
                        istart++;   // istart = 2
                else            // 30 >= 0 ? YES
                        iend--;    // iend = 2

Και γιατί όταν είναι το sum < 0 αυξάνεται το istart και όχι το iend; Το ίδιο και για το όταν το sum > 0.

[migf1]

Βάλε το έτσι όπως λες και κάνε το trace