Newsgroup: it.comp.lang.c++
Titolo: Conversione di un numero da stringa a vector<int>

Salve,
vi propongo il seguente problema.
Bisogna scrivere una funzione che prenda come argomenti un intero 
positivo B e una stringa che rappresenta un numero intero positivo in 
base 10. La funzione deve restituire una rappresentazione del numero in 
un vettore di interi, dove ogni elemento del vettore ï¿œ una cifra del 
numero in base B. La cifra piï¿œ significativa sta in cima nel vettore.
Il codice deve essere portabile e non deve assolutamente usare tipi piï¿œ 
grandi di un int. Per le dimensioni di un int si puï¿œ fare riferimento a 
numeric_limits.
Ecco un esempio:
Input:
	stringa = "253"
	B = 127
Output:
	v[0] = 126
	v[1] = 1

Dimenticavo la cosa piï¿œ importante. Il numero ha precisione arbitraria.
Anonymous ha scritto:



Ciao,
in realtï¿œ non ho capito bene se hai un problema o ti stai facendo fare i 
compiti, in ogni caso questa ï¿œ la mia soluzione:
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
main()
{
     unsigned int B = 127, N = 0;
     string s = "253";
     vector<unsigned int> v;
     vector<unsigned int> base2vect(string, unsigned int);
     v = base2vect(s, B);
     if(v.size() > 0)
         for(int i = 0; i < v.size(); i++)
             cout << "v[" << i << "] = " << v[i] << endl;
     else
         cout << endl << "Conversione fallita" << endl;
}
vector<unsigned int> base2vect(string s, unsigned int B)
{
     unsigned int N = 0;
     vector<unsigned int> v;
     istringstream cnv(s);
     if(!(cnv >> dec >> N).fail() && B > 1)
         for(unsigned int c = N; c > 0;)
         {
             v.push_back(c % B);
             c /= B;
         }
     return v;
}

 compiti, in ogni caso questa ï¿œ la mia soluzione:
E' un problema. Verifico la tua soluzione.
Grazie mille.


     if(!(cnv >> dec >> N).fail() && B > 1)
Non va bene. La capacitï¿œ di N puï¿œ essere insufficiente per un intero 
sufficientemente grande rappresentato dalla stringa di caratteri.
Per esempio: con "123132131231232132132132432034909102" la conversione 
fallirebbe dove un int ï¿œ di 32bit.

 fallirebbe dove un int ï¿œ di 32bit.
 >
Ciao,
non avevo proprio capito che la stringa poteva rappresentare un 
qualsiasi intero positivo, anzi, ho scritto la funzione proprio con 
l'intenzione di non ammettere valori superiori al massimo valore di un 
int. Sorry. Se non hai ancora risolto, ci penso ancora.


Ciao,
dato che non hai risposto, ho dato per assunto che tu non abbia ancora 
risolto e ti propongo quest'altra soluzione sperando che funzioni come 
t'aspetti. L'ho scritta di getto e provata poco quindi, probabilmente, 
mancherï¿œ qualche controllo:
vector<unsigned int> base2vect(string s, unsigned int B)
{
	vector<unsigned int> v, r, q;
	unsigned int i, vPos = 0, divD = 0;
	if(B <= 1)
		return r;
	for(i = 0; i < s.length(); i++)
	{
		if(isdigit(s[i]))
			v.push_back(atoi(s.substr(i, 1).c_str()));
	}
	do
	{
		for(i = vPos; i < v.size(); i++)
		{
			divD = (divD * 10) + v[i];
			if(divD >= B)
			{
				q.push_back(divD / B);
				divD %= B;
				vPos = i;
			}
			else
			{
				if(q.size() > 0)
					q.push_back(0);
			}
		}
		v = q;
		q.clear();
		r.push_back(divD % B);
		vPos = divD = 0;
	}
	while(v.size());
	return r;
}

verifico e ti faccio sapere
Grazie intanto
dmaxime ha scritto:


 }
La soluzione mi pare buona. Ci sono però delle cose che non capisco: a
cosa serve "vPos"? perché entri nel ciclo più esterno anche se "v" è
vuoto mettendo in "r" uno 0?
Ciao.

 Ciao.
Ciao,
non mi � chiara la tua seconda domanda, in ogni caso provo a descriverti 
l'algoritmo:
- la prima fase, come � ovvio, � il caricamento del vector, dove, tanto 
per iniziare, bisognerebbe far fallire la funzione se si incontrasse un 
carattere non numerico.
- la seconda ed ultima fase, quella del do-while, � tratta da esercizi 
di conversione di base scolastici. Un esempio lo puoi trovare qui: 
http://matematicamedie.blogspot.com/2007/10/conversione-di-numeri-da-base-10-base.html
- il ciclo for contenuto nel do-while, invece, lo dovresti leggere 
immaginando di fare una divisione con resto a mano su un foglio di 
carta. Quel vPos, in pratica, � il punto in cui partirebbe l'archetto 
che avresti disegnato sul numero prima di "abbassarlo".
Data la difficolt� nel valutare il numero contenuto nella stringa, mi � 
sembrato il modo pi� logico per affrontare il problema. Non sar� una 
scheggia ma al risultato c'arriva ;-)

 scheggia ma al risultato c'arriva ;-)
ben fatto. Ho cambiato solo:
"while (v.size()) {}" in "do { } while (v.size());" (per scelta personale)
e
"vector<unsigned int> base2vect(const string& s [...]"
in
"vector<unsigned int> base2vect(string s [...]"
per evitare la copia dell'argomento (a meno di ottimizzazioni del 
compilatore)

 "while (v.size()) {}" in "do { } while (v.size());" (per scelta personale)
il contrario volevo dire

>>          }
� un po lentina per numeri con un numero di cifre  sopra 10^6 e il 
vettore corrispondente occupa memoria che poi verr� comunque poi 
liberata. se si potesse evitare il ciclo sopra elaborarando direttamente 
i caratteri dalla stringa sarebbe meglio..



...l'uovo, la gallina, la botte piena e la moglie ubriaca?
Sostituendo malloc con new lo rallenterai sensibilmente:
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
using namespace std;
vector<unsigned int> base2vect(const char [], unsigned int);
int main()
{
     char tmp;
     const char s[] = "1505851632739161317";
     unsigned int B = 8;
     vector<unsigned int> v;
     v = base2vect(s, B);
     for(unsigned int i = 0; i < v.size(); i++)
         cout << "v[" << i << "] = " << v[i] << endl;
     return 0;
}
vector<unsigned int> base2vect(const char s[], unsigned int B)
{
     static vector<unsigned int> r;
     struct { unsigned int b : 1; } tgl = {0};
     unsigned int sLen = strlen(s);
     unsigned int i, qPos, vPos = 0, divD = 0;
     char *vq[2];
     vq[0] = (char *)malloc(sLen);
     vq[1] = (char *)malloc(sLen);
     if(B > 1)
         for(i = 0; i < sLen; i++)
             if(isdigit(s[i]))
                 vq[0][i] = s[i] - '0';
     if(i == sLen)
         while(sLen)
         {
             for(i = vPos, qPos = 0; i < sLen; i++)
             {
                 divD = (divD * 10) + vq[tgl.b][i];
                 if(divD >= B)
                 {
                     vq[(tgl.b ^ 1)][qPos++] = divD / B;
                     divD %= B;
                     vPos = i;
                 }
                 else
                     if(qPos > 0)
                         vq[tgl.b ^ 1][qPos++] = 0;
             }
             tgl.b++;
             sLen = qPos;
             r.push_back(divD);
             vPos = divD = 0;
         }
     free(vq[0]);
     free(vq[1]);
     return r;
}

 Sostituendo malloc con new lo rallenterai sensibilmente:
:) provo e ti faccio sapere . grazie

...ops...
     if(B > 1)
         for(i = 0; i < sLen; i++)
             if(isdigit(s[i]))
                 vq[0][i] = s[i] - '0';
va modificata:
     if(B > 1)
         for(i = 0; i < sLen && isdigit(s[i]); i++)


> :) provo e ti faccio sapere . grazie
... sparito!
... gli avrà portato sfiga il nickname?
;-)


No,
semplicemente gli serviva un lavoretto/compiti a casa e te glieli hai fatti ....
(rileggendo dai toni che ha usato) ed ora il gruppo non gli serve più.
:-(
Ciao.


Ho commentato proprio perché lo notassero tutti :-)

softwareEngineer ha scritto:

A molti di quelli che snobbano gli esercizi credendo che non si 
ripresentino nei casi reali, suggerisco di ritornare a scuola, perchè, 
da quello che vedo in giro, qualcuno di esercizi ne ha fatti veramente 
pochi nella sua vita. In ogni caso questo non è un compito.

dmaxime ha scritto:

ci sono.. vi vedo.. vi controllo..
non voglio fare il pignolo, ma si può migliorare.. se proprio devi 
creare  array di char intermedi, sappi che dentro un char ci tu fai 
stare una sola cifra, quando in realtà ci possono stare un numero di 
cifre in base 10 pari a n=std::numeric_limits<char>::digits10, riducendo 
quindi di 1/n gli accessi alla memoria. Ma a questo punto -se proprio 
devo - userei array di unsigned long.
Poi hai visto già visto se malloc() è effettivamente più veloce di
{ std::vector<char> v(0); v.reserve(sLen); } ?

 { std::vector<char> v(0); v.reserve(sLen); } ?
No, ma se ti serve sono disposto a verificarlo; anche con un 
data-analyzer... previo congruo compenso. Come ho gi� detto, mi 
procaccio il cibo con 'ste cose ma se ti pu� essere d'aiuto, posso dirti 
che a parte il metodo di allocazione che si riduce, praticamente sempre, 
a spostare degli indici o chieder spazio al sistema operativo, la new, 
quando si allocano array, perde anche un pochino di tempo a scrivere, 
nei primi campi dell'array allocato, il numero di celle effettivamente 
allocate.
Bene. Ora ti saluto e nell'attesa che tu decida se sia o meno il caso di 
chiedere aiuto ad un consulente pluri-decennale (pagando) per portare a 
termine il tuo "lavoro", mi dedico al mio esercizio yoga preferito: 
distendo la braccia avanti ed immagino di seguire con le mani, sino alla 
vetta, il profilo di una montagna che si specchia in un lago ;-)
PS:
In questo thread ho postato pi� volte soluzioni compilabili perch� mi 
sono vergognato. Mentre mi preparavo a testare la prima soluzione, ho 
cercato in rete dei "banchi" di prova: siti che mettono a disposizione 
convertitori di base. Molti di loro mi hanno restituito dei risultati 
assolutamente errati e mi � stato inevitabile sorriderne. Pensandoci 
bene, per�, di riderci sopra non � proprio il caso perch� quei siti 
sminuiscono la seriet� e la complessit� del Nostro lavoro. Credo che 
nessun informatico di professione potr� contestare quest'affermazione:
Conoscere solo ci� che concerne l'informatica non assicura a nessuno la 
possibilit� di essere sul mercato perch� dobbiamo conoscere anche il 
mestiere dei nostri committenti: un po' di contabilit�, di geometria, 
elettronica, analisi, sistemi, lingue (almeno l'inglese), processi di 
produzione e quant'altro.
Lo chiedo sopratutto a chi accetta di far lavori con contratti infimi o 
addirittura senza. Se non ne avete bisogno per sopravvivere non 
accettateli. Non realizzate nulla per dei tozzi di pane secco!
Mi piacerebbe che i gestori dei siti di cui sopra, sostituissero le loro 
porcate con ci� che ho proposto che � mia propriet� intellettuale e che 
dichiaro FREE, giusto per evitarci ulteriori figuracce. Sono sicuro che 
l'ultima versione della funzione possa essere tradotta in un linguaggio 
qualsiasi e che con minime modifiche sia in grado di convertire numeri 
di base qualsiasi in un'altra base qualsiasi. Spero ne approfittino per 
correggere quegli insulti alla nostra professione. Perdonate lo sfogo.
Tags: conversione base.

 analisi.
solo  vettore di int, non solo int in generale. shift e le operazioni 
fra bit solo molto veloci.. dopo pu� il compilatore ottimizza le 
operazioni aritmetiche con shift.

Sottoscrivo appieno.