ascendente.cpp
// $Id$
/* COMIENZO DE DESCRIPCION
__USE_WIKI__
Escribir una funci\'on
#int ascendente1 (list <int> &L, list<list<int> > &LL)#
que, dada una lista #L#, genera una lista de listas #LL#
de tal forma de que cada sublista es ascendente.
[Tomado en el Parcial 1 20-ABR-2006].
Escribir una funci\'on
#int ascendente2 (list <int> &L, vector < list<int> > &VL)#
que, dada una lista #L#, genera un vector de listas #VL#
de tal forma de que cada sublista es ascendente.
[Tomado en Examen Final 29-JUL-2004].
keywords: lista
FIN DE DESCRIPCION */
/*
En ciertas aplicaciones interesa separar las corridas ascendentes
en una lista de n\'umeros $L=~(~a_1,~a_2,~...,~a_n~)$, donde
cada corrida ascendente es una sublista de n\'umeros consecutivos
$a_i$, $a_{i+1}$, ..., $a_{i+k}$, la cual termina cuando
$a_{i+k}>a_{i+k+1}$, y es ascendente en el sentido de que
$a_i \le a_{i+1} \le ... \le a_{i+k}$. Por ejemplo, si la
lista es L = (0,5,6,9,4,3,9,6,5,5,2,3,7), entonces hay 6
corridas ascendentes, a saber: (0,5,6,9), (4), (3,9), (6),
(5,5) y (2,3,7).
\emph{Consigna:}
usando las operaciones de la clase lista, escribir una funci\'on
{\tt int ascendente (list <int> &L, list < list<int> > &LL)}
en la cual, dada una lista de enteros {\tt L}, almacena
cada corrida ascendente como una sublista en la lista de
listas {\tt LL}, devolviendo adem\'as el n\'umero $z$ de
corridas ascendentes halladas. \emph{Restricciones:}
a) El tiempo de ejecuci\'on del algoritmo debe ser $O(n)$,
b) La lista de listas {\tt LL} inicialmente est\'a vac\'{\i}a,
c) No usar otras estructuras auxiliares.
*/
// -----------------------------------------------------------------
#include <cmath>
#include <list>
#include <iostream>
#include "./util.h"
using namespace std ;
//--------------------------------------------------------------------
double drand_a() {
return double (rand())/double(RAND_MAX);
}
int irand_a(int m) {
return int(double(m)*drand());
}
//--------------------------------------------------------------------
void printa (list<int> & L){
list<int> :: iterator p, z;
cout << endl ;
cout << "lista ; L = " ;
p = L.begin();
while (p != L.end()) {
cout << *p << " " ; p++;
}
cout << endl << "pausa ... " ; cin.get ();
}
//--------------------------------------------------------------------
void printa (list<list<int> > & LL){
list<list<int> > :: iterator q;
list<int> :: iterator p, z;
int n, h ;
n = LL.size () ;
q = LL.begin();
h = 0 ;
while (q != LL.end()) {
p = q -> begin(); // comienzo de la sublista
z = q -> end(); // fin de la sublista
cout << endl ;
cout << "sublista " << h << " ; LL_h = " ;
while (p != z) {cout << *p << " " ; p++;}
cout << endl ;
h++;
q++;
} // end while
cout << endl ;
cout << "siza (LL) ; n = " << n << endl ;
cout << endl << "pausa ... " ; cin.get ();
}
//--------------------------------------------------------------------
void printa (vector<list<int> > & VL){
list<int> :: iterator p, z;
int n ;
n = VL.size () ;
for (int k = 0 ; k < n ; k++) {
cout << "sublista c : " ;
p = VL [k].begin ();
z = VL [k].end ();
while (p != z) cout << *p++ << " " ;
cout << endl ;
} // end k
cout << endl ;
cout << "siza (LL) ; n = " << n << endl ;
cout << endl << "pausa ... " ; cin.get ();
}
//--------------------------------------------------------------------
void genera_a (list<int> &L, int n, int maxval){
list<int> :: iterator p;
int k;
cout << endl ;
cout << "llena aleatoriamente una lista L de enteros" << endl;
p = L.begin ();
for (int j=0 ; j<n ; j++) {
k = irand (maxval); // valor aleatorio en [0,maxval)
p = L.insert (p,k); // inserta en la lista
}
}
//--------------------------------------------------------------------
// Item 1: lista de listas
//
// . los iteradores "p,q" recorren los numeros de la lista "L"
// . el iterador "r" va pasando de sublista en sublista, donde
// cada sublista es una corrida ascendente de la lista "L";
// . la lista vacia A es solo para inicializar cada nueva sublista.
int ascendente1_a (list <int> &L, list < list<int> > &LL) {
list < list<int> > :: iterator r;
list <int> :: iterator p, q;
list <int> A;
p = L.begin ();
while (p != L.end ()) {
// inserta una nueva sublista vacia "A" en la lista de listas "L"
r = LL.insert (LL.end(),A);
// inserta el valor "*p" de la lista "L" en la nueva sublista
r->insert (r->end(), *p) ;
// mientras no sea fin de la lista "L" y se verifica la condicion
// de corrida ascendente, va copiando a la sublista actual
q = p ; q++;
while (q != L.end () && *p <= *q) {
r->insert (r->end(), *q) ;
p++;
q++;
} // end while
p = q ; // se posiciona al principio de la sgte corrida
} // end while
printa (LL) ;
return LL.size() ;
}
//--------------------------------------------------------------------
// Item 1: lista de listas
// Otra solucion
int ascendente1_b (list<int> &L, list<list<int> > &LL) {
list<int>::iterator p, q;
list<list<int> >::iterator ql ;
int x ;
LL.clear();
p = L.begin ();
while (p != L.end ()) {
ql = LL.insert(LL.end(),list<int>());
while (1) {
x = *p++;
ql->insert(ql->end(),x);
if (p==L.end() || *p<x) break;
} // end while
} // end while
return LL.size();
}
//--------------------------------------------------------------------
// Item 2: vector de listas
//
// el iterador "p" recorre la lista "L"
// el iterador "q" recorre cada corrida ascendente en "L"
// el contador "h" va contando las corridas ascendentes halladas
int ascendente2 (list <int> &L, vector < list<int> > &VL) {
list <int> :: iterator p, q;
int h = 0 ;
p = L.begin ();
while (p != L.end ()) {
// copia el elemento "p" de "L" como el primero de la sublista "h"
VL [h].insert (VL [h].end (), *p) ;
// mientras no sea fin de lista y se verifica la condicion de
// corrida ascendente, va copiando elementos a la sublista "h"
q = p ; q++;
while (q != L.end () && *p <= *q) {
VL [h].insert (VL [h].end (), *q) ;
p++;
q++;
} // end while
h++ ; // para pasar a la eventual siguiente corrida ascendente
p = q ; // se posiciona al principio de la sgte corrida
} // end while
return (h) ;
}
//--------------------------------------------------------------------
void check(list<int> &L) {
list<list<int> > LL;
int nca = ascendente1_b (L,LL);
list<list<int> >::iterator ql = LL.begin();
while (ql!=LL.end()) {
cout << "sublista ascendente: ";
list<int>::iterator p = ql->begin();
while (p!=ql->end()) {
cout << " " << *p;
p++;
}
ql++;
cout << endl;
}
}
//--------------------------------------------------------------------
int main() {
list <int> L ;
list <list<int> > LL ;
int a [] = {3,7,0,0,3,4,6,4,2,7,-1};
int opcion = 2 ;
int h, n ;
// Titulos
cout << endl;
cout << "encuentra todas las Corridas Ascendentes (CA) " << endl ;
cout << "en una lista de numeros L " << endl;
int kaso = 1 ;
switch (kaso) {
case 1:
// Item 1: lista de listas "LL"
L.clear ();
genera_a (L, 50, 99) ; // Genera una lista "L" de numeros
printa (L);
h = ascendente1_a (L,LL) ; // una solucion
check (L); // otra solucion
break;
case 2:
// Item 2: vector de listas "VL"
if (opcion == 1) {
L.clear ();
insertl (L, a, -1) ; // Construye una lista predefinida
printa (L);
n = L.size () ; // alocamos para el peor caso: si las
vector <list<int> > VL (n); // sublistas resultaran de longitud 1
h = ascendente2 (L,VL) ;
printa (VL) ;
VL.clear ();
} else {
int const kmax = 20 ;
for (int k = 0; k < kmax ; k++) {
L.clear ();
randl (L,10,5.0);
printa (L);
n = L.size () ;
vector <list<int> > VL (n) ;
h = ascendente2 (L,VL) ;
printa (VL) ;
VL.clear () ;
} // end k
} // end if
break;
default:
cout << endl;
cout << "no previsto " << endl ;
} ;
cout << endl;
return 0;
}
// -----------------------------------------------------------------
Generated by GNU Enscript 1.6.6.