Esercizio C

[zavo91]

ho questo esercizio che dice:
Scrivere una funzione f che, ricevuti due interi b e n, restituisca la cifra più significativa di n,quando questo è rappresentato in base b.E' richiesto di scrivere la funzione in al massimo 4 righe.Ogni riga può contenere una sola istruzione,dichiarazione,o intestazione di ciclo.
esempio
f(321,10) ritorna 3 perchè 3 è la cifra più significativa di 321 in base 10
f(27,3) rritorna 1 perchè 27 in base 3 è 1000 e 1 è la cifra più significativa

io ho trovato un modo per trasformare un numero n in base b ma poi non so come fare per salvare il resto al contrario e andare a vedere la cifra più significaiva del resto.

int f(int n, int b)
{
	int r=0;
 	int i;
	for(i=0;i<n;i++)
   	{
		n/=b;
		r=n%b;
	}
	return r;
}

però già questo altro che 4 righe che mi servono poi

[claudio862]

Credo sia possibile in 3 linee.

Il trucco è capire come funziona la notazione posizionale. Se tu scrivi un numero in base 10 scrivi una lista ordinata di cifre comprese tra 0 e 9. In base n scrivi una lista ordinata di cifre in comprese tra 0 e n-1. Dividendo il numero per n (troncando i decimali) stai "scartando" la cifra meno significativa. Quello che vuoi fare tu è scartare tutte le cifre meno significative, quella che rimane sarà la cifra più significativa:

Esempio:
4268 (in base 10)
Divido per 10
426
Divido per 10
42
Divido per 10
4
Ok, ho finito.

27 (in base 3 = 1000)
Divido per 3
9
Divido per 3
3
Divido per 3
1
Ok, ho finito.

Devi solo capire quando smettere di fare divisioni (anche se in realtà te l'ho già detto).

[apatriarca]

"claudio86":Credo sia possibile in 3 linee.

Secondo me ne bastano due (utilizzando il tuo stesso metodo immagino.. ).

[vict85]

Questo è un po' come barare però:

int f(int n, int b)
{
  return (n<b)? n : f(n/b, b);
}

Non sono sicuro che l'operatore ternario varrebbe uno però

Questo era solo per giocare: al professore probabilmente non piacerebbe (sempre che sappia cos'è l'operatore ternario ). Inoltre probabilmente la versione con il ciclo sarebbe leggermente più veloce in c++. Se lo sai leggere è un piccolo hint sul metodo proposto da claudio.

Devo comunque dire che trovo abbastanza discutibile la mancata presenza di qualche test per il segno su una funzione di questo tipo. Infatti sarebbe stato più sensato se la funzione lavorasse su unsigned (io lavoro nel 99,999999% dei casi con unsigned a dire il vero) oppure che ci fosse qualche test che dicesse con chiarezza il comportamento con numeri negativi. Manca volendo anche un test per lo 0 di b.

[claudio862]

Non funziona nemmeno con b = 1 (dove comunque il risultato è banale). Diciamo che base 1 e base 0 sono abbastanza insolite da poter essere ignorate salvo esplicita richiesta (non saprei nemmeno se base 0 abbia un significato).
La consegna lascia intendere di implementarlo in modo iterativo, però in effetti è molto più elegante ricorsivo (anche se a me l'operatore ternario non piace).

[vict85]

Hai ragione, con b=1 hai un ciclo infinito.

[zavo91]

ottime spiegazioni ma non mi avete illuminato sul fatto di dire quale cifra, dopo aver cambiato di base il numero n in base b, è la più significativa cioè per esempio 27 in base 3 è 1000 come faccio io a dire che 1 è la più significativa dovrei controllare tutti i resti delle divisioni o sbaglio?

[claudio862]

Non è necessario fare il cambiamento di base. Guarda il procedimento che ho descritto prima per il numero 27 in base 3. Devi controllare solo il risultato (non il resto) dell'ultima divisione, quella è la cifra più significativa.

[zavo91]

allora mi sfugge un motivo del perchè l'ultima cifra del numero n è la più significativa....anche perchè il resto è quello che dice il numero nella diversa base perchè dovrei guardare solo il risultato e non il resto?
io devo trovare la cifra più significativa dopo aver cambiato il numero n in base b.

[vict85]

Prendi per esempio $9$ in base $7$

$9/7 = 1$, il resto è $2$.

Avremo che $9 = 1\cdot 7^1 + 2\cdot 7^0$.

Se tu hai bisogno solo della cifra più significativa allora quello che devi far tornare è 1.

[zavo91]

"vict85":Prendi per esempio $9$ in base $7$

$9/7 = 1$, il resto è $2$.

Avremo che $9 = 1\cdot 7^1 + 2\cdot 7^0$.

Se tu hai bisogno solo della cifra più significativa allora quello che devi far tornare è 1.

si però non ho capito perchè devo guardare il risultato e non il resto...a me hanno insegnato che per un cambio di base si guarda il resto e si moltiplica per la base elevata alle potenze 0,1,2,ecc

[claudio862]

Perché la prima divisione toglie la cifra delle unità, la seconda toglie quella delle "decine", la terza quella delle "centinaia"... Fino a che l'ultima divisione ha tolto tutte le cifre tranne quella più a sinistra, che è la più significativa. Ovviamente le parole "decine" e "centinaia" sono corrette solo in base 10, in base b si potrebbe usare "multipli di b", "multipli di b²".

[zavo91]

i però non ho capito perchè devo guardare il risultato e non il resto...a me hanno insegnato che per un cambio di base si guarda il resto e si moltiplica per la base elevata alle potenze 0,1,2,ecc

comunque non ho capito come potrei farlo in C
ok dovrò fare un ciclo

for(i=0;i<?????che cosa;i++)
n=n/b;
return n;

può andare per voi?

[apatriarca]

Perché l'ultima cifra è l'unica che puoi estrarre senza dover calcolare un resto. Quelle precedenti le devi infatti totalmente ignorare e l'ultima deve per forza già essere compresa tra $0$ e $b$ (se no non sarebbe la cifra più significativa).

[zavo91]

come lo dovrei fare il ciclo in 4 righe modificando quello che ho messo io poco fa?

[vict85]

Metto unsigned int e tutti i test del caso:

unsigned int f(unsigned int n, unsigned int b)
{
  if(b>1)
    for(; n > b; n /= b);
  return n;
}

nel caso ci sia b=1 o 0 allora ritornerà direttamente n, non è corretto ma tanto si tratta di un errore chiamare quella funzione con quei valori. Il for non deve necessariamente funzionare con un indice, tanto meno questo indice deve proseguire in modo così costante come nel caso comunemente usato. Inoltre il mio for non ha un "corpo".

Siccome però ci sono puritani a cui non piace l'uso del for di questo tipo si può usare un while:

unsigned int f(unsigned int n, unsigned int b)
{
  if(b>1)
  { 
    while(n > b) 
    {
      n/=b;
    }
  }
  return n;
} 

le parentesi non sono strettamente necessarie, ma ne aumentano la leggibilità.

Hai qualche dubbio?

[claudio862]

La condizione del while deve essere n >= b, con l'uguale. Altrimenti se n = b uscirebbe dal ciclo e restituirebbe n = b, che non è una cifra (es. in base 10, b = 10, e 10 non è una cifra).

Io sono un puritano, principalmente perché l'uso idiomatico del for è proprio ciclare su una sequenza in modo regolare (un po' come $\forall$), quindi confonde le idee a chi legge il codice. Comunque quando in un ciclo non c'è il corpo è meglio esplicitarlo, altrimenti si rischia ancora di sbagliare leggendo il codice:

unsigned int f(unsigned int n, unsigned int b)
{
  if(b>1)
    for(; n >= b; n /= b)
      ;
  return n;
}

La mia versione sarebbe:

int f(int n, int b)
{
    if (b <= 1) {
        return b;
    }
    while (n >= b) {
        n /= b;
    }
    return n;
}

(con il vincolo che n > 0 nella documentazione )

P.S.
Per b = 1 il risultato è proprio 1 (è l'unica cifra esistente, quindi la cifra più significativa è necessariamente 1).

[zavo91]

"vict85":Metto unsigned int e tutti i test del caso:

unsigned int f(unsigned int n, unsigned int b)
{
  if(b>1)
    for(; n > b; n /= b);
  return n;
}

Hai qualche dubbio?

si sul ciclo for che io non ho mai visto in questo modo ma solo usando il classico indice i=0 fino ad una condizione finale e poi il suo incremento...questo ciclo che hai scritto te nel caso dovessi ritrovarlo cosa significa che vedo che non ha neanche una condizione iniziale?

[vict85]

Il for prende 3 "parametri". Il primo gruppo è quello delle inizializzazioni, il secondo delle condizioni di uscita e il terzo quello delle operazioni finali. Di fatto:

for(assegnazione-1; test; operazioni-finali-1, operazioni-finali-2)
{
  corpo-del-for;
}

si traduce in:

assegnazione-1;
while(test)
{
  corpo-del-for;
  operazioni-finali-1;
  operazioni-finali-2;
}

Ho messo volutamente più essegnazioni e operazioni finali perché volevo farti vedere che potevi farne più di una. In genere abusarne crea un po' di confusione. Comunque eccoti un esempio da cerca di tradurre in un while (cerca anche di dire che fa):

unsigned int a = 30;
for(unsigned int i = 10, sum = 0; (sum < 100000)&&(i < 20) ; ++i, sum+=a)
{
  a = sum / i;
}

Ovviamente è un esempio un po' assurdo, è solo per esercizio. Non so neanche io esattamente a cosa possa servire. Cerca solo di capire che operazioni fa e quando.

x claudio: hai ragione ma cercavo di rimanere sotto le 4 righe pur aggiungendo il test . A mio avviso comunque usare gli int è proprio sbagliato, che significato ha una base negativa? Probabilmente una definizione in giro si trova ma direi che richiede una serie di controlli inutili. Sul >= era un errore di disattenzione, l'ho scritto velocemente e neanche provato.

[zavo91]

ok ora mi è più chiaro la questione e invece l'unsigned??? a cosa serve?
ho visto un'altra differenza i++ e ++i cosa cambia?

[claudio862]

L'errore dell'uguale l'avevo fatto pure io, ma me ne sono accorto prima di scrivere sul forum .

@zavo91
I tipi interi in C/C++ si dividono in signed e unsigned, cioè con segno e senza segno. Se non specifichi niente il tipo di default è signed (a parte per char che è un po' più complicato), cioè:

int a; // Con segno, implicito
signed int a; // Con segno, esplicito
unsigned int a; // Senza segno, esplicito

// Uguale con long, signed long, unsigned long
//            short, signed short, unsigned short
//            ...

I tipi con segno usano un bit per memorizzare il segno (positivo o negativo), mentre quelli senza segno no, quindi possono memorizzare solo numeri positivi (il doppio di quelli con segno, poiché hanno un bit in più).
Un'altra differenza è che per i tipi senza segno il comportamento in caso di overflow e underflow è definito:

unsigned int a = numeric_limits<unsigned int>::max();
// 'a' contiene il più alto valore che può contenere.
a += 1;
// Ora 'a' contiene 0, quando sfora in alto "riparte" dal basso (e viceversa)

signed int b = numeric_limits<signed int>::max();
// 'b' contiene il più alto valore che può contenere.
b += 1;
// Ora 'b' può contenere qualsiasi cosa, lo standard dice che in
// questa situazione il comportamento è indefinito.

Questo comportamento in caso di overflow e underflow emula l'aritmetica modulare (qualcuno è addirittura dell'idea che sia l'unico motivo valido per usare tipi senza segno).

@vict85
Ho l'impressione che usare unsigned int sia quasi più sbagliato che usare signed int. Sicuramente con numeri negativi la funzione così com'è non va, quindi ci sono due possibilità:
- documentare che la funzione si aspetta numeri positivi e b > 1;
- controllare che i numeri siano positivi e in caso contrario restituire un errore.
Usare unsigned invece introduce un altro possibile errore:

#include <iostream>

void f(unsigned int a)
{
    std::cout << a << '\n';
}

int main()
{
    signed int a = -9;
    f(a);
}

compilato con g++ -std=c++98 -pedantic -Wall -Wextra, non genera neppure un warning, e sul mio computer stampa 4294967287.
Un comportamento accettabile se tu passassi un valore n < 0 alla funzione sarebbe quello di calcolare la cifra più significativa di -n (cioè 9). Ma in questo caso c'è overflow, -n viene convertito in MAX_UINT - n, e il risultato è la cifra più significativa di MAX_UINT - n (cioè 4), che invece è sicuramente sbagliato.
Usando unsigned non si evitano problemi quando n < 0, anzi si ottiene un risultato valido ma sbagliato.


@zavo91
++i è equivalente a (i = i + 1). Si chiama pre-incremento, significa che prima incrementi il valore di i, poi usi quel valore:

int i = 3;
int a = 4 + ++i;
// i = 4
// a = 0

i++ invece si chiama post-incremento, significa che prima usi il valore di i, dopo lo incrementi:

int i = 3;
int a = 4 + i++;
// i = 4
// a = 1

Il problema grosso con i++ è che non sai quanto dopo viene incrementato il valore di i, quindi è spesso causa di comportamento indefinito:

i = i++;
// Questa istruzione potrebbe essere implementata come:
old = i;
i = old; // Assegnamento
i = i + 1; // Incremento
// L'incremento avviene alla fine dell'istruzione

// Oppure come:
old = i;
i = i + 1; // Incremento
i = old; // Assegnamento
// L'incremento avviene subito dopo aver memorizzato il valore precedente

In C e C++ l'ordine di valutazione degli operandi di un'espressione non è specificato, quindi potresti addirittura avere comportamento diverso all'interno dello stesso programma. Morale: se puoi usa il pre-incremento ++i.