Αλγοριθμικό πρόβλημα με πίνακες

[AfterForever]

Καλημέρα. Θα εκτιμούσα τη βοήθειά σας σε ένα πρόβλημα.

 

Έχουμε 4 πίνακες.

Έναν Β[3000] που έχει ονόματα βιβλίων.

Έναν Σ[3000] που έχει τα αντίστοιχα ονόματα των συγγραφέων (υπάρχει δλδ συσχέτιση των πινάκων Β και Σ).

Έναν ΟΝ[1000] που έχει τα ονόματα δανειστών και τέλος έναν δυσδιάστατο Δ[3000,12] που μας δείχνει τους δανεισμούς των βιβλίων ανά μήνα. Αν ένα κουτάκι του πίνακα έχει ένα νούμερο μέσα, μας δείχνει τον αύξοντα αριθμό του δανειστή, αλλιώς έχει το 0 που σημαίνει ότι δεν είναι δανεισμένο.

Παράδειγμα:

Αν Δ[5,3]=598, αυτό σημαίνει ότι ο βιβλίο Β[5] του συγγραφέα Σ[5] το 3ο μήνα Μάρτιο είναι δανεισμένο από τον ΟΝ[598].  Νομίζω ότι έχω γίνει κατανοητός ως εδώ.

 

Υπάρχει ερώτημα που λέει: δοθέντος του ονόματος ενός δανειστή, να βρίσκει ποιον συγγραφέα προτιμάει.

 

Πάω εγώ και λέω. Πάρε το όνομα του δανειστή. Βρες σε ποια θέση είναι στον ΟΝ[1000]. Ψάξε τη θέση στον πίνακα Δ[3000,12] ανά γραμμή. Φτιάξε έναν μονοδιάστατο πίνακα πχ ΣΥΧΝΟΤΗΤΑ_ΕΜΦΑΝΙΣΗΣ [3000] και σε κάθε γραμμή που βρίσκεις τον αύξοντα αριθμό του δανειστή, πρόσθεσε +1 για να ξέρεις τελοσπάντων ο δανειστής αυτός ποια βιβλία/ποιους συγγραφείς έχει επιλέξει. Μετά βρίσκοντας το μέγιστο στοιχείο του ΣΥΧΝΟΤΗΤΑ_ΕΜΦΑΝΙΣΗΣ [3000] ξέρεις ποιο βιβλίο / ποιον συγγραφέα έχει προτιμήσει πιο πολύ.

 

Το πρόβλημα και η δυσκολία έγκειται στο ότι τα βιβλία μεν είναι μοναδικά (προφανώς) όχι όμως και οι συγγραφείς! Αν ήταν μοναδικά, στη θέση που θα έβρισκες το μέγιστο στοιχείο του ΣΥΧΝΟΤΗΤΑ_ΕΜΦΑΝΙΣΗΣ [3000], η αντίστοιχη θέση είναι μεν το βιβλίο που προτιμάει, ΑΛΛΑ ο συγγραφέας μπορεί να εμφανίζεται σε περισσότερες από μία θέσεις στον Σ[3000].

 

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

Ευχαριστώ και σόρι για το σεντόνι.

[H_ANARXIA_EINAI_PSEMA]

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

 

Δηλαδη ας πουμε ότι είναι έτσι:

 

 

[0] = 3 ; Kazantzakhs
[1] = 7 ; Trivizas
[2] = 6 Kazantzakis

μετά την ταξηνόμιση θα είναι έτσι

 

[0] = 3 ; Kazantzakhs
[2] = 6 Kazantzakis
[1] = 7 ; Trivizas

μετά βρίσκεις τον συγγραφέα με τα περισσότερα βιβλία προσθέτοντας διαδοχικά (π.χ. ο πρώτος έχει 3 + 6 = 9)

[albNik]

Φτιαξε εναν αλλο πινακα Σ2 με τους διαφορετικους συγγραφεις και μια αντιστοίχηση προς τον Σ 

 

δλδ Σ[1]=Σ[15]=Σ[100]=Σ2[7]...

[migf1]

...

Το πρόβλημα και η δυσκολία έγκειται στο ότι τα βιβλία μεν είναι μοναδικά (προφανώς) όχι όμως και οι συγγραφείς!

...

Από την εκφώνηση που δίνεις ΔΕΝ προκύπτει το παραπάνω συμπέρασμά σου. Αντιθέτως, αναφέρεις πως υπάρχει συσχέτιση μεταξύ των πινάκων Β και Σ, κάτι που οδηγεί στο λογικό συμπέρασμα πως πρόκειται για parallel arrays (δηλαδή για 1 προς 1 αντιστοιχία μεταξύ των στοιχείων των 2 πινάκων).

 

Αν οι συγγραφείς ΔΕΝ ήταν μοναδικοί, τότε η λογική υποδεικνύει πως ο πίνακας Δ θα έπρεπε να ήταν 3-διάστατος (και όχι 2-διάστατος που είναι τώρα).

 

Βασικά το γράφεις και αλλού πως πρόκειται για 1 προς 1 αντιστοιχία. Εκεί που λες:

Αν Δ[5,3]=598, αυτό σημαίνει ότι ο βιβλίο Β[5] του συγγραφέα Σ[5] το 3ο μήνα Μάρτιο είναι δανεισμένο από τον ΟΝ[598].

ΥΓ. Σε τέτοιους είδους ασκήσεις, με μη μοναδικούς συγγραφείς, μια πολύ δημοφιλής προσέγγιση είναι με hash-tables, αλλά υποθέτω πως δεν τους έχετε μάθει ακόμα.

[AfterForever]

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

[migf1]

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

Δεν καταλαβαίνω τι εννοείς

 

Αυτή εδώ η σχέση που περιγραφεις στην εκφώνηση:

Αν Δ[5,3]=598, αυτό σημαίνει ότι ο βιβλίο Β[5] του συγγραφέα Σ[5] το 3ο μήνα Μάρτιο είναι δανεισμένο από τον ΟΝ[598]. Νομίζω ότι έχω γίνει κατανοητός ως εδώ

νομίζω κάνει σαφές πως ο πίνακας Δ συσχετίζει 3 πράγματα (2 indices κι 1 value). Λες λοιπόν πως το πρώτο πράγμα, δηλαδη το index 5, εκφράζει δυο "υπο-πράγματα" δηλαδή ΚΑΙ βιβλίο ΚΑΙ συγγραφέα, αλλά κατόπιν θέλεις να θεωρήσουμε πως το 5 εκφράζει μόνο το βιβλίο Β[5] και πως ο συγγραφέας μπορεί να είναι ας πούμε ο Σ[8] (ή το ανάποδο).

 

Αυτό δεν γίνεται με τα δεδομένα που δίνεις ως εκφώνηση (εκτός αν δεν έχω καταλάβει κάτι).

 

EDIT:

 

Για να στο πω αλλιώς. Ας πούμε ότι ισχύει αυτό που λες, ότι δηλαδή το βιβλίο Β[1] έχει 2 συγγραφείς. Μπορείς να μου πεις ποια λογική συσχέτιση υπάρχει μεταξύ του κελιού B[1] και του πίνακα Σ[]; Ποιο σημείο της εκφώνησής σου συσχετίζει το βιβλίο Β[1] με παραπάνω του ενός συγγραφέα;

[defacer]

Δεν μας είπες τι επιτρέπεται να κάνεις...

• επιτρέπεται να "χαλάσεις" τα δεδομένα εισόδου στην προσπάθειά σου να απαντήσεις στο ερώτημα;
• επιτρέπεται να χρησιμοποιήσεις επιπλέον μνήμη για υπολογισμούς; αν ναι, πόση;
• τι είδους δομές δεδομένων επιτρέπεται να χρησιμοποιήσεις;
• υπάρχει κάποιος περιορισμός όσον αφορά την απόδοση του ζητούμενου αλγορίθμου;

[AfterForever]

Δεν καταλαβαίνω τι εννοείς

 

Αυτή εδώ η σχέση που περιγραφεις στην εκφώνηση:

νομίζω κάνει σαφές πως ο πίνακας Δ συσχετίζει 3 πράγματα (2 indices κι 1 value). Λες λοιπόν πως το πρώτο πράγμα, δηλαδη το index 5, εκφράζει δυο "υπο-πράγματα" δηλαδή ΚΑΙ βιβλίο ΚΑΙ συγγραφέα, αλλά κατόπιν θέλεις να θεωρήσουμε πως το 5 εκφράζει μόνο το βιβλίο Β[5] και πως ο συγγραφέας μπορεί να είναι ας πούμε ο Σ[8] (ή το ανάποδο).

 

@defacer

Χρησιμοποιούνται πίνακες, δε μας νοιάζει η απόδοση κτλ. Και επιτρέπεται να τους πειράξουμε, πχ να τους ταξινομήσουμε.

Αυτό δεν γίνεται με τα δεδομένα που δίνεις ως εκφώνηση (εκτός αν δεν έχω καταλάβει κάτι).

 

EDIT:

 

Για να στο πω αλλιώς. Ας πούμε ότι ισχύει αυτό που λες, ότι δηλαδή το βιβλίο Β[1] έχει 2 συγγραφείς. Μπορείς να μου πεις ποια λογική συσχέτιση υπάρχει μεταξύ του κελιού B[1] και του πίνακα Σ[]; Ποιο σημείο της εκφώνησής σου συσχετίζει το βιβλίο Β[1] με παραπάνω του ενός συγγραφέα;

 

Το βιβλίο Β[5] έχει τον Σ[5].

Το Β[7] έχει τον Σ[7]. Τα Σ[5] και Σ[7] μπορεί να είναι ίδια (λέω εγώ τώρα).

Οι πίνακες είναι 1-1. Ο Σ[3000] όμως δε μας λέει κανείς ότι έχει 3000 διαφορετικές τιμές.

Η εκφώνηση είναι αυτή:

Η βιβλιοθήκη του δήμου, θέλει να οργανώσει τα διαθέσιμα βιβλία της ηλεκτρονικά. 
Διαθέτει 3000 βιβλία τα οποία θα αποθηκεύσει στον πίνακα Β[3000]. Επιπρόσθετα, στον πίνακα Σ[3000] θα αποθηκεύσει το όνομα του Συγγραφέα. 
Η βιβλιοθήκη καταχωρεί σε έναν ακόμη πίνακα ΟΝ[1000] το ονοματεπώνυμο των δανειστών της. Ο δανεισμός των βιβλίων είναι μηνιαίος. 
Τέλος σε έναν πίνακα Δ[3000, 12] καταχωρούνται οι δανεισμοί κάθε ενός από τα 3000 βιβλία για τους 12 μήνες του χρόνου. 
Αν κάποιο βιβλίο έχει δανειστεί για κάποιο μήνα τότε στην αντίστοιχη θέση του πίνακα καταχωρείται ο αύξων αριθμός του δανειστή από τον πίνακα ΟΝ, αλλιώς, 
αν το βιβλίο δεν είναι δανεισμένο μπαίνει ο αριθμός 0.
Το πρόγραμμα θα διαβάζει το όνομα ενός συνδρομητή και
 να εμφανίζει, ποιον συγγραφέα συνήθως προτιμά ο συγκεκριμένος δανειστής.

[migf1]

Οκ, αλλά και πάλι δεν προκύπτει από πουθενά πως ένα βιβλίο μπορεί να έχει περισσότερους του ενός συγγραφέα. Αντιθέτως προκύπτει πως κάθε βιβλίο έχει έναν μόνο συγγραφέα.

 

Οπότε, εφόσον δεν έχεις περιορισμούς υλοποίησης, μια προσέγγιση είναι να σκανάρεις τον Δ για το index του δανειστή, και να καταχωρήσεις σε έναν νέο πίνακα (έστω ΒΣ) όλα τα indices βιβλίων/συγγραφέων στα οποία βρέθηκε ο εν λόγω δανειστής. Κατόπιν πιάνεις τον νέο αυτόν πίνακα και φτιάχνεις έναν καινούριο πίνακα (έστω Σ2) με τα ονόματα των συγγραφέων που αντιστοιχούν στα indices του ΒΣ (αν θες να εξοικονομήσεις χώρο και χρόνο, τότε αντί για ονόματα μπορείς να χρησιμοποιήσεις δείκτες προς τον αυθεντικό πίνακα Σ).

 

Τέλος, μετράς τη συχνότητα εμφάνισης των συγγραφέων στον πίνακα Σ2, κι επιστρέφεις αυτόν με την μεγαλύτερη συχνότητα.

 

ΥΓ1. Μπορείς να κάνεις αρκετά πράγματα on-the-fly αντί να φτιάχνεις νέους πίνακες, αλλά εφόσον δεν υπάρχει περιορισμός χώρου/χρόνου νομίζω πως η παραπάνω προσέγγιση είναι straight-forward στην κατανόησή της.

 

ΥΓ2. Για να μετρήσεις τη συχνότητα, μάλλον θα χρειαστεί να φτιάξεις ακόμα έναν πίνακα από int, όπου το κάθε κελί θα αντιστοιχεί σε έναν μοναδικό συγγραφέα.

[whodatinsomniaK]

θα σε μπερδέψω:

1. Διδιάστατη κατανομή συχνοτήτων μεταξύ των τιμών του Δ και του Β: ΙΒ[3000,1000]

 

2. Βρίσκεις τον αριθμό μοναδικών συγγραφέων, έστω n.

 

3. Και μειώνεις τον ΙΒ σε ΙΒ[n,1000] (στην πρώτη διάσταση προσθέτεις τις εμφανίσεις του ίδιου συγγραφέα διαφορετικού βιβλίου)

 

Ο ΙΒ[n,1000] ειναι ένας πίνακας που ανά πάσα στιγμή σου δίνει (πολύ περισσότερη από) την πληροφορία που ζητάς.

[migf1]

...

ΥΓ2. Για να μετρήσεις τη συχνότητα, μάλλον θα χρειαστεί να φτιάξεις ακόμα έναν πίνακα από int, όπου το κάθε κελί θα αντιστοιχεί σε έναν μοναδικό συγγραφέα.

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

 

 

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

#define MAX_NAMES 8

/******************************************//**
 * Search an array of nelems c-strings (sarr) for a c-string (s).
 * Return the index of s in sarr, or -1 if s does not exist in sarr.
 **********************************************
 */
int sarr_lookup( char **sarr, char *s, int nelems )
{
	if ( NULL == sarr || NULL == s ) {
		return -1;
	}

	for (int i=0; i < nelems && NULL != sarr[i]; i++) {
		if ( 0 == strcmp(sarr[i], s) ) {
			return i;
		}
	}
	return -1;
}

/******************************************//**
 * Return an array of POINTERS to the unique c-strings found in an array
 * of nelems c-strings (sarr).
 * The count of the pointers in the returned array is passed to the caller
 * via the 3rd argument (count).
 **********************************************
 */
char **new_sarr_uniques( char **sarr, int nelems, int *count )
{
	*count = 0;
	char **ret = calloc(nelems, sizeof(char *));
	if ( NULL == ret ) {
		return NULL;
	}

	for (int i=0; i < nelems; i++) {
		if ( -1 == sarr_lookup(ret, sarr[i], nelems) ) {
			ret[(*count)++] = sarr[i];
		}
	}

	return ret;
}

/******************************************//**
 *
 **********************************************
 */
void sarr_print( char **sarr, int nelems, char *txtbefore )
{
	if ( NULL != txtbefore ) {
		puts( txtbefore );
	}

	if ( NULL == sarr ) {
		puts( "<NULL ptr argument>" );
		return;
	}

	for (int i=0; i < nelems && NULL != *sarr; i++) {
		puts( *sarr );
		sarr++;
	}
}

/******************************************//**
 *
 **********************************************
 */
void freqs_print( int *freqs, int nelems, char *txtbefore )
{
	if ( NULL != txtbefore ) {
		puts( txtbefore );
	}

	if ( NULL == freqs ) {
		puts( "<NULL ptr argument>" );
		return;
	}

	for (int i=0; i < nelems; i++) {
		printf( "%d\n", freqs[i] );
	}
}


/******************************************//**
 *
 **********************************************
 */
int main( void )
{
	char *names[MAX_NAMES] = {
		"John",
		"Mary",
		"George",
		"John",
		"Tom",
		"John",
		"Anna",
		"Mary"
	};

	int   count = 0;
	char **unqnames = NULL;
	int  *freqs = NULL;


	sarr_print( names, MAX_NAMES, "NAMES:" );

	/* create an array of pointers to the unique c-strings of names */
	unqnames = new_sarr_uniques(names, MAX_NAMES, &count);
	if ( NULL == unqnames ) {
		goto exit_failure;
	}

	sarr_print( unqnames, count, "\nUNIQUE NAMES:" );
	printf( "--- %d unique names found ---\n", count );

	/* create an array of frequencies, parallel to the array of unique names */
	freqs = calloc( count, sizeof(int) );
	if ( NULL == freqs ) {
		goto exit_failure;
	}

	/* update the array of frequences, from the array of names */
	for (int i=0; i < MAX_NAMES; i++) {
		freqs[ sarr_lookup( unqnames, names[i], count) ]++;
	}
	freqs_print( freqs, count, "\nFREQUENCES:" );

	free( freqs );
	free( unqnames );
	system( "pause" );

	return 0;

exit_failure:
	puts( "*** fatal error: possibly out of memory, bye..." );
	free( freqs );
	free( unqnames );
	system( "pause" );

	return 1;
}

 

Έξοδος:

NAMES:
John
Mary
George
John
Tom
John
Anna
Mary

UNIQUE NAMES:
John
Mary
George
Tom
Anna
--- 5 unique names found ---

FREQUENCES:
3
2
1
1
1

Ο πίνακας names είναι hard-coded και υποτίθεται πως περιέχει τα ονόματα των συγγραφέων που αντιστοιχούν στα βιβλία που έχει διαβάσει ο δανειστής. Η συνάρτηση new_sarr_uniques() παίρνει σαν όρισμα τον πίνακα names κι επιστρέφει έναν νέο πίνακα από ΔΕΙΚΤΕΣ στα μοναδικά ονόματα συγγραφέων του πίνακα names.

 

Δεν το έχω βάλει να επιστρέφει τον πιο συχνό συγγραφέα, αλλά είναι πλέον πολύ εύκολο. Βρίσκεις στον πίνακα freqs σε ποιο index βρίσκεται η μεγαλύτερη τιμή (το 0 στο παράδειγμα, μιας και το 3 είναι η μεγαλύτερη τιμή) και κατόπιν τυπώνεις το όνομα του συγγραφέα ως unqnames[index] (μιας και ο freqs είναι parallel με τον unqnames).