Αλγοριθμική ερώτηση

[migf1]

 

 

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

 

Ρεζουμε: αν δεν σε ενδιαφέρει και δεν έχεις χρόνο εσύ 1 φορά εμένα δεν με ενδιαφέρει και δεν έχω χρόνο 1000 φορές. So, lets keep going και όπου βγει...

 

 

[defacer]

Σου προτείνω να ψάξεις ένα ανέκδοτο που έχει σαν punch line τη φράση "ναι, αλλά κι εσείς που τυραννάτε τους μαύρους?". Χαρακτηρίζει τα όσα γράφεις απόλυτα.

[migf1]

 

 

Ευχαριστώ για τη πρόταση, θα την έχω υπόψη μου.

 

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

 

Over & Out από μένα προς το παρόν, πιθανότατα και προς το μέλλον (αν και δεν βάζω και το χέρι μου στη φωτιά για αυτό το τελευταίο).

 

 

[migf1]

Όπως είπαμε πολλάκις τα πάντα γίνονται αλλά εξαρτάται από αυτό που θέλεις. Σε ενδιαφέρει μόνο η πολυπλοκότητα να είναι ν1+ν2 ? Όπως σου είπε και ο migf1 μπορεί υπό συνθήκες το overhead της recursion να είναι μεγαλύτερο από το να αντέγραφες τη μία λίστα σε μια στοίβα ώστε να αντιστραφεί. Ανάλογα τη περίσταση σκέφτεσαι ποιος αλγόριθμος ταιριάζει και είναι βέλτιστος.

merge_r (alist, dlist)
Αν η alist δεν είναι NULL έχουμε
  merge_r(alist->next, dlist)

  Όσο η τιμή της dlist είναι μεγαλύτερη της alist τότε
    Τύπωσε τη τιμή της dlist
    Η dlist δείχνει στην επόμενη τιμή.

  Εμφάνισε την τιμή της alist


dlist = 60 -> 50 -> 40 -> 30 -> 20 -> 10
alist =  5 -> 15 -> 25 -> 35 -> 75

Έξοδος:
75 -> 60 -> 50 -> 40 -> 35 -> 30 -> 25 -> 20 -> 15 -> 10 -> 5

Όσο έχουμε και άλλες τιμές στην λίστα που βρίσκεται σε αύξουσα σειρά, τρέξουμε ξανά τη συνάρτηση αναδρομικά. Αφού τελειώσουν όλες οι τιμές αρχίζει το πισωγύρισμα και εμφανίζονται αντίστροφα οι τιμές της alist δηλαδή σε φθίνουσα σειρά. Πριν όμως την εμφάνιση της κάθε τιμής ελέγχονται οι τιμές της άλλης λίστας ώστε να τις παρεμβάλλει στη σωστή θέση. Έτσι παίρνουμε το αποτέλεσμα που φαίνεται πάνω και είναι η ένωση των δύο λιστών. Δεν μπορώ να πω ότι ο κώδικας είναι ο βέλτιστος και ότι τον δοκίμασα εκτενώς αλλά 3-4 λίστες που του πέταξα τις εμφανίζει σωστά.

 

 

 

Σε μένα γιατί δεν δουλεύει; Μπορείς να δώσεις τον ακριβή κώδικα της merge_r(); Ενδεχομένως σε spoiler μιας και ο nik δεν θέλει να τον δει.

 

Μιας και τον έγραψα που τον έγραψα για να δοκιμάσω την merge_r(), παραθέτω σε σποιλερ κώδικα σε C που λύνει το αρχικό ζητούμενο iteratively σε O(2n1+n2) = O(n1+n2)....

 

 

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct Node {
	int data;
	struct Node *next;
} Node;

/* --------------------------------------------- */
void list_print( Node *list )
{
	while ( NULL != list ) {
		printf( "%d ", list->data );
		list = list->next;
	}
	putchar( '\n' );
}

/* --------------------------------------------- */
void list_reverse_inplace( Node **list )
{
	Node *rev = NULL;

	if ( !list ) {
		fputs( "*** error: list was not reversed\n", stderr );
		return;
	}

	while ( NULL != *list)
	{
		// remove element from old list
		Node *temp = *list;
		*list = (*list)->next;

		// move element to new list
		temp->next = rev;
		rev = temp;
	}

	*list = rev;
}
/* --------------------------------------------- */
void list_merge_sorted( Node *dout, Node *l1, Node *l2 )
{
	if ( !dout ) {
		fputs( "*** error: lists were not merged\n", stderr );
		return;
	}

	while ( l1 && l2 )
	{
		if ( l1->data > l2->data ) {
			dout->data = l1->data;
			l1 = l1->next;
		}
		else {
			dout->data = l2->data;
			l2 = l2->next;
		}
		dout = dout->next;
	}

	// l1 not exhausted? 
	while ( l1 ) {
		dout->data = l1->data;
		l1 = l1->next;
		dout = dout->next;
	}
	// l2 not exhausted? 
	while ( l2 ) {
		dout->data = l2->data;
		l2 = l2->next;
		dout = dout->next;
	}
}
/* --------------------------------------------- */
int main( void )
{
	Node a[] = {
		{1,	&a[1]},
		{5,	&a[2]},
		{10,	&a[3]},
		{100,	NULL}
	};
	Node d[] = {
		{200,	&d[1]},
		{80,	&d[2]},
		{4,	NULL}
	};
	Node o[] = {
		{INT_MAX, &o[1]},
		{INT_MAX, &o[2]},
		{INT_MAX, &o[3]},
		{INT_MAX, &o[4]},
		{INT_MAX, &o[5]},
		{INT_MAX, &o[6]},
		{INT_MAX, NULL}
	};
	Node *alist = a, *dlist = d, *dout = o;

	puts( "alist: Ascendantly  ordered list of length n1" );
	puts( "dlist: Descendantly ordered list of length n2" );
	puts( "dout:  Descendantly ordered list as a result of merging alist with dlist" );

	puts( "\nINITIAL (dout, alist, dlist):" );
	list_print( dout );
	list_print( alist );
	list_print( dlist );

	printf( "\nREVERSED alist in O(n1): " );
	list_reverse_inplace( &alist );
	list_print( alist );

	printf( "\nMERGED dout in O(n1+n2): " );
	list_merge_sorted(dout, alist, dlist);
	list_print( dout );

	puts( "\nFINAL (dout, alist, dlist):" );
	list_print( dout );
	list_print( alist );
	list_print( dlist );

	system( "pause" );   /* Windows only */
	return 0;
}

Έξοδος:

alist: Ascendantly  ordered list of length n1
dlist: Descendantly ordered list of length n2
dout:  Descendantly ordered list as a result of merging alist with dlist

INITIAL (dout, alist, dlist):
2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647
1 5 10 100
200 80 4

REVERSED alist in O(n1): 100 10 5 1

MERGED dout in O(n1+n2): 200 100 80 10 5 4 1

FINAL (dout, alist, dlist):
200 100 80 10 5 4 1
100 10 5 1
200 80 4
Press any key to continue . . .

 

 

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

[imitheos]

Σε μένα γιατί δεν δουλεύει; Μπορείς να δώσεις τον ακριβή κώδικα της merge_r(); Ενδεχομένως σε spoiler μιας και ο nik δεν θέλει να τον δει.

Για τέτοιους κώδικες στα γρήγορα που δεν με ενδιαφέρει να τους κρατήσω, τα αρχεία τα σώζω στο /tmp οπότε με το reboot χάνονται. Αν είναι σημαντικό μπορώ να τον γράψω πάλι όποτε έχω χρόνο και δεν βαριέμαι.

[migf1]

No problem, δεν πειράζει... απλώς από περιέργεια ρώτησα εκείνη τη στιγμή γιατί δεν κατάφερα να το κάνω να μου δουλέψει.

[nik324]

Εστω οτι εχουμε το εξης δεντρο:

             5

            /  \

          /     \

     25       10

    /    \      /   \

   /       \          \

 45     30         15

           /  \         /

          /     \     / 

        40   35  20

 

 

To οποιο εχει την ιδιοτητα οταν το διατρεχουμε σε postorder να δινει να κλειδια σε φθινουσα διαταξη

Υπαρχει τροπος να κανουμε αναζητηση σε αυτο το δεντρο σε Ο(h) ?

Δεν θελω να μου γραψετε λυση... Ευχαριστω

[albNik]

Για το συγκεκριμενο εχεις 2 δεδομένα

 

left > right > root

 

left > καθε στοιχείο του υποδεντρου του right   (δλδ 25 > απο καθε στοιχείο κατω απο το 10)

 

π.χ το 26 δεν μπορει να είναι στο υποδεντρο του 10.

 

Αρα γίνεται.

[Erevis]

Εστω οτι εχουμε το εξης δεντρο:

             5

            /  \

          /     \

     25       10

    /    \      /   \

   /       \          \

 45     30         15

           /  \         /

          /     \     / 

        40   35  20

 

 

To οποιο εχει την ιδιοτητα οταν το διατρεχουμε σε postorder να δινει να κλειδια σε φθινουσα διαταξη

Υπαρχει τροπος να κανουμε αναζητηση σε αυτο το δεντρο σε Ο(h) ?

Δεν θελω να μου γραψετε λυση... Ευχαριστω

 

Αν μιλάμε για binary search tree δεν υφίσταται ποτέ τέτοιο δένδρο. Και τα 2 παιδιά του root έχουν μεγαλύτερο κλειδί (και όχι μόνο του root) κάτι που παραβιάζει τις ιδιότητες του bst.

 

Γράψτε λάθος.

[albNik]

Λέμε για το tree το οποιο εχει την ιδιοτητα οταν το διατρεχουμε σε postorder να δινει να κλειδια σε φθινουσα διαταξη.

[nik324]

Εστω οτι παμε να ψαξουμε το 40..

 

Οταν ειμαστε στη ριζα τοτε το 40 ειναι μεγαλυτερο και απο την ριζα και απο τα δυο παιδια της...Τοτε με ποια λογικη περνουμε το αριστερο μονοπατι;

[albNik]

το 40 θα ειναι

 

κατω απο το 25 και οχι απο το 10   ( κατω απο το 10 μπορει να ειναι  10<χ<25)

κατω απο το 30 και οχι απο το 45   (κατω απο το 30 μπορει  30<χ<45 και κάτω απο 45 πρεπει χ>45)

[nik324]

Νομιζω πως καταλαβα... Θα κατσω σε λιγο να το γραψω και τα ξανα στειλω αν προκυψει προβλημα

 

Σε ευχαριστω