C --> Πόσες φορές εμφανίζεται ένας χαρακτήρας

Penthesilea · 14 Σεπτεμβρίου 2011

Εν όψει εξεταστικής θέλω να λύσω κάποιες απορίες μου, για να πάω να δώσω προγραμματισμό.

Στο 1ο εξάμηνο ο καθηγητής είχε βάλει μία άσκηση, η οποία έλεγε:

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

Πολύ πιθανό να ξαναβάλει τέτοια άσκηση, οπότε αν μπορεί και ξέρει κάποιος ας με βοηθήσει.

ChRis6 · 14 Σεπτεμβρίου 2011

Για το πληθος των χαρακτηρων μπορεις να καλεσεις την strlen() . Αν δεν επιτρεπεται να χρησιμοποιησεις τετοιες συναρτησεις , αυτο που κανεις ειναι να κοιτας εναν εναν τους χαρακτηρες του string αυξανοντας καθε φορα ενα counter.

Για το πληθος των αριθμων που εμφανιζονται στο string : Κανεις ενα πινακα απο int με 9 θεσεις και τον αρχικοποιεις σε μηδεν. Παιρνοντας καθε χαρακτηρα απο string , απλα αυξανεις τη τιμη του πινακα κατα ενα με βαση το χαρακτηρα του string.Δηλαδη :

>
char* string;
int numbers[9] ;
/* arxikopoihsh se mhden */

for ( i = 0  ; i <= strlen(string ) ; i++ ){
numbers[ string[i] ]++ ;
}

parsifal · 14 Σεπτεμβρίου 2011

>
char* string;
int numbers[9] ;
/* arxikopoihsh se mhden */

for ( i = 0  ; i <= strlen(string ) ; i++ ){
       numbers[ string[i] ]++ ;
}

Αντιπροτείνω!

>
char *p, string[] = "0369345608754609806970110978654";    /* ενδεικτικά */
int histogram[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for(p = string; p[0] != '\0'; p++)
   histogram[p[0] - '0']++;

migf1 · 14 Σεπτεμβρίου 2011

Αντιπροτείνω!

>
char *p, string[] = "0369345608754609806970110978654";    /* ενδεικτικά */
int histogram[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for(p = string; p[0] != '\0'; p++)
   histogram[p[0] - '0']++;

Εννοείται πως αυτή είναι η προτιμότερη υλοποίηση, μιας και αποφεύγει συνεχείς κλήσεις στην strlen() <-- αργεί

Μια ακόμα υλοποίηση που κρατάει και το μήκος είναι η εξής...

>
char str[] = "0369345608754609806970110978654", *cp = str;
unsigned short freq[10] = { 0 }, len = 0;

for (; *cp; cp++,len++)
   freq[ (int)(*cp -'0') ]++;

ChRis6 · 15 Σεπτεμβρίου 2011

@parsifal Ειπα να μην παιξω με τους δεικτες !

@migf1 μου αρεσει πολυ ο τροπος που σκεφτεσαι

parsifal · 15 Σεπτεμβρίου 2011

@parsifal Ειπα να μην παιξω με τους δεικτες !

Το πρόβλημα δεν ήταν τόσο οι δείκτες όσο

1. Το inefficiency των επανειλημμένων κλήσεων της strlen, όπως ανέφερε ο φίλος migf1. Αν και σε εκπαιδευτικό περιβάλλον όπως είναι η περίπτωση του OP, αυτό συνήθως παραβλέπεται

2. Το μέγεθος του πίνακα συχνοτήτων/ιστόγραμμα: ο πληθάριθμος του συνόλου {0, 1, ..., 9} είναι 10, όχι 9!

3. Ο τρόπος που έκανες το indexing μέσα στον βρόχο οδηγεί σε σίγουρο segfault: Η τιμή ASCII του χαρακτήρα π.χ. '0' δε συμπίπτει με την τιμή που έχει ερμηνευόμενος ως αριθμός (δηλαδή 0), αλλά είναι πολύ μεγαλύτερη. Όταν ο πίνακάς σου έχει 9 (πιο σωστά, 10) θέσεις και πας να προσπελάσεις για εγγραφή το στοιχείο π.χ. numbers[65], τότε γίνεται «μπουμ»!

Timonkaipumpa · 15 Σεπτεμβρίου 2011

@oenthesilea

Πότε δίνεις προγραμματισμό, εάν επιτρέπεται;

defacer · 15 Σεπτεμβρίου 2011

>
char* string;
int numbers[9] ;
/* arxikopoihsh se mhden */

for ( i = 0  ; i <= strlen(string ) ; i++ ){
numbers[ string[i] ]++ ;              /// BUG
}

Αυτό δεν πρόκειται να δουλέψει γιατί θα έπρεπε να είναι string - '0' όπως σωστά έχουν οι υπόλοιπες λύσεις και όπως ο parsifal λέει παραπάνω.

Αντιπροτείνω!

>
char *p, string[] = "0369345608754609806970110978654";    /* ενδεικτικά */
int histogram[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

for(p = string; p[0] != '\0'; p++)
   histogram[p[0] - '0']++;

Η προτιμότερη λύση όπως το βλέπω -- μόνο που θα την έκανα λίγο διαφορετικά:

>
for(p = string; *p; p++)
   histogram[*p - '0']++;

Επίσης -- δεν το ανέφερε κανείς, και δεν το ζητάει η άσκηση, αλλά το θεωρώ εγκληματικό να γράφονται συναρτήσεις οι οποίες αν πάρουν input διαφορετικό απ' αυτό που περιμένουν θα κάνουν το πρόγραμμα crash and burn -- άσχετα από τι λέει η εκφώνηση. Οπότε:

>
for(p = string; *p; p++) {
   if(*p >= '0' && *p <= '9') {
       histogram[*p - '0']++;
   }
}

Penthesilea · 15 Σεπτεμβρίου 2011

Να 'στε καλά, παιδιά!!

@timonkaipumpa

Αύριο δίνω. Ο Θεός κι η ψυχή μου.

migf1 · 15 Σεπτεμβρίου 2011

...

Η προτιμότερη λύση όπως το βλέπω -- μόνο που θα την έκανα λίγο διαφορετικά:
>
for(p = string; *p; p++)
   histogram[*p - '0']++;

αυτό όμως δεν κρατάει κάπου το μήκος του string (η εκφώνηση το ζητάει)

Επίσης -- δεν το ανέφερε κανείς, και δεν το ζητάει η άσκηση, αλλά το θεωρώ εγκληματικό να γράφονται συναρτήσεις οι οποίες αν πάρουν input διαφορετικό απ' αυτό που περιμένουν θα κάνουν το πρόγραμμα crash and burn -- άσχετα από τι λέει η εκφώνηση. Οπότε:
>
for(p = string; *p; p++) {
   if(*p >= '0' && *p <= '9') {
       histogram[*p - '0']++;
   }
}

Κοίτα, καταρχήν η άσκηση αναφέρει ρητώς ως δεδομένο πως το string περιέχει μόνο ψηφία. Έπειτα, οι υλοποιήσεις που δώσαμε, συνειδητά δεν ήταν συναρτήσεις (τουλάχιστον σε ότι αφορά εμένα) μιας και η εκφώνηση δεν ζητάει συνάρτηση επί τούτου. Αν ήταν να το κάνουμε με συνάρτηση, τότε έχουμε πολλά περισσότερα να σκεφτούμε και να ελέγξουμε εκτός του isdigit(). Π.χ. ο πίνακας freq[] θα είναι καθολικός ή θα περνάει σαν όρισμα στη συνάρτηση; Ακόμα, τι γίνεται αν το string περαστεί ως NULL; Επίσης, αν το κάνουμε συνάρτηση, δεν χρειαζόμαστε καθόλου τον δείκτη p.

Με όλα τα παραπάνω (και μερικά ακόμα) μια πιθανή υλοποίηση με συναρτήσεις ενός ολοκληρωμένου, full-proof, προγράμματος είναι η εξής:

>
#include <stdio.h>                                      /* printf(), fputs()                */
#include <stdlib.h>                                     /* exit()                           */
#include <ctype.h>                                      /* isdigit()                        */
#include <string.h>                                     /* memset()                         */

#define FREQ_MAXLEN   10                                /* max length for frequency table   */
#define STR_MAXLEN    (100+1)                           /* max length for string = sizeof   */

/* ---------------------------------------------------------------------------------------- */
int analyze( const char *str, unsigned short int freq[], const int freqmaxlen )
{
   register int len = 0;

   if ( !str || !freq || freqmaxlen < 0 || freqmaxlen > FREQ_MAXLEN )    /* sanity checks  */
       return 0;                                                         /* ... early exit */

   if ( freqmaxlen < FREQ_MAXLEN )                                       /* sanity check   */
       return 0;                                                         /* ... early exit */

   memset(freq, 0, freqmaxlen * sizeof(unsigned short int) );

   for (len=0; *str; str++,len++)
       if ( isdigit( *str ) )
           freq[ (int)(*str - '0') ]++;

   return len;
}
/* ---------------------------------------------------------------------------------------- */
int print_freqs( const unsigned short freq[], const int freqmaxlen )
{
   register int i = 0;

   if ( !freq || freqmaxlen < 0 || freqmaxlen > FREQ_MAXLEN )            /* sanity checks  */
       return 0;            /* FALSE */                                  /* ... early exit */

   if ( freqmaxlen < FREQ_MAXLEN )                                       /* sanity check   */
       return 0;                                                         /* ... early exit */

   for (i=0; i < freqmaxlen; i++)
       printf("digit %d found %u times\n", i, freq[i] );

   return 1;                /* TRUE  */
}
/* ---------------------------------------------------------------------------------------- */
int main( void )
{
   char str[ STR_MAXLEN ] = {0};                                 /* initialized definition */
   unsigned short int freq[ FREQ_MAXLEN ] = {0};                 /* initialized definition */

   /* ask for the string str here */
   ...

   printf("\"%s\" contains %d digits\n", str, analyze(str, freq, FREQ_MAXLEN) );
   if ( !print_freqs( freq, FREQ_MAXLEN ) )
         fputs("*** error, check the params of the function: print_freqs(\n)", stderr);

   exit( EXIT_SUCCESS );
}

ΥΓ1. Πιθανώς να περιέχει bugs, δεν το έχω τεστάρει (το 'γραψα απευθείας εδώ).

ΥΓ2. Καλή επιτυχία στον ts!

παπι · 15 Σεπτεμβρίου 2011

@mig too much. Ανεβαζεις την πολυπλοκοτητα χωρις λογο, με αποτελεσμα να κανεις λογικα λαθη

πχ Κανεις ελεγχο αν το freq ειναι <0 kai >10 αλλα στη πραξη η συναρτηση δουλευει μονο οταν το freq ειναι 10 (αν ειναι 6 τοτε παμε για stackoverflow)

migf1 · 15 Σεπτεμβρίου 2011

@mig too much. Ανεβαζεις την πολυπλοκοτητα χωρις λογο, με αποτελεσμα να κανεις λογικα λαθη

πχ Κανεις ελεγχο αν το freq ειναι <0 kai >10 αλλα στη πραξη η συναρτηση δουλευει μονο οταν το freq ειναι 10 (αν ειναι 6 τοτε παμε για stackoverflow)

Στη πράξη αν δεν έχεις αυτούς τους ελέγχους μέσα στη συνάρτηση και την καλέσεις π.χ με freqmaxlen 20 χειρόγραφο, τότε πας για buffer-overflow. Ενώ τώρα είτε 200 του περάσεις χειρόγραφα ως freqmaxlen είτε -200 δεν κρασάρει το πρόγραμμα. Γενικώς δεν κρασάρει οτι και να κάνεις (ελπίζω δηλαδή, γιατί δεν το χω ψάξει κι ενδελεχώς)

Βασικά το έγραψα όσο πιο full-proof μπορούσα, ως προέκταση των όσων είπε ο defacer.

ΥΓ. Γιατί κάνει stack overflow αν του περάσεις 6; Δεν βλέπω τον λόγο (δεν ελέγχω για ΚΑΙ, για Η ελέγχω)!

Penthesilea · 15 Σεπτεμβρίου 2011

Μπερδεύτηκε πολύ το πράγμα. 1ο εξάμηνο είναι το μάθημα... δεν υπάρχει μια πιο απλή λύση στο πρόβλημά μου;

παπι · 15 Σεπτεμβρίου 2011

ΥΓ. Γιατί κάνει stack overflow αν του περάσεις 6; Δεν βλέπω τον λόγο (δεν ελέγχω για ΚΑΙ, για Η ελέγχω)!

...

migf1 · 15 Σεπτεμβρίου 2011

Ε, αυτό είναι άλλο πράγμα! Εκεί αλλάζεις τον ορισμό του πίνακα, εγώ μιλούσα για invalid παράμετρο, όχι για invalid ορισμό του freq.

Πάντως, κι αυτό λύνεται, πρόσθεσε ένα ακόμα sanity check κάτω από τα υπάρχοντα, στις 2 συναρτήσεις...

>
if ( freqmaxlen < FREQ_MAXLEN )			/* sanity check   */
	return 0;				/* ... early exit */

ΥΓ1. Πάω να το βάλω και στον προηγούμενο κώδικα

ΥΓ2. Το έβαλα! Τώρα επιστρέφει άμεσα σφάλμα, αλλά αν θέλουμε μπορούμε στο 2ο αυτό sanity check να βάζουμε το freqmaxlen να παίρνει την ελάχιστη τιμή μεταξύ του εαυτού του και του FREQ_MAXLEN.

ΥΓ3. @ts: οι απλές λύσεις είναι στην 1η σελίδα

Σύνδεση

C --> Πόσες φορές εμφανίζεται ένας χαρακτήρας

Προτεινόμενες αναρτήσεις

Penthesilea

ChRis6

parsifal

migf1

ChRis6

parsifal

Timonkaipumpa

defacer

Penthesilea

migf1

παπι

migf1

Penthesilea

παπι

migf1

Αρχειοθετημένο

Σύνδεση