Jump to content
Erivaldo Lourenço

codigo muito lento...

Recommended Posts

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á!

Edited by pmg
GeSHi

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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!

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.