This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
1) oraz cyklem [1 2 ... m] jeśli m parzyste. m
m
D o w ó d przebiega przez indukcję względem m, j a k zwykle w przypadku d o wodu poprawności algorytmów rekurencyjnych. Łatwo się bezpośrednio prze konać, że warunki W j , W są prawdziwe niech więc m > 3 . Wykażemy W przy założeniu prawdziwości W _ i . D o w ó d rozbijemy n a dwa przypadki, w za leżności od tego, czy m jest parzyste czy nieparzyste. 2
m
m
m nieparzyste. N a mocy założenia indukcyjnego wykonanie PERM(m—l) w wierszu 14 powoduje za każdym razem przesunięcie zawartości P [ l ] , P [m — 1] wzdłuż cyklu [l 2 ... m — l]. Transpozycja P [ni] -.= •.P [m-1] w wier szu 15 wybiera więc za każdym razem inny element do P [m]. Jeśli początkowo P [z] = ( i „ K i < m , t o w P [m] są umieszczane kolejno elementy a , a _, « m - 3 , •••> Ou m-i-PERM(m) generuje więc wszystkie permutacje elementów P[l],...,P[m]. Zauważmy, że przesunięcie P [ 1 ] , P [m — l ] wzdłuż cyklu [1 2 ... m— 1], a na stępnie dokonanie transpozycji P [m] ••= •• P [m — 1] jest równoważne przesunięciu P [I], ...,P [m] wzdłuż cyklu [1 2 ... m-3 m-2 m m-1] długości m. Gdyby transpozycja w wierszu 15 była dokonywana dla każdego i < m, t o wykonanie pętli 13 spowodowałoby sprowadzenie wszystkich elementów n a swoje początko we miejsca. W rzeczywistości natomiast ostatnia transpozycja, dla i = n, nie jest wykonywana. Zatem