Hej, muszę zaimplementować ten algorytm, by działał w sposób, że podajemy mu sekwencje, a on podaje nam wielomian charakterystyczny. Szukałem na internecie, ale nigdzie nie widzę dobrego wyjaśnienia jak to ma działać w środku i niestety nie potrafię tego zrozumieć. Jedyny działający kod znalazłem w Pythonie, ale niestety nie znam Pythona i kod muszę napisać w C++. Czy dałby radę ktoś wytłumaczyć co się dzieje w środku tego algorytmu, tak żeby dość łatwo go zaimplementować lub może ktoś ma ten kod i mógłby go podesłać, żebym mógł go lepiej zrozumieć?
0
0
#!/usr/bin/env python
def Berlekamp_Massey_algorithm(sequence):
N = len(sequence)
s = sequence[:]
for k in range(N):
if s[k] == 1:
break
f = set([k + 1, 0]) # use a set to denote polynomial
l = k + 1
g = set([0])
a = k
b = 0
for n in range(k + 1, N):
d = 0
for ele in f:
d ^= s[ele + n - l]
if d == 0:
b += 1
else:
if 2 * l > n:
f ^= set([a - b + ele for ele in g])
b += 1
else:
temp = f.copy()
f = set([b - a + ele for ele in f]) ^ g
l = n + 1 - l
g = temp
a = b
b = n - l + 1
# output the polynomial
def print_poly(polynomial):
result = ''
lis = sorted(polynomial, reverse=True)
for i in lis:
if i == 0:
result += '1'
else:
result += 'x^%s' % str(i)
if i != lis[-1]:
result += ' + '
return result
return (print_poly(f), l)
if name == 'main':
seq = (0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0)
(poly, span) = Berlekamp_Massey_algorithm(seq)
print ('The input sequence is %s.' % str(seq))
print ('Its characteristic polynomial is (%s),' % poly,)
print ('and linear span is %d.' % span)
To jest kod który znalazłem
0
To teraz, których instrukcji Pythona, nie Rozumiesz, to Ci napiszę czym one są w C++.
0
lion137 napisał(a):
To teraz, których instrukcji Pythona, nie Rozumiesz, to Ci napiszę czym one są w C++.
Głównie
for k in range(N):
if s[k] == 1:
break
i jaki ten for ma zasięg, w sensie jakby w C++ dać for(..){ } to co jest w klamerkach, gdzie się for Pythonowy kończy. Druga rzecz f ^= set([a - b + ele for ele in g]) oraz f = set([b - a + ele for ele in f]) ^ g , b = n - l + 1 , result += 'x^%s' % str(i) , result += ' + '
1
W Pythonie scope wyznaczają wcięcia, więc ten for kończy się instrukcją: break. Następna instrukcja już jest na wysokości for, więc jest poza pętlą, tak samo w "ifie" wcięte jest break.
Kolejną trzeba rozbic mentalnie:
-
f ^= sth- to samo co w C++:f = f XOR sth; -
[f(args) for arg in <iterable collection>]- to wyrażenie zwraca listę, którą Uworzyłbyś mapując jakąś funkcję na iterowalną kolekcję, np. :
[x * x for x in [1, 2, 3]] = [1, 4, 9], czyl iw powyższym, w C++, do każdego elementu kolekcjig, trzeba dodaća - b; -
set(iterable)- tworzyhashsetz iterowalnej kolekcjiiterable, w C++, na przykład z listy: https://www.tutorialspoint.com/cpp_standard_library/cpp_set_init_constructor.htm
0
lion137 napisał(a):
W Pythonie scope wyznaczają wcięcia, więc ten
forkończy się instrukcją:break. Następna instrukcja już jest na wysokościfor, więc jest poza pętlą, tak samo w "ifie" wcięte jestbreak.
Kolejną trzeba rozbic mentalnie:
f ^= sth- to samo co w C++:f = f XOR sth;[f(args) for arg in <iterable collection>]- to wyrażenie zwraca listę, którą Uworzyłbyś mapując jakąś funkcję na iterowalną kolekcję, np. :
[x * x for x in [1, 2, 3]] = [1, 4, 9], czyl iw powyższym, w C++, do każdego elementu kolekcjig, trzeba dodaća - b;set(iterable)- tworzyhashsetz iterowalnej kolekcjiiterable, w C++, na przykład z listy: https://www.tutorialspoint.com/cpp_standard_library/cpp_set_init_constructor.htm
Dzięki, prawie już rozumiem tylko jeszcze jedna rzecz, po co jest w takim razie ta część
for k in range(N):
if s[k] == 1:
break
skoro kończy się na break, co ona w ogóle wykonuje? Rozumiem, że to jest for(int k=0; k<N; k++){if (s[k]==1) k=N;}, czemu to ma służyć?
0
He, he, rzeczywiście, nie ma to sensu (ta pętla robi nic: iteruje po kolekcji i jak napotka w niej element o wartości 1 to się zatrzymuje). Algorytm na pewno dobrze działa? Może reszta linijek zaczynając od: f = set([k + 1, 0]), a kończąc na b = 0, ma też być w tej pętli (ma być wcięta), wtedy wyglądałoby to tak:
for k in range(N):
if s[k] == 1:
break
f = set([k + 1, 0]) # use a set to denote polynomial
l = k + 1
g = set([0])
a = k
b = 0
Najlepiej Wrzuć źródło tego kodu, proszę.
0
lion137 napisał(a):
He, he, rzeczywiście, nie ma to sensu (ta pętla robi nic: iteruje po kolekcji i jak napotka w niej element o wartości
1to się zatrzymuje). Algorytm na pewno dobrze działa? Może reszta linijek zaczynając od:f = set([k + 1, 0]), a kończąc nab = 0, ma też być w tej pętli (ma być wcięta), wtedy wyglądałoby to tak:for k in range(N): if s[k] == 1: break f = set([k + 1, 0]) # use a set to denote polynomial l = k + 1 g = set([0]) a = k b = 0Najlepiej Wrzuć źródło tego kodu, proszę.
Kod jest z https://github.com/bozhu/BMA/blob/master/bma.py , wytłumaczyłbyś proszę jeszcze jak działają te 2 linijki ze sobą? f = set([k + 1, 0]) tworzy tablicę np. {4, 0} , a potem
for ele in f:
d ^= s[ele + n - l]
, to ten for ele inn f: to pętla która sprawdza nam te dwa elementy w tablicy f ?
0
f = set([k + 1, 0]) tworzy zbiór (hashset); do konstruktora zbioru dajemy listę ([] - lista w Pythonie) i zwraca nam zbiór złożony z elementów listy.
To zaś:
for ele in f:
d ^= s[ele + n - l]
Pętla, jak for (auto & ele : f) {d ^= s[ele + n - 1]} w C++, a w pętli: s[i] to operator zwracający element kolekcji s o indeksie i, a dalej, jak wyżej pisałem,
d = d XOR s[ele + n - 1].
0
DarQxxx napisał(a):
Dzięki, prawie już rozumiem tylko jeszcze jedna rzecz, po co jest w takim razie ta część
for k in range(N): if s[k] == 1: breakskoro kończy się na
break, co ona w ogóle wykonuje? Rozumiem, że to jestfor(int k=0; k<N; k++){if (s[k]==1) k=N;}, czemu to ma służyć?
Ta część ustawia wartość k.
Odpowiada raczej takiej konstrukcji:
int k;
for(k=0; k<N; k++)
{
if(s[k] == 1)
break;
}
//tu coś robię z k
Po usunięciu klamer nawet wizualnie będzie podobne.
0
Pisalismy o tym, wyglada, ze to robi nic. Moze jakies pozostalosci po debuggowaniu:-)?