Średnia arytemyczna w tablicy

Natknąłem się na takie zadanko: (chyba z wdp uw)

Dostajemy tablice, w której elementy to średnie arytmetyczne sąsiednich elementów tej tablicy, przy założeniu że tablica była cykliczna, czyli prawym sąsiadem ostatniego elementu jest pierwszy, a lewym sąsiadem pierwszego ostatni. Chcemy odnaleźć oryginalną tablicę tzn:

np na wejściu jest [70,55,25] to chcemy otrzymac [10,40,100]. Mój pomysł jest taki by rozwiązać układ równań np tutaj:

x3+x2 = 140
x1+x3 = 110
x2+x1 = 50
Zapuszczamy jakiegoś Gaussa-Crouta i w O(n^3) dostajemy odpowiedź. Fajnie.
Moim zdaniem bez rozwiązania układu równań nie ma szans. Ale że zadanie należy do zbioru zadań "sprytnie" rozwiązywalnych...

pytanie: czy da się to zrobić lepiej, sprytniej :>
Dzięki za pomoc.

Nie mam teraz pomysłu na inne rozwiązanie, ale na pierwszy rzut oka Gauss w przypadku macierzy rzadkiej takiej jak tutaj to może nie być najlepszy pomysł, bo masz tu na dobrą sprawę macierz 2 przekątniową + ten jeden wiersz gdzie tablica sie zapętla.

Da się zrobić sprytniej. Na przykładzie:

[70,55,25]

Generujemy tablice różnic sąsiadów prawy-lewy:

[55-25,25-70,70-55]
czyli
[30,-45,15]

odejmujemy pionowo od oryginału (z góry na dół) i zapisujemy wynik w prawym sąsiedzie

Mieliśmy:[70,55,25]
a teraz: [30,-45,15]
różnica:[10,40,100]

Samo odejmowanie ilość działań dla wejścia równego n=2*n złożoność liniowa

Oczywiście przyszło mi to do głowy więc nie daje na to gwarancji :P, dam natomiast prosty kodzik w pythonie, żeby było można łatwo obalić tę tezę:

#!/usr/bin/python
shift=lambda l,n:l[n:]+l[:n]
subs=lambda x,y:x-y
tab=[70,55,25]
roznice=map(subs,shift(tab,1),shift(tab,-1))
print " ",tab,"\n","-",roznice
wynik=shift(map(subs,tab,roznice),-1)
print "=",wynik

a-tablica liczb
A- tablica średnich

dla i<n

dla n parzystych:

dostajemy warunek sensowności danych. Przykład prosty: [3, 6] czyli średnia a1 i a2 daje 3 a średnia a2 i a1 daje 6 czyli bezsensu.
Dla spełnionego warunku jest nieskończenie wiele rozwiązań (bo masz n zmiennych a tylko n-1 niezależnych liniowo równań), więc do jednego elementu podstawiasz cokolwiek i doliczasz resztę i masz jakiś wynik.

dla n nieparzystych:

A ponieważ równania są cykliczne (można poprzesuwać indeks) to jest to wzór uniwersalny.

Pomysł wydawał się trafiony, ale znalazłem kontrprzykład:

Dla tablicy [7, 21, 16, 25, 11, 12] odpowiedz powinna byc [8, 12, 34, 20, 16, 2].
Korzystajac z Twojego sposoby dostaje tablice roznic [9, 9, 4, -5, -13, -4].
No i 7-9 = -2 i się nie zgadza niestety :-/

Marek - przeanalizuje Twoj sposob.
Dziekuje wszystkim za pomoc i zainteresowanie.

Paweł G napisał(a)

Pomysł wydawał się trafiony, ale znalazłem kontrprzykład:

Dla tablicy [7, 21, 16, 25, 11, 12] odpowiedz powinna byc [8, 12, 34, 20, 16, 2].
Korzystajac z Twojego sposoby dostaje tablice roznic [9, 9, 4, -5, -13, -4].
No i 7-9 = -2 i się nie zgadza niestety :-/

Dałeś przykład o parzystej długości ciągu (n - parzyste), którego naprzemienna suma nie daje zera, więc rozwiązań brak.

W sumie zamiast korzystać z cykliczności równań, to mój wzór lepiej wykorzystać tylko dla obliczania pierwszego elementu, a następnie na podstawie tego elementu ciągu należy poobliczać pozostałe (kolejne) elementy.

Tak już rozumiem :-)
Dziękuję za pomoc jeszcze raz.