|
1
|
Programación / Programación C/C++ / Re: Pila en C++
|
en: 6 Noviembre 2022, 00:15 am
|
Pfff... Hay muchos errores. Es posible que entre tanto código pierdas la perspectiva. - Separa la interacción (cin, cout) de la implementación de la pila
- No uses variables globales. Tiene un pase que quieras hacer una pila "singleton", o sea, que no puedas más que declarar una valor de pila (p_pila), pero nunca la variable auxiliar. Si no, corres el riesgo de asumir valores que en realidad no tiene
Siguiendo un poco "tu voz", esto es lo que he enmendado. #include <iostream> #include <stdlib.h> using namespace std; typedef struct pila { int elemento; pila* enlace; } pila_t, *pila_tp; void push(const int n); int pop(); int empty(); void display(); void liberar(); static pila* p_pila = NULL; int main() { int opcion; cout << "Pila de tipo dinamica" << endl; cout << "\tMenu\n"; cout << "1)Insertar nuevo elemento a la pila" << endl; cout << "2)Sacar elemento de la pila" << endl; cout << "3)Mostrar los elementos de la pila" << endl; cout << "4)Liberar memoria" << endl; cout << "5)Salir\n\n"; do { cout << "Escoga un opcion: " ; cin >> opcion; switch (opcion) { case 1: int n; cout << "Numero a insertar "; cin >> n; push(n); break; case 2: if (!empty()) cout << pop() << endl; else cout << "Pila vacia" << endl ; break; case 3: display(); break; case 4: liberar(); break; case 5: cout << "Saliendo del programa"; break; default: cout << "Opcion no valida"; } } while (opcion != 5); return 0; } int empty() { return p_pila == NULL; } void push(const int n) { pila_tp p_aux = new pila; p_aux->elemento=n; p_aux->enlace = p_pila; p_pila = p_aux; } int pop() { /* Take control of p_aux!*/ const int n = p_pila->elemento; pila_tp p_aux = p_pila; p_pila = p_aux->enlace; delete p_aux; return n; } /* I/O operation */ void display() { pila_tp p_aux = p_pila; while (p_aux != NULL) { cout << "\t" << p_aux->elemento << endl; p_aux = p_aux->enlace; } } void liberar() { pila_tp p_aux = p_pila; while (p_aux!= NULL) { const pila_tp p_next = p_aux->enlace; delete p_aux; p_aux = p_next; } p_pila = NULL; }
Resultado Pila de tipo dinamica Menu 1)Insertar nuevo elemento a la pila 2)Sacar elemento de la pila 3)Mostrar los elementos de la pila 4)Liberar memoria 5)Salir
Escoga un opcion: 1 Numero a insertar 10 Escoga un opcion: 1 Numero a insertar 13 Escoga un opcion: 3 13 10 Escoga un opcion: 1 Numero a insertar 256 Escoga un opcion: 3 256 13 10 Escoga un opcion: 2 256 Escoga un opcion: 3 13 10 Escoga un opcion:
|
|
|
2
|
Programación / Programación C/C++ / Re: Mostrar el mayor valor de una pila
|
en: 12 Agosto 2022, 17:02 pm
|
A ver, aprecio dos errores en tu programa. En primer lugar, propiamente no estás implementando una pila. Es cierto que parece que la simulas con un vector y un indice al ultimo elemento ( por cierto, es más natural marcar cuantos elementos tiene la pila), pero no das ninguna rutina de abstracción y el programador puede acceder al tipo emulador (vector e indice) con total libertad. Queda a tu elección el rigor con que lo quieras tratar. En el mundo Python por ejemplo, ya nadie implementaria un tipo para pila, todo el mundo usa las listas directamente, como tu sugieres. Si escoges la implementación hecha en la librer'ia estadard, esta es tu rutina. #include <stack> #include <iostream> #include <cassert> #include <algorithm> // using max function. int compute_max(const std::stack<int> &s) { assert(s.size() > 0); std::stack<int> copy(s); int M = copy.top(); copy.pop(); while (!empty(copy)) { M = std::max(M,copy.top()); copy.pop(); } return M; }
Observa que el problema est'a solo definido si como m'inimo tienes un elemento en la pila, y observa como debemos hacer una copia de la pila original, para no modificiarla. int main(int argc, char const *argv[]) { std::stack<int> s ; int N; for( ; std::cin >> N ;) s.push(N); int M = compute_max(s); std::cout << M; return 0; }
Para experimentar interactivamente con el programa,,,
|
|
|
3
|
Programación / Programación C/C++ / Re: Comparacion de arrays y eliminacion de elementos iguales
|
en: 9 Junio 2022, 10:52 am
|
Lo que Serapis propone es emular la unión de conjuntos con vectores, dado que en su representación más básica en C, los conjuntos consisten en vectores con elementos no repetidos. Un algoritmo que hace esto muy eficiente (dadas ciertas restricciones*), es una versión del algoritmo 'counting-sort'. ...
Dicho brevemente, sea max(A) el maximo numero de A, N el tamaño de A y M el tamaño de B . Entonces la solucion de Serapis - Tiempo: O(max(A)+N+M)
- Memoria: O(max(A)+N+M)
La mía, (si implementese la uni'on de conjuntos, con memoria dinamica... etc) - Tiempo: O(N*M)
- Memoria: O(N+M)
en resumen, es una solución de compromiso, dependiendo del valor relativo del máximo y las longitudes de A y B se puede bajar en tiempo de N*M a lineal en N+M+max(A)... a base de invertir en memoria, que nunca baja,por supuesto... Bueno, no estoy muy seguro de lo que digo. CAUTION.
|
|
|
4
|
Programación / Programación C/C++ / Re: Comparacion de arrays y eliminacion de elementos iguales
|
en: 2 Junio 2022, 10:16 am
|
Hay una pequeña confusion en lo que planteas. - si hablas de eliminar elementos iguales (como en la prosa), la operacion es A union B \ (A intersec. B) . Es decir A={1,2,3,4,5} B={2,4,6,8,10} C={1,3,5,8,10}, lo que dice Falo.
- si hablas de resta o diferencias de conjuntos (como en el programa), la operación es A\B, quitando del primero los del segundo. Es decir A={1,2,3,4,5} B={2,4,6,8,10} C={1,3,5}NO ES CONMUTATIVA (Esto es importante). a
Empiezo por la segunda - que creo que es la que quires realmente hacer. el mayor fallo es que no inicializas k y el bucle no es correcto. mira este. k=0; for(i=0;i<TC;i++){ for(j=0;j<TC && a[i]!=b[j];j++); // cuerpo vacio a proposito if (j==TC) { c[k]=a[i]; k++; } }
Y la salida es A={ 1 2 3 4 5 } B={ 2 4 6 8 10 } La diferencia es: { 1 3 5 } En el caso de la primera, es cierto que C puede llegar a ser la suma de A y B (si no tienen elementos en comun). Pon, por ejemplo, c[5+5] . El bucle se repite para ambos lados. k=0; for(i=0;i<TC;i++){ for(j=0;j<TC && a[i]!=b[j];j++); // cuerpo vacio a porposito if (j==TC) { c[k]=a[i]; k++; } } for(i=0;i<TC;i++){ for(j=0;j<TC && b[i]!=a[j];j++); // cuerpo vacio a proposito. if (j==TC) { c[k]=b[i]; k++; } }
Y la salida es . A={ 1 2 3 4 5 } B={ 2 4 6 8 10 } La diferencia es: { 1 3 5 6 8 10 }
|
|
|
5
|
Programación / Programación C/C++ / Re: Modificar busqueda binaria
|
en: 2 Junio 2022, 06:12 am
|
Si tenes como premisa que el dato de entrada es un numero que se encuentra en el arreglo, que creo que es este el caso que planteaste, seria asi hacer mientras (bajo <= alto) centro = (bajo + alto) / 2 si (clave = array[centro]) hacer mientras (centro < size) si (clave < array[centro]) devolver centro centro = centro + 1 Repetir devolver -1 o si (clave < array[centro]) alto = centro sino bajo = centro + 1 repetir
La primera solucion de Serapis devuelve el indice donde esta la clave y no el siguiente mayor. Ésta, -si fuese correcta, que depende de los valores iniciales de alto y bajo- no es efficiente como la búsqueda binaria, sino que degrada a busqueda lineal O(n)... Imagina un millon de 1´s y la ultima posición es 2... Entonces, el programa itera 500.000 veces, o sea O(N/2) = O(N). La que yo expuse, iteraría como mucho 20 (<= log_2 10^6)
|
|
|
7
|
Programación / Programación C/C++ / Re: Modificar busqueda binaria
|
en: 1 Junio 2022, 21:51 pm
|
Te paso la original y una variación que devuelve el indice del primer número mayor y en caso contrario devuelve el tamaño del vector size . (Esto es más natural que -1..) Tu ya lo cambias si quieres. #include <iostream> int binary_search(const int V[], const int N, const int elem); int binary_search2(const int V[], const int N, const int elem); #define size 15 int main(){ int numero; int array[size] = {0, 1, 1, 2, 3, 5, 8, 13, 13, 21, 34, 55, 89, 144, 144}; std::cout << "Buscar numero: "; std::cin >> numero; const int index = binary_search2(array, size,numero); if (index == size) std::cout << "No hay elemento mayor a " << numero << std::endl; else std::cout << "Array[" << index << "] = " << array[index] << std::endl; return 0; } #define h ((i+j)/2) /* P: N >= 1, V sorted , elem in V*/ /* original */ int binary_search(const int V[], const int N, const int elem) { int i,j; i=0; j=N; while (V[h]!= elem) if (V[h]>elem) j=h; else i=h+1; return h; } /* P: N >= 1, V sorted , elem in V*/ /* Variation */ int binary_search2(const int V[], const int N, const int elem) { int i,j; i=0; j=N; // I : 0<= i < j <= N and V[i] <= V[elem] <= V[j-1] while (V[h]!= elem || (h<N-1 && V[h]==V[h+1])) // <= B: Changes. if (V[h]>elem) j=h; else i=h+1; return h+1; // V[h] points to element. }
EDIT: La linea while (V[h]!= elem || (h<N-1 && V[h]==V[h+1])) // <= B: Changes. tenía un error tipográfico. (Crédito: jca1) La salida da Buscar numero: 8 Array[7] = 13 Buscar numero: 144 No hay elemento mayor a 144
No quiero abrumar con formalismos. Fijate especialmente en: - la precondicion P: el array ordenado y el numero que pases tiene que existir
- la parada B: A la derecha de h hay uno mayor, o esta en ultima posicion
Un saludo.
|
|
|
8
|
Programación / Programación C/C++ / Re: Frustracion
|
en: 25 Junio 2021, 21:21 pm
|
Aqui te va una propuesta de conteo de palabras con recursion... (No es pa tanta frustración... Más se perdio en Cuba, que decía mi abuelo... ) Decir que es imprescindible llevar control de la primera posición de la linea - si queremos admitir lineas vacias - y del resultado provisional. #include <ctype.h> #include <stdio.h> #include <stdlib.h> // Immersion: // ac = #i : 0 <= i < n : V[i]='nb' and (i>0 -> V[i-1]='b') // (s act as index n, in C-ish style) // 0 <= n <= len(p) int num_wordG(const char *p,const char *s, int ac) { if (*s) if (isspace(*s )) return num_wordG (p ,++s ,ac ); // Rec. else return num_wordG (p ,s +1,ac +(p ==s || isspace(*(s -1)))); // Rec. return ac; // Basis case. } int main(int argc, char *args[]) { char *line = NULL; size_t len = 0 ; ssize_t nread; for ( ; (nread = getline(&line, &len, stdin)) != -1; ) { line[nread-1]=0; // chop the \n printf("%s -> %i\n",line ,num_wordG (line ,line ,0)); } return 0; }
Algunos casos de prueba... En un lugar de la Mancha En un lugar de la Mancha -> 6 son 3 palabras son 3 palabras -> 3 una una -> 1
-> 0
|
|
|
10
|
Programación / Programación C/C++ / Re: Semaforos en c
|
en: 25 Junio 2021, 10:22 am
|
... A cada hilo le podrías enviar como parámetro entero su número de índice. Cada hilo "n" espera por el semáforo n, e incrementa (sem_post) el semáforo n + 1, a excepción del último (2), que incrementará el primero (0).
El planteamiento es correcto. Pero es importante resaltar el valor inicial de los semáforos. Todos a 0, menos el primero, a 1. Aqui va una implementación. #include <pthread.h> #include <stdlib.h> #include <stdio.h> #include <semaphore.h> #include <unistd.h> // sleep thread. #include <string.h> // memcopy static const char values[3]={'A','B','C'}; static sem_t semaphore[3]; static pthread_t thread[3]; static void *routine(void *arg); int main(int argc, char *args[]) { for (int i = 0; i < 3; i++) if (sem_init(&(semaphore[i]), 0, (i==0)?1:0)) { } for (int i = 0; i < 3; i++) { int *local_idx; if ((local_idx = (int *)malloc(sizeof(int)))==NULL ) { } *local_idx=i; if (pthread_create(&thread[i], NULL, routine, local_idx)) { } } for (int i = 0; i < 3; i++) if (pthread_join(thread[i], NULL)) { } } static void *routine(void *arg) { int local_id; memcpy(&local_id ,arg ,sizeof(int)); for( ; 1 ; ) { if (sem_wait(&semaphore[local_id])) { } printf("%c",values [local_id ]); //sleep(1); if (sem_post(&semaphore[(local_id+1)%3])) { } } }
Ejemplo de salida ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABC...
|
|
|
|
|
|
|