elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Estamos en la red social de Mastodon


  Mostrar Mensajes
Páginas: 1 2 3 4 5 6 7 8 9 [10] 11
91  Programación / Programación C/C++ / Re: Funcion palíndromo. en: 22 Marzo 2018, 10:49 am
Cita de: Spider-Net en 17 Septiembre 2008, 01:43 am
Esto es una tontería pero bueno...

Código
  1. ....
  2. int Comprobar_frase (char frase[])
  3.  {
  4.  int longitud=strlen(frase);
  5.  int i=0;
  6.  while (i<=longitud/2 && frase[i]==frase[longitud-1-i])
  7.   {
  8.   i++;
  9.   }
  10.  if (i>longitud/2)
  11.    return 1;
  12.    else
  13.    return 0;
  14. }
  15. ...
  16.  

Quizás no sea tan tontería, amigo mío... :D  El
Código:
(i<=longitud/2)

hay que cambiarlo por

Código:
(i<longitud/2)

y el epílogo de la rutina

Código:
(i>longitud/2)

por

Código:
(i>=longitud/2)


EXPLICACION:
--------------
 el programa es incorrecto si la palabra de entrada es vacía... ya que se accede a la posición [-1]. Y es claro que la palabra vacía es palíndromo.

"La palabra vacía no tiene ningún caracter. Por eso todos sus caracteres (es decir, ninguno, notese la paradoja) cumplen que son simétricos"

En lo de la forma de programar C, no me meto... Pero en general hay que usar con precaución el operador / de division entera...

Aquí teneis la solución que se pedía en pseudocódigo (luego lo hice en python)

https://foro.elhacker.net/ejercicios/necesito_ayuda_para_resolver_este_algoritmo-t481597.0.html;msg2157302#new
92  Programación / Ejercicios / Re: necesito ayuda para resolver este algoritmo (palindromo en pseudocodigo) en: 17 Marzo 2018, 23:49 pm
Cita de: engel lex en 16 Marzo 2018, 18:50 pm
Código:
Entero i
Para i empezando en 0 y terminando en largo_palabra/2:
  Si palabra en i != palabra en largo_palabra - i:
    Imprimir no es palíndromo
    Terminar
  Fin Si
Fin Para

Imprimir palabra es palíndromo

Creo que la solución aportada está mal. Si empezamos a numerar las posiciones de una palabra en 0, como es normal en a mayoría de los lenguajes, W[0..N), con una palabra de longitud N=2, la expresión

Código:
palabra en largo_palabra - i:

compara los caracteres W[0] y  W[2-0], estando el segundo fuera de rango...

Es un problema sencillito, que todos hemos intentado siempre de memoria, pero del que se puede aprender mucho meditando...

Propongo dos ideas, las dos en complejidad O(n), aunque en términos absolutos, la segunda es el doble de rápida que la primera...

Primera, sin tener en cuenta la propia simetría del problema, en un bucle de N veces...
Es un problema de decisión y se trata de devolver el menor indice n que no cumpla la condición de palíndromo con su homólogo N-n-1 o en su defecto, N, si todos lo cumplen. Formalmente

Código:

P : N >= 0
Q : N==min i: 0<=i and (N=i or V[i]!=V[N-i-1]):i

0     1    n=2               N-2   N-1   N
+-----+-----+-----+-...-+-----+-----+-----+
|  A  |  B  |     |     |     |  B  |  A  |
+-----+-----+-----+-...-+-----+-----+-----+

I : \forall i : 0 <= i < n : V[i] == V[N-i-1]
      and
      0 <= n <= N
B :  (n < N) and (V[n]==V[N-n-1])
init : n = 0
Restore: skip
C(N,n) : N-n >= 0
Step : n = n + 1  
O(n)

Y este es el código

Código:
Pseudocode
------------
n=0
while n<N and V[n]==V[N-n-1] 
   n = n +1
done
return n==N

Como habréis notado, una vez se pasa de la mitad, resulta innecesario seguir procesando.
Esa es la idea que quiso desarrollar engel lex. De trivial no tiene nada.

Se trata de buscar el intervalo de longitud máxima menor que N y de la forma [i..N-i) tal que sus extremos i e N-i-1 no cumplan la condición de palindromo, o el intervalo vacío o de un elemento si todos lo cumplen. Si este intervalo es menor o igual que 1, la palabra es palindromo. La idea formal, ilustrada con un dibujo, puede ser esta

Código:
                     i  N-i
                     ....
                  3         N-3
                  ------------
            2                      N-2
            ------------------------
      1                                  N-1
      ------------------------------------
0                                               N
-------------------------------------------------
0     1     2     3          N-3   N-2   N-1    N 
+-----+-----+-----+-...-+-...-+-----+-----+-----+
|  A  |  B  |  C  |     |     |  C  |  B  |  A  |
+-----+-----+-----+-...-+-...-+-----+-----+-----+



  Key : Think on [i..N-i) intevals and distances: (N-i)-i
  
 P : N >= 0
 Q : 0=max i:(N>=(N-i)-i)and ((N-i)-i=0 or V[i]!=V[N-i-1]):N-i-i

 I : N>=N-n-n>=0 and
     \forall i : N>= N-i-i > (N-n-n) : V[i]=V[N-i-1]

 B  : N-n-n > 1 and V[n]==V[N-n-1]   
 init n=0
 Restore: skip
 C(N,n) : N-n-n >= 0
 Step : n = n + 1  (decreases on two!)
y este es el código. Como vemos, no inspecciona todas las casillas dos veces, como el anterior. Notablemente es más difícil, claro, aunque igual de complejidad temporal O(n)

Código:
Pseudocode
------------
n=0
while (((N-n)-n) > 1) and V[i]==V[N-i-1] 
   n = n +1
done
return (((N-n)-n) <= 1)

Notese que la expresión

Código:
(((N-n)-n) > 1)

es equivalente, -en este caso- a la que persguía engel lex,

Código:
n<N/2

 pero nosotros, tardando un poco más hemos llegado a ella razonadamente, completando la intuición que todos hemos tenido de siempre de este algoritmo y que, como es el caso, podría llevarnos a errores.

Me he permitido pasarlo a python, para tener alguna "experiencia real"  del algoritmo.

Código:
def palyndrome(V):
    n = 0
    while ((len(V)-n)-n > 1) and V[n]==V[-n-1]:
        n+=1
    return ((len(V)-n)-n <= 1)



Con estos resultados.

Código:
>>> palyndrome("abccba")
True
>>> palyndrome("abcba")
True
>>> palyndrome("abcca")
False
>>> palyndrome("aaabbb")
False
>>> palyndrome("aaabbbaa")
False
>>> palyndrome("aaabbbaaa")
True
>>> palyndrome("123454321")
True
>>> palyndrome("123454322")
False
>>> palyndrome("")
True
>>> palyndrome("1")
True
>>> palyndrome("12")
False
>>> palyndrome("11")
True
93  Programación / Ejercicios / Re: Dándole vueltas al ejercicio anterior...necesito vuestra ayuda para seguir en: 12 Marzo 2018, 21:58 pm
Es muy fácil. Aquí va esta solución, que pide en primer lugar el número de notas y después las notas.

Consejo: Pon el "asunto" algo más significativo de lo que quieres resolver para poder saber que buscas. Todos son ejercicios, todos necesitamos ayuda... Por ejemplo, en tu caso , sería una buena idea para distinguirlo del resto.

Asunto: media aritmética

Y el código:
Código
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. /*
  6.    P : N > 0
  7.    Q : sum = \sum i : 0 <= i < N : V[i]
  8.        less = #i : 0 <= i < N : N*V[i] < sum 
  9.        greater = #i : 0 <= i < N : N*V[i] > sum 
  10. */
  11. void statistics(const int V[], const int N, int &sum, int &less, int &greater)
  12. {
  13.   int n;
  14.   for (n=sum=0;n<N;n++) sum+=V[n];
  15.   for (n=less=greater=0;n<N;n++)
  16.     {
  17.       less+=((N*V[n]) < sum) ;
  18.       greater+=((N*V[n]) > sum) ;
  19.     }
  20.   return ;
  21. }
  22.  
  23. #define MAX 1000
  24.  
  25. int main()
  26. {
  27.   int V[MAX];
  28.   int N, sum, less,greater;
  29.   cin >> N ;
  30.   for (int n=0; n < N ; n++)  cin >> V[n];
  31.   statistics(V,N,sum,less,greater);
  32.   cout << ((float)sum/N) << "  " << less << "  " << greater << endl;
  33.   return 0 ;
  34. }
  35.  

Algunos ejemplos:

Dos notas, valores 1 y 2 ...
Código:
2
1 2

 La media es 0.5 y hay 1 menor (el 1) y 1 mayor (el 2)
Código:
1.5  1  1

Tres valores.
Código:
3
1 0 0

 La media es 0.333333 (cuidado!, los "float" no son precisos!, es 0.3333333333333... infinitas veces)  y hay 2 menores (los 0) y 1 mayor (el 1)
Código:
0.333333  2  1


(Te dejo que interpretes tú este)

Código:
3
2 2 2

(salida)
Código:
2  0  0
94  Programación / Ejercicios / Particion aritmetica en python en: 11 Marzo 2018, 00:47 am
Vuelvo a recuperar la cuestión no resuelta desde Mayo del 2017

https://foro.elhacker.net/ejercicios/ejercicio_bucle_while_en_python-t469250.0.html

"Dados dos números enteros n (n≥0) y a (a>0) encontrar, si existe, el
menor entero x del intervalo [0, n] para el que se cumpla lo siguiente: la diferencia
entre las sumas de los valores enteros de los intervalos [n-x, n] y [0, x] coincide
con a."

Se mostraron dos soluciones:

La primera es incorrecta, ya que para n = 100000 y para a= 350 se daba x=449, cosa que no
es cierta, pues

Código:
>>> n,a,x = 100000, 350, 449
>>> n,a,x
(100000, 350, 449)
>>> a == sum(range(x,n+1)) - sum(range(0,x+1))
False
>>> a ,  sum(range(x,n+1)) - sum(range(0,x+1))
(350, 4999848399)

En la segunda, se dice que el problema se puede resolver en O(1) sin más que resolver la ecuacion
Código:
 (n-x)x+(n-x)=a
diciendo que (n-x)x+(n-x)  es la diferencia buscada. Cosa que no es, ya que

Código:
>>> n,x
(100000, 449)
>>> (n-x)*x+(n-x) ==  sum(range(x,n+1)) - sum(range(0,x+1))
False
>>> (n-x)*x+(n-x) , sum(range(x,n+1)) - sum(range(0,x+1))
(44797950, 4999848399)

Propongo mi solución. La ecuación que hay que resolver en valores enteros 0 <= x <=n es (al final del mensaje digo como la he obtenido):

Código:
n(n+1) = 2(a+x^2)

En el cuerpo de los complejos, siempre tiene solución, pero en los enteros 0 <= x <= n puede que ésta no exista, por lo que emplearé el tipo None de Python para expresar esta circunstancia...


El algoritmo python que lo resuelve es el siguiente:

Código
  1. '''
  2.    P :  N >= 0 and a > 0
  3.    Q : x = min i : 0 <= i <= N and N(N+1)==2(a +i^2) : i 
  4. '''
  5. def partition(N,a):
  6.     m = 0
  7.     while (m<=N) and (N*(N+1)!=2*(a+m*m)):
  8.         m=m+1
  9.     return (None if m>N else m)



Van algunos ejemplos

Código:
>>> for n in range(5,10):     
        for a in range(6,10): 
            print n,a , " => Sol : " , partition(n,a)


Lo que arroja esta salida
Código:
5 6  => Sol :  3
5 7  => Sol :  None
5 8  => Sol :  None
...
9 7  => Sol :  None
9 8  => Sol :  None
9 9  => Sol :  6


Vemos que
Código:

>>> n,a,x = 5,6,3
>>> n,a,x
(5, 6, 3)
>>> a == sum(range(x,n+1)) - sum(range(0,x+1))
True
>>> a , sum(range(x,n+1)) - sum(range(0,x+1))
(6, 6)

El caso n=100000 y a = 350, no tiene solución.

Si puedo, mañana escribo de donde sale la ecuación.
95  Programación / Programación C/C++ / Re: Buenos días,tengo muchas dudas con un ejercicio de caracteres. en: 27 Febrero 2018, 12:47 pm
Un problema bonito y "raro"...
Ahí va un programa que vale para cualquiera N carcateres, (hasta 1000), metidos por teclado, hasta que se mete el fin de fichero... (no incluye separadores entre los caracteres)

Código
  1. #include <iostream>
  2. #include <algorithm> // min, max
  3.  
  4. using namespace std;
  5.  
  6. #define MAX 1000
  7.  
  8. /*
  9.  
  10.  
  11.   P : N >= 0
  12.   Q : count = #i : 0 <= i < N-1: twin(V,N,i)
  13.  
  14.   where twin(V,N,i) ::= V[i]==V[i+1]) &&
  15.                         ((i==0) || 
  16.                         ((i>0) and V[i]!=V[i-1]) ||
  17.                         (i>1) and V[i-1]==V[i-2])
  18.  
  19. */
  20. int twins(const int V[MAX], const int N)
  21. {
  22.   int n,count;
  23.   for(n=count=0; n<N-1 ; n+=1+(V[n]==V[n+1]))
  24.     count += (V[n]==V[n+1]) ; 
  25.   return count;
  26. }
  27.  
  28. int main(int argc, char *args[])
  29. {
  30.   char c;
  31.   int N;
  32.   int V[MAX];
  33.   for ( N=0  ; (N<MAX) && (cin >> c) ; N++ )  V[N]= c;
  34.   cout << N << " " << twins(V,N) << endl;
  35.   return 0;
  36. }
  37.  
  38. /*
  39.  
  40. 0           n                             N
  41. +-----+-----+-----+-----+-----+-...-+-----+
  42. |  a  |  a  |  a  |  b  |  b  |     |  r  |
  43. +-----+-----+-----+-----+-----+-...-+-----+
  44.  
  45. (Bizarre...)
  46.  
  47.   I : Q[N/n] and
  48.       0 <= n <= N 
  49.        
  50.   B : n<N-1
  51.   C(n) : N-n >= 0 
  52.   step : n = n + (1 + V[i]==V[i+1])
  53.   O(n) (linear)
  54.  
  55. */




Código:
a

El primer parametro da el numero de caracteres leidos (N) el segundo, el numero de "parejas" según el criterio del problema

Código:
1 0

Código:
aaa

Código:
3 1

Código:
aaaaa

Código:
5 2

Código:
aaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooo*

Código:
46 15

(La linea tiene 46 caracteres y 15 parejas)

Y la bonita. Es importante el * porque cin no toma separadores y saldrian más parejas de las normales, juntando los renglones.
Código:
aaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooo*
oooaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnn*
nnnoooaaabbbcccdddeeefffggghhhiiijjjkkklllmmm*
mmmnnnoooaaabbbcccdddeeefffggghhhiiijjjkkklll*
lllmmmnnnoooaaabbbcccdddeeefffggghhhiiijjjkkk*
kkklllmmmnnnoooaaabbbcccdddeeefffggghhhiiijjj*
jjjkkklllmmmnnnoooaaabbbcccdddeeefffggghhhiii*
iiijjjkkklllmmmnnnoooaaabbbcccdddeeefffggghhh*
hhhiiijjjkkklllmmmnnnoooaaabbbcccdddeeefffggg*
ggghhhiiijjjkkklllmmmnnnoooaaabbbcccdddeeefff*
fffggghhhiiijjjkkklllmmmnnnoooaaabbbcccdddeee*
eeefffggghhhiiijjjkkklllmmmnnnoooaaabbbcccddd*
dddeeefffggghhhiiijjjkkklllmmmnnnoooaaabbbccc*
cccdddeeefffggghhhiiijjjkkklllmmmnnnoooaaabbb*
bbbcccdddeeefffggghhhiiijjjkkklllmmmnnnoooaaa*

15 lineas por 15 parejas da 225 parejas


Código:
690 225
96  Programación / Programación C/C++ / Re: Necesito ayuda con un programa en c (Triangulo de pascal) en: 23 Febrero 2018, 23:41 pm
Primero va una muestra del cálculo del trangulo de Pascal de base N=10

Código:
10

Código:
    1     1     1     1     1     1     1     1     1     1 
    1     2     3     4     5     6     7     8     9 
    1     3     6    10    15    21    28    36 
    1     4    10    20    35    56    84 
    1     5    15    35    70   126 
    1     6    21    56   126 
    1     7    28    84 
    1     8    36 
    1     9 
    1

Y ahora uno de N=20. Quizás puedas no apreciarla dependiendo de la distorsión que pueda ocasionar la resolución de carcateres.

Código:
20
Código:
    1     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1 
    1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18    19 
    1     3     6    10    15    21    28    36    45    55    66    78    91   105   120   136   153   171 
    1     4    10    20    35    56    84   120   165   220   286   364   455   560   680   816   969 
    1     5    15    35    70   126   210   330   495   715  1001  1365  1820  2380  3060  3876 
    1     6    21    56   126   252   462   792  1287  2002  3003  4368  6188  8568 11628 
    1     7    28    84   210   462   924  1716  3003  5005  8008 12376 18564 27132 
    1     8    36   120   330   792  1716  3432  6435 11440 19448 31824 50388 
    1     9    45   165   495  1287  3003  6435 12870 24310 43758 75582 
    1    10    55   220   715  2002  5005 11440 24310 48620 92378 
    1    11    66   286  1001  3003  8008 19448 43758 92378 
    1    12    78   364  1365  4368 12376 31824 75582 
    1    13    91   455  1820  6188 18564 50388 
    1    14   105   560  2380  8568 27132 
    1    15   120   680  3060 11628 
    1    16   136   816  3876 
    1    17   153   969 
    1    18   171 
    1    19 
    1

Puedes computar tritangulos de base hasta N=30, pero a no ser que tengas una resolucion suficiente en el terminal de caracteres por pantalla, las figuras saldran sin formatear, y el efecto del trangulo se puede perder... Cuidado también con N altos porque los enteros se pueden salir de rango y acabar en negativos... usar unsigned long....


Y este es el código que lo resuelve... Ah!, empecé a hacerlo en C++, pero con pocos cambios puedes pasarlo a C.

Código
  1. #include <iostream>  // cin, cout
  2. #include <iomanip>  // setw
  3.  
  4. using namespace std;
  5.  
  6. #define MAX 1000
  7.  
  8. // P : N > 0 
  9. // Q : \forall ii,jj : 0 <= ii,jj < N : M[ii][jj]=C(ii+1,jj+1)
  10. // I : i > 0 -> \forall jj : 0 <= jj < N : M[i-1][jj]=C(i-1,jj)
  11.  
  12. // Inner loop
  13. // I2 : \forall jj : 0 <= jj < j : M[i][jj]=C(i+1,jj+1)
  14. // and
  15. // acum = i>0 -> acum= \sum k:0<=k<j: M(i-1,k)
  16.  
  17. // where C(i,j) is combinatory number
  18. //  C(1,j) = 1
  19. //  C(i+1,j) = \sum k:1<=k<=j: C(i,k)
  20.  
  21. void pascal(int M[][MAX], const int N)
  22. {
  23.   int acum;
  24.   int i,j;
  25.   for ( i=0; i<N ; i++)
  26.     for ( j=acum=0; j< N-i ; j++)
  27.       if (i==0) 
  28. 	M[i][j]= 1;
  29.       else
  30. 	{
  31. 	  acum += M[i-1][j];
  32. 	  M[i][j] = acum;
  33. 	}
  34.   return;
  35. }
  36.  
  37. int main(int argc, char **args)
  38. {
  39.   int N;
  40.   int M[MAX][MAX];
  41.   cin >> N ;
  42.   pascal(M,N);
  43.   for (int i=0; i < N ; i++)
  44.     {
  45.       for (int j=0; j < N-i ; j++)
  46. 	cout << setw(5) << M[i][j] << " " ;
  47.       cout << endl;
  48.     }
  49.   return 0;
  50. }
97  Programación / Programación C/C++ / Re: Ayuda con ejercicio de ficheros C en: 16 Febrero 2018, 14:59 pm
A ver, no se si tiene mucho interes quitar los espacios del principio del fichero, pero yo contribuyo a resolver la ultima parte del mensaje

Cita de: ByFuenteS en 14 Febrero 2018, 10:48 am
[...]
Alguien me podria ayudar con este codigo y a poder ser también con la busqueda de una palabra que aparece varias veces en mi código y necesito indicar la linea y la posicion en la que aparece. Muchas gracias!!!

Primero el ejemplo de ejecución: buscar "en el código" (o cualquier fichero de texto en general) las apariciones de una palabra "perror" (o cualquier palabra) indicando linea y columna.

Entrada

Código:
searchWord.c perror

(Creo que la segunda falla, porque el editor emacs que uso mete \t para dar formato al texto C...pero ya no sigo a corregirlo.)

Salida
Código:
45:6	perror
53:3	perror
80:6	perror

Y ahora el código... Se trata del algoritmo más trivial de este estilo, con una complejidad theta(N*M), siendo N el numero de caracteres del archivo y M la longitud (mayor que 0) del patron a buscar. (Está claro que los google engines nunca utilizarán este algoritmo  ;D)


Código
  1. /* 
  2.   Naive string matching on file .
  3.   Theta(N*M) ,
  4.   N (length of contents)
  5.   M (length of pattern)
  6. */
  7.  
  8. #include <stdio.h>
  9. #include <errno.h>
  10. #include <stdlib.h>
  11. #include <assert.h>
  12.  
  13. #include <string.h>
  14.  
  15.  
  16. /*
  17.  
  18.  I : lineno = #i : 0 <= i <= n : V[i]='\n'
  19.      column = max p : 0<= p <= n and AllesNotRet(V,p,n)   : n-p
  20.      buf[0..min(n,m))=V[max(n-m,0),n)
  21.  
  22.   Invariant snapshot
  23.  
  24. 0                                        n=7
  25. +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  26. |  a  |  b  |  c  | \n  |  s  |  e  |  r  |  a  |     |     |
  27. +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
  28.  
  29.               buf= "\nser"
  30. 	      lineno=1	
  31. 	      colum=3
  32. 	      pattern=sera
  33. 	      m = 4
  34. */
  35.  
  36.  
  37. // IO
  38. void searchPattern(FILE *f, const char pattern[])
  39. {
  40.   int n,lineno,column;
  41.   const int m = strlen(pattern);
  42.   char *buf ;
  43.   if (!(buf=(char *)calloc(m,sizeof(char))))
  44.     {
  45.       perror("calloc");
  46.       exit(EXIT_FAILURE);
  47.     }
  48.   for(lineno=column=n=0 ; !feof(f) ; n++)
  49.     {
  50.       char chr=fgetc(f);
  51.       if (ferror(f))
  52. 	{
  53. 	  perror("fgetc");
  54. 	  exit(EXIT_FAILURE);
  55. 	}
  56.       int i;
  57.       for(i=0; i<m-1 ; i++) buf[i]=buf[i+1]; // shift window
  58.       buf[m-1]=chr;
  59.       if (strncmp(buf,pattern,m)==0)
  60. 	printf("%d:%d\t%s\n",lineno+1,column-m+1,pattern);
  61.       lineno += (chr=='\n');
  62.       column =  (chr =='\n')?0:(column+1);
  63.     }
  64.   free(buf);
  65.   return;
  66. }
  67.  
  68.  
  69. int main (void)
  70. {
  71.   FILE *f;
  72.   int n,N;
  73.  
  74. #define MAX 10000
  75.   char path[MAX];
  76.   char word[MAX];
  77.   scanf("%s %s",path,word);
  78.   if (!(f = fopen(path,"r")))
  79.     {
  80.       perror("fopen");
  81.       exit(EXIT_FAILURE);
  82.     };
  83.   searchPattern(f,word);
  84.   fclose(f);
  85.   return 0;
  86. }
  87.  
  88. /*
  89. Note : Formal Specification is done referring to V[0..N)/(POS[0..P))
  90.        instead of file stream (f)/(stdin)
  91.        
  92. P : M > 0
  93. Q : P = #i : 0 <= i < N : buf[0..m)=V[i,min(i+m,N))
  94.     \forall i : 0 <= i < P : V[POS[i]..POS[i]+m)=pattern[0..m)
  95.                              V[POS[i]-COLUMN[i]-1]=\n and
  96.                              LINE[i]=#i : 0 <= i < POS[i] : V[i]=\n
  97. */                           
  98.  
  99.  
  100.  
98  Programación / Programación C/C++ / Re: C++ Memoria dinámica en: 12 Febrero 2018, 16:18 pm
Comentando un poco el problema original

Cita de: rafaelfinacut10 en  4 Febrero 2018, 08:28 am
[...] es un programa que opera en la colección dinámica de datos.
[...]
Esto es lo que se espera
1.Si la colección está vacía, debe asignar un vector de un elemento y almacenar un nuevo valor en él
2. Si la colección no está vacía, debe asignar un nuevo vector con una longitud mayor en uno que el vector actual, luego copiar todos los elementos del antiguo vector al nuevo, agregar un nuevo valor al nuevo vector y finalmente liberar el vector viejo.

Le veo un fallo a este planteamiento. Está claro que la mayor ventaja de emplear dinámica es que se ajusta más la memoria seǵun la necesidad en tiempo de ejecución... Pero se incurre en gran ineficiencia en cuanto a tiempo...
Me explico:

Añadir el primer elemento cuesta 1, el segundo 2, el tercero 3, el cuarto 4... debido a que tienes que hacer una copia del array aumentado a cada momento... De esta manera incurres en coste cuadratico O(n^2), cuando, con memoria estatica, aunque ineficaz en espacio,  tenias un coste  O(n) en tiempo

Código:
1+2+3 + ... + n = n(n+1)/2  \in O(n^2)

lo que hace muy costoso e ineficiente...

Este es un viejo problema de coste amortizado...

Básicamente consiste en, cada vez que se incremente en la memoria, hacerlo multiplicando por un factor - que depende de una heurística o de la aplicación particular...

En nuestro caso, elegimos FACTOR=2, por lo que cada vez que se "llene la memoria" la duplicamos, y solo en ese momento, hacemos copia del vector original . Es cierto que se pierde precisión con respecto  a la idea dinamica original de tu planteamiento llegando a gastar N*2 cuando sólo se tiene N+1 en el caso peor, pero en términos de coste amortizado en tiempo es de coste constante O(1)...  (es algo complejo de explicar en un solo post)


Primero vamos con la entrada (1 renglon) y salida (2 y 3 renglon) de los programas. El programa almacena la colección de entrada en un array estatico de como mucho 1000 elementos y despues lo convierte a colección dinámica. Se puede ver el ratio de memoria empleada/reservada
 
Código:
1
1 
N/MAX=1/10000 vs. N/NN=1/1

Código:
1 2
1 2 
N/MAX=2/10000 vs. N/NN=2/2


Código:
1 2 3 4
1 2 3 4 
N/MAX=4/10000 vs. N/NN=4/4

Código:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
N/MAX=16/10000 vs. N/NN=16/16


Código:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 
N/MAX=32/10000 vs. N/NN=32/32

Ahora el codigo del programa.
Yo voy a lo sustancial, no manejo "structs" , pero es posible que a tí te interese para simular un TAD, y lo podrás adoptar a tu manera con "structs". Tampco programo la reservar memoria, porque viene con

Código
  1. #include <stdlib.h>
  2. void *realloc(void *ptr, size_t size);
  3.  

pero a ti te puede interesar programarla "por razones didácticas"

Este es el programa

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define MAX 10000
  5.  
  6. #define FACTOR 2
  7.  
  8.  /* Pre : *NN = 1  */
  9. void static2Dynamic(const int V[],const int N,int **D, int *NN)
  10. {
  11.   int nn,n;
  12.  
  13.    /* I : nn <= *NN  */
  14.   for ( nn=n=0; n<N; n++)
  15.     {
  16.       if (nn == *NN)
  17.       	{
  18.           (*NN) *= FACTOR;
  19. 	  if  (!(*D=(int *)realloc(*D,sizeof(int)*(*NN))))
  20.       	    {
  21.       	      perror("realloc");
  22.       	      exit(EXIT_FAILURE);
  23.       	    }
  24.       	}
  25.       (*D)[nn++]= V[n]; 
  26.     }
  27. }
  28.  
  29. int main (int argc, char **args)
  30. {
  31.   int *D ;
  32.   int N,n,NN;
  33.   int V[MAX];
  34.   if  (!(D=(int *)malloc(sizeof(int))))
  35.     {
  36.       perror("malloc");
  37.       exit(EXIT_FAILURE);
  38.     }
  39.   NN=1;
  40.   for(N=0; (scanf("%d",&V[N])!=EOF); N++);
  41.   static2Dynamic(V,N,&D,&NN);
  42.   for( n=0; n<N; n++) printf("%d ",D[n]);
  43.   printf("\nN/MAX=%d/%d vs. N/NN=%d/%d\n",N,MAX,N,NN);
  44.   return 0;
  45. }
  46.  
  47.  
  48.  

Ahora bien, fijate lo que psa si metemos, digamos 33 elementos...
Código:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 
N/MAX=33/10000 vs. N/NN=33/64

Se despercia casi la mitad, pero aún así, no tanto como 33/10000...

Por ultimo, si quieres progrmaarte tu realloc, puede ser algo así

Código
  1. void *myrealloc(const int *ptr, const size_t old_size,const size_t new_size )
  2. {
  3.   int *p;
  4.   if (!(p = malloc(new_size)))
  5.     {
  6.       perror("malloc");
  7.       exit(EXIT_FAILURE);      
  8.     }
  9.   int i;
  10.   for (i=0; (i < old_size) && (i < new_size);i++) *(p+i) = *(ptr+i);
  11.   free((void *)ptr);
  12.   return p;
  13. }
  14.  

Cambiando lo que haya que cambiar en el fuente del main
99  Programación / Programación C/C++ / Re: ayuda , guardar en un regsitro, inconvenientes en: 12 Febrero 2018, 09:30 am
Si sabes con garantías que el fichero de entrada tiene un formato definido...
¿ por qué no utilizar entrada-salida formateada? Es más fácil. te ahorras procesamiento de comas y espacios...

Aquí te dejo una idea. Tu la cojes y la adaptas a tus estructuras de registros, etc..  Yo he puesto fn, como abreviatura de "field"....


Código
  1. /* 
  2.   string formatted input-output 
  3. */
  4.  
  5. #include <stdio.h>
  6. #include <errno.h>
  7. #include <stdlib.h>
  8.  
  9. #define MAX 1000
  10.  
  11. int main (void)
  12. {
  13.   FILE *f;
  14.   int f0[MAX],f1[MAX],f2[MAX],
  15.       f3[MAX],f4[MAX],f5[MAX],f6[MAX];
  16.   int n,N;
  17.  
  18.   if (!(f = fopen("listaprocesos.in","r")))
  19.     {
  20.       perror("fopen");
  21.       exit(EXIT_FAILURE);
  22.     };
  23.   for (N=0 ; fscanf(f,"%d, %d, %d, %d, %d, %d, %d\n",
  24. 		    &f0[N],&f1[N],&f2[N],&f3[N],&f4[N],&f5[N],&f6[N])!=EOF; N++ );
  25.  
  26.   for (n=0 ; n<N ; n++)
  27.     printf("%d, %d, %d, %d, %d, %d, %d\n",
  28. 	   f0[n],f1[n],f2[n],f3[n],f4[n],f5[n],f6[n]);
  29.   fclose(f);
  30.   return 0;
  31. }


Contenido de "listaprocesos.in"

Código:
1, 0, 1, 0, 0, 0, 0
1, 1, 2, 1, 0, 0, 1
3, 3, 6, 1, 0, 1, 2
2, 3, 1, 0, 0, 3, 2

Salida del programa.

Código:
1, 0, 1, 0, 0, 0, 0
1, 1, 2, 1, 0, 0, 1
3, 3, 6, 1, 0, 1, 2
2, 3, 1, 0, 0, 3, 2
100  Programación / Programación C/C++ / Re: Duda sobre C (rangos de valores) en: 8 Febrero 2018, 15:59 pm
Este programa se puede compilar y ejecutar en tu plataforma de desarrollo.
Por cierto, que no sé la fuente-url de dónde lo he sacado, pero no es propio.

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4. #include <float.h>
  5.  
  6.  
  7. int main(int argc, char** argv) {
  8.  
  9.     printf("CHAR_BIT    :   %d\n", CHAR_BIT);
  10.     printf("CHAR_MAX    :   %d\n", CHAR_MAX);
  11.     printf("CHAR_MIN    :   %d\n", CHAR_MIN);
  12.     printf("INT_MAX     :   %d\n", INT_MAX);
  13.     printf("INT_MIN     :   %d\n", INT_MIN);
  14.     printf("LONG_MAX    :   %ld\n", (long) LONG_MAX);
  15.     printf("LONG_MIN    :   %ld\n", (long) LONG_MIN);
  16.     printf("SCHAR_MAX   :   %d\n", SCHAR_MAX);
  17.     printf("SCHAR_MIN   :   %d\n", SCHAR_MIN);
  18.     printf("SHRT_MAX    :   %d\n", SHRT_MAX);
  19.     printf("SHRT_MIN    :   %d\n", SHRT_MIN);
  20.     printf("UCHAR_MAX   :   %d\n", UCHAR_MAX);
  21.     printf("UINT_MAX    :   %u\n", (unsigned int) UINT_MAX);
  22.     printf("ULONG_MAX   :   %lu\n", (unsigned long) ULONG_MAX);
  23.     printf("USHRT_MAX   :   %d\n", (unsigned short) USHRT_MAX);
  24.     printf("FLT_MAX     :   %g\n", (float) FLT_MAX);
  25.     printf("FLT_MIN     :   %g\n", (float) FLT_MIN);
  26.     printf("-FLT_MAX    :   %g\n", (float) -FLT_MAX);
  27.     printf("-FLT_MIN    :   %g\n", (float) -FLT_MIN);
  28.     printf("DBL_MAX     :   %g\n", (double) DBL_MAX);
  29.     printf("DBL_MIN     :   %g\n", (double) DBL_MIN);
  30.     printf("-DBL_MAX     :  %g\n", (double) -DBL_MAX);
  31.  
  32.     printf("Storage size for int : %d \n", sizeof(int));
  33.     printf("Storage size for unsigned int : %d \n", sizeof(unsigned int));    
  34.     printf("Storage size for unsigned long : %d \n", sizeof(unsigned long));
  35.     printf("Storage size for long long : %d \n", sizeof(long long ));
  36.     printf("Storage size for unsigned long long : %d \n", sizeof(unsigned long long));        
  37.     return (EXIT_SUCCESS);
  38. }
  39.  

Esto cambia según la plataforma de desarrollo. En linux-x86-64, a mí me sale esto, pero entros puede salir otra cosa.
Código:
CHAR_BIT    :   8
CHAR_MAX    :   127
CHAR_MIN    :   -128
INT_MAX     :   2147483647
INT_MIN     :   -2147483648
LONG_MAX    :   9223372036854775807
LONG_MIN    :   -9223372036854775808
SCHAR_MAX   :   127
SCHAR_MIN   :   -128
SHRT_MAX    :   32767
SHRT_MIN    :   -32768
UCHAR_MAX   :   255
UINT_MAX    :   4294967295
ULONG_MAX   :   18446744073709551615
USHRT_MAX   :   65535
FLT_MAX     :   3.40282e+38
FLT_MIN     :   1.17549e-38
-FLT_MAX    :   -3.40282e+38
-FLT_MIN    :   -1.17549e-38
DBL_MAX     :   1.79769e+308
DBL_MIN     :   2.22507e-308
-DBL_MAX     :  -1.79769e+308
Storage size for int : 4 
Storage size for unsigned int : 4 
Storage size for unsigned long : 8 
Storage size for long long : 8 
Storage size for unsigned long long : 8

Páginas: 1 2 3 4 5 6 7 8 9 [10] 11
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines