C Maior Frequência em C

eduardobraz · 22 de novembro de 2019

Dada uma sequência de N números entre 0 e 100. Determine qual o valor de maior frequência. Caso
haja mais de um valor tenha a maior frequência, mostre o menor deles.
Entrada
Na primeira linha há um inteiro N, 1 N 1000000, representando a quantidade números. Nas N
linhas seguintes haverá um número natural entre 0 e 100 inclusive por linha.
Saída
O programa gera apenas duas linhas. Na primeira dela mostre qual foi o valor com maior frequência. E
na segunda linha, mostre a quantidade de vezes que esse número apareceu na sequência de valores. Após
a impressão deste último valor quebre uma linha. Caso haja mais de um valor tenha a maior frequência,
mostre o menor deles.
Exemplo
Entrada
10
1
7
4
29
7
4
7
8
7
29
Saída
7
4

Código <- Não sei porque funciona

//Programa 13

#include <stdio.h>

int main(){
int vetor[1000000], i, j, n, aux, k, total;

while(1){
    scanf("%d",&n);
    if(n <= 1000000 && n > 0){
      break;
    }
}

for (i = 0; i < n; i++){
    scanf("%d", &vetor);
}
for (i = 0; i < n; i++){
    for(j = i + 1; j < n; j++){
      if (vetor == vetor[j]){
        aux = vetor[j];
      }
    }
}

for (k = 0; k < n; k++){
      if (aux == vetor[k]){
        total++;
      }
}

printf("%d", aux);
printf("\n%d", total);
}

eduardobraz · 24 de novembro de 2019

Preciso de ajuda

devair1010 · 24 de novembro de 2019

@Eduardo_Braz opa , esse exercício é do uri online judge ?

https://www.urionlinejudge.com.br/judge/pt/login?redirect=%2Fpt

eduardobraz · 25 de novembro de 2019

@devair1010 Foi baseado eu acho

devair1010 · 25 de novembro de 2019

@Eduardo_Braz esse enunciado está faltando algumas palavras , por exemplo :

=============================================================================================

Dada uma sequência de N números entre 0 e 100. Determine qual o valor de maior frequência. Caso
haja mais de um valor QUE tenha a MESMA maior frequência , mostre o menor deles.
Entrada
Na primeira linha há um inteiro N, 1 < N < 1000000 , representando a quantidade DE números. Nas N
linhas seguintes haverá um número natural entre 0 e 100 , inclusive , por linha.
Saída
O programa gera apenas duas linhas. Na primeira dela mostre qual foi o valor com maior frequência. E
na segunda linha, mostre a quantidade de vezes que esse número apareceu na sequência de valores. Após
a impressão deste último valor quebre uma linha. Caso haja mais de um valor QUE tenha a MESMA maior frequência,
mostre o menor deles.

=============================================================================================

creio que precisaria das letras em vermelho , e seguindo essa ideia

lá em cima você quis dizer que não funciona ! , então se você puder usar vetores e matriz será bem mais fácil , pode ?

eduardobraz · 25 de novembro de 2019

@devair1010 Pode só que eu não sei matriz

adicionado 6 minutos depois

5 minutos atrás, Eduardo_Braz disse:

@devair1010 Pode só que eu não sei matriz

Não tenho ideia alguma de Matriz

arfneto · 25 de novembro de 2019

39 minutos atrás, Eduardo_Braz disse:

Não tenho ideia alguma de Matriz

Matriz ou vetor não acrescentam nada de especial. Trata-se apenas de uma variável que digamos

acontece um certo número de vezes então você usa o mesmo com o mesmo nome
e você numera as ocorrências chamando o número da ocorrência de índice. Só isso.

Acho que a coisa mais frequente que a gente tem disso no dia a dia é uma tabela, como uma nota fiscal, onde você tem algo como item, quantidade, descrição / preço unitário, preço total. E cada linha é um produto. Então no programa você tem uma linha por produto e nesse caso por exemplo 5 campos então você poderia declarar

tipo     nota_fiscal[10][5];

indicando por exemplo 5 colunas e dez linhas. E na linha 2 estaria então seu terceiro produto e em cada coluna estariam os campos. Nesse exemplo a última coluna é o preço total , então a quinta coluna da segunda linha teria o preço total do segundo produto, e você escreveria

nota_fiscal[2][4] = nota_fiscal[2][1] * nota_fiscal[2][3];

para indicar que o preço total do produto é o preço unitário multiplicado pela quantidade. Só isso. Quanto faz sentido você pode usar 1, 2,3 ou mais índices. Nada muda na lógica.

De volta ao seu problema

Seu caso é muito simples e na verdade não precisa usar nada "novo": use dois vetores, um com o número e outro com o número de ocorrências e pronto... E usa o óbvio número da linha para associar o valor com o número de ocorrências.

devair1010 · 26 de novembro de 2019

@Eduardo_Braz para postar seu código é melhor usar o botão <>

que está desenhado lá na barra de ferramentas da janela de postar , pois senão seu código fica faltando alguns caracteres como os [ i ] que sumiram do seu código , e usando vetores , que aqui são vetores dinâmicos , para poder criar um vetor em tempo de execução , e usar a quantidade de números escolhidos pelo usuário , senão você precisaria criar um vetor com 1 Milhão de posições e que ocuparia 4 Mega Bytes de memória , em cada um desses vetores criados , por isso optei pelos dinâmicos , e seu código poderia ser assim :

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int main(){
    int *num,*freq,*m,
        j,i,n;
    scanf("%d",&n);
    num  = (int *)malloc(n*sizeof(int));                 /* vetor dinamico para os números            */
    freq = (int *)malloc(n*sizeof(int));                 /* vetor dinamico para a frequencia          */
    m    = (int *)malloc(n*sizeof(int));                 /* vetor dinamico para o freq repetidas      */
    for(i=0; i<n; i++                  )                 /* pegar todos os n números                  */
        scanf("%d",&num[i]            );                 /* pega os números                           */
    for(i=0;i<n;i++){                                    /* testar com todos os números               */
        freq[i]=1;                                       /* o número saiu pelo menos uma vez          */
        for(j=0;j<n;j++){                                /* calculando a frequencia de cada número    */
            if(num[i] == num[j] && num[i]!=-1 && j != i){/* se repetiu e não é o mesmo e nem inválido */
                freq[i]++;                               /* incremnta a frequencia do número repetido */
                num[j]=-1;                               /* número repetido é marcado com inválido    */
            }
        }
    }
    int q=n;                                             /* preserva o valor de n                     */
    for(i=0; i<n; i++             ){                     /* percorre todos os números                 */
        while(num[i] == -1        ){                     /* enquanto neesa posição tiver o valor -1   */
            for(j=i; j<q-1;    j++){                     /* porcorre todo o vetor                     */
                num[ j] = num[ j+1];                     /* puxando os números para baixo             */
                freq[j] = freq[j+1];                     /* e a frequencia também                     */
            }
            num[q]=-2;                                   /* marca essa posição para ser descartada    */
            q--;                                         /* decrementa a quantidade de números válidos*/
        }                                                /* pois esse repetiu */
    }
    q++;                                                 /* incrementa                                */
    int aux;                       /* auxiliar no bubblesort         */
    for(i=0; i<q-1; i++           )/* percorre todo o vetor          */
        for(j=i+1; j<q; j++       )/* ordenando o vetor              */
            if( freq[i] < freq[j]){/* de forma decrescente           */
                aux     = num[ i] ;/* pega o menor número            */
                num[i]  = num[ j] ;/* troca com o próximo maior      */
                num[j]  = aux     ;/* coloca o menor depois do maior */
                aux     = freq[i] ;/* pega a menor frequencia        */
                freq[i] = freq[j] ;/* troca com a próxima maior      */
                freq[j] = aux     ;/* coloca a menor depois da maior */
            }
    for(i=0;i<q;i++){              /* poercorre todo o vetor         */
        if(freq[i]==freq[i+1]){    /* se tem duas frequencias iguais */
            if(num[i+1] < num[0])
                num[0] = num[i+1]; /* pegar o número menor que tem   */
        }                          /* a mesma frequencia             */
        else
            if(freq[i] > freq[i+1])/* se a freq seguinte for menor   */
                break;             /* sai do loop pois               */
    }                              /* já localizou o menor número    */
    printf("\n%d\n",freq[0]);
    printf("%d\n"  ,num[ 0]);
    free(m);
    /*free(freq);                                                    */
    /*  um erro no free(freq) não descobri o motivo mas td bem       */
    free(num);
    return 0;
}

arfneto · 26 de novembro de 2019

6 horas atrás, devair1010 disse:

usando vetores , que aqui são vetores dinâmicos , para poder criar um vetor em tempo de execução , e usar a quantidade de números escolhidos pelo usuário , senão você precisaria criar um vetor com 1 Milhão de posições e que ocuparia 4 Mega Bytes de memória , em cada um desses vetores criados , por isso optei pelos dinâmicos , e seu código poderia ser assim

Olá

@devair1010 é certo o que você disse sobre os vetores e tal, mas alocar um vetor ou 3 de alguns megabytes de memória não é nada assim importante. Postei aqui um programa outro dia com uma função que mostra quanto pode alocar aproximadamente de memória em um dado momento e mesmo para um computador modesto os valores são bem maores que isso. Imagine que alocar até uns 25% da memória de sua máquina não deve ser nada preocupante. Num computador com 2GB de RAM, até uns 512mb eu não me preocuparia. Teste. Claro, quando esse programa vai rodar o dia todo, ou tem outras coisas importantes rodando na máquina é saudável se preocupar

Em seu programa, o que pretendia fazer com o vetor m[]?

Classificar o vetor não é necessário. Não está no enunciado. E se o aluno perder metade do tempo fazendo isso pode comprometer os prazos a toa. Por outro lado, ao classificar durante a inserção não há razão para usar coisas como bubble sort ou quicksort ou heapsort ou xyzSort. Como você está inserindo os valores a partir do vetor vazio, apenas insira já na posição correta. Sim, seria como o insertion sort, mas bem menos: comece do fim do vetor e abra espaço para o novo na posição final. Muito mais simples de programar e faz o número mínimo de comparações sempre.

POR OUTRO LADO, não precisa de vetor nenhum...

Em 22/11/2019 às 10:48, Eduardo_Braz disse:

Dada uma sequência de N números entre 0 e 100. Determine qual o valor de maior frequência. Caso
haja mais de um valor tenha a maior frequência, mostre o menor deles

@Eduardo_Braz @devair1010 Está certo que pode ter um milhão de números, podiam ser 10 milhões, é só uma pegadinha.

Citação

Os números estão entre 0 e 100. TODOS.

Usem um vetor de 101 posições apenas. E um int para o resultado. Iniciem todas as posições com -1 e marquem os números conforme vão aparecendo... Note que até a questão do menor em caso de empate já está resolvida: o primeiro índice, já que estão naturalmente na ordem... Imagine que entraram um milhão de itens, metade zero e metade um. Ao final do programa o vetor vai ter

vetor[0] = 500 000
vetor[1] = 500 000
vetor[2] = -1

...

vetor[100] = -1

Ao ler os valores você obviamente vai mantendo registro do mais frequente. Então ao ler o último sabe que o mais frequente apareceu meio milhão de vezes. Como o vetor tem os números de frequência basta achar o primeiro que tenha essa frequência que será o menor, certo? Nesse caso 0.

arfneto · 26 de novembro de 2019

Olá

vocês tem uma solução funcionando ou quase então não há porque não mostrar outra possibilidade, eu acho.

Como eu disse, é mais simples partir dos possíveis números e não dos números fornecidos na execução:

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

int main()
{
	int N;					// o total de numeros
	int numeros[101];		// os possiveis numeros
	int maior_frequencia = INT_MIN;	// o resultado
	int i, v;				// auxiliares

	if (scanf("%d", &N) != 1) return -1; // nao leu N
	if (N < 1 || N > 1000000) return -2; // N invalido
	for (int i = 0; i <= 100; i += 1) numeros[i] = 0;	// prepara o vetor

	for (i = 1; i <= N; i += 1)
	{	// le um cara e marca
		if (scanf("%d", &v) != 1) return -3; // nao leu algum
		if (v < 0 || v > 100) return -4; // nao esta entre 0 e 100
		numeros[v] = numeros[v] + 1;
		if (numeros[v] > maior_frequencia) maior_frequencia = numeros[v];
	};	// for
	// terminou: 
	for (i = 0; i <= 100; i += 1)
	{
		if (numeros[i] == maior_frequencia)
		{
			printf("%d\n%d", i, maior_frequencia);
			return 0;	// so isso
		};	// if
	};	// for
};	// main()

Esse é o trecho importante

    if (scanf("%d", &v) != 1) return -3; // nao leu algum
    if (v < 0 || v > 100) return -4; // nao esta entre 0 e 100
    numeros[v] = numeros[v] + 1;
    if (numeros[v] > maior_frequencia) maior_frequencia = numeros[v];

Só isso. Ao final maior_frequencia vai ter o valor esperado, porque começou em INT_MIN e basta procurar no vetor numeros[] o primeiro item que tem esse número de ocorrências

Ansi C · 26 de novembro de 2019

@Eduardo_Braz Boa Tarde.

Sua maior dificuldade fica no enunciado do problema que mal editado ti prejudica ainda mais em todos os quesitos. Por sorte, o colega de fórum @devair1010 encontrou (belíssimo portal) o URI seu enunciado bem mais detalhado.

hum...

Em 22/11/2019 às 10:48, Eduardo_Braz disse:

Código <- Não sei porque funciona

//Programa 13

#include <stdio.h>

int main(){
int vetor[1000000], i, j, n, aux, k, total;

while(1){
    scanf("%d",&n);
    if(n <= 1000000 && n > 0){
      break;
    }
}

for (i = 0; i < n; i++){
    scanf("%d", &vetor);
}
for (i = 0; i < n; i++){
    for(j = i + 1; j < n; j++){
      if (vetor == vetor[j]){
        aux = vetor[j];
      }
    }
}

for (k = 0; k < n; k++){
      if (aux == vetor[k]){
        total++;
      }
}

printf("%d", aux);
printf("\n%d", total);
}

Notamos aqui (sem demora) todos os assuntos essências para resolução do problema: estruturas de fluxo, iteração e dados.

Só que logicamente mal postos, ou seja, faltou lógica.

Por exemplo; alimentar a estrutura de 1E+6 elementos para depois determinar suas frequências é uma etapa "fútil".

^{Se você não sabe eu não sei ...}

Ignore todas as soluções até o momento apresentadas (aqui ou qualquer lugar) enquanto elabora o seu próprio raciocínio (você só tem a ganhar pensando desda base) a partir do enunciado postado por @devair1010 .

Preste bastante atenção no enunciado para evita o convencimento de mais uma outra interpretação que não a do portal/professor/exame ...

"Como o seu cérebro resolve isso ...", porque a parte do assunto de C está correto.

Até...