Wypisanie wyrazów ciągu do podanej przez użytkownika liczby – sprawdzenie kodu

2018-11-02 01:14
0

Witam, mam problem z napisaniem programu dla ciągu Fibonacciego w C. Ma on wypisywać wyrazy ciągu do podanej przez użytkownika liczby. Zrobiłem coś takiego wzorując się na schematach w internecie, ale nie wiem czy te tablice są dobrze zrobione. Nie wiem głównie jak zapisać ciąg. Oto mój kod:

#include <stdio.h>
#include <conio.h>
int main()
{
    long double fib[100000];
    int n, i, suma;
    printf("\nPodaj ilosc wyrazow ciagu Fibonacciego: ");
    scanf("%d", &n);
    {
        if (n == 0)
            printf("\nKolejne wyrazy ciagu to: 0");
    }
    {
        if (n == 1)
            printf("\nKolejne wyrazy ciagu to: 1");
    }
    do {
        for (i = 0; i <= n; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
        printf("\nKolejne wyrazy ciagu to: %d", fib[i]);
        return 0;
    } while (n >= 2);
    getch();
    return 0;
}
edytowany 2x, ostatnio: furious programming, 2018-11-02 02:08

Pozostało 580 znaków

2018-11-02 01:25
kq
2

Ta tablica może być za duża do trzymania na stosie, ale to detal.

    do {
        for (i = 0; i <= n; i++)
            fib[i] = fib[i - 1] + fib[i - 2];
        printf("\nKolejne wyrazy ciagu to: %d", fib[i]);
        return 0;
    } while (n >= 2);
  • To nie ma sensu, po co w pętli wielokrotnie liczysz te same wartości ciągu? One się nie zmienią.
  • Nie ustawiasz nigdzie pierwszych dwóch wartości ciągu.
  • Dla i równego 0, czym jest fib[i-1] i fib[i-2]?

Pozostało 580 znaków

2018-11-02 01:53
5

Tak to nie Powalczysz, Musisz zasymulować rekurencję (start od a = 0, b = 1 i zamiana w pętli" a = b, b = a + b), wtedy będzie drukować po kolei od początku (czas liniowy i, co ważniejsze, pamięć stała):

#include <stdio.h>
void fibo_print(unsigned long n)
{
    unsigned long a = 0;
    unsigned long b = 1;
    n += 1;
    while (n > 0)
    {
        unsigned long tmp = a;
        printf("%lu", a);
        printf("\n");
        a = b;
        b = tmp + a;
        n -= 1;
    }
}
int main(void) {
  fibo_print(8L); /* -> 0
1
1
2
3
5
8
13
21*/
  return 0;
}

edytowany 1x, ostatnio: lion137, 2018-11-02 11:42

Pozostało 580 znaków

2018-11-02 10:16
Smutny Kot
0

Tutaj jest takie ciekawe dla mnie pytanie. Jeżeli chodziłoby o C++. to rozwiązałbym w taki sposób:

int fibNumber(int anIndex)
{
    static std::vector<int> fibTable = { 0, 1 };
    static int theLastIndex = 2;
    if (anIndex > theLastIndex)
    {
        do 
        {
            fibTable.push_back(fibTable[theLastIndex - 1] + fibTable[theLastIndex - 2]);
        } while (++theLastIndex <= anIndex);
    }
    return fibTable[anIndex];
}

int main()
{
    std::cout << "Trzydziesty pierwszy wyraz ciagu Fibonacciego to jest " << fibNumber(31) << std::endl;
    std::cout << "Jedynasty wyraz ciagu Fibonacciego to jest " << fibNumber(11) << std::endl;
    std::cout << "Trzydziesty dziewiaty wyraz ciagu Fibonacciego to jest " << fibNumber(39) << std::endl;
    system("pause");
    return 0;
}

Ale tutaj chodzi o C, ale biblioteka standardowa C nie ma takiego dynamicznie rozszerzanego kontenera, jak vector w C++. W takim razie czy możemy użyć takie podejście w C?

edytowany 1x, ostatnio: furious programming, 2018-11-02 17:58

Pozostało 580 znaków

2018-11-02 11:53
2

Niepotrzebnie, imho, wprowadzając na scenę dynamiczną tablicę, Dodajesz do problemu złożoność. Poza tym, trzeba zapuścić Twoją funkcję w pętli, co daje złożoność kwadratową:
n + (n - 1) + (n - 2) + ... + 1 = O(n^2)


edytowany 1x, ostatnio: furious programming, 2018-11-02 17:58
Nie cytuj całego posta, jeśli odpowiadasz zaraz pod nim i do jego całości się odnosisz. Strasznie się wątek rozciąga w pionie… - furious programming 2018-11-02 17:58

Pozostało 580 znaków

2018-11-02 12:55
0

Dzięki za pomoc, a jeśli zrobiłbym warunek, że n musi być większe od 2 i wtedy rozwiązałbym to w ten sposób?

do {
    for(i=2;i<=n;i++)

printf("\nKolejne wyrazy ciagu to: 0 1 %d", i);

Tylko nie wiem jak zapisać ten ciąg, bo jest to mój 1 program, który zmienia i, a nie je sumuje, mnoży itp.
robiąc np i=(i-1)+(i-2) policzy mi tylko ostatni wyraz, a jak zrobić tak, żeby liczyło od 2 do n?

edytowany 2x, ostatnio: furious programming, 2018-11-02 17:59

Pozostało 580 znaków

2018-11-02 13:24
2

Hm... Nie wiem czy jesteśmy na tej samej stronie:). Poczytaj i Upewnij się, że bardzo dobrze Rozumiesz takie pojęcia, jak: iteracja, rekurencja, funkcja, instrukcje przypisania...
Klasycznie, Fibonacci to rekurencyjna funkcja, F(n):
Dla n = 0, F(n) = 0;
Dla n = 1, F(n) = 1;
Dla n >= 2, F(n) = F(n - 1) + F(n - 2).
Mógłbyś ją zaimplementować bezpośrednio:

#include <stdio.h>
unsigned long f(unsigned long n)
{
    if (n == 0) 
        return 0;
    else if  (n == 1)
        return 1;
    else
        return f(n - 1) + f(n - 2); 
}       

int main()
{
    printf("%lu", f(6)); // -> 8
    printf("\n");

    return 0;
}

Działa, ale Zauważ, że z każdym wywołaniem funkcji okładamy na stos jej dwie kolejne kopie, więc pamięć rośnie proporcjonalnie do 2^n. To samo można zrobić iteracyjnie, zauważając, że kolejne wyrazy ciągu można generować tak:
Zaczynjąc od a = 0, b = 1
Dalej, iteracyjnie, (w pętli) symultanicznie, wykonujemy przypisania: a = b, b = a + b.
Symultanicznie, czyli podstawienie b = a + b musi uzywać "starego" a (stąd tymczasowa zmienna tmpw funkcji powyżej).
Sprawdź to na kartce, a potem Przestudiuj kod powyżej.


Pozostało 580 znaków

2018-11-02 13:27
0

Domyślam się, że mogę pisać rzeczy absurdalne i wydające się oczywiste, ale z programowaniem nie miałem nigdy styczności i niektórych linijek kodu o których pisałeś jeszcze nie miałem, dlatego próbuję to jakoś przekształcić na to co już się "nauczyłem". Jak wrócę do domu to postaram się to rozpisać według tych wskazówek i zobaczymy co z tego wyjdzie, tak czy tak dzięki za pomoc.

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0