Как я могу использовать функцию, которая возвращает целочисленное значение? - PullRequest
Новая
       41

Как я могу использовать функцию, которая возвращает целочисленное значение?

0 голосов
/ 03 апреля 2020

Я видел тот же вопрос, но только на других языках, которые я не знаю.

Я пытался создать функцию, которая возвращает количество движений, необходимое для определенного числа колец (n) в проблема «Ханойская башня», все выглядело хорошо, но время для запуска программы, когда n> 24 было слишком длинным, и онлайн-судья не думал.

Так что я подумал, что если значение было назначается, когда n = 24? Для следующих чисел программа будет компилироваться намного быстрее

Итак, я попробовал ввести: 

if ( n == 24){
    aux++;
    return 16777215;
}

Но, когда я ввел 24, у меня было 1, а не 16777215

Мой код: 

int hanoi(int n, int orig, int dest, int temp){ 
    if (n == 1){ 
        aux++;
        return 0; 
    } 
    if ( n == 24){
        aux++;
        return 16777215;
    }
    hanoi(n-1, orig, temp, dest);
    hanoi(n-1, temp, dest, orig); 
    aux++;
    return 1;
}

Я пытался быть самым подходящим c, я до сих пор не знаю, как задать хороший вопрос в stackOverflow, на данный момент, заранее спасибо !

1 Ответ

0 голосов
/ 03 апреля 2020

Вопросы об этих сторонах «онлайн-соревнования» в большинстве случаев никогда не могут быть решены с помощью грубого подхода. Они хотят, чтобы вы подумали об алгоритме. И, башни Ханойской проблемы и связанные алгоритмы хорошо описаны в net. Вы можете начать с Википедии. Пожалуйста, смотрите здесь .

Решение для количества минимальных ходов: 2^n-1

Программа, которая решает эту проблему: 

#include <iostream>
#include <algorithm>

int main() {

    // Inform user on what the program does.
    std::cout << "\nThis application will calculate the minimum number of moves\n"
        "for a given number of discs: Please enter the number of discs (1-40): ";

    // Get the number of discs from the user and check, if the input worked
    if (unsigned long numberOfDiscs{}; std::cin >> numberOfDiscs) {

        // Limit input value to meaningful borders
        numberOfDiscs = std::clamp(numberOfDiscs, 1UL, 40UL);

        // Calculate the minmum number of moves   2^n - 1
        unsigned long long minimumNumberOfMoves = (1ULL << numberOfDiscs) - 1;

        std::cout << "\n\n The minimum number of moves is: " << minimumNumberOfMoves << "\n";
    }
    return 0;
}

По сути, не требуется (под) функция. Но если вы хотите иметь его, вы можете использовать: 

unsigned long long calculateMinimumNumberOfMoves(unsigned int numberOfDiscs) {
    return (1ULL << numberOfDiscs) - 1;
}

Пожалуйста, будьте осторожны с типом переменной. int имеет на большинстве машин только 4 байта и не будет работать более чем на 30 дисках. Вам необходимо использовать типы данных, которые могут содержать большие значения.

...