[SOLUCIONADO] arreglos y sus elementos repetidos

[JarolGarcia]

sea un arreglo entero
int A[8] ={2,4,7,2,3,4,7,7}

nos debe indicar en orden sin repetir los elementos:
el elemento 2 se repite 2 veces
el elemento 4 se repite 2 veces
el elemento 7 se repite 3 veces
el elemento 3 se repite 1 veces

quien lo intenta.....saludos

[eferion]

No nos tomes por tontos... eso "no se intenta" o se hace o no se hace... otra cosa es que tu no sepas hacerlo e intentes que te hagamos la tarea.

Ponte a hacerlo porque, en caso contrario, no vas a aprender en la vida. Si al hacerlo te aparecen dudas, lo cual sería totalmente lógico, entonces vienes y preguntas tus dudas... que gustosamente te intentaremos solucionar.

Un saludo.

[JarolGarcia]

Iniciado por JarolGarcia

sea un arreglo entero
int A[8] ={2,4,7,2,3,4,7,7}

nos debe indicar en orden sin repetir los elementos:
el elemento 2 se repite 2 veces
el elemento 4 se repite 2 veces
el elemento 7 se repite 3 veces
el elemento 3 se repite 1 veces

quien lo intenta.....saludos

.......lo que quiero decir es:

#include<fstream.h>
#include<conio.h>
void main()

{
int A[8],i,j,cont=0;
A[8] ={2,4,7,2,3,4,7,7}
cout<<"\n";
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(a[i]==a[j])
cont++;
}
cout<<"el elemento "<<a[i]<<" se repite "<<cont<<" veces\n";
cont=0;
}
getch();
}

el problema es que me vota asi por ejemplo A[8] ={2,4,7,2,3,4,7,7}
2 se repite 2 veces
4 se repite 2 veces
7 se repite 3 veces
2 se repite 2 veces
3 se repite 1 veces
4 se repite 2 veces
7 se repite 3 veces
7 se repite 3 veces
pero yo quiero que me vote simplemente asi
2 se repite 2 veces
4 se repite 2 veces
7 se repite 3 veces
3 se repite 1 veces

[eferion]

Lo primero, intenta poner ejemplos que compilen. El código que has puesto tiene bastantes errores: variables no declaradas, falta un punto y coma y los includes están mal. Además de eso, es importante decorar el código con las etiquetas "HighLight", para que sea legible... también es bastante importante tabular el código correctamente... esto último no se si lo has hecho o no porque tal y como está el código no se puede saber, pero lo pongo por si acaso.

Hablando de tu problema: Dado que te piden que no repitas la salida, no tiene sentido que, para cada número, recorras el vector desde el principio contando apariciones. Más bien deberías:

1. Para cada número buscas coincidencias en posiciones anteriores:
1a. Si existen pasas al siguiente número puesto que este ya está procesado
1b. Si no se han encontrado, buscas y cuentas las coincidencias que hay en posiciones siguientes... una vez has terminado, muestras el mensaje

Código C++:

#include<iostream>
 
int main()
{
  int cont, pasar;
  int i, j;
 
  int a[] = {2, 4, 7, 2, 3, 4, 7, 7};
  const int N = sizeof( a ) / sizeof( int );
 
  std::cout << "\n";
  for ( i = 0; i < N; i++ )
  {
    pasar = 0;
    for ( j = i; j-- && !pasar; )
      pasar = a[i] == a[j];
 
    if( !pasar )
    {
      for( j=i, cont=0; j < N; ++j )
        cont += a[i] == a[j];
 
      std::cout << "el elemento " << a[i] << " se repite " << cont << " veces\n";
    }
  }
}
 

[lareto]

No quiero complicarle la vida a JarolGarcia con una versión más compleja que la que pueda asimilar, pero me parece que puede resultar interesante hacer una comparación entre una solución relativamente simple y artesanal, en estilo C (para lo que tomo como ejemplo y acomodando un poco la respuesta de eferion), y otra en estilo C++.

Yo creo que el estilo C++ tiene una ventaja inmediata: es mucho más fácil pensar en una solución y esa solución es muy fácil de hacer eficiente, mientras que la solución en estilo C puede no ser difícil de pergeniar, pero es más difícil de hacer eficiente o, por lo menos, se necesita bastante más esfuerzo y reinventar varios paraguas para conseguir una solución equivalente. Mi idea es que para obtener una solución eficiente en C++ no hace falta ser demasiado inteligente, sólo estudiar un poco más.

Va el ejemplo de comparación, que espero pueda servirle a alguien.

Para el que quiera compilar y ejecutar el programa, va a necesitar un compilador conforme con el estándar C++11 y un poco de paciencia, porque la prueba así como está en mi máquina se demora casi un minuto entero.

Código C++:

#include <iostream>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <chrono>
#include <iomanip>
#include <cstdlib>
 
 
std::unordered_map<int, int> estilo_cpp(int N)
{
    std::unordered_map<int, int> m;  // las funciones devuelven un map para
                                     // no tener que mostrar con cout
                                     // los miles de valores
 
 
    std::minstd_rand0 generator;     // llena un vector con elementos al azar
 
    std::vector<int> v;
    v.reserve(N);
    for(int i=0; i<N; ++i) {
        v.push_back(generator()%N);
    }
    std::sort(std::begin(v), std::end(v));  // comienza el procese real
 
    int cont = 0;
 
    for(auto i=std::begin(v), j=std::end(v); i!=j; i+=cont) {
        auto rango = std::equal_range(i, j, *i);
        cont = std::distance(rango.first, rango.second);
 
        m[*i] = cont;
    }
 
    return m;
}
 
 
std::unordered_map<int, int> estilo_c(int N)
{
    int cont, pasar;
    int i, j;
    std::unordered_map<int, int> m;  // lo mismo que en la función de arriba
 
    std::minstd_rand0 generator;
 
    int* a = new int[N];
    for(int i=0; i<N; ++i) {
        a[i] = generator()%N;     // llena el array con valores al azar
    }
 
    for ( i = 0; i < N; i++ ) {   // comienza el proceso real
        pasar = 0;
        for ( j = i; j-- && !pasar; )
            pasar = a[i] == a[j];
 
        if( !pasar ) {
            for( j=i, cont=0; j < N; ++j )
                cont += a[i] == a[j];
 
            m[i] = cont;
        }
    }
 
    delete[] a;
    return m;
}
 
 
int main()
{
    using namespace std::chrono;
    steady_clock::time_point t1;
    duration<double> demora1, demora2;
    std::unordered_map<int, int> m1, m2;
 
    for(int n=1; n<300000; n*=2) {
        std::cout << "n = " << n << '\n';
 
        t1 = steady_clock::now();
        m1 = estilo_c(n);
        demora1 = duration_cast<duration<double>>(steady_clock::now() - t1);
 
        t1 = steady_clock::now();
        m2 = estilo_cpp(n);
        demora2 = duration_cast<duration<double>>(steady_clock::now()- t1);
 
        std::cout << std::setprecision(6) << std::fixed;
        std::cout << "estilo_c()  : " << demora1.count() << " segundos\n";
        std::cout << "estilo_cpp(): " << demora2.count() << " segundos\n";
        std::cout << "diferencia relativa = " << (demora1.count()-demora2.count())/demora2.count() * 100 << " %\n" << std::endl;
        // a partir de 128 elementos las diferencias relativas aumentan proporcionalmente con n.
        // más allá de 32.000 elementos, estilo_c() se hace inviable.
    }
 
}
 

[eferion]

Iniciado por lareto

No quiero complicarle la vida a JarolGarcia con una versión más compleja que la que pueda asimilar, pero me parece que puede resultar interesante hacer una comparación entre una solución relativamente simple y artesanal, en estilo C (para lo que tomo como ejemplo y acomodando un poco la respuesta de eferion), y otra en estilo C++.

No era mi intención complicarle la vida... explico los pasos y pongo un código que, si bien funciona, no es algo típico que alguien pueda limitarse a copiar y pegar... tiene detalles que cantan.

La idea es que tenga un ejemplo que le sirva de base... pero al final tiene que ser él el que elabore una solución funcional.

Iniciado por lareto

Yo creo que el estilo C++ tiene una ventaja inmediata: es mucho más fácil pensar en una solución y esa solución es muy fácil de hacer eficiente, mientras que la solución en estilo C puede no ser difícil de pergeniar, pero es más difícil de hacer eficiente o, por lo menos, se necesita bastante más esfuerzo y reinventar varios paraguas para conseguir una solución equivalente. Mi idea es que para obtener una solución eficiente en C++ no hace falta ser demasiado inteligente, sólo estudiar un poco más.

Coincido contigo en parte.

En C se pueden conseguir soluciones mucho más eficientes que C++... pero ello te obliga a reinventar la rueda varias veces, lo cual pocas veces compensa, hasta aquí conforme.

Sin embargo eso de que para programar C++ no hace falta ser demasiado inteligente... es distinto. Creo que para controlar C++ tienes que pensar de forma más abstracta a como se hace con C, pero de ahí a insinuar que programar en C++ es más fácil...

Iniciado por lareto

Va el ejemplo de comparación, que espero pueda servirle a alguien.

He optimizado un poco tu función C++, lo cual refuerza la teoría de que con un buen diseño en C++ es más fácil aplicar optimizaciones (esta nueva versión es un 25% más rápida):

Código C++:

std::unordered_map<int, int> estilo_cpp(int N)
{
    std::unordered_map<int, int> m;  // las funciones devuelven un map para
                                     // no tener que mostrar con cout
                                     // los miles de valores
 
 
    std::minstd_rand0 generator;     // llena un vector con elementos al azar
 
    std::vector<int> v;
    v.reserve(N);
    for(int i=0; i<N; ++i) {
        v.push_back(generator()%N);
    }
 
    std::map< int, int > temp;
    for( auto it = m.begin( ); it != m.end( ); ++it )
      temp[ it->first ]++;
 
    for( auto it = temp.begin( ); it != temp.end( ); ++it )
      m[it->first] = it->second;
 
    return m;
}
 

Un saludo.

[lareto]

Iniciado por eferion

Coincido contigo en parte.

En C se pueden conseguir soluciones mucho más eficientes que C++...

Bueno, no, yo no dije eso.
Algunas veces se podrán conseguir soluciones más eficientes en C y otras veces no. Incluso creo que es más probable obtener soluciones más eficientes en C++ que en C.

...pero de ahí a insinuar que programar en C++ es más fácil...

Otra vez discrepamos; yo no quise insinuar que programar en C++ es más fácil que programar en C, estoy seguro que es más fácil.

He optimizado un poco tu función C++... (esta nueva versión es un 25% más rápida)

Esta nueva versión es más rápida porque no hace nada. Pero de todos modos, si al corregirla conservas la idea, no será más rápida; las dos son de una complejidad O(log N) pero la "optimizada" tendría el doble de pendiente, demoraría el doble que mi versión.

[eferion]

Iniciado por lareto

Esta nueva versión es más rápida porque no hace nada. Pero de todos modos, si al corregirla conservas la idea, no será más rápida; las dos son de una complejidad O(log N) pero la "optimizada" tendría el doble de pendiente, demoraría el doble que mi versión.

Si y no... Es cierto que la versión que he puesto al final no funciona... cosas de montar el código directamente en el foro... pero no pasa nada, pongo un ejemplo completo, compilado y probado... ahora si puedo compilar :)

Código C++:

std::unordered_map<int, int> estilo_cpp1(std::vector< int > v)
{
    std::unordered_map<int, int> m;  // las funciones devuelven un map para
                                     // no tener que mostrar con cout
                                     // los miles de valores
 
 
 
    std::sort(std::begin(v), std::end(v));  // comienza el procese real
 
    int cont = 0;
 
    for(auto i=std::begin(v), j=std::end(v); i!=j; i+=cont) {
        auto rango = std::equal_range(i, j, *i);
        cont = std::distance(rango.first, rango.second);
 
        m[*i] = cont;
    }
 
    return m;
}
 
std::unordered_map<int, int> estilo_cpp2(std::vector< int > v)
{
    std::unordered_map<int, int> m;  // las funciones devuelven un map para
                                     // no tener que mostrar con cout
                                     // los miles de valores
 
    std::sort(std::begin(v), std::end(v));  // comienza el procese real
    for( auto it = v.begin( ); it != v.end( ); ++it )
      m[ *it ]++;
 
    return m;
}
 
int main()
{
  using namespace std::chrono;
  steady_clock::time_point t1;
  duration<double> demora1, demora2;
  std::unordered_map<int, int> m1, m2;
 
  std::minstd_rand0 generator;     // llena un vector con elementos al azar
 
  for(int n=1; n<30000000; n*=2)
  {
    std::cout << "n = " << n << '\n';
    std::vector<int> v;
    v.reserve( n );
    for ( int i = 0; i < n; ++i )
    v.push_back ( generator() % n );
 
    t1 = steady_clock::now();
    m1 = estilo_cpp1(v);
    demora1 = duration_cast<duration<double>>(steady_clock::now() - t1);
 
    t1 = steady_clock::now();
    m2 = estilo_cpp2(v);
    demora2 = duration_cast<duration<double>>(steady_clock::now()- t1);
 
    std::cout << std::setprecision(6) << std::fixed;
    std::cout << "estilo_cpp1(): " << demora1.count() << " segundos\n";
    std::cout << "estilo_cpp2(): " << demora2.count() << " segundos\n";
    std::cout << "diferencia relativa = " << (demora1.count()-demora2.count())/demora2.count() * 100 << " %\n" << std::endl;
  }
}
 

...conseguimos exactamente la misma salida y con una mejora del rendimiento que varía... con pocos elementos he llegado a una mejora cercana al 2000% (poco fiable son procesos muy rápidos y cualquier interrupción dispara los tiempos) pero con cifras más altas la mejora se situa en torno al 12% - 15%.

Por cierto, he sacado la generación del vector fuera de las funciones por dos motivos:

1. Su generación no afecta a la medida de tiempos (medidas más precisas)
2. Ambas funciones van a trabajar con la misma colección de datos.

Sobre el motivo de usar el mapa... pues no se, como no podía probarlo tampoco tenía muy claro el impacto que podía tener con respecto a tu versión... esta mañana lo he probado y efectivamente rueda un 20% más lento (aprox.), cosas del directo.

Un saludo

[lareto]

Me cito a mí mismo...

Yo creo que el estilo C++ tiene una ventaja inmediata: es mucho más fácil pensar en una solución y esa solución es muy fácil de hacer eficiente, mientras que la solución en estilo C puede no ser difícil de pergeniar, pero es más difícil de hacer eficiente o, por lo menos, se necesita bastante más esfuerzo y reinventar varios paraguas para conseguir una solución equivalente. Mi idea es que para obtener una solución eficiente en C++ no hace falta ser demasiado inteligente, sólo estudiar un poco más.

Y me cito textualmente por dos motivos; el primero es para plantarme en la cara que puse pergeniar, así, con 'ni', y el segundo es para insistir:

- Idear una solución C++ suele ser más fácil que idear una solución C.

- Hacer eficiente (que no es lo mismo que optimizar) una solución C++ es más fácil que hacer eficiente una solución C.

El ejemplo que puse tenía la intención de comparar una primera solución C con una primera solución C++. Y dejando correr el ejemplo, puede verse que mientras que esa primera solución C es de grado O(N log N), su homóloga C++ es de grado O(log N). Entonces, optimizar la primera no sólo es más difícil, sino que lo prudente sería buscarse otra, con lo que se duplica el esfuerzo sólo para llegar al mismo lugar donde nos dejaba la segunda.

Otro tema es el de las optimizaciones, que vienen después de haber elegido los algoritmos y de tener todo funcionando correctamente, y, como su nombre indica, se busca mejorar lo hecho.

Y es en este asunto en donde se ha embarullado eferion.

...conseguimos exactamente la misma salida y con una mejora del rendimiento que varía...

No todavía.

Estoy seguro que mi primera versión puede optimizarse, y sí, estoy de acuerdo con que (si ya no es necesaria la comparación con la versión original de estilo C) es mejor separar la generación de datos y la función responsable del cómputo; pero si tu versión anterior trabajaba para no hacer nada, esta otra trabaja para dejar todo como está.

[eferion]

Iniciado por lareto

Estoy seguro que mi primera versión puede optimizarse

Seguro puedes estar... la versión que te he puesto es el ejemplo.

Iniciado por lareto

Idear una solución C++ suele ser más fácil que idear una solución C

totalmente de acuerdo. Es un lenguaje de más alto nivel y eso facilita las cosas.. Siguiendo la misma regla de 3, hacer lo mismo en C# o en Java suele ser muchísimo más facil que hacerlo en C++... más fácil con menos errores y en menos tiempo.

Iniciado por lareto

pero si tu versión anterior trabajaba para no hacer nada, esta otra trabaja para dejar todo como está.

La versión que he puesto genera exactamente la misma salida que la versión que tu has puesto... es decir, ante una misma entrada generan una misma salida. Si mi versión trabaja para dejar todo como está la tuya también.

Tu has tirado de std::distance para calcular el número de items repetidos y yo he ido acumulando las repeticiones en el mapa directamente... si dejase las cosas como están las salidas de ambas funciones serían diferentes.

[lareto]

No veo cómo un cambio trivial a un programa trivial, y que no produce ninguna diferencia, puede provocar tanta excitación.

Y, ah, por cierto, este es mi programa trivial, el tuyo es es el de más arriba, ¿recuerdas? Aunque puedo copiarlo aquí también:

Código:

#include<iostream>
 
int main()
{
  int cont, pasar;
  int i, j;
 
  int a[] = {2, 4, 7, 2, 3, 4, 7, 7};
  const int N = sizeof( a ) / sizeof( int );
 
  std::cout << "\n";
  for ( i = 0; i < N; i++ )
  {
    pasar = 0;
    for ( j = i; j-- && !pasar; )
      pasar = a[i] == a[j];
 
    if( !pasar )
    {
      for( j=i, cont=0; j < N; ++j )
        cont += a[i] == a[j];
 
      std::cout << "el elemento " << a[i] << " se repite " << cont << " veces\n";
    }
  }
}

Incluso, mira, en esta dirección puedes mostrarnos cómo queda todo más fácil y eficiente en C# y en Java si te apetece:
http://rextester.com/runcode

[JarolGarcia]

encontré la manera

Código:

#include <stdio.h>
#include <string.h>

int main()
{
   int arrayPrincipal[10]={1,2,3,7,4,1,7,1,2,1};
   int aux[10];
   int x,y,pos,size=10,contador;

   for(x=0;x<size;x++)
   {
      pos=0;
      contador=0;
      for(y=0;y<size;y++)
      {
         if(arrayPrincipal[x] != arrayPrincipal[y]){
            aux[pos++]=arrayPrincipal[y];
         }else{
            contador++;
         }
      }

      printf("El numero %d se repite %d veces\n",arrayPrincipal[x],contador);
      size-=contador;
     for(int u=0;u<size;u++){
     arrayPrincipal[u]=aux[u];
    }
    x--;
   }
   return 0;
}

[aguml]

perdon, me confundi.