Mensajes

Comentando un poco el problema original

[...] 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 [Seleccionar] Expandir

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 [Seleccionar] Expandir


1
1
N/MAX=1/10000 vs. N/NN=1/1

Código [Seleccionar] Expandir

1 2
1 2
N/MAX=2/10000 vs. N/NN=2/2

Código [Seleccionar] Expandir

1 2 3 4
1 2 3 4
N/MAX=4/10000 vs. N/NN=4/4

Código [Seleccionar] Expandir


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 [Seleccionar] Expandir


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 (c) [Seleccionar] Expandir


#include <stdlib.h>
void *realloc(void *ptr, size_t size);


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

Este es el programa

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>

#define MAX 10000

#define FACTOR 2

/* Pre : *NN = 1  */
void static2Dynamic(const int V[],const int N,int **D, int *NN)
{
 int nn,n;

  /* I : nn <= *NN  */
 for ( nn=n=0; n<N; n++)
   {
     if (nn == *NN)
      {
         (*NN) *= FACTOR;
 if  (!(*D=(int *)realloc(*D,sizeof(int)*(*NN))))
         {
           perror("realloc");
           exit(EXIT_FAILURE);
         }
      }
     (*D)[nn++]= V[n];
   }
}

int main (int argc, char **args)
{
 int *D ;
 int N,n,NN;
 int V[MAX];
 if  (!(D=(int *)malloc(sizeof(int))))
   {
     perror("malloc");
     exit(EXIT_FAILURE);
   }
 NN=1;
 for(N=0; (scanf("%d",&V[N])!=EOF); N++);
 static2Dynamic(V,N,&D,&NN);
 for( n=0; n<N; n++) printf("%d ",D[n]);
 printf("\nN/MAX=%d/%d vs. N/NN=%d/%d\n",N,MAX,N,NN);
 return 0;
}




Ahora bien, fijate lo que psa si metemos, digamos 33 elementos...

Código [Seleccionar] Expandir


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 (c) [Seleccionar] Expandir


void *myrealloc(const int *ptr, const size_t old_size,const size_t new_size )
{
 int *p;
 if (!(p = malloc(new_size)))
   {
     perror("malloc");
     exit(EXIT_FAILURE);      
   }
 int i;
 for (i=0; (i < old_size) && (i < new_size);i++) *(p+i) = *(ptr+i);
 free((void *)ptr);
 return p;
}


Cambiando lo que haya que cambiar en el fuente del main

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 (c) [Seleccionar] Expandir

/*
  string formatted input-output
*/

#include <stdio.h>
#include <errno.h>
#include <stdlib.h>

#define MAX 1000

int main (void)
{
  FILE *f;
  int f0[MAX],f1[MAX],f2[MAX],
      f3[MAX],f4[MAX],f5[MAX],f6[MAX];
  int n,N;
 
  if (!(f = fopen("listaprocesos.in","r")))
    {
      perror("fopen");
      exit(EXIT_FAILURE);
    };
  for (N=0 ; fscanf(f,"%d, %d, %d, %d, %d, %d, %d\n",
    &f0[N],&f1[N],&f2[N],&f3[N],&f4[N],&f5[N],&f6[N])!=EOF; N++ );
 
  for (n=0 ; n<N ; n++)
    printf("%d, %d, %d, %d, %d, %d, %d\n",
   f0[n],f1[n],f2[n],f3[n],f4[n],f5[n],f6[n]);
  fclose(f);
  return 0;
}


Contenido de "listaprocesos.in"

Código [Seleccionar] Expandir

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 [Seleccionar] Expandir

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

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 (c) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <float.h>


int main(int argc, char** argv) {

   printf("CHAR_BIT    :   %d\n", CHAR_BIT);
   printf("CHAR_MAX    :   %d\n", CHAR_MAX);
   printf("CHAR_MIN    :   %d\n", CHAR_MIN);
   printf("INT_MAX     :   %d\n", INT_MAX);
   printf("INT_MIN     :   %d\n", INT_MIN);
   printf("LONG_MAX    :   %ld\n", (long) LONG_MAX);
   printf("LONG_MIN    :   %ld\n", (long) LONG_MIN);
   printf("SCHAR_MAX   :   %d\n", SCHAR_MAX);
   printf("SCHAR_MIN   :   %d\n", SCHAR_MIN);
   printf("SHRT_MAX    :   %d\n", SHRT_MAX);
   printf("SHRT_MIN    :   %d\n", SHRT_MIN);
   printf("UCHAR_MAX   :   %d\n", UCHAR_MAX);
   printf("UINT_MAX    :   %u\n", (unsigned int) UINT_MAX);
   printf("ULONG_MAX   :   %lu\n", (unsigned long) ULONG_MAX);
   printf("USHRT_MAX   :   %d\n", (unsigned short) USHRT_MAX);
   printf("FLT_MAX     :   %g\n", (float) FLT_MAX);
   printf("FLT_MIN     :   %g\n", (float) FLT_MIN);
   printf("-FLT_MAX    :   %g\n", (float) -FLT_MAX);
   printf("-FLT_MIN    :   %g\n", (float) -FLT_MIN);
   printf("DBL_MAX     :   %g\n", (double) DBL_MAX);
   printf("DBL_MIN     :   %g\n", (double) DBL_MIN);
   printf("-DBL_MAX     :  %g\n", (double) -DBL_MAX);

   printf("Storage size for int : %d \n", sizeof(int));
   printf("Storage size for unsigned int : %d \n", sizeof(unsigned int));    
   printf("Storage size for unsigned long : %d \n", sizeof(unsigned long));
   printf("Storage size for long long : %d \n", sizeof(long long ));
   printf("Storage size for unsigned long long : %d \n", sizeof(unsigned long long));        
   return (EXIT_SUCCESS);
}


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 [Seleccionar] Expandir

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

Sacado de http://www.cplusplus.com/reference/algorithm/copy/?kw=copy

Código (c) [Seleccionar] Expandir

// copy algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::copy
#include <vector>       // std::vector

int main () {
  int myints[]={10,20,30,40,50,60,70};
  std::vector<int> myvector (7);

  std::copy ( myints, myints+7, myvector.begin() );

  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it = myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}

[Imporante:]

A ver, vamos por partes.
En vez del buscaminas, hagamos una simplificación del problema para entenderlo mejor. Después solo lo adaptas al buscaminas (numeros, visible...)

De una matriz NxM de 0's y 1's, tenemos que dar una posición donde encontrar un 1. Nos vale cualquiera.

Código [Seleccionar] Expandir


M=4, N=5
   0     i      M
   +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
  |1 |  |  |  |
  +--+--+--+--+
j |  |  |  | 1|
  +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
         N

   Sol:  V[2][3]=1



Lo primero que te tienes que dar cuenta es de que la complejidad en el caso peor va a ser Omega(n^2) y no puedes bajar de ahí (imagina que está en la última casilla en el orden de  búsqueda).

Ahora viene la siguiente cuestión: se pide recursiva, de acuerdo, pero...
Por que no intenar dividiendo el tamaño del problema en  vez de sustrayendo?  

Me explico, se divide la matriz en cuatro cuadrantes A,B,C,D dividiendo sus dimensiones N,M por la mitad, y por recursión damos por resuelto el problema. Hay dos casos base posible:

• matriz sin celdas, o vacía, donde nunca encuentras un 1. (significa que te has salido del rango)
• 
  matriz con UNA celda : si está, devolvemos cierto y las coordenadas de la celda. en otro caso falso y da igual las coordenadas
  

Imporante: En esta implementación siempre pensamos en el operador cortocircuitado OR... Es decir (true || a == 6 ) nunca pasa a evaluar la segunda expresi'on a==6. De otro modo, esto puede no funcionar. En la práctica, la mayoría de los compiladores proceden así, pero no se sabe si algun optimizador puede cambiar el orden.

Ahí va la solucion

Código (c) [Seleccionar] Expandir


#include <iostream>

using namespace std;

#define MAX 100
/*
 
M=4, N=5
          0     i      M
          +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
  |1 |  |  |  |
  +--+--+--+--+
j |  |  |  | 1|
  +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
  |  |  |  |  |
  +--+--+--+--+
         N

   Sol:  V[2][3]=1
*/


/*
  Global inmersion
 
  P : V[j0..jn)[i0..in)
      0<=i0<=in<=M, 0<=j0<=jn<=N
  Q : found -> V[x][y]= 1

  B1 : empty square
  B2 : one-cell square
  C(i0,in,j0,j0) = (in-i0)*(jn-j0) (Area)
  O(n^2), since A=4,B=2, k=0 and 4 > 2
*/
bool RR(const int V[][MAX],
const int j0, const int jn, // N
const int i0, const int in, // M
int &x, int &y)
{

 if (((in-i0)*(jn-j0)) == 0) // empty
   return false;
 if (((in-i0)*(jn-j0)) == 1) // 1 cell
   {
     x=j0;
     y=i0;
     return (V[x][y]==1);
   }
 else // 2 or more cells
   {
     const int hi = (in + i0) /2 ;
     const int hj = (jn + j0) /2 ;
     return
(
RR(V,j0,hj,i0,hi,x,y) || RR(V,j0,hj,hi,in,x,y) ||
RR(V,hj,jn,i0,hi,x,y) || RR(V,hj,jn,hi,in,x,y)
);
   }
}  



/*
  P : \exists i : 0 <= i<N , 0 <=j<M : V[i][j]=1

  Q : M[x][y]=1

*/
void R(const int V[][MAX],
     const int N, const int M,
      int &x, int &y)
{
 RR(V,0,N,0,M,x,y);
 return;
}


int main()
{
 int V[MAX][MAX] ;
 int n,N,m,M ;
 int x,y;
 cin >> N;
 cin >> M;
 for(int n=0; n<N; n++)
   for(int m=0; m<M; m++) cin >> V[n][m];
 R(V,N,M,x,y);
 cout << "(" << x << "," << y << ")" << endl;
 return 0;
}


Algunos casos de prueba

Código [Seleccionar] Expandir

6 5

0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0

Resultado

Código [Seleccionar] Expandir


(0,2)



Otro

Código [Seleccionar] Expandir


12 5

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0


Código [Seleccionar] Expandir

(8,4)

Un problema bonito, si señor...7 variables! 3 entrada, 2 de salida, y dos locales...

La clave está en como formalizamos en aritmética, que "si tengo 5 productos" y me exigen lotes de 3 para aplicar el descuento, el 4 o el 5 no tienen descuento. Eso es lo que hace con el chorizo de

Código [Seleccionar] Expandir


\chi((i+(pck-1)-i%pck))<N)

Si voy por el 5 producto (i=4), con lotes de 3  (pck=3) entonces 4+(3-1)-(4%3) = 6 -1 >= 5=N , o sea, "se sale del array"...

Por otro lado, hay que ir actualizando el descuento cada "pack" unidades a la mitad, de ahi que multipliquemos por 2 a disc cada "pack" veces en el cuerpo del for.

Código (c) [Seleccionar] Expandir

#include <iostream>

using namespace std;
/*

 let \chi(true)=1 \chi(false)=0

 P : V[0..N) of nat  0<pck
 Q : T = \sum i : 0 <= i < N : V[i]
     D = \sum i : 0 <= i < N  : \chi((i+(pck-1)-i%pck))<N)*V[i]/(5*2^(i/pck)) *

     * Informaly,
        chunk \chi(...) expresses condition
        for applying discount 0 or 1

  I  : Q[N/n] and 0 <= n <= N and
       disc = (5*2^n)  (efficiency reasons.)
  B  : n < N
  C(N-n) = N-n >= 0

*/

void discount(const int V[], const int N, const int pck,
             int &T, int &D)
{
 int n,disc;
 for(n=T=D=0, disc=5;n<N;n++)
   {
     T += V[n];
     D += ((n+(pck-1)-(n%pck))<N)*V[n]/disc;
     disc *=((n+1)%pck)?1:2;
   }
 return;
}

#define MAX 1000
int main()
{
 int V[MAX] ;
 int n,N ;
 int pck;
 int T,D;
 cin >> pck;
 cin >> N;
 for(int n=0; n<N; n++) cin >> V[n];
 discount(V,N,pck,T,D);
 cout << T << " " << D << " " << (T-D) << endl;
 return 0;
}

El ejemplo reproducido que se daba

Código [Seleccionar] Expandir


3
8
400 800 500 100 400 300 200 500


Da como salida

Código [Seleccionar] Expandir

3200 420 2780

Si en cambio, decidimos que hay que tener un minimo de 9 productos para aplicar el descuento...

Código [Seleccionar] Expandir


9
8
400 800 500 100 400 300 200 500

Entonces, no hay descuento, como era de esperar

Código [Seleccionar] Expandir

3200 0 3200

Como mínimo, en la condición del bucle while.

Código (c) [Seleccionar] Expandir

while ((res == 0) || (cad[i] != '\0')) {

Cambiando el operador || (OR) por && (AND)

Código (c) [Seleccionar] Expandir

while ((res == 0)  && (cad[i] != '\0')  ) {

De todas formas, aunque este disponible como

Código (c) [Seleccionar] Expandir


#include <string.h>

char *strchr(const char *s, int c);


como ejercicio de programación , yo haría esta:

Código (c) [Seleccionar] Expandir

int EncontrarCaracter(const char cad[], const char n)
{
 const char *c;
 for ( c=cad; *c && (*c!=n);c++);
 return *c;
}

Es un poco crípitica, pero my C-style... Devuelve 0 si no esta, o el valor decimal del caracter ASCII si esta...


Ojo! Sería ambiguo preguntar por el caracter "\0", ya que en toda cadena de C, está, y devolvería precisamente 0, que es su valor en decimal...

Entoces... está o no está? Parece que está, pero el convenio escogido dice que no. Ojo!

La "strchr" dice que devuelve un PUNTERO a la primera ocurrencia de ese valor... El caracter nulo "\0" es considerado PARTE de la cadena.

[Importante]

A ver, campeón, que te has liado mucho!
Piensa que no se trata de hacer una aplicación profesional, sino un sencillo algoritmo de cómputo de partes aliquotas con una pequeña variación según sea repartidor o camarero!

En mi solución el "nombre" del trabajador es un entero 1, 2... No aporta nada a la metáfora añadir identificadores de tipo string... si hubieras puesto algun caso de salida, lo habría hecho.

Ahí te va mi solución:

• Si estás en un curso introductorio de programación, no hagas caso de los comentarios formales.
  Están ahí para controlar los valores del algoritmo. Pero eso es otro "subject".
  
• Importante : He optado por soluciones enteras (int), no float... 100/30 (el inverso de 30/100) no es 3, sino un poco mas,  pero a este nivel de programación, los floats de C tampoco representan correctamente 100/30 . O sea que tambien es "impreciso" usar float. Eso hara que el redondeo de los pesos de los repartidores sea al alza (mira despues el ejemplo)
  
• Basicamente, se distinguen repartidores de camareros por el identificador n<D y n>=D

Código (c) [Seleccionar] Expandir

#include <iostream>

using namespace std;


#define MAX 1000

/*
 P : T,W,D >= 0 ,
     \forall i : 0 <= i < (W+D) : HH[i]>= 0
     H = \sum i : 0 <= i < (W+D) : HH[i]
 Q : \forall i : 0 <= i < (W+D) : TT[i] = RATED_TIP(T,H,i,D)
     where
       RATED_TIP(T,H,i,D) ::= T*(HH[n]/H)*0.30^(i<D)));

 I : Q[(W+D)/n] and 0 <= n <= (W+D)
 O(n)
*/
void computeTip(const int T,const int H,
const int D, const int W,
               const int HH[], int TT[])
{
 for (int n=0; n<(W+D) ; n++)
   TT[n] = (T*HH[n])/(H*((n<D)?(100/30):1));
}
int main(int argc, char *args[])
{
 int T,D,W,H ;
 int HH[MAX];
 int TT[MAX];
 int n;
 cin >> T >> D >> W ; // Tip,Dispatchers,Waiters
 for (n=H=0; n < W+D ; n++)  { cin >> HH[n] ; H+=HH[n] ;}
 computeTip(T,H,D,W,HH,TT);
 for (n=0; n < W+D ; n++)  cout << n << " " << TT[n] << endl;  
}


Aqui van algunas muestras, siguiendo un protocolo de entrada, que es el que se suele seguir en os concursos de programación.

Primero, el bote a repartir , despues el numero de repartidores, despues el numero de camareros.
En el siguiente renglon, las horas de cada repartidor y en el siguiente renglón , las horas de cada camarero.

Código [Seleccionar] Expandir


100 3 1
1 1 1
1


Resultado. Se han trabajado 4 horas. El camarero 1, al 100% de la parte aliquota (25), le da 25. Si los repartidores fueran al 100% también tendrían 25 cada uno, pero como van al 30%, se llevan 25*0.3=7.5 , que redodeado es 8.

Código [Seleccionar] Expandir


0 8
1 8
2 8
3 25


Ahora los tres trabajadores trabajan cada 1 una hora y el camarero, nada...

Código [Seleccionar] Expandir


18 3 1
1 1 1
0

El camarero, como no ha trabajado, no cobra. Si cada camarero estuviera al 100% de su parte aliquota
(6), cobraría 6, pero como esta al 30%, cobra 6*0.3=1.8, que redondeado queda dos...

Código [Seleccionar] Expandir


0 2
1 2
2 2
3 0


Casos exactos. Sin redondeo. Ahora no hay camareros, solo 2 repartidores. Entonces no hay tercera linea de entrada

Código [Seleccionar] Expandir


90 2 0
4 2


El segundo repartidor , si tuviese la parte aliqyita del bote cobraria 30. Cmo esta al 30% cobra 10. Logicamente el primer repartidor ha trabajado el doble, pues cobra el doble, 20.

Código [Seleccionar] Expandir

0 20
1 10


Y ultimo caso!. Un  repartidor y dos camareros se erparten un bote de 100.

Código [Seleccionar] Expandir


100 1 2
4
8 4


El prrimer camarero ha trabajado la mitad de las horas , al 100%, por lo que se queda 50. El segundo ha trabjado la mitad del primero, pues cobra la mitad, 25. El reartidor habria cobrado 25 también al 100%, pero como está al 30%, cobra 8... (redondeo de 7.5)

Código [Seleccionar] Expandir

0 8
1 50
2 25

Ah! Se me olvidaba... Yo tampoco puedo recoger "infinitos" camareros con cin.. Pero hasta 1000, si podría...

Te pongo 30 repartidores y 30 camareros, con un bote de  15000... Pero te toca a ti, comprobar si está bien  

Código [Seleccionar] Expandir


15000 30 30
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
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Es broma... Las anotaciones que pongo en la especificación comprueban que el algoritmo es correcto (salvo el error arrastrado por el redondeo)  para _cualquier_ valor de N...por grande que sea

Código [Seleccionar] Expandir

0 5
1 10
2 16
3 21
4 26
5 32
6 37
7 43
8 48
9 53
10 59
11 64
12 69
13 75
14 80
15 86
16 91
17 96
18 102
19 107
20 112
21 118
22 123
23 129
24 134
25 139
26 145
27 150
28 155
29 161
30 483
31 467
32 451
33 435
34 419
35 403
36 387
37 370
38 354
39 338
40 322
41 306
42 290
43 274
44 258
45 241
46 225
47 209
48 193
49 177
50 161
51 145
52 129
53 112
54 96
55 80
56 64
57 48
58 32
59 16

Te dejo este codigo. Lo hice tal como dice el enunciado.
Salu2

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

const int maximo=5;

float notas[maximo];
float mayor=0;
float menor,diferencia;
float suma=0;
int i;

int main() {
 
 for(i=0; i<maximo; i++)
 {
   cout<<"Ingrese la nota"<<i<<endl;
   cin>>notas[i];
 }
 
 //Encuentro el mayor,menor
 menor = notas[1];
 
 for(i=0; i<maximo; i++)
 {
   if(notas[i] > mayor)
     mayor=notas[i];
   else if (notas[i] < menor)
     menor=notas[i];
  }
 
  diferencia = mayor - menor;
 
  cout << "La diferencia entre la nota mayor y la nota menor es " << diferencia;
 
  return 0;
}


El programa está mal. contraejemplo: [-5,-5,-5,-5,-4] con 5 enteros, da diferencia 5, y debe dar 1. -4 -(-5)= 1

En otro post... https://foro.elhacker.net/programacion_cc/tengo_un_ejercicio_al_que_no_doy_formanecesito_un_empujon-t479671.0.html hablo del problema de un incorrecto valor inicial.


El siguiente problema da la diferencia entre la nota mayor y menor de un array de (N) elementos...

Código (c) [Seleccionar] Expandir


#include <iostream>
using namespace std;

/*
 P : N > 0
 Q : d = M - m
 where
 M = max i : 0 <= i < N : V[i]
 m = min i : 0 <= i < N : V[i]

 I : Q[N/n] and 1<= n <= N and *
 M = max i : 0 <= i < n : V[i]
 m = min i : 0 <= i < n : V[i]  

 *  M,m for efficiency reasons.
 C(n) : N - n >= 0
 O(n)
*/
int dist(const int V[], const int N)
{
 int M,m,n;
 for(M=m=V[0], n=1 ; n < N ; n++)
   {
     M = (V[n] > M)?V[n]:M;
     m = (V[n] < m)?V[n]:m;      
   }
 return (M-m);
}

#define MAX 1000
int main (int argc, char **args)
{
 int N=0;
 int V[MAX];
 for ( ; cin >> V[N]; N++);
 cout << dist(V,N) << endl;
}


Salida de pantalla

Código [Seleccionar] Expandir

-5 -5 -4
1

Otro

Código [Seleccionar] Expandir

-5 25 -2 -3
30

Algunos comentarios antes:

• 
  Recomendable: Nombres cortos y significativos, M "grande" para maximo, m "pequeña" para minimo, cuando sea posible.
  
• Recomendable: No usar caracteres que no sean ANSI en los fuentes (ó,í..). Dependiendo de la configuración, los compiladores pueden no procesar bien el fuente
  
• 
  Recomendable: separar el proceso de computo (hallar distancias) de la IO (scanf, printf)
  
• 
  Se exije al menos un elemento en el array. Parece que no pero esta da problemas en las inicializaciones... a 1, no a 0.
  
• 
  Si el vector tiene elementos repetidos, la respuesta no es unica. i.e en -3,-3, puede ser 0,1,-1
  
• 
  Se pide la distancia entre posiciones M,m, no entre valores V[M],V[m]
  
• Para un curso elemental, obviar los comentarios de especificación.

Código (c) [Seleccionar] Expandir


#include <stdio.h>

/*
  P : N > 0
  Q : d = M - m
  where
  V[M] = max i : 0 <= i < N : V[i]
  V[m] = min i : 0 <= i < N : V[i]

  I : Q[N/n] and 0 <= M,m < n , 1<= n <= N and *
  V[M] = max i : 0 <= i < n : V[i]
  V[m] = max i : 0 <= i < n : V[i]   

  *  M,m for efficiency reasons.
  C(n) : N - n >= 0
  O(n)
*/
int dist(const int V[], const int N)
{
  int M,m,n;
  for(M=m=0, n=1 ; n < N ; n++)
    {
      M = (V[n] > V[M])?n:M;
      m = (V[n] < V[m])?n:m;     
    }
  return (M-m);
}

#define MAX 1000
int main (int argc, char **args)
{
  int N=0;
  int V[MAX];
  while (scanf("%d",&V[N])!=EOF) N++;
  printf("%d\n",dist(V,N));
}


Ejemplo de salida

Código [Seleccionar] Expandir


-5
-3
-1
1
3
5
7
9
11
13
15
10

Valores introducidos a mano. El ultimo valor es la distancia 10 (computada) entre el elemento -5 y 15