Ich habe nach dem Problem der Tribonatch-Sequenz in C ++ und der Anzahl der Funktionsaufrufe beim Schreiben mit einer Wiederholungsfunktion gefragt (Python ist ebenfalls verfügbar).

Einführung

Dies ist mein erster Artikel. Ich fand einen Artikel, der interessant aussah, also habe ich es versucht. Ich habe versucht, das Problem der Tribonacci-Sequenz mit Ruby zu lösen (Zeitlimit 10 Minuten) Pionier

• Ich habe versucht, das Problem der Tribonacci-Sequenz mit Elixir zu lösen (Zeitlimit 10 Minuten)
• Ich habe versucht, das Problem der Tribonacci-Sequenz in Ruby mit Wiederholung zu lösen.

Was ich getan habe

・ 10 Minuten Herausforderung mit C ++ (fehlgeschlagen, weil die Berechnungszeit zu lang ist) ・ 30 Minuten Herausforderung (klar) mit C ++ -Über die Anzahl der Funktionsaufrufe beim rekursiven Schreiben (einschließlich Python-Implementierung)

10 Minuten Herausforderung in C ++ (Fehler)

Zunächst habe ich mir eine Methode ausgedacht, um sie rekursiv zu machen, und sie so geschrieben, wie sie ist. Es geht darum, den 50. Teil der Tribonacci-Sequenz im ersten Term zu finden [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;
}

Ja, dies beendet die Berechnung nicht in Matomo-Zeit. Also schreibe ich es neu, damit ich keine unnötigen Berechnungen durchführen muss. Zu diesem Zeitpunkt waren 10 Minuten vergangen, sodass die Herausforderung fehlschlug.

30 Minuten Herausforderung mit C ++ (klar)

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;
}

Die Verarbeitung bei 3 oder weniger ist nicht gut, kann aber sofort berechnet werden. Der Code wird von Tri (1) bis Tri (50) ausgegeben, beträgt jedoch immer noch 20 ms. Es wird genug sein.

Anzahl der Funktionsaufrufe beim rekursiven Schreiben

Nun, als ich es rekursiv schrieb, verstehe ich, dass es nutzlose Berechnungen durchführt, aber wie erhöht sich die Anzahl der Aufrufe dieser Funktion?

Du kannst es sehen. Die Anzahl der Anrufe wird durch die Tribonacci-Sequenz des ersten Terms {1,1,1} berechnet. Es ist natürlich, wenn Sie darüber nachdenken, aber es ist eine schöne Tatsache.

Ich habe versucht, die Berechnungszeit rekursiv zu messen. Nehmen Sie nur dort auf, wo es mit einer Matomo-Berechnungszeit endet (messen Sie 10 Mal und nehmen Sie den Durchschnitt).

In den Punkten 34 bis 36 beträgt die Berechnungszeit etwa das 1,85-fache bzw. das 1,87-fache. Wie wäre es mit der Anzahl der Anrufe? Ich habe es in dem Python geschrieben, den ich gewohnt bin.

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

Sie sehen also, dass die Anzahl der Funktionsaufrufe für jeden weiteren Begriff etwa 1,84-mal beträgt. Die Verlängerung der Berechnungszeit entspricht hauptsächlich dem Anrufaufwand.

abschließend

Es war mein erster Beitrag und er befand sich in einem Zustand von Markdown oder Nanisore. Bitte lassen Sie mich wissen, wenn Sie es leichter finden, wenn Sie es so schreiben. Ich bin noch neu in der Programmierung und Codierung, aber es macht Spaß, diese Probleme zu lösen und auf verschiedene Weise zu überprüfen. Danke fürs Lesen.