Você está aqui: C ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) |
Como usar a busca binária em C - Pesquisa binária na linguagem CQuantidade de visualizações: 476 vezes |
A busca binária, ou pesquisa binária, é um algoritmo eficiente para encontrar um item em uma lista (vetor ou array) ordenada. Sim, os itens devem, obrigatoriamente, estar ordenados. O processo é bem simples. A busca binária começa a partir do meio da lista e compara o item nesta posição com o valor sendo pesquisado. Se o valor não for encontrado e for menor que o item no meio da lista, o algoritmo passa para a porção à esquerda da lista, eliminando, assim, metade dos elementos do vetor ou array (a porção maior que o valor pesquisado). Se o valor não for encontrado e for maior que o item no meio da lista, então a busca reinicia a partir da metade da sub-lista à direita (os itens maiores que o valor pesquisado). Essa divisão continua até que o valor seja encontrado ou não seja mais possível dividir a lista pela metade. Se um array ou vetor possuir 100 elementos e usarmos a busca binária nele, precisaremos efetuar no máximo 7 tentativas para encontrar o valor desejado. Se a lista possuir 4 bilhões de itens nós teremos que fazer no máximo 32 tentativas. Isso acontece porque a pesquisa binária é executada em tempo logarítmico, ou seja, log2 n, onde n é a quantidade de itens no vetor. Dessa forma, se tivemos 1.000 itens em um array, log2 1000 = 10 tentativas. Lembre-se de que, na programação log e log2 retornam resultados diferentes: log(10) = 2.302585092994046 enquanto log2(10) = 3.321928094887362. Na análise da busca binária nós usamos sempre log2. Vamos agora ver como podemos codificar a busca binária em C. Veja o código a seguir: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <locale.h> #define TAM_ARRAY 10 // função principal do programa int main(int argc, char *argv[]){ setlocale(LC_ALL,""); // para acentos do português // variáveis para ajudar na resolução do problema int i, numero, esquerda, direita, meio, encontrado; // vamos criar uma um vetor ordenado de inteiros int valores[] = {3, 5, 7, 8, 9, 12, 43, 50, 52, 60}; // vamos mostrar os elementos do vetor printf("Os valores do array são: "); for(i = 0; i < TAM_ARRAY; i++){ printf("%d, ", valores[i]); } // vamos pedir o item a ser pesquisado printf("\n\nInforme o número a ser pesquisado: "); scanf("%d", &numero); // agora vamos pesquisar o número no array usando a pesquisa // binária // a variável esquerda aponta para o primeiro elemento do vetor esquerda = 0; // a variável direita aponta para o último elemento do vetor direita = TAM_ARRAY - 1; // para indicar se o valor foi encontrado encontrado = 0; // enquanto houver mais de um elemento a ser comparado while (esquerda <= direita){ // obtemos o elemento na metade da lista meio = (esquerda + direita) / 2; // fazemos a comparação if (numero == valores[meio]){ printf("O número foi encontrado no índice %d", meio); encontrado = 1; break; // sai do laço } // o item atual é maior que o valor pesquisado? if (valores[meio] > numero){ direita = meio - 1; } // o item atual é menor que o valor pesquisado? else{ esquerda = meio + 1; } } // o valor foi encontrado? if (!encontrado){ printf("O valor pesquisado não foi encontrado"); } printf("\n\n"); system("PAUSE"); return 0; } Ao executar este código C nós teremos o seguinte resultado: Os valores da lista são: [3, 5, 7, 8, 9, 12, 43, 50, 52, 60] Informe o número a ser pesquisado: 9 O número foi encontrado no índice 4 |
Link para compartilhar na Internet ou com seus amigos: |
C ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes) |
Exercícios Resolvidos de C - Escreva um programa C para mover todos os zeros para o final do vetor, sem alterar a ordem dos elementos já presentes no arrayQuantidade de visualizações: 731 vezes |
Pergunta/Tarefa: Dado o seguinte vetor de inteiros: // vamos declarar e construir um vetor de 8 inteiros int valores[] = {0, 3, 0, 5, 7, 4, 0, 9}; Sua saída deverá ser parecida com: Vetor na ordem original: 0 3 0 5 7 4 0 9 Vetor com os zeros deslocados para o final: 3 5 7 4 9 0 0 0 Veja a resolução comentada deste exercício usando C: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <locale.h> int main(int argc, char *argv[]){ // vamos declarar e construir um vetor de 8 inteiros int valores[] = {0, 3, 0, 5, 7, 4, 0, 9}; int i; // para o controle do laço int j; // variável auxiliar int temp; // variável temporária setlocale(LC_ALL,""); // para acentos do português // vamos mostrar o vetor na ordem original printf("Vetor na ordem original:\n"); for(i = 0; i < 8; i++){ printf("%d ", valores[i]); } // vamos inicializar j como 0 para que ele aponte para // o primeiro elemento do vetor j = 0; // agora o laço for percorre todos os elementos do vetor, // incrementanto a variável i e deixando o j em 0 for(i = 0; i < 8; i++){ // encontramos um valor que não é 0 if(valores[i] != 0){ // fazemos a troca entre os elementos nos índices // i e j temp = valores[i]; valores[i] = valores[j]; valores[j] = temp; // e avançamos o j para o elemento seguinte j++; } } // agora mostramos o resultado printf("\n\nVetor com os zeros deslocados para o final:\n"); for(i = 0; i < 8; i++){ printf("%d ", valores[i]); } printf("\n\n"); system("pause"); return 0; } Não se esqueça: A resolução do exercício deve ser feita sem a criação de um vetor, array ou lista adicional, e os elementos diferentes de zero devem permanecer na mesma ordem que eles estavam antes. |
C ::: Dicas & Truques ::: Recursão (Recursividade) |
Como somar os elementos de um vetor em C usando uma função recursiva - Linguagem C para iniciantesQuantidade de visualizações: 5251 vezes |
Em algumas ocasiões ficamos imaginando o que pode ser feito com os métodos e funções recursivas. A resposta é: praticamente tudo. Veja abaixo um programa C completo no qual eu mostro como escrever uma função recursiva que recebe um array e mostra a soma de seus elementos (lembre-se de que um array é o mesmo que vetor, ou seja, uma matriz de uma linha e várias colunas): ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> // função recursiva para somar todos os elementos de um array int somar(int indice, int tamanho, int vetor[]){ // o caso base...hora de encerrar a recursividade if(indice == (tamanho - 1)){ return vetor[indice]; } else{ // ainda não é o caso base? vamos fazer uma nova chamada à função somar() return vetor[indice] + somar(indice + 1, 10, vetor); } } // função principal do programa int main(int argc, char *argv[]){ // vamos declarar um array de 10 elementos int valores[10]; int i, soma; // vamos pedir ao usuário para informar os valores para o vetor for(i = 0; i < 10; i++){ printf("Informe o valor do elemento %d: ", i); scanf("%d", &valores[i]); } // vamos efetuar uma chamada à função recursiva somar(); // nota que estamos passando o índice inicial, o tamanho do // array e o array em si soma = somar(0, 10, valores); printf("\nA soma dos elementos è: %d", soma); printf("\n\n"); system("PAUSE"); return 0; } Ao executarmos este código C nós teremos o seguinte resultado: Informe o valor do elemento 0: 7 Informe o valor do elemento 1: 3 Informe o valor do elemento 2: 1 Informe o valor do elemento 3: 3 Informe o valor do elemento 4: 8 Informe o valor do elemento 5: 9 Informe o valor do elemento 6: 4 Informe o valor do elemento 7: 3 Informe o valor do elemento 8: 2 Informe o valor do elemento 9: 6 A soma dos elementos é: 46 |
C ::: Desafios e Lista de Exercícios Resolvidos ::: Arrays e Matrix (Vetores e Matrizes) |
Exercícios Resolvidos de C - Desafio do número ausente. Dado um vetor de números naturais 1..n, encontre o valor ausenteQuantidade de visualizações: 550 vezes |
Pergunta/Tarefa: Dado o vetor: int valores[] = {1, 8, 7, 2, 6, 5, 3}; Encontre o elemento ausente na sequência de valores do vetor, sabendo que o primeiro valor é 1 e o último elemento é 8. Perceba que o vetor não precisa estar ordenado. Além disso, o entrevistador se certificará de que os valores serão sempre positivos e não haverá valores repetidos. Sua saída deverá ser parecida com: O número ausente é: 4 Dica: Use a fórmula n * (n + 1) / 2 para facilitar a resolução do exercício. Veja a resolução comentada deste exercício usando C: ---------------------------------------------------------------------- Se precisar de ajuda com o código abaixo, pode me chamar no WhatsApp +55 (62) 98553-6711 (Osmar) ---------------------------------------------------------------------- #include <stdio.h> #include <stdlib.h> #include <locale.h> // função principal do programa int main(int argc, char *argv[]){ // vamos declarar um vetor de inteiros faltando // um valor na sequência (não necessariamente ordenada) // Note a ausência do número 4 int valores[] = {1, 8, 7, 2, 6, 5, 3}; int i, soma_n, ausente, soma_elementos; int quant = 8; // tamanho do vetor + 1 setlocale(LC_ALL,""); // para acentos do português // o primeiro passo é obter a soma de 1..n elementos // natuais usando a fórmula n*(n+1)/2 soma_n = (quant * (quant + 1)) / 2; // agora vamos somar os elementos do vetor soma_elementos = 0; for(i = 0; i < 7; i++){ soma_elementos = soma_elementos + valores[i]; } // agora calculamos o valor ausente ausente = soma_n - soma_elementos; // vamos mostrar o resultado printf("O número ausente é: %d", ausente); printf("\n\n"); system("PAUSE"); return 0; } |
Vamos testar seus conhecimentos em Fenômeno de Transportes e Hidráulica |
Fórmula de Hazen-Williams A fórmula de Hazen-Williams (1903) é resultado de um estudo estatístico com grande número de dados experimentais, recomendada para escoamento turbulento de transição, água a 20ºC e diâmetro maior ou igual a 50mm. Calcule o diâmetro de uma tubulação de aço (C=90), com 1.000m de comprimento e perda de carga de 51m, cuja vazão é de 200l/s. A) Aproximadamente 0,3m de diâmetro. B) Aproximadamente 0,4m de diâmetro. C) Aproximadamente 0,1m de diâmetro. D) Aproximadamente 0,5m de diâmetro. E) Aproximadamente 0,2m de diâmetro. Verificar Resposta Estudar Cards Todas as Questões |
Vamos testar seus conhecimentos em Hidrologia |
Marque a alternativa que indica uma característica da rede hidrográfica brasileira. A) É formada principalmente por rios intermitentes. B) Não apresenta cursos de água em área de planalto. C) Possui rios com o predomínio de foz do tipo estuário. D) Todos os rios brasileiros possuem regime nival. E) É composta por rios de baixo aproveitamento hídrico. Verificar Resposta Estudar Cards Todas as Questões |
Vamos testar seus conhecimentos em JavaScript |
Na construção switch...case...default do JavaScript, em qual parte colocamos a expressão a ser avaliada? A) O JavaScript não possui switch...case B) switch C) case D) default Verificar Resposta Estudar Cards Todas as Questões |
Vamos testar seus conhecimentos em JavaScript |
Qual o resultado da execução do seguinte código JavaScript?document.write(false == '0'); A) 0 B) false C) 1 D) true E) Erro de execução Verificar Resposta Estudar Cards Todas as Questões |
Vamos testar seus conhecimentos em Engenharia Civil - Estruturas de Aço e Madeira |
Evolução das estruturas Até o início do século XIX os metais exerciam uma função estrutural limitada nas edificações. O aço em abundância e econômico tornou-se disponível pela primeira vez na década de 1850. Assinale a opção correta quanto aos motivos que levaram à expansão da utilização de elementos metálicos em estruturas: Selecione a resposta: A) A utilização do ferro forjado e o sentido estético da época levaram a maior utilização da estrutura metálica. B) Devido à introdução do Processo Bessemer, em que grandes quantidades de ferro podiam ser transformadas em aço, em aproximadamente 20 minutos resultando em um metal com propriedades estruturais bastante superiores ao do ferro fundido. C) A carência de profissionais capacitados, artesãos, em trabalhar a alvenaria de pedra como elemento estrutural levaram a uma mudança em termos de tecnologia estrutural, havendo a utilização da estrutura metálica em larga escala. D) O incremento da urbanização e a necessidade da rapidez na construção de casas para as pessoas que vinham para as cidades trabalhar nas fábricas levaram à larga utilização da estrutura metálica, reduzindo assim, o seu custo. E) A verticalização das cidades e a ousadia dos arquitetos e dos construtores de se construir edifícios cada vez mais altos. Verificar Resposta Estudar Cards Todas as Questões |
Mais Desafios de Programação e Exercícios e Algoritmos Resolvidos de C |
Veja mais Dicas e truques de C |
Dicas e truques de outras linguagens |
Códigos Fonte |
Software de Gestão Financeira com código fonte em PHP, MySQL, Bootstrap, jQuery - Inclui cadastro de clientes, fornecedores e ticket de atendimento Diga adeus às planilhas do Excel e tenha 100% de controle sobre suas contas a pagar e a receber, gestão de receitas e despesas, cadastro de clientes e fornecedores com fotos e histórico de atendimentos. Código fonte completo e funcional, com instruções para instalação e configuração do banco de dados MySQL. Fácil de modificar e adicionar novas funcionalidades. Clique aqui e saiba mais |
Controle de Estoque completo com código fonte em PHP, MySQL, Bootstrap, jQuery - 100% funcional e fácil de modificar e implementar novas funcionalidades Tenha o seu próprio sistema de controle de estoque web. com cadastro de produtos, categorias, fornecedores, entradas e saídas de produtos, com relatórios por data, margem de lucro e muito mais. Código simples e fácil de modificar. Acompanha instruções para instalação e criação do banco de dados MySQL. Clique aqui e saiba mais |
Linguagens Mais Populares |
1º lugar: Java |