J'ai posé le problème de la séquence tribonatch en C ++ et le nombre d'appels de fonction lors de l'écriture avec une fonction de récurrence (python est également disponible)

introduction

Ceci est mon premier article. J'ai trouvé un article qui avait l'air intéressant, alors je l'ai essayé. J'ai essayé de résoudre le problème de la séquence Tribonacci avec Ruby (délai de 10 minutes) Pionnier

• J'ai essayé de résoudre le problème de la séquence Tribonacci avec Elixir (délai de 10 minutes)
• J'ai essayé de résoudre le problème de la séquence Tribonacci en Ruby, avec récurrence.

Ce que j'ai fait

・ Défi de 10 minutes avec C ++ (échec car le temps de calcul est trop long) ・ Défi de 30 minutes (clair) avec C ++ -À propos du nombre d'appels de fonction lors de l'écriture récursive (y compris l'implémentation python)

Défi de 10 minutes en C ++ (échec)

Tout d'abord, j'ai trouvé une méthode pour le faire de manière récursive et l'ai écrite telle quelle. Le point est de trouver le 50e de la séquence tribonacci dans le premier terme [1,3,7].

tribonacci_recursive.cpp

#include <iostream>
#include <chrono>
using namespace std;

long long tri_r(int num){
    if(num<=3){
        int templist[3] = {1,3,7};
        return templist[num-1];
    }
    else{
        return tri_r(num-1)+tri_r(num-2)+tri_r(num-3);
    }
}

int main(){
    chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();
    cout << tri_r(51) << endl;
    end = std::chrono::system_clock::now();
    double e_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cout << e_time << " ms" << endl;
}

Oui, cela ne termine pas le calcul à l'heure de Matomo. Donc, je le réécris pour ne pas avoir à faire de calculs inutiles. À ce stade, 10 minutes s'étaient écoulées, le défi a donc échoué.

Défi de 30 minutes avec C ++ (effacer)

tribonacci.cpp

long long tri(int num){
    if(num<3){
        int templist[3] = {1,3,7};
        return templist[num-1];
    }
    else{
        long long tri_list[num] = {1,3,7};
        for(int i=3; i<num; i++){
            tri_list[i] = tri_list[i-1] + tri_list[i-2] + tri_list[i-3];
        }
        return tri_list[num-1];
    }
}
int main(){
    chrono::system_clock::time_point  start, end;
    start = std::chrono::system_clock::now();
    for(int i=1; i<51; i++){
        cout << i << "  " << tri(i) << endl;
    }
    end = std::chrono::system_clock::now();
    double e_time = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
    cout << e_time << " ms" << endl;
}

Le traitement quand il est de 3 ou moins n'est pas bon, mais il peut être calculé en un instant. Le code sort de tri (1) à tri (50), mais il est toujours de 20 ms. Cela suffira.

Nombre d'appels de fonction lors de l'écriture récursive

Eh bien, quand je l'ai écrit récursivement, je comprends qu'il fait des calculs inutiles, mais comment le nombre d'appels à cette fonction augmente-t-il?

Tu peux le voir. Le nombre d'appels est calculé par la séquence tribonacci du premier terme {1,1,1}. C'est naturel quand on y pense, mais c'est un fait intéressant.

J'ai essayé de mesurer le temps de calcul par récursif. Ramassez seulement là où il se termine avec un temps de calcul matomo (mesurez 10 fois et prenez la moyenne).

Aux points 34 à 36, le temps de calcul est d'environ 1,85 fois et 1,87 fois, respectivement. Et le nombre d'appels? Je l'ai écrit dans le Python auquel je suis habitué.

tri_calc.py

def tri(num):
    ans_list = [1,1,1]
    if num > 3:
        for i in range(3, num):
            ans_list.append(ans_list[i-3] + ans_list[i-2] + ans_list[i-1])
    return ans_list

calc_num = tri(50)
print(calc_num[35]/calc_num[34])  #1.8392867552142929
print(calc_num[36]/calc_num[35])  #1.8392867552141035

Ainsi, vous pouvez voir que le nombre d'appels de fonction est d'environ 1,84 fois pour chaque terme supplémentaire. La majeure partie de l'augmentation du temps de calcul équivaut à une surcharge d'appel.

en conclusion

C'était mon premier message, et c'était dans un état de Markdown ou de Nanisore. S'il vous plaît laissez-moi savoir si vous trouvez qu'il est plus facile à lire si vous l'écrivez comme ça. Je suis encore nouveau dans la programmation et le codage, mais c'est amusant de résoudre ces problèmes et de les vérifier de différentes manières. Merci pour la lecture.