Analiza algorytmu ( zad6 ze zbioru matrualnego )

Question

Hej! wyjaśnił by mi ktoś jak działa algorytm z  zad6(a)  ze zbioru maturalnego z informatyki (CKE) http://www.cke.edu.pl/images/_EGZAMIN_MATURALNY_OD_2015/Materialy/Zbiory_zadan/Matura_Zbi%C3%B3r_zada%C5%84_Informatyka.pdf

Zadanie znajduje się na 18 stronie.
Powiem co rozumiem :

- rozumiem , że zawsze na pierwszym miejscu będzie " 1" wynika to z" A[1...2^k] — tablica liczb całkowitych"

i według tego "k=2 ; Początkowa zawartość tablicy A[1...2^k] -> [4, 3, 1, 2] ; Końcowa zawartość tablicy A[1...2^k] -> [1, 4, 3, 2]"  <- ( przykład ) 
Rozumiem dlaczego " 1" jest pierwsze ale idąc tropem tej tablicy to ostatnie powinno chyba być "4" a nie "2"

Czy ktoś mógłby mi wytłumaczyć mi ten przykład ( fajnie jakby ktoś to przedstawił pod względem podstawiania ale nie trzeba )

 

Answer 1

Chyba szybciej napisać własny kod, licząc ręcznie za pierwszym razem się pomyliłem.

Na początku n = 2^k = 4

Wchodzimy do wewn. pętli z s=1, j=1. Tutaj warunek jest spełniony (A[j] > A[s+j] czyli A[1] > A[2] bo 4>3). Po zamianie mamy A=[3, 4, 1, 2]. Wchodzimy do drugiego obiegu wewn. pętli z j=3 (nadal s=1). Tym razem warunek nie jest spełniony (patrzymy że A[j] > A[s+j] czyli A[3] > A[4] da nam sprzeczność 1>2). Opuszczamy wewn. pętlę bo j=5 nie spełnia warunku j<n.

Pierwsza pętla wchodzi w drugi obieg z s=2. Wchodzimy do wewn. pętli z j=1. Warunek jest spełniony (A[j] > A[s+j] czyli A[1] > A[3] bo 3>1). Po zamianie A=[1, 4, 3, 2]. Przerywamy wewn. pętlę bo j=5 nie spełnia warunku j<n. Na pierwszej pętli s=4 co nie spełnia warunku s<n (4<4).

Czyli program kończy się wykonywać z A=[1, 4, 3, 2].

Answer 2

int main() {
	int temp;
	
	int k = 3;
	int s;
	int j;
	
	int tab[] = { 8, 7, 6, 5, 4, 3, 2, 1 };
	
	int n = 1;
	
	for(int i=1; i<=k; i++)
		n *= 2;
	
	s = 1;
	
	while( s < n ) {
		j = 1;
		
		while( j < n ) {
			if( tab[j-1] > tab[j+s-1] ) {
				temp = tab[j-1];
				tab[j-1] = tab[j+s-1];
				tab[j+s-1] = temp;
			}
			
			j += 2*s;
			
			for( int i = 0; i<4; i++ ) {
				std::cout<<tab[i]<<", ";		
			}
		   	std::cout<<std::endl;
		}
		s *= 2;
	}
	
	
	return 0;
}

późno już na tłumaczenie więc załączę ten kodzik w c++ który jest implementacją pierwszego algorytmu, wyświetla zawartość tablicy co pętle, zwykle preferuję naukę przez praktykę może w ten sposób szybciej zrozumiesz algorytm, przy drobnej edycji możesz wyświetlać co się dzieje z poszczególnymi zmiennymi co myślę jest kluczem do zrozumienia całości, powodzenia ;)

Edit. Nie sprawdziłem działu i co prawda nie ma nic o językach programowania ale myślę że zdając maturę z informatyki rozszerzonej tego typu odpowiedź okaże się dość zrozumiała