Categoria: Computational Complexity

1. Qual é o menor valor inteiro de n tal que um algoritmo cujo tempo de execução é 100n2 funciona mais rápido que um algoritmo cujo tempo de execução é 2n na mesma máquina? Implemente um algoritmo que imprima na tela a resposta correta.

#include 
#include 

int main(){
    int n;
    for(n = 1; n < 20; n++){
        if( (100 * n * n) < pow(2, n) ){
            printf("%s %d\n", "100*n^2 funciona mais rapido apartir de: ", n);
            break;
        }
    }
    return 0;
}

2. Supondo que estamos comparando implementações de ordenação por inserção e por intercalação na mesma máquina. Para entradas de tamanho n, a ordenação por inserção é executada em \(8n^2\) etapas, enquanto a ordenação por intercalação é executada em \(64n log_2 n\) etapas. A partir de qual valor inteiro de n a ordenação por intercalação supera a ordenação por inserção. Implemente um algoritmo que imprima a resposta correta na tela.

#include 
#include 

int main(){
    int n = 1;
    float a = 0, b = 1;
    while(n<50){ a = 8 * n * n; b = 64 * n * log2(n); printf("%f %f \n", a, b ); if(a>b&&n>1){
            printf("O algoritmo de itercalação vale a pena a partir de n = %d", n);
            break;
        }
        n++;
    }
    return 0;
}

Implementar um jogo “adivinha-número” utilizando busca binária:
Deve ser solicitado ao usuário que pense em um número entre 1 e 10000

O programa deve dar o primeiro palpite
– Se estiver errado, deve ser perguntado se o número é maior ou menor que um certo número
– O programa apresenta um novo palpite e assim por diante até que adivinha o número certo.
– O programa deve contar quantos palpites foram necessários para acertar o número

 

#include <stdio.h>
#include <math.h>

int guess(int i, int j){
    char r1, r2;
    int g = abs((i+j) / 2);
    printf("E o numero: %d ?(Y = Sim, N = Nao)\n", g);
    scanf(" %c", &r1);
    if(r1 == 'Y'){
        return g;
    }
    else{
        printf("O numero eh maior ou menor que %d ?(M = Maior, N = Menor)\n", g);
        scanf(" %c", &r2);
        if(r2 == 'M'){
            guess(g,j);
        }
        else{
            guess(i,g);
        }
    }
}
int main(){
    printf("Pense em um numero entre 1 e 10000.\n");
    guess(1,10001);
}