Como descobrir qual o menor número?

[Porval's]

Olá,

estou com um problema de lógica. Eu preciso descobrir qual o menor entre 5 números.

É um vetor com cinco espaços, que são preenchidos com números randomicos de 0 a 10. Qual o jeito menos complicado de descobrir o menor entre eles?

O único jeito que pensei seria comparando todo o vetor dentro de um laço 'for' e fazendo a comparação com 'if'. Ficaria muiiito extenso para algo tão simples.

Alguém sabe algo mais simples!?

Grato.

[duda3005]

Bem.. voce quer a resposta ou a LOGICA pra tentar resolver?

a lógica acho que é mais ou menos assim...

voce tem um vetor com 5 posiçoes... ou seja ...

v[0] v[1] v[2] v[3] v[4]

certo.... percebe-se que todos eles são do MESMO VETOR .. ou seja v onde i é a posição do elemento...

com um loop ... voce poderá incrementar ou decrementar o i ... para poder fazer ele mudar de posição toda vez que o loop rodar...

voce precisara de uma variaver extra ... tipo... sei la.... MENOR para armazenar o menor numero...

agora voce tenta monta ai ... com FOR ou WHILE ...

PS: poste o que voce ja tem.... se ja tiver feito algo... dai agente ve como voce pode arrumar, otimizar ou algo do tipo...

abrac.

[Sir Jhonn]

um jeito não muito chique é fazer com IF...

tipo

if (v[1] < v[2] && v[3] && v[4] && v[5]) {

prinft("o vetor 1 é o menor");

...

faz ele testar todos o 5 ;P

[thiago_hmc]

declara menor

declara contador

menor<-v[0]

para contador=1 ; contador < 5 ; contador<-contador +1

{

se v<menor

menor<-v

}

imprime menor

Acredite esse é um algoritmo ótimo, não é possível resolvê-lo com menos de n-1 comparações. Caso alguém saiba como por favor me diga! =p

É possível fazê-lo recursivamente, se se interessar avise e eu posto a ideia.

Abraços...

[SuperNov4]

#include <stdio.h>

int main()
{
    const int n[5] = { 2, 3, 1, 2, 0 };
    unsigned int min, x;

    min = ~0;
    for(x = 0; x < 5; x++)
    {
        if(n[x] < min)
        {
            min = n[x];
        }
    }

    printf("Valor minimo encontrado: %d\n\n\n", min);
}

[Adrianled]

O código

#include <stdio.h>
#include <conio.h>

main(){

//definição de variaveis       
int i, vetor[5], elem;

//Entrada de dados
for(i=0; i<5; i++)
{
   printf("\n\n Informe o %d%c valor : ", i+1, 167);  
   scanf("%d", &vetor[i]); 
}
   printf("\n\n\n");
   elem = vetor[0];

//Processamento
for(i=1; i<5; i++)
{       
   if(vetor[i] < elem)
   {
   elem = vetor[i];           
   }  
}
//saida em tela
   printf("\n O menor elemento e = %d \n\n\n", elem);

system("pause");
}

[Porval's]

Valeu galera, bastante gente ajudou, porém infelizmente eu não expliquei direito.

Desculpem pelo erro.

Vamos lá então:

Eu preciso fazer um escalonador FCFS/FIFO, tenho 5 processos com Hora de chegada e duração do processo aleatórios. Eu preciso, na verdade, colocar todos os processos na ordem crescente de hora de chegada.

Por ex:

P1 = chegada 5

P2 = chegada 0

P3 = chegada 2

P4 = chegada 4

P5 = chegada 1

preciso deixar assim:

0

1

2

4

5

Sou péssimo em lógica. Para fazer calculos com um escalonador FIFO eu preciso pegar

o menor, dois o segundo menor...etc..

Será que eu preciso fazer todas essas comparações de menor/maior para fazer essa cálculo?

Grato.

EDIT:

tive uma ideia agora:

usar o for para descobrir o menor dentre os 5 e usar o menor para calcular o fifo

depois usar novamente o for, mas retirando o ultimo numero descoberto.

assim continuar até comparar todos...

Talvez esse comparador do Thiago_hmc seja eficiente, mas gostei também do código do Adrianled

Espero resposta.

[Lawsann]

Porval,

você poderia usar um algoritmo de ordenação para ordenar seu vetor e poder acessar os elementos em ordem. Algoritmos de ordenação são muitos, e para um vetor tão pequeno qualquer um seria útil, não necessitaria de um tão sofisticado (procure na literatura por Seleção, Inserção, Shellsort, Bubblesort, Quicksort, Heapsort, Mergesort, Heapsort - o que lhe achar mais conveniente).

Mas se tratando de um escalonador você poderia usar uma fila de prioridades, assim poderia tratar ainda da inserção de novos elementos no vetor de uma forma bem elegante e eficiente. Um exemplo bom seria a estratégia Heap.

[Porval's]

Porval,

você poderia usar um algoritmo de ordenação para ordenar seu vetor e poder acessar os elementos em ordem. Algoritmos de ordenação são muitos, e para um vetor tão pequeno qualquer um seria útil, não necessitaria de um tão sofisticado (procure na literatura por Seleção, Inserção, Shellsort, Bubblesort, Quicksort, Heapsort, Mergesort, Heapsort - o que lhe achar mais conveniente).

Mas se tratando de um escalonador você poderia usar uma fila de prioridades, assim poderia tratar ainda da inserção de novos elementos no vetor de uma forma bem elegante e eficiente. Um exemplo bom seria a estratégia Heap.

Lawsann, eu achei alguns exemplos de Heap mas não tenho ideia de como implementar no meu código atual. Fiquei meio perdido, porque é a primeira vez que vejo esses algoritmos.

Poderia ser mais específico?..

Código do Heapsort:

void heapsort(tipo a[], int n)
{
   int i = n/2, pai, filho;
   tipo t;

   for (;
   {
      if (i > 0)
      {
          i--;
          t = a[i];
      }
      else
      {
          n--;
          if (n == 0)
             return;
          t = a[n];
          a[n] = a[0];
      }

      pai = i;
      filho = i*2 + 1;

      while (filho < n)
      {
          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho]))
              filho++;
          if (a[filho] > t)
          {
             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;
          }
          else
             break;
      }
      a[pai] = t;
   }

}

Obrigado!

[Lawsann]

Ok. Vamos lá.

Heap é uma estrutura de dados definida como uma sequência de itens ( arranjo de n posições - c[1], c[2], c[3], ... , c[n]), tal que c >= c[2i] && c >= c[2i + 1], ou seja, um item que esteja na posição i é maior ou igual que os itens que se encontram nas posições 2i e 2i + 1 , para todo i indo de 1 até n/2. Esta estrutura pode ser melhor vislumbrada se a sequência de chaves for desenhada em uma árvore binária completa.

A figura a seguir mostra um heap para o seguinte vetor:

100, 30, 70, 25, 15, 10, 60

Cada item de uma árvore é chamado nó. O nó na posição 1 é o nó raiz. Há ainda uma relação na árvore binária completa que é a de nó pai e nós filho: se o item da posição k/2 é um nó pai, o item na posição k é o nó filho. Exemplo: na imagem que anexei: o nó na posição 2 (conteúdo = 30) é o nó pai dos nós das posições 4 (conteúdo = 25) e 5 (conteúdo = 15). Repare que, como enunciado lá em cima na definição de heap, os itens na posição 2x2 e 2x2 + 1 são maiores que o item na posição 2 (substituindo i por 2). Vendo de outra forma este enunciado: os nós pais são sempre maiores ou iguais que os nós filhos.

Esta estrutura é uma fila de prioridades chamada heap. Não é de uma implementação das mais simples, mas é muito eficaz. Tão eficaz que é até mesmo usada para ordenação. Veja: nesta fila de prioridades, garantimos que o primeiro termo é sempre o maior de todo o arranjo, certo? No entanto, os itens que se seguem não estão necessariamente em ordem. Com base nesse raciocínio, o Heapsort (método de ordenação que usa a estrutura heap - viu a diferença entre heap e heapsort? ) rearranja os elementos do vetor de modo a ordená-los, com um tempo de execução na ordem de nlogn (nada mal, para quem não tem muita intimidade com análise de complexidade). Logo, este algoritmo que você achou e postou aí, é uma adaptação do heapsort para a linguagem c. Vou tentar dar uma pincelada de como este algoritmo acima funciona.

Primeiro ele recebe como parâmetro o arranjo (ponteiro para vetor) a, e o tamanho do arranjo n. Ele começa do item que está no meio do vetor: como estamos em c, e aqui os vetores começam na posição 0, o meio estará em n/2 - 1.

Veja:

int i = n/2

      if (i > 0)
      {
          i--;
          t = a[i];
      }

Depois ele olha para os nós filhos do item que está no meio do vetor. Primeiro para o filho da direita, que tem o índice maior que o da esquerda.

      pai = i;
      filho = i*2 + 1;

No trecho a seguir ele executa a seguinte ação: caso algum filho seja maior que o pai, então troque-os de lugar. Desse modo, o algoritmo estará montando a estrutura heap, organizando o vetor de acordo com ela, certo?

      while (filho < n)
      {
          if ((filho + 1 < n)  &&  (a[filho + 1] > a[filho]))
              filho++;
          if (a[filho] > t)
          {
             a[pai] = a[filho];
             pai = filho;
             filho = pai*2 + 1;
          }
          else
             break;

Então após olhar o item que está na metade do caminho e seus filhos, ele passa para o item imediatamente anterior a ele. E faz a mesma análise... assim segue até chegar no nó raiz e quando terminar terá a estrutura heap pronta. Neste momento, i será 0 e então o seguinte código será contemplado:

      else
      {
          n--;
          if (n == 0)
             return;
          t = a[n];
          a[n] = a[0];
      }

Isto consiste na estratégia do heapsort em ordenar o vetor. Pense: se tenho a estrutura heap pronta, o item na posição 0 será o maior. Se eu colocá-lo na última posição do vetor (posição n - 1) e montar outro heap com os n - 1 itens restantes, teremos na posição 0 o segundo maior item. Se eu colocá-lo, por sua vez, na penúltima posição do vetor e montar outro heap com os n - 2 itens restantes, teremos na posição 0 o terceiro maior item. E assim por diante, achando os maiores itens e os colocando nos devidos lugares da ordenação.

Assim funciona o heapsort, usando a estratégia do heap. São coisas diferentes, sacou? Mas para ordenar um vetor tão pequeno, lhe indicaria um algoritmo mais simples. O heap eu usaria mais como estrutura de organização do vetor mesmo, para tratar os elementos do escalonador, de modo que você atribuiria mais prioridade a alguns processos. Os processos respeitariam a hierarquia da fila de prioridades do escalonador. Espero ter ajudado amigo e me disponho para maiores esclarecimentos.

[duda3005]

bom.... acho bubblesort mais fácil...

mais dai vai de cada um...

for (i=0; i<5; i++){

if (v > v[i+1]) {

aux = v;

v = v[i+1];

v[i+1] = aux;

}

}

acho que é isso...

[Porval's]

Olá,

me desculpem ficar tanto tempo sem responder o tópico. Eu tive alguns contratempos e não pude mais visitar o fórum.

Mas voltando ao assunto original. eu ordenei o vetor mas estou com outro problema.

Como estou fazendo um escalonador FIFO eu preciso alem de ordenar o vetor da "Hora da chegada do processo" precisa manter seu respectivo "tempo de duração"

Por exemplo:

V1 V2

53 8

34 9

89 46

37 4

58 24

Preciso deixar assim:

34 9

37 4

53 8

58 24

89 46

Eu preciso ordenar o Vetor 1, mas mantendo seu respectivo valor do vetor 2.

Eu não consigo manter seu valor do 2, esse é um problema para mim agora.

Eu vou colocar o código completo aqui para vocês verificarem: (o problema está em azul)

// Variables:
        // hoa : Hour of Arrival
        // dop : Duration of Process
        // wt  : Wait Time
        // rt  : Response Time
        // uid : User ID


#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "windows.h"

#define NUM      5
#define VALIDO   1
#define REPETIDO 0
#define VET      5
#define TAM 5

struct escalonador
{
    int wt[VET], 
        hoa[VET], 
        dop[VET], 
        rt[VET],
        uid[VET];
}process;

int temp[5];

void clrscr (void ) {
    HANDLE hStdOut = GetStdHandle(STD_OUTPUT_HANDLE);
    COORD coord = {0, 0};
    DWORD count;
    CONSOLE_SCREEN_BUFFER_INFO csbi;
    GetConsoleScreenBufferInfo(hStdOut, &csbi);
    FillConsoleOutputCharacter(hStdOut, ' ', csbi.dwSize.X * csbi.dwSize.Y, coord, &count);
    SetConsoleCursorPosition(hStdOut, coord);
}


void setcolor (int n) {
    HANDLE hConsoleOutput;
    hConsoleOutput = GetStdHandle (STD_OUTPUT_HANDLE);
    SetConsoleTextAttribute (hConsoleOutput, n);
}


[COLOR=Blue][B]void OrdenaVetor(int vet[])
{
  int aux, i=0, j=0,aux2;

  for(i=0; i<TAM; i++)
  {

    for(j=0; j<TAM; j++)
    {
      if(vet[i]<vet[j])
      {

        aux=vet[i];
        temp[i]=process.dop[j];
        vet[i]=vet[j];
        vet[j]=aux;


      }
    }
  }
}


void esc_fifo(){
 OrdenaVetor(process.hoa);

 int i;


  for(i=0; i<TAM; i++){
    printf(" HOA  %d\t",process.hoa[i]);
    printf(" DOP  %d\n\n",temp[i]);
  }

  printf("\n\n\n");

    getchar();

}    [/B][/COLOR]

int _tmain(int argc, _TCHAR* argv[]){

    int X, Y, status;
    setcolor(15);
    puts ("AQUI estão OS DADOS DE TODOS OS 5 PROCESSOS:\n\n");
    srand(time(NULL));

    for (X=0; X < 5; X++){
        process.hoa[X]  = rand() % 100;
        process.dop[X]  = rand() % 50;
    }

    for (X = 0; X < 5; X++) {

        do {

            process.uid[X] = rand() % (2001-1000)+1000;
            status = VALIDO;

            for (Y = 0; Y < X; Y++)
            {
                if (process.uid[X] == process.uid[Y])
                status = REPETIDO;
            }

           } while (status == REPETIDO);
       setcolor(15);
       printf ("HOUR OF ARRIVAL = %d \nDURATION OF PROCESS = %d \n",process.hoa[X], process.dop[X]);    
       setcolor(10);
       printf ("USER ID = %d\n\n",process.uid[X]);

    }
    getchar();
    clrscr();
    setcolor(10);
    puts ("ESCOLHA QUAL ESCALONADOR QUER USAR:\n\n");
    puts ("1 - FCFS [FIRST COME, FIRST SERVED]");
    esc_fifo();
    getchar();

}

Grato.