Quale algoritmo è più veloce? [chiuso]

-2

Sto creando un piccolo gioco, in cui il computer genera un numero pseudo casuale nell'intervallo, e l'utente deve indovinarlo. Ho anche fatto l'opzione di giocare al computer vs computer. Voglio dire che il computer genera un numero casuale e il computer dovrebbe indovinarlo.

Il modo più semplice che ho trovato è stato quello di creare per loop e aumentare una variabile di 1 finché non lo indovina. Ma ho deciso di provare a creare il mio algoritmo su questo.
Fondamentalmente la variabile che contiene il numero di indovinare è uguale all'intervallo / 2, e quindi il programma entra nel ciclo while dove se il numero casuale > il numero che viene generato dalla logica (quello che è = nell'intervallo / 2) quindi 2 a due e ne aggiunge 1. Se il numero è < il programma * per 2 e aggiungine uno fino a quando non indovina il numero.

Ecco il codice in C ++:

void aiVsAI(int range){ // range argument is used to be given to the randome generator func
    int random_number = generate_random_number(range); // assigning the random number to variable
    int guess = range / 2; // the computer guess number
    int tries = 0; // how many tries the computer needed to guess the number
    while(guess != random_number){ // while the guess isn't equel to the random number
        if(guess > random_number){ // if the guess is > than the random number
            guess = guess / 2 + 1; // dev it to 2 and add one to it
        }
        else if(guess < random_number){ // if the number is < than the number then
            guess = guess * 2 + 1; // * it with 2 and add one
        }
        tries++; // increase the number of tires
    }
    std::cout << tries;
}

il generate_random_number è una funzione che genererà un numero pseudo-casuale.

La mia domanda è quale algoritmo è più veloce questo o semplicemente usando per il ciclo e aumentando la variabile con uno finché non indovina il numero?

Ecco il codice completo se qualcuno ne ha bisogno per qualcosa:

#include <iostream>
#include <string>
#include <cstdlib>
#include <time.h>


//function that will generate random number
int generate_random_number(int range){  // the range argument is used to represent the maximum value of the number
    if(range < 10){ // the range couln't be < 10 but can be ==
        std::cout << "range can't be less than 10";
        exit(1);
    }
    std::srand(time(NULL)); // making sure that the random number will be different every time
    return rand() % range; // returning the random generated number in the specific range
}

//Game computer vs computer
void aiVsAI(int range){ // range argument is used to be given to the randome generator func
    int random_number = generate_random_number(range); // assigning the random number to variable
    int guess = range / 2; // the computer guess number
    int tries = 0; // how many tries the computer needed to guess the number
    while(guess != random_number){ // while the guess isn't equel to the random number
        if(guess > random_number){ // if the guess is > than the random number
            guess = guess / 2 + 1; // dev it to 2 and add one to it
        }
        else if(guess < random_number){ // if the number is < than the number then
            guess = guess * 2 + 1; // * it with 2 and add one
        }
        tries++; // increase the number of tires
    }
    std::cout << tries;
}


// Game human vs human
void humanVsAI(int range){ // range argument is given to the generate random function
    int random_number = generate_random_number(range); // assigning the random number to variable
    int input = 0; // this var represents the user input
    int tries = 0; // the number of tries user had make to guess the number
    while(input != random_number){
        std::cout << "Enter number: "; // alerting the user to enter a number
        std::cin >> input; // getting the number
        if(input < random_number) // checking if the input > than the random num
            std::cout << "You didn't guess it,you are too low..., try again!\n"; // alerting the user
        else{ // else it will be > than the number
            std::cout << "You didn't guess it,you are too high..., try again!\n"; // alerting the user
        }
        tries++; // increasing tries by one for each try//
    }
    std::cout << "\n\nYou guess it! You need " << tries << " to do this.\n\n";
}


//game Human vs Human
void humanVsHuman(int range){
    int number_to_guess; // the number which must be guessed
    int user_guess; // user input
    int guess;
    std::cout << "Enter number int range 1- "<< range<<": \n"; // alerting the user to enter number
    std::cin >> number_to_guess; // entering number
    for(int i = 0; i < 100;i++){ //Clearing the screen
        std::cout << "\n";
    }
    while(user_guess != number_to_guess){
        guess++;
        std::cout << "Please enter numer:\n"; // alerting the user
        std::cin >> user_guess; // Getting the user input
        if(user_guess < number_to_guess)
            std::cout << "You didn't guess it,you are too low..., try again!\n";
        else if(user_guess > number_to_guess)
            std::cout << "You didn't guess it,you are too high..., try again!\n";
    }
    std::cout << "You guess the number\n";
}
int main(){
    std::string game_type;
    char play_game;
    int range = 0;
    while(1){
        std::cout << "Please enter range(type 100 to leave it as default)\n";
        std::cin >> range;
        std::cout <<"What you want to play AI vs human, human vs human or AI vs AI ?\n";
        std::cin.ignore(); // for get line
        std::getline(std::cin, game_type); // getting the user input
        std::cin.clear(); // clearing
        if(game_type == "AI vs AI" || game_type == "ai vs ai"){ // if the user chose AI vs AI
            std::cout<<"You choosed AI vs AI\n";
            aiVsAI(range); // calling the AI function
        }
        else if(game_type == "human vs ai"
                || game_type  == "ai vs human"
                || game_type == "human vs AI"
                || game_type == "Human vs AI"
                || game_type == "Human vs ai"
                ){ // if the user chossed AI vs human
            std::cout << "You choosed human vs AI\n";
            humanVsAI(range); // calling the human vs human function
        }
        else if(game_type == "human vs human"
                ||game_type == "Human vs Human"
                ||game_type == "Human vs human"
                ||game_type == "human vs Human"){ // if the user choosed human vs human
            std::cout <<"You choose human vs human\n";
            humanVsHuman(range); // calling the human vs human function
        }
        else{ // In case of any error
            std::cerr << "An error occured!";
        }
        std::cout << "Do you want to play another game?\n"; // do you want another game????
        std::cin >> play_game;
        if(play_game == 'y' || play_game == 'Y')
           std::cout <<" starting another game\n";
        else
            break;  // enough playing for now.
    }
    return 0;

}
    
posta user3868594 24.07.2014 - 13:45
fonte

2 risposte

1

Finché l'ipotesi è costantemente alta, il tuo algoritmo si comporta bene approssimativamente dimezzando l'ipotesi.
Dopo aver fatto una bassa ipotesi, l'algoritmo si deteriora gravemente nelle prestazioni. Raddoppiando dopo una bassa ipotesi, si è certi che la prossima ipotesi sarà troppo alta. Ora entrano in gioco i fattori +1 (in particolare quello dopo il dimezzamento), che ti permettono di camminare verso il numero giusto a metà della velocità di un loop normale.

Per le misurazioni delle prestazioni, mi aspetto che il passo lento sia il fattore dominante, rendendo il tuo algoritmo più lento della media del ciclo semplice. Date le tue misure, o le mie aspettative sono sbagliate, o la distribuzione dei tuoi valori pseudo-casuali sembra essere leggermente a favore dell'algoritmo.

Se vuoi una sfida, puoi provare a implementare una ricerca binaria . Con un intervallo di 100, quell'algoritmo è in grado di trovare qualsiasi numero entro 10 passi (dato che conosce l'intervallo).

    
risposta data 24.07.2014 - 15:38
fonte
1

L'algoritmo più sofisticato è decisamente più efficiente: richiede il tempo logaritmico rispetto al tempo lineare per trovare il valore. Qui è una descrizione della ricerca binaria; questo è fondamentalmente ciò che hai reinventato.

    
risposta data 24.07.2014 - 13:59
fonte

Leggi altre domande sui tag