Δημιουργία λέξεων(συνδιασμοί) απο έναν αριθμό

[Haris]

Γεια σε ολους!
Εχω αρχισει προγραμματισμο εδω και ενα μήνα, στη γλωσσα C. Εχω αρκετά μεγάλες δυσκολίες να καταλάβω μερικές φορές των κώδικα, και ακόμη πως να σκεφτώ για την λύση ενός αλγόριθμου.
Θα ήθελα να θέσω μια ερώτηση σχετικά με μια άσκηση:
"Γράψτε ένα πρόγραμμα που λαμβάνει ένα επταψήφιο αριθμό τηλεφώνου και μάθετε ποιες λέξεις μπορεί να συσταθουν από τον αριθμό αυτό και ταυτόχρονα να περιλαμβάνονται στο αρχείο lexeis.txt."
Δηλαδή εγω γράφω ενα επταψήφιο αριθμό και το προγραμμα ελεγχει ποιες λέξεις ταιριαζουν απο το αρχειο exeis.txt και τις τυπωνει στην οθονη.
Η αναλογία αριθμών - ψηφίων ειναι ετσι:
http://img843.imageshack.us/i/thl.png/
Σκέφτηκα να εχω δυο arrays που το ενα να ελεγχει τους αριθμους και το αλλο τα γραμματα, αλλά πως θα τα τα ενώσω, και πως θα αποθηκεύσω αυτο που ελεγχει?

Ευχαριστώ εκ των προτέρων.

[linuxs]

ίσως να έχεις βρεί ήδη την απάντησή σου...αλλα σε περίπτωση που "δεν" το αρχείο lexeis.txt τι περιέχει περίπου.?

[M.Jackson]

Θα θεσω την δικη μου σκεψη.
Τα arrays στην C ξεκινανε απο το 0. Αυτο ειναι καλο για το προβλημα σου.
Θα φτιαξεις ενα array με 10 θεσεις [0-9] οπου θα ειναι String.
Στην συνεχεια θα γεμισεις τον πινακα αναλογα με την εικονα που μου εδωσες πιο πανω δηλαδη στην θεση 0 θα βαλεις το "XYZ" στην θεση 1 θα βαλεις το "AB" κτλ.

Μετα θα διαβασεις τον επταψηφιο αριθμο σου. Θα τον βαλεις σε ενα array οπου θα μπενει ενας αριθμος σε καθε θεση. Μετα θα ελεχεις τον πρωτο αριθμο αν πχ ειναι το 1 σε μια μεταβλητη String θα βαλεις την λεξη που αντοιστιχει στον πινακα με τα γραμαμτα, τα αλλα ειναι ευκολα για να δωσο λιγο φως θα το γραψω σε ψευδοκοδικα γιατι βιαζομε.

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

string lexeis [9]
lexeis [0] = "XYZ"
lexeis [1] = "AB"
.
.
lexeis [9] = "UWV"

int x;
read x;

int nums[] = x.toIntArray; //nmz iparxi etimi sinartisi metatropis mias metavlitis se analogo array an den iparxi stin C giati iparxi stin java kanto xirokinita

String result;

for (int i=0; i<=6; i++)
{
for(int j=0; j<=9; j++)
{
if(nums[i] == j)
{
result = result + lexeis[j]
}
}
}

input = file ("lexeis.txt");
elexos sto arxio lexeis.txt gia tin lexi stin metavliti result.

Ελπιζω να καταλαβες.

[migf1]

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

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

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

1. Οι λέξεις μέσα στο αρχείο "lejeis.txt" ΠΡΕΠΕΙ να είναι η μία κάτω από την άλλη (βαρέθηκα να το κάνω πιο ευέλικτο στην ανάγνωσής τους). Το διάβασμά τους το κάνω με τη συνάρτηση:

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

char *s_fget(char *s, size_t len, FILE *fp)

η οποία είναι η παραλλαγή για αρχεία της συνάρτησης που έχω παραθέσει σε αυτό εδώ το post.

2. Το νούμερο που εισαγάγει ο χρήστης το διαβάζω ως string 7 ψηφίων, με τη συνάρτηση:

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

int digs_ngets( char *digs, int n )

η οποία σε συνδυασμό με το do-while loop στην main() ΑΠΑΙΤΕΙ το νούμερο να είναι 7-ψήφιο.

3. Για να το συγκρίνω με κάθε λέξη του αρχείου, στο loop διαβάσματος μετατρέπω προσωρινά την κάθε λέξη επίσης σε string ψηφίων, με το κάθε ψηφίο να αντιστοιχεί στο κάθε γράμμα της λέξης βάσει των τηλεφωνικών κουμπιών που δείχνει η εικόνα της εκφώνησης. Η μετατροπή αυτή γίνεται με τη συνάρτηση:

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

char *s_word2digs( char *digs, char *word, int *map )

(εξηγώ παρακάτω τι είναι το 'map')

4. Προφανώς η μετατροπή γράμματος σε ψηφίο, προϋποθέτει να υπάρχει αρχικά ένας πίνακας από strings, με τη θέση του κάθε string μέσα στον πίνακα να αντιστοιχεί στο ψηφίο του εκάστοτε κουμπιού και το ίδιο το string να αποτελείται από τα γράμματα του κουμπιού. Αυτός ο πίνακας στον κώδικα είναι ο:

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


char *buttons[ MAX_BUTTONS ] = {
"xyzXYZ", "abAB", "cdeCDE", "fgFG", "hijHIJ",
"klKL", "mnoMNO", "pqrPQR", "stST", "uwvUWV"
};


(έχω προσθέσει και τα πεζά γράμματα μαζί με τα κεφαλαία).

5. Ενδεχομένως ο πιο κοινός τρόπος να γίνει η μετατροπή ενός γράμματος σε αντίστοιχο ψηφίο είναι με ένα loop από το κουμπί 0 έως το 9 στον παραπάνω πίνακα, και κατόπιν είτε με τη χρήση της στάνταρ συνάρτησης strchr() είτε με δικιά μας συνάρτηση να ελέγξουμε αν υπάρχει το γράμμα που ψάχνουμε μέσα στο string του τρέχοντος κουμπιού, κι αν υπάρχει να επιστρέφουμε τη θέση του string μέσα στον πίνακα (0 έως 9 δηλαδή) που είναι και το ζητούμενο ψηφίο. Αλλιώς να πηγαίνουμε στο επόμενο κουμπί και να επαναλαμβάνουμε τη διαδικασία.

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

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

6. Για να αποφύγω λοιπόν όλη αυτή την καθυστέρηση, χρησιμοποιώ έναν πίνακα αντιστοίχισης 'map' οπότε δεν χρειάζεται να κάνω ΚΑΜΙΑ αναζήτηση, με μοναδικό ΕΦΑΠΑΞ κόστος την αρχικοποίηση του πίνακα και το casting από char σε int, στη συνάρτηση:

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

void map_buttons( int *map, char **buttons )

Αυτό που κάνω ουσιαστικά είναι ότι χαρτογραφώ μέσα στον πίνακα 'map' όλον τον πίνακα ASCII (256 χαρακτήρες δηλαδή). Αυτό σημαίνει πως οι θέσεις του πίνακα 'map' (δλδ τα indices του) είναι τα ASCII codes των χαρακτήρων από το 0 έως το 255. Με την ταχύτατη memset() αρχικοποιώ τις τιμές των κελιών του 'map' σε -1 και κατόπιν με ένα loop από 0 έως 9 (10 κουμπιά δλδ) διατρέχω τα κουμπιά εξετάζοντας τα γράμματα των strings τους, βάζοντας το ψηφίο που αντιστοιχεί στο κάθε γράμμα ως τιμή στο αντίστοιχο κελί του 'map' .

Οπότε, έχω πλέον ανά πάσα στιγμή το ψηφίο που αντιστοιχεί π.χ. στο γράμμα Α με ένα απλό indexing στον πίνακα map στη θέση 'A'...

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


map['A']


Στον κώδικα έχω γράψει επίσης πολλά επεξηγηματικά σχόλια. Ελπίζω να φανεί χρήσιμος σε κάποιους. Βελτιώσεις, παρατηρήσεις, επισημάνσεις πάντα ευπρόσδεκτες. Κοιτάξτε και για κάνα bug, γιατί δεν έκανα πολύ testing με λέξεις.

ΟΛΟΚΛΗΡΩΜΕΝΟΣ ΚΩΔΙΚΑΣ

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


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

#define MAX_BUTTONS 10
#define MAPPED_NCHARS 256
#define MAXLEN_WORD 7+1

#define myexit(n) printf("\npress ENTER to exit..."); fflush(stdin); getchar(); exit((n))

typedef enum { FALSE=0, TRUE } bool;

// ------------------------------------------------------------------------------------
// Διαβάζει το string 'digs' από το πληκτρολόγιο έως ότου είτε συμπληρωθούν 'n'
// χαρακτήρες, είτε πατηθεί ENTER, είτε εισαχθεί χαρακτήρας που ΔΕΝ είναι ψηφίο και
// μηδενίζει τον τελικό χαρακτήρα (αν ο τελικός ήταν ENTER ή ΜΗ ψηφίο, τον αντικαθιστά).
// ΕΠΙΣΤΡΕΦΕΙ -1 αν έστω κι ένας από τους χαρακτήρες δεν ήταν ψηφίο, αλλιώς επσιτρέφει
// το πλήθος των χαρακτήρων που εκχωρήθηκαν στο 'digs', εξαιρουμένου του τελικού '\0'
//
int digs_ngets( char *digs, int n )
{
bool digvalid = TRUE;
register char *cp = digs;

while ( digvalid && (*cp=getc(stdin)) != '\n' && (cp-digs) < n-1 )
{
if ( !isdigit( *cp ) )
digvalid = FALSE;
cp++;
}
*cp = '\0';

return digvalid ? cp-digs : -1 ;
}

// ------------------------------------------------------------------------------------
// Διαβάζει το string 's' από το αρχείο 'fp' έως ότου είτε συμπληρωθούν 'len' χαρακτήρες
// είτε βρεθεί αλλαγή γραμμής, είτε βρεθεί EOF. Αν δεν βρεθεί EOF, μηδενίζει τον τελικό
// χαρακτήρα (αν ήταν ENTER το σβήνει).
// ΕΠΙΣΤΡΕΦΕΙ NULL αν βρεθεί EOF, αλλιώς το "διαβασμένο" string 's'
//
char *s_fget(char *s, size_t len, FILE *fp)
{
if ( !fp )
return NULL;

char *cp = s;
for ( ; (*cp=getc(fp)) != '\n' && *cp != EOF && (cp-s) < len-1; cp++ )
; // for-loop with empty body

if ( *cp == EOF) // we've reached end of file
return NULL;

*cp = '\0'; // null-terminate last character

return s;
}

// ------------------------------------------------------------------------------------
// Χρησιμοποιεί τον πίνακα αντιστοίχισης 'map' για να αντιστοιχήσει τους χαρακτήρες
// του string 'word' σε χαρακτήρες ψηφίων, τους οποίους αποθηκεύει στο string 'digs'.
// ΕΠΙΣΤΡΕΦΕΙ το string 'digs' ή NULL σε περίπτωση σφάλματος.
//
char *s_word2digs( char *digs, char *word, int *map )
{
if ( !word || !map )
return NULL;

char *save = digs;
for ( ; *word; word++)
*digs++ = '0' + map[ (unsigned) *word ];
*digs = '\0';

return save;
}

// ------------------------------------------------------------------------------------
// Χρησιμοποιεί τα γράμματα των κουμπιών 'buttons' ως τιμές ευρετηρίου (indices) για
// τον πίνακα αντιστοίχισης 'map', και αποθηκεύει στον 'map'το ψηφίο που αντιστοιχεί
// στο κάθε γράμμα...
// π.χ. map['x'] = map['y'] = map['z] = 0, map['a'] = map['b'] = 1, κλπ.
// Όσοι χαρακτήρες δεν υπάρχουν στα κουμπιά, αρχικοποιούνται με την τιμη -1 (μέσω
// της συνάρτησης memset() ). Ο πίνακας αντιστοίχισης 'map' έχει χώρο για 256
// χαρακτήρες (MAPPED_NCHARS) ώστε να μπορούν να προστεθούν στα κουμπιά και χαρακτήρες
// με ASCII code από 128 έως 255 (όπως για παράδειγμα τα Ελληνικά της κωδικοσελίδας 737)
//
void map_buttons( int *map, char **buttons )
{
register int i;
register char *cp = NULL;

memset( map, -1, MAPPED_NCHARS * sizeof(int) );
for (i=0; i < MAX_BUTTONS; i++ )
for ( cp=buttons[i]; *cp != '\0'; cp++ )
map[ (int)*cp ] = i;

return;
}

// ------------------------------------------------------------------------------------
int main( void )
{
// τα γράμματα των κουμπιών (η θέση των κουμπιών
char *buttons[ MAX_BUTTONS ] = { // στον πίνακα ταυτίζεται με το ψηφίο τους)
"xyzXYZ", "abAB", "cdeCDE", "fgFG", "hijHIJ",
"klKL", "mnoMNO", "pqrPQR", "stST", "uwvUWV"
};
int map[ MAPPED_NCHARS ]; // για την αντιστοίχιση των γραμμάτων σε ψηφία
FILE *fp = NULL; // για το αρχείο 'lejeis.txt'
char word[ MAXLEN_WORD ]=""; // string για το διάβασμα λέξεων από το αρχείο
char digits[ MAXLEN_WORD ]=""; // το string ψηφίων που διαβάζουμε από το χρήστη
char tempdigs[ MAXLEN_WORD ] = ""; // προσωρινό string ψηφίων
int ndigits = 0; // προσωρινή μεταβλητή

fp = fopen("lejeis.txt", "r"); // άνοιγμα του αρχείου
if ( !fp ) { // αποτυχία ανοίγματος
puts("*** error: cannot open file"); // πρόωρος τερματισμός προγράμματος
myexit(1);
}

map_buttons(map, buttons); // γέμισμα του πίνακα αντιστοίχισης

do // εισαγωγή αριθμού από τον χρήστη
{ // (απαιτεί να είναι 7-ψήφιο νούμερο)
printf("Enter a valid 7-digit phone number: ");
fflush( stdin );
ndigits = digs_ngets( digits, MAXLEN_WORD );
} while ( ndigits == -1 || ndigits != MAXLEN_WORD-1 );

/*
* Διάβασμα των λέξων από το αρχείο 'lejeis.txt'.
* Η κάθε λέξη μετατρέπεται προσωρινά σε νέο string από ψηφία (tempdigs), τα οποία
* ψηφία αντιστοιχούν στα γράμματα της αυθεντικής λέξης. Κατόπιν, το προσωρινό
* string συγκρίνεται με το string ψηφίων που εισήαγαγε ο χρήστης (digits),
* κι αν ταιριάζουν τότε τυπώνεται η αυθεντική λέξη (word) στην οθόνη.
*/

bool dummy = FALSE;
while ( s_fget(word, MAXLEN_WORD, fp) ) // διάβασμα λέξης από αρχείο
{
s_word2digs(tempdigs, word, map); // μετατροπή της λέξης σε string ψηφίων

if ( !strcmp(digits, tempdigs) ) { // σύγκριση με τα ψηφία του χρήστη
puts(word);
dummy = (dummy || TRUE);
}
}

fclose( fp ); // κλείσιμο του αρχείου

if ( !dummy )
puts("No matching words found inside the file");

myexit(0);
}



ΕΝΔΕΙΚΤΙΚΟ ΑΡΧΕΙΟ: lejeis.txt
(ΔΟΚΙΜΑΣΤΕ ΚΙ ΑΛΛΕΣ ΛΕΞΕΙΣ, ΑΥΤΕΣ ΕΙΝΑΙ ΑΝΕΠΑΡΚΕΙΣ ΓΙΑ ΟΛΕΣ ΤΙΣ ΠΙΘΑΝΕΣ ΠΕΡΙΠΤΩΣΕΙΣ)

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


BIOLOGY
KICKASS
PLAYERS
HIDEFTV
WELCOME
DRIVERS
MUSICAL
LEONARD
ROOMIES
FALLING



[linuxs]

Σε συγχαίρω για την απάντηση. Πραγματικά, πιο αναλυτικα δεν θα μπορούσε να είναι.

[migf1]

Σε ευχαριστώ φίλε linuxs, πραγματικά είναι χαρά μου να βοηθάω όπου ξέρω και μπορώ.

ΥΓ. Είχα κι ένα λάθος στον κώδικα και το διόρθωσα, τα ASCII characters είναι 256 κι όχι 255 που τα είχα πριν.

[linuxs]

Χαίρομαι να υπάρχουν τέτοια άτομα.. Συνέχισέ το όσο μπορείς...

[andreask16]

Γεια σας,

Είμαι αρχάριος στη γλώσσα C και θα ήθελα να ρωτήσω για κάτι που παρατήρησα.

Είδα ότι γίνεται πιο πάνω να απαιτήσεις ο αριθμός να είναι 7ψήφιος.

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

Μπορεί κάποιος να με βοηθήσει;

Ευχαριστώ!

[linuxs]

Καλησπέρα,

αρχικά θα σου πω πως μπορείς να το κάνεις αυτό με ψευδογλώσσα αν θέλεις να προχωρήσεις σε κάποια γλώσσα(πχ. C) πες μου να σου δώσω κώδικα... Επίσης αν θέλεις να προσπαθήσεις να γράψεις κώδικα δοκίμασε το να δείς τι μπορείς να κάνεις. Λοιπόν,

μια πιθανή λύση είναι να έχεις ένα while loop και να διαβάζεις συνεχώς αριθμούς. Μέσα στο llop εξετάζεις αν ο αριθμός είναι < η > απο το 6 τότε θα βγάζεις μήνυμα σφάλαματος χρησιμοποιώντας την if και ως εντολές στο block θα ξαναδιαβάζεις αριθμό. Δηλαδή,

σε C υλοποιείται κάπως έτσι...

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

main() {
int number;
scanf(number);
while(number<6 || number>6) {
printf(error);
scanf(number);
}
return 0;
}

προσπάθησα να το κάνω σχετικά απλό. Υπάρχουν και άλλοι τρόποι υλοποίησης

[migf1]

Γεια σας,

Είμαι αρχάριος στη γλώσσα C και θα ήθελα να ρωτήσω για κάτι που παρατήρησα.

Είδα ότι γίνεται πιο πάνω να απαιτήσεις ο αριθμός να είναι 7ψήφιος.

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

Μπορεί κάποιος να με βοηθήσει;

Ευχαριστώ!

Οι 6ψήφιοι θετικοί αριθμοί αρχίζουν με τον 100000 και τελειώνουν στον 999999 (υποθέτω μιλάμε για θετικούς), οπότε ο έλεγχος που χρειάζεσαι είναι αν ο αριθμός που διαβάζεις βρίσκεται ή όχι μέσα σε αυτό το εύρος τιμών (θα πρέπει να χρησιμοποιήσεις τους τελεστές σύζευξης ή διάζευξης, δηλαδή && ή ||).

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

Ένα ακόμα σημείο που πρέπει να προσέξεις είναι ο τύπος της μεταβλητής στην οποία θα διαβάζεται ο αριθμός σου. Για να είναι συμβατός ο κώδικάς σου δεν μπορείς να χρησιμοποιήσεις τον τύπο int, διότι το στάνταρ ορίζει πως πρέπει να μπορεί να απεικονίσει τουλάχιστον ότι χωράει σε 16bits (-32767 έως 32767 signed, 0 έως 65535 unsigned) που σημαίνει πως είναι απόλυτα θεμιτό για έναν compiler να μην απεικονίζει μεγαλύτερους αριθμούς από αυτές τις τιμές σε μεταβλητές τύπου int.