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: 516 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 ::: Estruturas de Controle |
Exercício Resolvido de C - Como testar se um ano é bissexto em C - Um programa que lê um ano com quatro dígitos e informa se ele é bissexto ou nãoQuantidade de visualizações: 871 vezes |
Pergunta/Tarefa: Chama-se ano bissexto o ano ao qual é acrescentado um dia extra, ficando ele com 366 dias, um dia a mais do que os anos normais de 365 dias, ocorrendo a cada quatro anos (exceto anos múltiplos de 100 que não são múltiplos de 400). Isto é feito com o objetivo de manter o calendário anual ajustado com a translação da Terra e com os eventos sazonais relacionados às estações do ano. O último ano bissexto foi 2012 e o próximo será 2016. Um ano é bissexto se ele for divisível por 4 mas não por 100, ou se for divisível por 400. Escreva um programa C que pede ao usuário um ano com quatro dígitos e informa se ele é bissexto ou não. Sua saída deverá ser parecida com: Informe o ano: 2024 O ano informado é bissexto. Veja a resolução comentada deste exercício usando C console: ---------------------------------------------------------------------- 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[]){ int ano; setlocale(LC_ALL,""); // para acentos do português // vamos solicitar que o usuário informe um ano printf("Informe o ano: "); scanf("%d", &ano); // vamos verificar se o ano informado é bissexto if(((ano % 4 == 0) && (ano % 100 != 0)) || (ano % 400 == 0)){ printf("\nO ano informado é bissexto.\n"); } else{ printf("\nO ano informado não é bissexto.\n"); } printf("\n\n"); system("pause"); return 0; } |
C ::: Dicas & Truques ::: Strings e Caracteres |
Como escrever uma função strtolower() para transformar uma palavra inteira em letras minúsculas usando a linguagem CQuantidade de visualizações: 9851 vezes |
O C padrão não possui uma função para transformar todas as letras de uma palavra em minúsculas, embora alguns compiladores a forneça. O que temos é a função: int tolower(int c); que permite transformar um caractere em seu correspondente minúsculo. Podemos tirar vantagem disso e escrever uma função strtolower() personalizada. Veja a listagem logo abaixo: ---------------------------------------------------------------------- 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> void strtolower(char *string){ while(*string){ *string = tolower(*string); string++; } } int main(int argc, char *argv[]) { char frase[] = "PROGRAMANDO EM C"; strtolower(frase); printf("%s\n\n", frase); system("PAUSE"); return 0; } Ao executar este código nós teremos o seguinte resultado: programando em c Pressione qualquer tecla para continuar... |
C ::: Desafios e Lista de Exercícios Resolvidos ::: Engenharia Civil - Cálculo Estrutural |
Exercícios Resolvidos de C - Como calcular as reações de apoio, momento de flexão máxima e forças cortantes em uma viga bi-apoiada com carga distribuída retangular usando CQuantidade de visualizações: 792 vezes |
Pergunta/Tarefa: Veja a seguinte figura: Nesta imagem temos uma viga bi apoiada com uma carga q distribuída de forma retangular a uma distância l. Para fins didáticos, vamos considerar que a carga q será em kN/m e a distância l será em metros. O apoio A é de segundo gênero e o apoio B é de primeiro gênero. Escreva um programa C que solicita ao usuário que informe o valor da carga q e a distância l entre os apoios A e B. Em seguida mostre os valores das reações nos apoios A e B, o momento de flexão máxima da viga e o momento de flexão para uma determinada distância (que o usuário informará) a partir do apoio A. Mostre também as forças cortantes nos apoios A e B. Lembre-se de que, para uma carga distribuída de forma retangular, o diagrama de momento fletor é uma parábola, enquanto o diagrama de cortante é uma reta (com o valor zero para a força cortante no meio da viga). Sua saída deve ser parecida com: Valor da carga em kN/m: 10 Distância em metros: 13 A reação no apoio A é: 65.000000 kN A reação no apoio B é: 65.000000 kN O momento fletor máximo é: 211.250000 kN Informe uma distância a partir do apoio A: 4 O momento fletor na distância informada é: 180.000000 kN A força cortante no apoio A é: 65.000000 kN A força cortante no apoio B é: -65.000000 kN 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 <math.h> int main(int argc, char *argv[]) { // variáveis usadas na resolução do problema float carga, distancia, reacao_a, reacao_b; float flexao_maxima, distancia_temp, flexao_distancia; float cortante_a, cortante_b; // vamos pedir para o usuário informar o valor da carga printf("Valor da carga em kN/m: "); scanf("%f", &carga); // vamos pedir para o usuário informar a distância entre os apoios printf("Distancia em metros: "); scanf("%f", &distancia); // vamos calcular a reação no apoio A reacao_a = (1.0 / 2.0) * carga * distancia; // vamos calcular a reação no apoio B reacao_b = reacao_a; // vamos calcular o momento fletor máximo flexao_maxima = (1.0 / 8.0) * carga * pow(distancia, 2.0); // e mostramos o resultado printf("\nA reacao no apoio A e: %f kN", reacao_a); printf("\nA reacao no apoio B e: %f kN", reacao_b); printf("\nO momento fletor maximo e: %f kN", flexao_maxima); // vamos pedir para o usuário informar uma distância a // partir do apoio A printf("\n\nInforme uma distancia a partir do apoio A: "); scanf("%f", &distancia_temp); // vamos mostrar o momento fletor na distância informada if (distancia_temp > distancia) { printf("\nDistancia invalida.\n"); } else { flexao_distancia = (1.0 / 2.0) * carga * distancia_temp * (distancia - distancia_temp); printf("O momento fletor na distancia informada e: %f kN", flexao_distancia); } // vamos mostrar a força cortante no apoio A cortante_a = (1.0 / 2.0) * carga * distancia; printf("\n\nA forca cortante no apoio A e: %f kN", cortante_a); // vamos mostrar a força cortante no apoio B cortante_b = cortante_a * -1; printf("\nA forca cortante no apoio B e: %f kN\n\n", cortante_b); printf("\n\n"); system("PAUSE"); return 0; } |
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 |