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ć?
#!/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
To teraz, których instrukcji Pythona, nie Rozumiesz, to Ci napiszę czym one są w C++.
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 += ' + '
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)
- tworzyhashset
z iterowalnej kolekcjiiterable
, w C++, na przykład z listy: https://www.tutorialspoint.com/cpp_standard_library/cpp_set_init_constructor.htm
lion137 napisał(a):
W Pythonie scope wyznaczają wcięcia, więc ten
for
koń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)
- tworzyhashset
z 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ć?
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ę.
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
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 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 = 0
Najlepiej 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
?
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]
.
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: break
skoro 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.
Pisalismy o tym, wyglada, ze to robi nic. Moze jakies pozostalosci po debuggowaniu:-)?