Algorytm średniej arytmetycznej operujący na tablicy

[Duke]

Witam,
Jaki ejst algorytm do takiego zadanka.
Mamy tablicę n elementową, chcemy zastąpić każdy element tablicy począwszy od 2 do n-1 przez średnią arytmetyczną sąsiadów tablicy pierwotnej(nacisk na o pierwotnej, bo nie wiem jak to zrobić, żeby poprzednie wartości i wyniki wzajemnie się nie zamazywały).
Dzięki za odp. Może być kod w Pascalu, pseudokod, tekstowo, cokolwiek.

[soku11]

Wyniki policz sobie w oddzielnej tablicy, to ci się dane nie zamażą Tak będzie najszybciej i bez jakichś kombinacji.

Pozdrawiam.

[Duke]

Tak zrobić ne mogę.(odgórne zasady)Zależy mi na optymalnym alogrytmie o koszcie pamięciowym stałym(niezależnym od n) i złożoności obliczeniowej liniowej.

Przy okazji jak znaleźć drugą co do wartości wielkość w tablicy? Wykreślenie największej i szukanie od nowa nie wchodzi w rachubę, algorytm musi być optymalny. :C help

Upieram się tak bo za algorytmy wolniejsze uwalają u mnie.-- 1 listopada 2009, 19:44 --Jak wypełnić ręcznie tablicę w pascalu
var t:array [1..n] of integer;
i,l:integer;
begin
i:=1;
l:=1;
t=[1,2,3,4,5,6,7,8,9,10];

Tak jest zle to jak dobrze, n=10

[abc666]

Musisz mieć 2 zmienne pomocniczą i trzymać tam np.2 ostatnie, niezapisane średnie a potem je przypisywać odpowiednio. Cała filozofia.

Jak znaleźć drugi element liniowo? Tak jak maks a tylko zapisuj dwie liczby. Trochę więcej warunków tylko będzie.

[peterp]

W pascalu nie piszę, więc podaję przykładowy kod w C. Jest trochę komentarzy, to powinno pomóc:

Kod: Zaznacz cały

#include <stdio.h>
// stała ILE_ELEMENTOW - liczba elementów tablicy
const unsigned ILE_ELEMENTOW=20;
int wyswietl(double tab[]);
int zamien(double tab[]);
main() {
    int i;
    double tab[ILE_ELEMENTOW];
    srand(time(0));
    // inicjujemy tablicę losowymi wartościami
    for(i = 0; i < ILE_ELEMENTOW; i++) tab[i]=rand()%20;
    // wyświetlamy elementy tablicy
    printf("Tablica poczatkowa:
");
    wyswietl(tab);
    // wywołujemy funkcję obliczającą średnie arytmetyczne
    zamien(tab);
    // wyświetlamy nowe elementy tablicy
    printf("
Tablica po wykonaniu dzialan:
");
    wyswietl(tab);
    return 0;
}

int wyswietl(double tab[]) {
    int i;
    for(i=0; i<ILE_ELEMENTOW; i++) printf("%lg	", tab[i]);
    return 0;
}

int zamien(double tab[]) {
    int i;
    //poprzednia - zmienna zachowująca wartość poprzedniego elementu tablicy
    double poprzednia=tab[0], srednia;
    for(i=1; i<ILE_ELEMENTOW-1; i++) {
        srednia=(poprzednia+tab[i]+tab[i+1])/3;
        poprzednia=tab[i];
        tab[i]=srednia;
    }
    return 0;
}

Najważniejsza jest funkcja zamien(). Reszta to tylko "ozdobniki".
Pozdrawiam.

-- 1 listopada 2009, 20:44 --

Jeśli chodzi o problem nr 2

Przy okazji jak znaleźć drugą co do wartości wielkość w tablicy? Wykreślenie największej i szukanie od nowa nie wchodzi w rachubę, algorytm musi być optymalny. :C help

to wydaje się, że w 1 przebiegu nie da się tego zrobić. Gdyby tak było, to sortowanie byłoby prostsze
Ale 2 przebiegi gwarantują rozwiązanie, poza tym zachowują liniowość algorytmu, więc nie widzę problemu.

[kadiii]

Co do drugiego, czyli szukanie drugiego największego elementu, to można to zrobić optymalnie w \(\displaystyle{ n+log_{2}n-2}\) porównań korzystając ze struktury drzewa. ładny przykład jest w M.M.Sysło - układasz sobie drabinkę turnieju, potem zabierasz mistrza i korzystasz z wcześniejszych wyników meczów.