Πρόγραμμα ευρεσης μεγίστου σε C

[p04155]

Καλησπέρα σε όλους,είμαι καινουργιος στο forum ωστόσο είναι πολλές οι φορές που εχω βοηθηθεί διαβάζοντας κάποια threads. Μήπως θα μπορούσε να με βοηθήσει κάποιος με την δημιουργία κώδικα εύρεσης μεγίστου αριθμού από πίνακα ο οποίος θα χωρίζεται σε 2 υποπίνακες?όλο αυτό πρέπει να γίνεται αναδρομικά...έχω κανει αρκετές προσπάθειες όμως κολλάω και χρειάζομαι την βοήθεια ποιο έμπειρων ατόμων πάνω στο αντικείμενο...Ευχαριστώ!ο χρόνος που έχω στην διάθεση μου είναι περιορισμένος και δεν μπορώ να συνεχίσω με άλλα πειράματα!κάθε βοήθεια είναι δεκτή!!!

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Speedy]

Δώσε την εκφώνηση της άσκησης είτε εδώ είτε με pm γιατί δεν κατάλαβα αυτό με τους υποπίνακες που ζητάς...

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

Πρέπει να γράψω ένα πρόγραμμα σε C το οποίο να βρίσκει με αναδρομικό τρόπο το μέγιστο στοιχείο ενός πίνακα. Ο αλγόριθμος θα διαιρεί τον πίνακα σε δύο υποπίνακες και θα επιστρέφει το μέγιστο από τα μέγιστα στοιχεία των δύο υποπινάκων. Ελπίζω τώρα να έγινε σαφέστερο το πρόβλημά μου... Ευχαριστώ πολύ!

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[woochoogirl]

Αν κατάλαβα καλά με divide and conquer πρέπει να το προσεγγίσεις. Ψάξε divide and conquer maximum element of an array ωστε να δεις καποιον ψευδοκωδικα και μετα το μεταφερεις σε C, στην οποια δυστυχως εχω μεσανυχτα πια ωστε να σε βοηθησω :/

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

Αυτό είναι και εμένα το πρόβλημά μου, η προσέγγιση που προσπαθώ να κάνω είναι με Divide and Conquer δηλαδή διαίρει και βασίλευε οι πληροφορίες που βρίσκω στο διαδίκτυο είναι όλες για ψευδικώδικα. Η δυσκολία είναι να φτιαχτεί ο κώδικας που θα μπορεί να περάσει από τον compiler...

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Speedy]

Η κυριότερη λύση είναι να σπασεις τον πίνακα στα 2 να κανεις αναζητηση μεγίστου σε κάθε έναν και έπειτα να συγκρίνεις τα 2 μέγιστα.. Αν θες αυτό είναι 5 min υπόθεση.. Το διαίρει και βασίλευε χρησιμοποιείται σε ταξινομήσεις πινάκων όπου δεν βρίσκει απλά μέγιστο αλλά ταξινομεί έναν πίνακα βλέπε Quick Sort, Merge Sort κτλ.. Για ποιο λόγο να κάνεις ταξινόμηση με διαίρει και βασίλευε απο τι στιγμή που θές απλά μέγιστο.. Πραγματικά Αν μπορείς δώσε την εκφώνηση δεν καταλαβαίνω πραγματικά τι ζητάς....

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

Η ακριβής εκφώνηση είναι η εξής:
Να γράψετε ένα πρόγραμμα σε C το οποίο να βρίσκει με αναδρομικό τρόπο το μέγιστο στοιχείο ενός πίνακα. Ο αλγόριθμος θα διαιρεί τον πίνακα σε δύο υποπίνακες και θα επιστρέφει το μέγιστο από τα μέγιστα στοιχεία των δύο υποπινάκων. Επίσης, να κάνετε ανάλυση του χρόνου εκτέλεσης του προγράμματός σας και να αποδείξετε επαγωγικά ότι ο αλγόριθμός σας βρίσκει το μέγιστο στοιχείο του πίνακα. Μαζί με την απάντησή σας, να δώσετε και τα αποτελέσματα του προγράμματος σε έναν test πίνακα.
Ευχαριστώ και πάλι!

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[JosefK]

Η κυριότερη λύση είναι να σπασεις τον πίνακα στα 2 να κανεις αναζητηση μεγίστου σε κάθε έναν και έπειτα να συγκρίνεις τα 2 μέγιστα.. Αν θες αυτό είναι 5 min υπόθεση.. Το διαίρει και βασίλευε χρησιμοποιείται σε ταξινομήσεις πινάκων όπου δεν βρίσκει απλά μέγιστο αλλά ταξινομεί έναν πίνακα βλέπε Quick Sort, Merge Sort κτλ.. Για ποιο λόγο να κάνεις ταξινόμηση με διαίρει και βασίλευε απο τι στιγμή που θές απλά μέγιστο.. Πραγματικά Αν μπορείς δώσε την εκφώνηση δεν καταλαβαίνω πραγματικά τι ζητάς....

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

#include <stdio.h>


int maximum(int array[],int n)
{
int x,y;
if (n==1) return array[0];
else if (n==2)
{
if (array[0]> array[1]) return array[0];
else return array[1];
}
else
{
x=maximum(array,n/2);
y=maximum(array+n/2,n-n/2);
if (x>y) return x;
else return y;
}
}



int main()
{
int array[] = {3,0,1212,1,7,23,10,352175,27,12};
printf ("%d\n",maximum(array,10));
return 0;
}

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

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

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[JosefK]

Να κάνω και μία διευκρίνηση!
Όταν έγραψα " Εντελώς βλακεία άσκηση, ούτε καν για εκπαιδευτικούς λόγους δεν αξίζει."
δεν εννοούσα ότι πρόκειται για πανεύκολη άσκηση για κάποιον αρχάριο, εννούσα ότι αυτός ο τρόπος εύρεσης μεγίστου είναι "κακός", ταλαιπωρία για το τίποτα. Γίνεται πολύ πιο απλά και πιο γρήγορα. Καλό είναι οι ασκήσεις που μπαίνουν για εκπαιδευτικούς λόγους να έχουν και κάποια πρακτική αξία και λογική.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

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

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Speedy]

#include <stdio.h>


int maximum(int array[],int n)
{
int x,y;
if (n==1) return array[0];
else if (n==2)
{
if (array[0]> array[1]) return array[0];
else return array[1];
}
else
{
x=maximum(array,n/2);
y=maximum(array+n/2,n-n/2);
if (x>y) return x;
else return y;
}
}



int main()
{
int array[50];//η όσα στοιχεία θές να έχεισ συνολικά αντι για 50.

[COLOR=#ed1c24]for(int i=0;i<50;i++){
printf("Dwse to %d stoixeio tou pinaka:",i+1);
scanf("%d",&array[i]);
}[/COLOR]

printf ("%d\n",maximum(array,10));
return 0;
}

Υ.Γ. Στρώσου στο διάβασμα αυτά είναι τα πλέον βασικά που πρέπει να γνωρίζεις..

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

Ευχαριστώ και πάλι το θέμα είναι πως διαβάζω αυτά που διαβάζω τα καταλαβαίνω είναι απλά και κατανοητά όταν όμως προσπαθώ να συνθέσω ένα τέτοιο πρόγραμμα όλα γίνονται βουνό και δύσκολα. Πολύ διαβασμα λοιπόν από εδώ και πέρα!

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Speedy]

Σιγα σιγά μαθαίνεις προγραμματισμό... Είναι ένας μαγικός κόσμος και σου εύχομαι καλή περιήγηση!

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

Να συνεχίσω να ρωτάω πράγματα? Πιστευω να μην σπάω τα νεύρα κανενός...και με τον πρωτο κώδικα και με τον δεύτερο κώδικα που διωρθώνει τον πρώτο καταργείτε η δυνατότητα εισαγωγής λιγότερων ή περισσότερων στοιχείων στον πίνακα...θέλω να πω ότι εφόσον δεν υπάρχει η δυνατότητα εισαγωγής ενός μοναδικού στοιχείου ή δύο στοιχείων τότε τα if που εξετάζουν το ενδεχόμενο εισαγωγής 1 ή 2 στοιχείων δεν χρησιμεύουν πουθενά. προσπαθώ να είσάγω από χτες το κομμάτι κώδικα που να ζητά το μέγεθος του πίνακα στην αρχή και εν συνεχεία να εισάγει ο χρήστης ένα-ένα τα στοιχεία που θέλει..αλλά κάτι κάνω λάθος με τις μεταβλητές. αυτό το κομμάτι του κώδικα με τα scanf/printf πρέπει να είναι μέσα στη main? οι μεταβλητές που θα χρησιμοποιώ στην main πρέπει να ταυτίζονται με αυτά της εξωτερικής συνάρτησης?

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[JosefK]

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

Δυστυχώς δεν έχεις καταλάβει ακόμα τη λειτουργία μιας αναδρομικής συνάρτησης. Δεν καλείται μία φορά, καλείται πολλές φορές αναδρομικά. Αν πχ έχουμε αρχικά ένα πίνακα 50 στοιχείων, θα καλεστεί μία φορά με όρισμα ολόκληρο τον πίνακα, μετά θα σπάσει τον πίνακα στα 2 και θα καλεστεί 2 φορές για πίνακες 25 στοιχείων, μετά τον κάθε πίνακα 25 στοιχείων τον σπάει και καλέιται από 2 φορές με ορίσματα πίνακες 12 και 13 στοιχείων κ.ο.κ., μέχρι να φτάσει στα 1 ή 2 στοιχεία.

αυτό το κομμάτι του κώδικα με τα scanf/printf πρέπει να είναι μέσα στη main?

ναι

οι μεταβλητές που θα χρησιμοποιώ στην main πρέπει να ταυτίζονται με αυτά της εξωτερικής συνάρτησης?

Κάθε συνάρτηση χρησιμοποιεί τις δικές της, διαφορετικές μεταβλητές. Μία συνάρτηση μπορεί να περνάει σε μία άλλη ως όρισμα τις τιμές κάποιων μεταβλητών.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[p04155]

πολύ καίριες οι παρατηρήσεις σου josefk!
Να'σαι καλά!

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.