Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

Dopisz brakujący fragment kodu w programie, który sortuje nierosnąco daną mu listę.

Swoje rozwiązanie przetestuj dla listy lista = [5, 8, 4, 7, 3, 9, 11, 16, 18, 19, 99, 20, 65].

Specyfikacja:

Dane:

lista – dane do posortowania; lista zawierająca liczby całkowite

Wynik:

Na standardowym wyjściu wyświetlane są posortowane nierosnąco elementy listy lista.

R1VagrqcJdCHH1

Przykładowe rozwiązanie zadania:

Linia 1. def scal podkreślnik dwie podkreślnik czesci otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks przecinek indeks podkreślnik konca zamknij nawias okrągły dwukropek. Linia 2. rozmiar podkreślnik lewej podkreślnik czesci znak równości srodkowy podkreślnik indeks minus indeks podkreślnik poczatku plus 1. Linia 3. rozmiar podkreślnik prawej podkreślnik czesci znak równości indeks podkreślnik konca minus srodkowy podkreślnik indeks. Linia 5. kopia podkreślnik lewej podkreślnik czesci znak równości lista otwórz nawias kwadratowy indeks podkreślnik poczatku dwukropek indeks podkreślnik poczatku plus rozmiar podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 6. kopia podkreślnik prawej podkreślnik czesci znak równości lista otwórz nawias kwadratowy srodkowy podkreślnik indeks plus 1 dwukropek srodkowy podkreślnik indeks plus rozmiar podkreślnik prawej podkreślnik czesci plus 1 zamknij nawias kwadratowy. Linia 8. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci znak równości 0. Linia 9. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci znak równości 0. Linia 10. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy znak równości indeks podkreślnik poczatku. Linia 12. while biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik lewej podkreślnik czesci and biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik prawej podkreślnik czesci dwukropek. Linia 13. if kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy dwukropek. Linia 14. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 15. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci plus znak równości 1. Linia 16. else dwukropek. Linia 17. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy. Linia 18. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci plus znak równości 1. Linia 20. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 22. while biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik lewej podkreślnik czesci dwukropek. Linia 23. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 24. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci plus znak równości 1. Linia 25. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 27. while biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik prawej podkreślnik czesci dwukropek. Linia 28. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy. Linia 29. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci plus znak równości 1. Linia 30. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 33. def sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek indeks podkreślnik konca zamknij nawias okrągły dwukropek. Linia 34. if indeks podkreślnik poczatku otwórz nawias ostrokątny indeks podkreślnik konca dwukropek. Linia 36. kratka minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus. Linia 37. kratka Brakująca część programu. Linia 39. kratka Krok 1 minus podziel liste na dwie czesci. Linia 40. srodkowy podkreślnik indeks znak równości otwórz nawias okrągły indeks podkreślnik konca plus indeks podkreślnik poczatku zamknij nawias okrągły prawy ukośnik prawy ukośnik 2. Linia 42. kratka Krok 2 minus podziel lewą część dalej. Linia 43. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks zamknij nawias okrągły. Linia 45. kratka Krok 3 minus podziel prawą część dalej. Linia 46. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek srodkowy podkreślnik indeks plus 1 przecinek indeks podkreślnik konca zamknij nawias okrągły. Linia 48. kratka Krok 4 minus scal dwie czesci. Linia 49. scal podkreślnik dwie podkreślnik czesci otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks przecinek indeks podkreślnik konca zamknij nawias okrągły. Linia 51. kratka minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus. Linia 53. else dwukropek. Linia 54. return. Linia 57. lista znak równości otwórz nawias kwadratowy 5 przecinek 8 przecinek 4 przecinek 7 przecinek 3 przecinek 9 przecinek 11 przecinek 16 przecinek 18 przecinek 19 przecinek 99 przecinek 20 przecinek 65 zamknij nawias kwadratowy. Linia 59. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek 0 przecinek len otwórz nawias okrągły lista zamknij nawias okrągły minus 1 zamknij nawias okrągły. Linia 61. print otwórz nawias okrągły lista zamknij nawias okrągły.

def scal_dwie_czesci(lista, indeks_poczatku, srodkowy_indeks, indeks_konca):
	rozmiar_lewej_czesci = srodkowy_indeks - indeks_poczatku + 1
	rozmiar_prawej_czesci = indeks_konca - srodkowy_indeks

	kopia_lewej_czesci = lista[indeks_poczatku:indeks_poczatku + rozmiar_lewej_czesci]
	kopia_prawej_czesci = lista[srodkowy_indeks + 1:srodkowy_indeks + rozmiar_prawej_czesci + 1]

	biezacy_indeks_lewej_czesci = 0
	biezacy_indeks_prawej_czesci = 0
	biezacy_indeks_oryginalnej_listy = indeks_poczatku

	while biezacy_indeks_lewej_czesci < rozmiar_lewej_czesci and biezacy_indeks_prawej_czesci < rozmiar_prawej_czesci:
		if kopia_lewej_czesci[biezacy_indeks_lewej_czesci] >= kopia_prawej_czesci[biezacy_indeks_prawej_czesci]:
			lista[biezacy_indeks_oryginalnej_listy] = kopia_lewej_czesci[biezacy_indeks_lewej_czesci]
			biezacy_indeks_lewej_czesci += 1
		else:
			lista[biezacy_indeks_oryginalnej_listy] = kopia_prawej_czesci[biezacy_indeks_prawej_czesci]
			biezacy_indeks_prawej_czesci += 1

		biezacy_indeks_oryginalnej_listy += 1

	while biezacy_indeks_lewej_czesci < rozmiar_lewej_czesci:
		lista[biezacy_indeks_oryginalnej_listy] = kopia_lewej_czesci[biezacy_indeks_lewej_czesci]
		biezacy_indeks_lewej_czesci += 1
		biezacy_indeks_oryginalnej_listy += 1

	while biezacy_indeks_prawej_czesci < rozmiar_prawej_czesci:
		lista[biezacy_indeks_oryginalnej_listy] = kopia_prawej_czesci[biezacy_indeks_prawej_czesci]
		biezacy_indeks_prawej_czesci += 1
		biezacy_indeks_oryginalnej_listy += 1


def sortuj_przez_scalanie(lista, indeks_poczatku, indeks_konca):
	if indeks_poczatku < indeks_konca:
        
		# ------------------------
		# Brakująca część programu

		# Krok 1 - podziel liste na dwie czesci
		srodkowy_indeks = (indeks_konca + indeks_poczatku) // 2

		# Krok 2 - podziel lewą część dalej
		sortuj_przez_scalanie(lista, indeks_poczatku, srodkowy_indeks)

		# Krok 3 - podziel prawą część dalej
		sortuj_przez_scalanie(lista, srodkowy_indeks + 1, indeks_konca)

		# Krok 4 - scal dwie czesci
		scal_dwie_czesci(lista, indeks_poczatku, srodkowy_indeks, indeks_konca)

		# ------------------------

	else:
		return


lista = [5, 8, 4, 7, 3, 9, 11, 16, 18, 19, 99, 20, 65]

sortuj_przez_scalanie(lista, 0, len(lista) - 1)

print(lista)

Ćwiczenie 2

Dopisz brakujący fragment kodu w programie, który sortuje nierosnąco daną mu listę.

Swoje rozwiązanie przetestuj dla listy lista = [5, 8, 4, 7, 3, 9, 11, 16, 18, 19, 99, 20, 65].

Specyfikacja:

Dane:

lista – lista zawierająca liczby całkowite

Wynik:

Na standardowym wyjściu wyświetlane są posortowane nierosnąco elementy listy lista.

RxnBnVTblxP7P1

Przykładowe rozwiązanie zadania:

Linia 1. def scal podkreślnik dwie podkreślnik czesci otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks przecinek indeks podkreślnik konca zamknij nawias okrągły dwukropek. Linia 2. rozmiar podkreślnik lewej podkreślnik czesci znak równości srodkowy podkreślnik indeks minus indeks podkreślnik poczatku plus 1. Linia 3. rozmiar podkreślnik prawej podkreślnik czesci znak równości indeks podkreślnik konca minus srodkowy podkreślnik indeks. Linia 5. kopia podkreślnik lewej podkreślnik czesci znak równości lista otwórz nawias kwadratowy indeks podkreślnik poczatku dwukropek indeks podkreślnik poczatku plus rozmiar podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 6. kopia podkreślnik prawej podkreślnik czesci znak równości lista otwórz nawias kwadratowy srodkowy podkreślnik indeks plus 1 dwukropek srodkowy podkreślnik indeks plus rozmiar podkreślnik prawej podkreślnik czesci plus 1 zamknij nawias kwadratowy. Linia 8. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci znak równości 0. Linia 9. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci znak równości 0. Linia 10. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy znak równości indeks podkreślnik poczatku. Linia 12. kratka minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus. Linia 13. kratka Brakująca część programu. Linia 15. while biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik lewej podkreślnik czesci and biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik prawej podkreślnik czesci dwukropek. Linia 16. if kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy dwukropek. Linia 17. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 18. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci plus znak równości 1. Linia 19. else dwukropek. Linia 20. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy. Linia 21. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci plus znak równości 1. Linia 23. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 25. while biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik lewej podkreślnik czesci dwukropek. Linia 26. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 27. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci plus znak równości 1. Linia 28. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 30. while biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik prawej podkreślnik czesci dwukropek. Linia 31. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy. Linia 32. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci plus znak równości 1. Linia 33. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 35. kratka minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus. Linia 38. def sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek indeks podkreślnik konca zamknij nawias okrągły dwukropek. Linia 39. if indeks podkreślnik poczatku otwórz nawias ostrokątny indeks podkreślnik konca dwukropek. Linia 40. kratka Krok 1 minus podziel liste na dwie czesci. Linia 41. srodkowy podkreślnik indeks znak równości otwórz nawias okrągły indeks podkreślnik konca plus indeks podkreślnik poczatku zamknij nawias okrągły prawy ukośnik prawy ukośnik 2. Linia 43. kratka Krok 2 minus podziel lewą część dalej. Linia 44. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks zamknij nawias okrągły. Linia 46. kratka Krok 3 minus podziel prawą część dalej. Linia 47. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek srodkowy podkreślnik indeks plus 1 przecinek indeks podkreślnik konca zamknij nawias okrągły. Linia 49. kratka Krok 4 minus scal dwie czesci. Linia 50. scal podkreślnik dwie podkreślnik czesci otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks przecinek indeks podkreślnik konca zamknij nawias okrągły. Linia 51. else dwukropek. Linia 52. return. Linia 55. lista znak równości otwórz nawias kwadratowy 5 przecinek 8 przecinek 4 przecinek 7 przecinek 3 przecinek 9 przecinek 11 przecinek 16 przecinek 18 przecinek 19 przecinek 99 przecinek 20 przecinek 65 zamknij nawias kwadratowy. Linia 57. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek 0 przecinek len otwórz nawias okrągły lista zamknij nawias okrągły minus 1 zamknij nawias okrągły. Linia 59. print otwórz nawias okrągły lista zamknij nawias okrągły.

def scal_dwie_czesci(lista, indeks_poczatku, srodkowy_indeks, indeks_konca):
    rozmiar_lewej_czesci = srodkowy_indeks - indeks_poczatku + 1
    rozmiar_prawej_czesci = indeks_konca - srodkowy_indeks

    kopia_lewej_czesci = lista[indeks_poczatku:indeks_poczatku + rozmiar_lewej_czesci]
    kopia_prawej_czesci = lista[srodkowy_indeks + 1:srodkowy_indeks + rozmiar_prawej_czesci + 1]

    biezacy_indeks_lewej_czesci = 0
    biezacy_indeks_prawej_czesci = 0
    biezacy_indeks_oryginalnej_listy = indeks_poczatku
    
    # ----------------------
    # Brakująca część programu

    while biezacy_indeks_lewej_czesci < rozmiar_lewej_czesci and biezacy_indeks_prawej_czesci < rozmiar_prawej_czesci:
        if kopia_lewej_czesci[biezacy_indeks_lewej_czesci] >= kopia_prawej_czesci[biezacy_indeks_prawej_czesci]:
            lista[biezacy_indeks_oryginalnej_listy] = kopia_lewej_czesci[biezacy_indeks_lewej_czesci]
            biezacy_indeks_lewej_czesci += 1
        else:
            lista[biezacy_indeks_oryginalnej_listy] = kopia_prawej_czesci[biezacy_indeks_prawej_czesci]
            biezacy_indeks_prawej_czesci += 1

        biezacy_indeks_oryginalnej_listy += 1

    while biezacy_indeks_lewej_czesci < rozmiar_lewej_czesci:
        lista[biezacy_indeks_oryginalnej_listy] = kopia_lewej_czesci[biezacy_indeks_lewej_czesci]
        biezacy_indeks_lewej_czesci += 1
        biezacy_indeks_oryginalnej_listy += 1

    while biezacy_indeks_prawej_czesci < rozmiar_prawej_czesci:
        lista[biezacy_indeks_oryginalnej_listy] = kopia_prawej_czesci[biezacy_indeks_prawej_czesci]
        biezacy_indeks_prawej_czesci += 1
        biezacy_indeks_oryginalnej_listy += 1
        
    # ----------------------


def sortuj_przez_scalanie(lista, indeks_poczatku, indeks_konca):
    if indeks_poczatku < indeks_konca:
        # Krok 1 - podziel liste na dwie czesci
        srodkowy_indeks = (indeks_konca + indeks_poczatku) // 2

        # Krok 2 - podziel lewą część dalej
        sortuj_przez_scalanie(lista, indeks_poczatku, srodkowy_indeks)

        # Krok 3 - podziel prawą część dalej
        sortuj_przez_scalanie(lista, srodkowy_indeks + 1, indeks_konca)

        # Krok 4 - scal dwie czesci
        scal_dwie_czesci(lista, indeks_poczatku, srodkowy_indeks, indeks_konca)
    else:
        return


lista = [5, 8, 4, 7, 3, 9, 11, 16, 18, 19, 99, 20, 65]

sortuj_przez_scalanie(lista, 0, len(lista) - 1)

print(lista)

Ćwiczenie 3

Napisz program, który, używając sortowania przez scalanie, posortuje niemalejąco zbiór lista.

Swoje rozwiązanie przetestuj dla listy lista = [5, 8, 4, 7, 3, 9, 11, 16, 18, 19, 99, 20, 65].

Specyfikacja:

Dane:

lista – lista zawierająca liczby całkowite

Wynik:

Na standardowym wyjściu wyświetlane są posortowane niemalejąco elementy listy lista.

RU4JeupQbCt0z1

Przykładowe rozwiązanie zadania:

Linia 1. def scal podkreślnik dwie podkreślnik czesci otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks przecinek indeks podkreślnik konca zamknij nawias okrągły dwukropek. Linia 2. rozmiar podkreślnik lewej podkreślnik czesci znak równości srodkowy podkreślnik indeks minus indeks podkreślnik poczatku plus 1. Linia 3. rozmiar podkreślnik prawej podkreślnik czesci znak równości indeks podkreślnik konca minus srodkowy podkreślnik indeks. Linia 5. kopia podkreślnik lewej podkreślnik czesci znak równości lista otwórz nawias kwadratowy indeks podkreślnik poczatku dwukropek indeks podkreślnik poczatku plus rozmiar podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 6. kopia podkreślnik prawej podkreślnik czesci znak równości lista otwórz nawias kwadratowy srodkowy podkreślnik indeks plus 1 dwukropek srodkowy podkreślnik indeks plus rozmiar podkreślnik prawej podkreślnik czesci plus 1 zamknij nawias kwadratowy. Linia 8. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci znak równości 0. Linia 9. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci znak równości 0. Linia 10. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy znak równości indeks podkreślnik poczatku. Linia 12. while biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik lewej podkreślnik czesci and biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik prawej podkreślnik czesci dwukropek. Linia 13. if kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy dwukropek. Linia 14. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 15. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci plus znak równości 1. Linia 16. else dwukropek. Linia 17. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy. Linia 18. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci plus znak równości 1. Linia 20. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 22. while biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik lewej podkreślnik czesci dwukropek. Linia 23. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik lewej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci zamknij nawias kwadratowy. Linia 24. biezacy podkreślnik indeks podkreślnik lewej podkreślnik czesci plus znak równości 1. Linia 25. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 27. while biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci otwórz nawias ostrokątny rozmiar podkreślnik prawej podkreślnik czesci dwukropek. Linia 28. lista otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy zamknij nawias kwadratowy znak równości kopia podkreślnik prawej podkreślnik czesci otwórz nawias kwadratowy biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci zamknij nawias kwadratowy. Linia 29. biezacy podkreślnik indeks podkreślnik prawej podkreślnik czesci plus znak równości 1. Linia 30. biezacy podkreślnik indeks podkreślnik oryginalnej podkreślnik listy plus znak równości 1. Linia 33. def sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek indeks podkreślnik konca zamknij nawias okrągły dwukropek. Linia 34. if indeks podkreślnik poczatku otwórz nawias ostrokątny indeks podkreślnik konca dwukropek. Linia 35. kratka Krok 1 minus podziel liste na dwie czesci. Linia 36. srodkowy podkreślnik indeks znak równości otwórz nawias okrągły indeks podkreślnik konca plus indeks podkreślnik poczatku zamknij nawias okrągły prawy ukośnik prawy ukośnik 2. Linia 38. kratka Krok 2 minus podziel lewą część dalej. Linia 39. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks zamknij nawias okrągły. Linia 41. kratka Krok 3 minus podziel prawą część dalej. Linia 42. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek srodkowy podkreślnik indeks plus 1 przecinek indeks podkreślnik konca zamknij nawias okrągły. Linia 44. kratka Krok 4 minus scal dwie czesci. Linia 45. scal podkreślnik dwie podkreślnik czesci otwórz nawias okrągły lista przecinek indeks podkreślnik poczatku przecinek srodkowy podkreślnik indeks przecinek indeks podkreślnik konca zamknij nawias okrągły. Linia 46. else dwukropek. Linia 47. return. Linia 50. lista znak równości otwórz nawias kwadratowy 5 przecinek 8 przecinek 4 przecinek 7 przecinek 3 przecinek 9 przecinek 11 przecinek 16 przecinek 18 przecinek 19 przecinek 99 przecinek 20 przecinek 65 zamknij nawias kwadratowy. Linia 52. sortuj podkreślnik przez podkreślnik scalanie otwórz nawias okrągły lista przecinek 0 przecinek len otwórz nawias okrągły lista zamknij nawias okrągły minus 1 zamknij nawias okrągły. Linia 54. print otwórz nawias okrągły lista zamknij nawias okrągły.

def scal_dwie_czesci(lista, indeks_poczatku, srodkowy_indeks, indeks_konca):
	rozmiar_lewej_czesci = srodkowy_indeks - indeks_poczatku + 1
	rozmiar_prawej_czesci = indeks_konca - srodkowy_indeks

	kopia_lewej_czesci = lista[indeks_poczatku:indeks_poczatku + rozmiar_lewej_czesci]
	kopia_prawej_czesci = lista[srodkowy_indeks + 1:srodkowy_indeks + rozmiar_prawej_czesci + 1]

	biezacy_indeks_lewej_czesci = 0
	biezacy_indeks_prawej_czesci = 0
	biezacy_indeks_oryginalnej_listy = indeks_poczatku

	while biezacy_indeks_lewej_czesci < rozmiar_lewej_czesci and biezacy_indeks_prawej_czesci < rozmiar_prawej_czesci:
		if kopia_lewej_czesci[biezacy_indeks_lewej_czesci] <= kopia_prawej_czesci[biezacy_indeks_prawej_czesci]:
			lista[biezacy_indeks_oryginalnej_listy] = kopia_lewej_czesci[biezacy_indeks_lewej_czesci]
			biezacy_indeks_lewej_czesci += 1
		else:
			lista[biezacy_indeks_oryginalnej_listy] = kopia_prawej_czesci[biezacy_indeks_prawej_czesci]
			biezacy_indeks_prawej_czesci += 1

		biezacy_indeks_oryginalnej_listy += 1

	while biezacy_indeks_lewej_czesci < rozmiar_lewej_czesci:
		lista[biezacy_indeks_oryginalnej_listy] = kopia_lewej_czesci[biezacy_indeks_lewej_czesci]
		biezacy_indeks_lewej_czesci += 1
		biezacy_indeks_oryginalnej_listy += 1

	while biezacy_indeks_prawej_czesci < rozmiar_prawej_czesci:
		lista[biezacy_indeks_oryginalnej_listy] = kopia_prawej_czesci[biezacy_indeks_prawej_czesci]
		biezacy_indeks_prawej_czesci += 1
		biezacy_indeks_oryginalnej_listy += 1


def sortuj_przez_scalanie(lista, indeks_poczatku, indeks_konca):
	if indeks_poczatku < indeks_konca:
		# Krok 1 - podziel liste na dwie czesci
		srodkowy_indeks = (indeks_konca + indeks_poczatku) // 2

		# Krok 2 - podziel lewą część dalej
		sortuj_przez_scalanie(lista, indeks_poczatku, srodkowy_indeks)

		# Krok 3 - podziel prawą część dalej
		sortuj_przez_scalanie(lista, srodkowy_indeks + 1, indeks_konca)

		# Krok 4 - scal dwie czesci
		scal_dwie_czesci(lista, indeks_poczatku, srodkowy_indeks, indeks_konca)
	else:
		return


lista = [5, 8, 4, 7, 3, 9, 11, 16, 18, 19, 99, 20, 65]

sortuj_przez_scalanie(lista, 0, len(lista) - 1)

print(lista)

Ćwiczenie 4

Napisz program, w którym scalisz dwie posortowane tablice w jedną (również posortowaną). Wypisz utworzoną tablicę, oddzielając jej elementy znakiem spacji.

Swój program przetestuj dla następujących tablic:

tablica1 = [ 4, 65, 432, 543, 654, 7654 ]
tablica2 = [ 2, 23, 45, 65, 75, 432, 9211 ]

Specyfikacja:

Dane:

n – liczba naturalna
m – liczba naturalna
tablica1 – n-elementowa posortowana niemalejąco tablica liczb naturalnych
tablica2 – m-elementowa posortowana niemalejąco tablica liczb naturalnych

Wynik:

Na standardowym wyjściu wyświetlane są wszystkie elementy posortowanej niemalejąco tablicy, będącej wynikiem scalenia tablic wejściowych. Elementy są oddzielone pojedynczym znakiem spacji.

R1AnCzzkN05xp

Linia 1. tablica1 znak równości otwórz nawias kwadratowy 4 przecinek 65 przecinek 432 przecinek 543 przecinek 654 przecinek 7654 zamknij nawias kwadratowy. Linia 2. tablica2 znak równości otwórz nawias kwadratowy 2 przecinek 23 przecinek 45 przecinek 65 przecinek 75 przecinek 432 przecinek 9211 zamknij nawias kwadratowy. Linia 4. def scalTablice otwórz nawias okrągły tablica1 przecinek tablica1Dlugosc przecinek tablica2 przecinek tablica2Dlugosc przecinek tablicaDocelowa zamknij nawias okrągły dwukropek. Linia 5. biezacyIndeksWTablicy1 znak równości 0. Linia 6. biezacyIndeksWTablicy2 znak równości 0. Linia 7. biezacyIndeksWTablicyDocelowej znak równości 0. Linia 9. while biezacyIndeksWTablicy1 otwórz nawias ostrokątny tablica1Dlugosc and biezacyIndeksWTablicy2 otwórz nawias ostrokątny tablica2Dlugosc dwukropek. Linia 10. if tablica1 otwórz nawias kwadratowy biezacyIndeksWTablicy1 zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości tablica2 otwórz nawias kwadratowy biezacyIndeksWTablicy2 zamknij nawias kwadratowy dwukropek. Linia 11. tablicaDocelowa otwórz nawias kwadratowy biezacyIndeksWTablicyDocelowej zamknij nawias kwadratowy znak równości tablica1 otwórz nawias kwadratowy biezacyIndeksWTablicy1 zamknij nawias kwadratowy. Linia 12. biezacyIndeksWTablicy1 plus znak równości 1. Linia 13. else dwukropek. Linia 14. tablicaDocelowa otwórz nawias kwadratowy biezacyIndeksWTablicyDocelowej zamknij nawias kwadratowy znak równości tablica2 otwórz nawias kwadratowy biezacyIndeksWTablicy2 zamknij nawias kwadratowy. Linia 15. biezacyIndeksWTablicy2 plus znak równości 1. Linia 16. biezacyIndeksWTablicyDocelowej plus znak równości 1. Linia 18. while biezacyIndeksWTablicy1 otwórz nawias ostrokątny tablica1Dlugosc dwukropek. Linia 19. tablicaDocelowa otwórz nawias kwadratowy biezacyIndeksWTablicyDocelowej zamknij nawias kwadratowy znak równości tablica1 otwórz nawias kwadratowy biezacyIndeksWTablicy1 zamknij nawias kwadratowy. Linia 20. biezacyIndeksWTablicy1 plus znak równości 1. Linia 21. biezacyIndeksWTablicyDocelowej plus znak równości 1. Linia 23. while biezacyIndeksWTablicy2 otwórz nawias ostrokątny tablica2Dlugosc dwukropek. Linia 24. tablicaDocelowa otwórz nawias kwadratowy biezacyIndeksWTablicyDocelowej zamknij nawias kwadratowy znak równości tablica2 otwórz nawias kwadratowy biezacyIndeksWTablicy2 zamknij nawias kwadratowy. Linia 25. biezacyIndeksWTablicy2 plus znak równości 1. Linia 26. biezacyIndeksWTablicyDocelowej plus znak równości 1. Linia 28. tablicaDocelowa znak równości otwórz nawias kwadratowy 0 zamknij nawias kwadratowy asterysk 13. Linia 30. scalTablice otwórz nawias okrągły tablica1 przecinek len otwórz nawias okrągły tablica1 zamknij nawias okrągły przecinek tablica2 przecinek len otwórz nawias okrągły tablica2 zamknij nawias okrągły przecinek tablicaDocelowa zamknij nawias okrągły. Linia 32. for i in range otwórz nawias okrągły 13 zamknij nawias okrągły dwukropek. Linia 33. print otwórz nawias okrągły tablicaDocelowa otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły.

tablica1 = [4, 65, 432, 543, 654, 7654]
tablica2 = [2, 23, 45, 65, 75, 432, 9211]

def scalTablice(tablica1, tablica1Dlugosc, tablica2, tablica2Dlugosc, tablicaDocelowa):
    biezacyIndeksWTablicy1 = 0
    biezacyIndeksWTablicy2 = 0
    biezacyIndeksWTablicyDocelowej = 0

    while biezacyIndeksWTablicy1 < tablica1Dlugosc and biezacyIndeksWTablicy2 < tablica2Dlugosc:
        if tablica1[biezacyIndeksWTablicy1] <= tablica2[biezacyIndeksWTablicy2]:
            tablicaDocelowa[biezacyIndeksWTablicyDocelowej] = tablica1[biezacyIndeksWTablicy1]
            biezacyIndeksWTablicy1 += 1
        else:
            tablicaDocelowa[biezacyIndeksWTablicyDocelowej] = tablica2[biezacyIndeksWTablicy2]
            biezacyIndeksWTablicy2 += 1
        biezacyIndeksWTablicyDocelowej += 1

    while biezacyIndeksWTablicy1 < tablica1Dlugosc:
        tablicaDocelowa[biezacyIndeksWTablicyDocelowej] = tablica1[biezacyIndeksWTablicy1]
        biezacyIndeksWTablicy1 += 1
        biezacyIndeksWTablicyDocelowej += 1

    while biezacyIndeksWTablicy2 < tablica2Dlugosc:
        tablicaDocelowa[biezacyIndeksWTablicyDocelowej] = tablica2[biezacyIndeksWTablicy2]
        biezacyIndeksWTablicy2 += 1
        biezacyIndeksWTablicyDocelowej += 1

tablicaDocelowa = [0] * 13

scalTablice(tablica1, len(tablica1), tablica2, len(tablica2), tablicaDocelowa)

for i in range(13):
    print(tablicaDocelowa[i], end=" ")

Symulacja interaktywna

Dla nauczyciela