Ir para o conteúdo
Erivaldo Lourenço

codigo muito lento...

Mensagens Recomendadas

Erivaldo Lourenço

Boa noite pessoal, tou com um preblema no seguinte codigo :

#include <stdio.h>
#include <stdlib.h>
main()
{

   int N,Soma,Valor=0,i=0,j=0,k=0,a;

   scanf("%d",&N);

   int Casa[N];

   for(; i<N; i=i+1)
   {
       scanf("%d",&Casa[i]);
   }

   scanf("%d",&Soma);

   while(j<=N-1)
   {
       k=0;
       while(k<=N-1)
       {

           if(Casa[j]+Casa[k]==Soma)
           {
               a=k;
               k=N+1;
               i=j;
               j=N+1;
               printf("%d %d\n",Casa[i],Casa[a]);
           }
           k=k+1;

       }
       j=j+1;
   }
}

O problema é o seguinte, é dado um numero que indica quantos números vai ter o conjunto, e logo depois de digitar esses números, é dado a um outro inteiro indicando a soma de dois desses do conjunto, exemplo...

5 - quantidade de inteiros

3

5

9

11

13

16 - soma de dois numero no conjunto, no caso 11 + 5

Detalhe os números, são em ordem crescente e essa soma é única.

O meu problema é q o código está lento, ta na ordem de n², tem como eu fazer isso de outra forma, só queria uma dica de algum assunto q devo estudar pra melhorar o código, agradeço muito desde já!

Editado por pmg
GeSHi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não vejo nada no teu código que leve a demorar muito tempo

até porque fiz isso num código melhorado e a resposta é praticamente instantâneo (se bem que as melhorias não tem haver com o processo realizado)

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

#define BUFFER_SIZE 256
#define LIST_MIN_SIZE 2
#define LIST_MAX_SIZE 10

int read_int(const char * message, ...)
{
 char buffer[bUFFER_SIZE];
 char fmessage[bUFFER_SIZE];
 int ok, value;
 va_list ap;

 va_start (ap, message);
 vsnprintf(fmessage, BUFFER_SIZE, message, ap);
 va_end (ap);

 do {
   printf("%s", fmessage);
   fflush(stdout);
   fgets(buffer, BUFFER_SIZE, stdin);
   ok = sscanf(buffer, "%d", &value);
 } while (!ok);

 return value;
}

int main()
{
 int min = 0, max = 0, size = 0, sum = 0, i = 0, j = 0;

 do {
   size = read_int("insira o número de elmentos do array (entre %d e %d) : ", LIST_MIN_SIZE, LIST_MAX_SIZE);
 } while (size < LIST_MIN_SIZE || size > LIST_MAX_SIZE);
 int list[size];

 min = read_int("insira o limite minimo dos números a serem inseridos : ");
 do {
   max = read_int("insira o limite maximo dos números a serem inseridos (min : %d): ", min + size);
 } while (max < min + size);

 for(; i < size; i++) {
   do {
     list[i] = read_int("insira o número de indice %d do array (entre %d e %d) : ", i, min, max);
   } while (list[i] < min || list[i] > max);
 }

 sum = read_int("insira o valor da soma a ser verificado: ");

 for (i = 0; i < size; i++) {
   for (j = i + 1; j < size; j++) {
     if (list[i] + list[j] == sum)
       printf("e possivel obter o valor %d atraves dos elementos de indice %d e %d (%d e %d)\n", sum, i, j, list[i], list[j]);
   }
 }

 return 0;
}


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Uma maneira de melhorar a performance do código para O(n) (ou O(n log n) se for preciso ordenar) é

0) ordenar o array se necessario

1) somar os valores das pontas (o primeiro e o ultimo)

2) se for igual ao pretendido: parar -- ou, se for para achar mais pares, "apertar" o array nos dois lados

3) se for maior: "apertar" o array à direita

4) se for menor: "apertar" o array à esquerda

5) se ainda houver elementos ir para ponto 1

Para o teu exemplo, somava-se o 3 e o 13 obtendo 16 (o par 3, 13 é uma solução)

depois soma-se o 5 e 11. Também é solução

depois o array fica só com 1 elemento e podemos parar o algoritmo

Se a ideia for encontrar um par que some 20

1) soma 3 e 13: é pouco

4) aperta à esquerda

1) soma 5 e 13: é pouco

4) aperta à esquerda

1) soma 9 e 13: é muito

3) aperta à direita

1) soma 9 e 11: uma solução


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.