Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

Napisz program, który wykorzystując sortowanie przez wybieranie, poda x najmniejszych liczb z n-elementowej tablicy liczb naturalnych dane. Swój program przetestuj dla następujących danych:

n = 17
dane = [696, 587, 501, 811, 162, 980, 18, 207, 638, 49, 329, 316, 305, 406, 25, 16, 542]
x = 5

Specyfikacja problemu:

Dane:

n – liczba elementów tablicy dane; liczba naturalna
dane – n-elementowa tablica liczb naturalnych
x – liczba najmniejszych liczb z tablicy dane, które program powinien wypisać; liczba naturalna; $x \leq n$ .

Wynik:

Program wypisuje x najmniejszych liczb z n-elementowej tablicy dane. Liczby powinny być wypisane w jednej linii i oddzielone znakiem spacji.

R1HyKDlkcRNIc1

Przykładowe rozwiązanie zadania:

Linia 1. def znajdz podkreślnik indeks podkreślnik minimum otwórz nawias okrągły n przecinek dane przecinek i zamknij nawias okrągły dwukropek. Linia 2. indeks podkreślnik najmniejszego podkreślnik elementu znak równości i. Linia 4. for j in range otwórz nawias okrągły i plus 1 przecinek n zamknij nawias okrągły dwukropek. Linia 5. if dane otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny dane otwórz nawias kwadratowy indeks podkreślnik najmniejszego podkreślnik elementu zamknij nawias kwadratowy dwukropek. Linia 6. indeks podkreślnik najmniejszego podkreślnik elementu znak równości j. Linia 8. return indeks podkreślnik najmniejszego podkreślnik elementu. Linia 10. def zamien otwórz nawias okrągły dane przecinek a przecinek b zamknij nawias okrągły dwukropek. Linia 11. tmp znak równości dane otwórz nawias kwadratowy a zamknij nawias kwadratowy. Linia 12. dane otwórz nawias kwadratowy a zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy b zamknij nawias kwadratowy. Linia 13. dane otwórz nawias kwadratowy b zamknij nawias kwadratowy znak równości tmp. Linia 15. def sortowanie podkreślnik wybieranie otwórz nawias okrągły x przecinek n przecinek dane zamknij nawias okrągły dwukropek. Linia 16. for i in range otwórz nawias okrągły 0 przecinek x zamknij nawias okrągły dwukropek. Linia 17. indeks znak równości znajdz podkreślnik indeks podkreślnik minimum otwórz nawias okrągły n przecinek dane przecinek i zamknij nawias okrągły. Linia 18. zamien otwórz nawias okrągły dane przecinek i przecinek indeks zamknij nawias okrągły. Linia 20. n znak równości 17. Linia 21. dane znak równości otwórz nawias kwadratowy 696 przecinek 587 przecinek 501 przecinek 811 przecinek 162 przecinek 980 przecinek 18 przecinek 207 przecinek 638 przecinek 49 przecinek 329 przecinek 316 przecinek 305 przecinek 406 przecinek 25 przecinek 16 przecinek 542 zamknij nawias kwadratowy. Linia 22. x znak równości 5. Linia 24. sortowanie podkreślnik wybieranie otwórz nawias okrągły x przecinek n przecinek dane zamknij nawias okrągły. Linia 26. for i in range otwórz nawias okrągły x zamknij nawias okrągły dwukropek. Linia 27. print otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły.

def znajdz_indeks_minimum(n, dane, i):
	indeks_najmniejszego_elementu = i

	for j in range(i + 1, n):
		if dane[j] < dane[indeks_najmniejszego_elementu]:
			indeks_najmniejszego_elementu = j

	return indeks_najmniejszego_elementu

def zamien(dane, a, b):
	tmp = dane[a]
	dane[a] = dane[b]
	dane[b] = tmp

def sortowanie_wybieranie(x,n, dane):
	for i in range(0, x):
		indeks = znajdz_indeks_minimum(n, dane, i)
		zamien(dane, i, indeks)

n = 17
dane = [696, 587, 501, 811, 162, 980, 18, 207, 638, 49, 329, 316, 305, 406, 25, 16, 542]
x = 5

sortowanie_wybieranie(x, n, dane)

for i in range(x):
	print(dane[i], end=" ")

Ćwiczenie 2

Napisz program, który sortuje niemalejąco n-elementową tablicę dane z użyciem algorytmu sortowania przez wybieranie i wypisuje dwie liczby naturalne będące liczbą porównań i liczbą przestawień wykonaną przez algorytm. Swój program przetestuj dla następujących zestawów danych:

n1 = 17, dane1 = [8, 19, 35, 67, 76, 101, 112, 124, 147, 153, 178, 199, 216, 235, 245, 261, 281]
n2 = 17, dane2 = [274, 258, 247, 227, 210, 190, 174, 166, 152, 123, 108, 98, 68, 57, 47, 22, 9]
n3 = 17, dane3 = [22, 271, 115, 199, 95, 260, 265, 161, 186, 151, 256, 255, 224, 36, 138, 142, 236]
n4 = 7, dane4 = [117, 151, 191, 190, 239, 128, 139]

Specyfikacja problemu:

Dane:

n – liczba elementów w tablicy dane
dane – n-elementowa tablica liczb naturalnych do posortowania

Wynik:

Program wypisuje dwie liczby: liczbę porównań oraz liczbę przestawień wykonanych w trakcie działania algorytmu sortowania. Liczby powinny być wypisane w jednej linii i oddzielone znakiem spacji.

Uwaga!

Program powinien wypisać po dwie liczby dla każdego zestawu danych, co daje w sumie osiem liczb wypisanych w czterech liniach.

Przykład 1

Dla zestawu danych:

n = 4
dane = [15, 17, 5, 4]

program powininen wypisać: 6 3.

Algorytm kolejno wykonuje następujące operacje:

porównanie 17 z 15
porównanie 5 z 15
porównanie 4 z 5
zamiana 15 z 4
porównanie 5 z 17
porównanie 15 z 5
zamiana 17 z 5
porównanie 15 z 17
zamiana 17 z 15

R1UPost8GsCXD1

Przykładowe rozwiązanie zadania:

Linia 1. def zamien otwórz nawias okrągły dane przecinek a przecinek b zamknij nawias okrągły dwukropek. Linia 2. tmp znak równości dane otwórz nawias kwadratowy a zamknij nawias kwadratowy. Linia 3. dane otwórz nawias kwadratowy a zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy b zamknij nawias kwadratowy. Linia 4. dane otwórz nawias kwadratowy b zamknij nawias kwadratowy znak równości tmp. Linia 6. def sortowanie podkreślnik wybieranie otwórz nawias okrągły n przecinek dane zamknij nawias okrągły dwukropek. Linia 7. porownania znak równości 0. Linia 8. zamiany znak równości 0. Linia 10. for i in range otwórz nawias okrągły 0 przecinek n minus 1 zamknij nawias okrągły dwukropek. Linia 11. indeks podkreślnik najmniejszego podkreślnik elementu znak równości i. Linia 13. for j in range otwórz nawias okrągły i plus 1 przecinek n zamknij nawias okrągły dwukropek. Linia 14. if dane otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny dane otwórz nawias kwadratowy indeks podkreślnik najmniejszego podkreślnik elementu zamknij nawias kwadratowy dwukropek. Linia 15. indeks podkreślnik najmniejszego podkreślnik elementu znak równości j. Linia 16. porownania plus znak równości 1. Linia 18. zamien otwórz nawias okrągły dane przecinek i przecinek indeks podkreślnik najmniejszego podkreślnik elementu zamknij nawias okrągły. Linia 19. zamiany plus znak równości 1. Linia 21. print otwórz nawias okrągły porownania przecinek zamiany zamknij nawias okrągły. Linia 23. n1 znak równości 17. Linia 24. dane1 znak równości otwórz nawias kwadratowy 8 przecinek 19 przecinek 35 przecinek 67 przecinek 76 przecinek 101 przecinek 112 przecinek 124 przecinek 147 przecinek 153 przecinek 178 przecinek 199 przecinek 216 przecinek 235 przecinek 245 przecinek 261 przecinek 281 zamknij nawias kwadratowy. Linia 26. n2 znak równości 17. Linia 27. dane2 znak równości otwórz nawias kwadratowy 274 przecinek 258 przecinek 247 przecinek 227 przecinek 210 przecinek 190 przecinek 174 przecinek 166 przecinek 152 przecinek 123 przecinek 108 przecinek 98 przecinek 68 przecinek 57 przecinek 47 przecinek 22 przecinek 9 zamknij nawias kwadratowy. Linia 29. n3 znak równości 17. Linia 30. dane3 znak równości otwórz nawias kwadratowy 22 przecinek 271 przecinek 115 przecinek 199 przecinek 95 przecinek 260 przecinek 265 przecinek 161 przecinek 186 przecinek 151 przecinek 256 przecinek 255 przecinek 224 przecinek 36 przecinek 138 przecinek 142 przecinek 236 zamknij nawias kwadratowy. Linia 32. n4 znak równości 7. Linia 33. dane4 znak równości otwórz nawias kwadratowy 117 przecinek 151 przecinek 191 przecinek 190 przecinek 239 przecinek 128 przecinek 139 zamknij nawias kwadratowy. Linia 35. sortowanie podkreślnik wybieranie otwórz nawias okrągły n1 przecinek dane1 zamknij nawias okrągły. Linia 36. sortowanie podkreślnik wybieranie otwórz nawias okrągły n2 przecinek dane2 zamknij nawias okrągły. Linia 37. sortowanie podkreślnik wybieranie otwórz nawias okrągły n3 przecinek dane3 zamknij nawias okrągły. Linia 38. sortowanie podkreślnik wybieranie otwórz nawias okrągły n4 przecinek dane4 zamknij nawias okrągły.

def zamien(dane, a, b):
	tmp = dane[a]
	dane[a] = dane[b]
	dane[b] = tmp

def sortowanie_wybieranie(n, dane):
	porownania = 0
	zamiany = 0

	for i in range(0, n - 1):
		indeks_najmniejszego_elementu = i

		for j in range(i + 1, n):
			if dane[j] < dane[indeks_najmniejszego_elementu]:
				indeks_najmniejszego_elementu = j
			porownania += 1

		zamien(dane,i,indeks_najmniejszego_elementu)
		zamiany += 1

	print(porownania, zamiany)

n1 = 17
dane1 = [8, 19, 35, 67, 76, 101, 112, 124, 147, 153, 178, 199, 216, 235, 245, 261, 281]

n2 = 17
dane2 = [274, 258, 247, 227, 210, 190, 174, 166, 152, 123, 108, 98, 68, 57, 47, 22, 9]

n3 = 17
dane3 = [22, 271, 115, 199, 95, 260, 265, 161, 186, 151, 256, 255, 224, 36, 138, 142, 236]

n4 = 7
dane4 = [117, 151, 191, 190, 239, 128, 139]

sortowanie_wybieranie(n1, dane1)
sortowanie_wybieranie(n2, dane2)
sortowanie_wybieranie(n3, dane3)
sortowanie_wybieranie(n4, dane4)

Przeczytaj

Dla nauczyciela