Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

Uzupełnij luki w kodzie tak, aby program wykonywał poprawne sortowanie tablicy dane niemalejąco, za pomocą algorytmu sortowania pozycyjnego, przy wykorzystaniu algorytmu sortowania przez zliczanie. Wypisz posortowaną tablicę dane i oblicz jej medianę. Swoje rozwiązanie przetestuj dla przedstawionych danych:

dane = {876, 111, 412, 908, 765, 321, 765, 23, 3}
liczbaElementow = 9
liczbaCyfr = 3

Specyfikacja:

Dane:

dane – jednowymiarowa tablica liczb naturalnych; wejściowy zbiór zawierający liczby do posortowania
liczbaElementow – liczba naturalna; rozmiar tablicy dane
liczbaCyfr – liczba naturalna; maksymalna liczba cyfr, z których składają się liczby w tabeli dane

Wynik:

dane – jednowymiarowa tablica liczb naturalnych posortowana w kolejności niemalejącej
mediana – liczba rzeczywista

RRByIPnhsMd6o

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. static int dane otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 4. 876 przecinek. Linia 5. 111 przecinek. Linia 6. 412 przecinek. Linia 7. 908 przecinek. Linia 8. 765 przecinek. Linia 9. 321 przecinek. Linia 10. 765 przecinek. Linia 11. 23 przecinek. Linia 12. 3. Linia 13. zamknij nawias klamrowy średnik. Linia 14. static int liczbaElementow znak równości 9 średnik. Linia 15. static int liczbaCyfr znak równości 3 średnik. Linia 17. static void sortowaniePrzezZliczanie otwórz nawias okrągły int pozycjaCyfry zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int temp otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości new int otwórz nawias kwadratowy liczbaElementow zamknij nawias kwadratowy średnik. Linia 19. int tablicaZliczenCyfr otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości new int otwórz nawias kwadratowy 10 zamknij nawias kwadratowy średnik prawy ukośnik prawy ukośnik 10 minus bo 0 minus 9. Linia 21. int wspolczynnikCyfry znak równości otwórz nawias okrągły int zamknij nawias okrągły Math kropka pow otwórz nawias okrągły 10 przecinek pozycjaCyfry zamknij nawias okrągły średnik. Linia 23. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. int odczytanaCyfra znak równości otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wspolczynnikCyfry zamknij nawias okrągły procent 10 średnik. Linia 25. tablicaZliczenCyfr otwórz nawias kwadratowy odczytanaCyfra zamknij nawias kwadratowy plus plus średnik. Linia 26. zamknij nawias klamrowy. Linia 28. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny 10 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. tablicaZliczenCyfr otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości tablicaZliczenCyfr otwórz nawias kwadratowy i zamknij nawias kwadratowy plus tablicaZliczenCyfr otwórz nawias kwadratowy i minus 1 zamknij nawias kwadratowy średnik. Linia 30. zamknij nawias klamrowy. Linia 32. for otwórz nawias okrągły int i znak równości liczbaElementow minus 1 średnik i zamknij nawias ostrokątny znak równości 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. int odczytanaCyfra znak równości otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik wspolczynnikCyfry zamknij nawias okrągły procent 10 średnik. Linia 34. int indeksWTablicyWynikowej znak równości tablicaZliczenCyfr otwórz nawias kwadratowy odczytanaCyfra zamknij nawias kwadratowy minus 1 średnik. Linia 35. temp otwórz nawias kwadratowy indeksWTablicyWynikowej zamknij nawias kwadratowy znak równości dane otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 36. tablicaZliczenCyfr otwórz nawias kwadratowy odczytanaCyfra zamknij nawias kwadratowy minus minus średnik. Linia 37. zamknij nawias klamrowy. Linia 39. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. dane otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 41. zamknij nawias klamrowy. Linia 42. zamknij nawias klamrowy. Linia 44. public static void main otwórz nawias okrągły String args otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 45. for otwórz nawias okrągły int numerCyfry znak równości 0 średnik numerCyfry otwórz nawias ostrokątny liczbaCyfr średnik numerCyfry plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 46. sortowaniePrzezZliczanie otwórz nawias okrągły numerCyfry zamknij nawias okrągły średnik. Linia 47. zamknij nawias klamrowy. Linia 49. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczbaElementow średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 50. System kropka out kropka print otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 51. zamknij nawias klamrowy. Linia 53. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 55. double mediana znak równości 0 kropka 0 średnik. Linia 57. int polowa znak równości otwórz nawias okrągły int zamknij nawias okrągły otwórz nawias okrągły liczbaElementow prawy ukośnik 2 zamknij nawias okrągły średnik. Linia 58. if otwórz nawias okrągły liczbaElementow procent 2 znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 59. mediana znak równości otwórz nawias okrągły dane otwórz nawias kwadratowy polowa minus 1 zamknij nawias kwadratowy plus dane otwórz nawias kwadratowy polowa zamknij nawias kwadratowy zamknij nawias okrągły prawy ukośnik 2 kropka 0 średnik. Linia 60. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 61. mediana znak równości dane otwórz nawias kwadratowy polowa zamknij nawias kwadratowy średnik. Linia 62. zamknij nawias klamrowy. Linia 64. System kropka out kropka print otwórz nawias okrągły mediana zamknij nawias okrągły średnik. Linia 66. zamknij nawias klamrowy. Linia 67. zamknij nawias klamrowy.

public class Main {

	static int dane[] = {
		876,
		111,
		412,
		908,
		765,
		321,
		765,
		23,
		3
	};
	static int liczbaElementow = 9;
	static int liczbaCyfr = 3;

	static void sortowaniePrzezZliczanie(int pozycjaCyfry) {
		int temp[] = new int[liczbaElementow];
		int tablicaZliczenCyfr[] = new int[10]; //10 - bo 0-9

		int wspolczynnikCyfry = (int) Math.pow(10, pozycjaCyfry);

		for (int i = 0; i < liczbaElementow; i++) {
			int odczytanaCyfra = (dane[i] / wspolczynnikCyfry) % 10;
			tablicaZliczenCyfr[odczytanaCyfra]++;
		}

		for (int i = 1; i < 10; i++) {
			tablicaZliczenCyfr[i] = tablicaZliczenCyfr[i] + tablicaZliczenCyfr[i - 1];
		}

		for (int i = liczbaElementow - 1; i >= 0; i--) {
			int odczytanaCyfra = (dane[i] / wspolczynnikCyfry) % 10;
			int indeksWTablicyWynikowej = tablicaZliczenCyfr[odczytanaCyfra] - 1;
			temp[indeksWTablicyWynikowej] = dane[i];
			tablicaZliczenCyfr[odczytanaCyfra]--;
		}

		for (int i = 0; i < liczbaElementow; i++) {
			dane[i] = temp[i];
		}
	}

	public static void main(String args[]) {
		for (int numerCyfry = 0; numerCyfry < liczbaCyfr; numerCyfry++) {
			sortowaniePrzezZliczanie(numerCyfry);
		}

		for (int i = 0; i < liczbaElementow; i++) {
			System.out.print(dane[i] + " ");
		}

		System.out.println();

		double mediana = 0.0;

		int polowa = (int) (liczbaElementow / 2);
		if (liczbaElementow % 2 == 0) {
			mediana = (dane[polowa - 1] + dane[polowa]) / 2.0;
		} else {
			mediana = dane[polowa];
		}
            
		System.out.print(mediana);
            
	}
}

Ćwiczenie 2

Książki ustawione są na półce od najniższej do najwyższej (od lewej do prawej). Napisz program, który dla nieuporządkowanych par (wysokość książki i jej tytuł) wskaże, które książki znajdą się na półce na pozycjach od p do q włącznie, licząc od lewej ściany półki, numerując książki od 0. Program powinien wypisać tytuły książek w kolejności ich rosnących wysokości, każdy tytuł w oddzielnej linii. Nie ma dwóch książek o tej samej wysokości. Użyj sortowania pozycyjnego, z wykorzystaniem sortowania bąbelkowego. Przetestuj swój program dla następujących danych:

wysokosc = {250, 30, 1, 5, 10, 300, 299, 100}
tytul = {"A", "B", "C", "D", "E", "F", "G", "H"}
p = 1
q = 3

Specyfikacja:

Dane:

wysokosc – jednowymiarowa tablica liczb naturalnych; zawiera parami różne liczby naturalne z zakresu [1, 300], reprezentujące wysokości książek
tytul – jednowymiarowa tablica ciągów znaków o dowolnej długości; element i-ty w tablicy tytul odpowiada książce o wysokości i-tej z tablicy wysokosc
p – liczba naturalna; początkowy indeks, od którego zaczynamy wypisywać książki
q – liczba naturalna; końcowy indeks, na którym kończymy wypisywać książki; p <= q

Wynik:

tytul – jednowymiarowa tablica ciągów znaków o dowolnej długości posortowana w kolejności rosnących wysokości
wysokosc – jednowymiarowa tablica liczb naturalnych posortowana w kolejności niemalejącej

R1cZYXwJVKDnr

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. static Integer wysokosc otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 250 przecinek 30 przecinek 1 przecinek 5 przecinek 10 przecinek 300 przecinek 299 przecinek 100 zamknij nawias klamrowy średnik. Linia 4. static String tytul otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy cudzysłów A cudzysłów przecinek cudzysłów B cudzysłów przecinek cudzysłów C cudzysłów przecinek cudzysłów D cudzysłów przecinek cudzysłów E cudzysłów przecinek cudzysłów F cudzysłów przecinek cudzysłów G cudzysłów przecinek cudzysłów H cudzysłów zamknij nawias klamrowy średnik. Linia 5. static int p znak równości 1 średnik. Linia 6. static int q znak równości 3 średnik. Linia 8. static void zamien otwórz nawias okrągły Object otwórz nawias kwadratowy zamknij nawias kwadratowy tab przecinek int i przecinek int j zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. Object temp znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 11. tab otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości temp średnik. Linia 12. zamknij nawias klamrowy. Linia 14. static void sortowanieBabelkowe otwórz nawias okrągły int pozycjaCyfry zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny wysokosc kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. for otwórz nawias okrągły int j znak równości i plus 1 średnik j otwórz nawias ostrokątny wysokosc kropka length średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. if otwórz nawias okrągły otwórz nawias okrągły wysokosc otwórz nawias kwadratowy j zamknij nawias kwadratowy prawy ukośnik pozycjaCyfry zamknij nawias okrągły procent 10 otwórz nawias ostrokątny otwórz nawias okrągły wysokosc otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik pozycjaCyfry zamknij nawias okrągły procent 10 zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. zamien otwórz nawias okrągły wysokosc przecinek i przecinek j zamknij nawias okrągły średnik. Linia 19. zamien otwórz nawias okrągły tytul przecinek i przecinek j zamknij nawias okrągły średnik. Linia 20. zamknij nawias klamrowy. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 25. public static void main otwórz nawias okrągły String args otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. for otwórz nawias okrągły int p znak równości 1 średnik p otwórz nawias ostrokątny znak równości 100 średnik p asterysk znak równości 10 zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. sortowanieBabelkowe otwórz nawias okrągły p zamknij nawias okrągły średnik. Linia 29. zamknij nawias klamrowy. Linia 31. for otwórz nawias okrągły int i znak równości p średnik i otwórz nawias ostrokątny znak równości q średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. System kropka out kropka println otwórz nawias okrągły tytul otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy.

public class Main {
	
	static Integer wysokosc[] = {250, 30, 1, 5, 10, 300, 299, 100};
	static String tytul[] = {"A", "B", "C", "D", "E", "F", "G", "H"};
	static int p = 1;
	static int q = 3;

	static void zamien(Object[] tab, int i, int j) {
		Object temp = tab[i];
		tab[i] = tab[j];
		tab[j] = temp;
	}

	static void sortowanieBabelkowe(int pozycjaCyfry) {
		for (int i=0; i<wysokosc.length; i++) {
			for (int j=i+1; j<wysokosc.length; j++) {
				if ((wysokosc[j]/pozycjaCyfry)%10 < (wysokosc[i]/pozycjaCyfry)%10) {
					zamien(wysokosc, i, j);
					zamien(tytul, i, j);
				}
			}
		}
	}

	public static void main(String args[]) {
		
		for (int p=1; p<=100; p*=10) {
			sortowanieBabelkowe(p);
		}
		
		for (int i = p; i <= q; i++) {
			System.out.println(tytul[i]);
		}
	}
}

Ćwiczenie 3

Uzupełnij luki w odpowiednich miejscach w kodzie, tak aby program wykonywał poprawne sortowanie zadanej tablicy liczby nierosnąco za pomocą algorytmu sortowania pozycyjnego, przy wykorzystaniu algorytmu sortowania przez wstawianie. Swoje rozwiązanie przetestuj dla tablicy:

liczby = {345, 123, 567, 234, 888, 544, 342, 111, 100}

Specyfikacja:

Dane:

liczby – jednowymiarowa tablica liczb naturalnych; wejściowy zbiór zawierający liczby do posortowania

Wynik:

liczby – jednowymiarowa tablica liczb naturalnych (oddzielonych spacjami) posortowanych w kolejności nierosnącej

R17w9m58W9l1R

Przykładowe rozwiązanie zadania:

Linia 1. public class SortowaniePozycyjne otwórz nawias klamrowy. Linia 3. static int znajdzMax otwórz nawias okrągły int otwórz nawias kwadratowy zamknij nawias kwadratowy tab zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. int max znak równości tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 6. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny tab kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias ostrokątny max zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. max znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 9. zamknij nawias klamrowy. Linia 10. zamknij nawias klamrowy. Linia 11. return max średnik. Linia 12. zamknij nawias klamrowy. Linia 14. static void sortowaniePrzezWstawianie otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int pozycjaCyfry zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny tab kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. int cyfra znak równości otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy prawy ukośnik pozycjaCyfry zamknij nawias okrągły procent 10 średnik. Linia 19. int wartosc znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 20. int j znak równości i minus 1 średnik. Linia 22. while otwórz nawias okrągły otwórz nawias okrągły j zamknij nawias ostrokątny znak równości 0 zamknij nawias okrągły ampersant ampersant otwórz nawias okrągły otwórz nawias okrągły otwórz nawias okrągły tab otwórz nawias kwadratowy j zamknij nawias kwadratowy prawy ukośnik pozycjaCyfry zamknij nawias okrągły procent 10 zamknij nawias okrągły otwórz nawias ostrokątny cyfra zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. tab otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 24. j znak równości j minus 1 średnik. Linia 25. zamknij nawias klamrowy. Linia 26. tab otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości wartosc średnik. Linia 27. zamknij nawias klamrowy. Linia 28. zamknij nawias klamrowy. Linia 30. static void sortowaniePozycyjne otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. int max znak równości znajdzMax otwórz nawias okrągły tab zamknij nawias okrągły średnik. Linia 33. for otwórz nawias okrągły int poz znak równości 1 średnik max prawy ukośnik poz zamknij nawias ostrokątny 0 średnik poz asterysk znak równości 10 zamknij nawias okrągły. Linia 34. sortowaniePrzezWstawianie otwórz nawias okrągły tab przecinek poz zamknij nawias okrągły średnik. Linia 35. zamknij nawias klamrowy. Linia 37. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. int liczby otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy. Linia 40. 345 przecinek. Linia 41. 123 przecinek. Linia 42. 567 przecinek. Linia 43. 234 przecinek. Linia 44. 888 przecinek. Linia 45. 544 przecinek. Linia 46. 342 przecinek. Linia 47. 111 przecinek. Linia 48. 100. Linia 49. zamknij nawias klamrowy średnik. Linia 50. sortowaniePozycyjne otwórz nawias okrągły liczby zamknij nawias okrągły średnik. Linia 52. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny liczby kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. System kropka out kropka print otwórz nawias okrągły liczby otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 54. zamknij nawias klamrowy. Linia 55. zamknij nawias klamrowy. Linia 56. zamknij nawias klamrowy.

public class SortowaniePozycyjne {

   static int znajdzMax(int[] tab) {
       int max = tab[0];

       for (int i = 0; i < tab.length; i++) {
           if (tab[i] > max) {
               max = tab[i];
           }
       }
       return max;
   }

   static void sortowaniePrzezWstawianie(int tab[], int pozycjaCyfry) {

       for(int i = 1; i < tab.length; i++) {

           int cyfra = (tab[i] / pozycjaCyfry) % 10;
           int wartosc = tab[i];
           int j = i - 1;

           while((j >= 0) && (((tab[j] / pozycjaCyfry) % 10) < cyfra)){
               tab[j+1] = tab[j];
               j = j - 1;
           }
           tab[j+1] = wartosc;
       }
   }

   static void sortowaniePozycyjne(int tab[]) {
       int max = znajdzMax(tab);

       for (int poz = 1; max / poz > 0; poz *= 10)
           sortowaniePrzezWstawianie(tab, poz);
   }

   public static void main(String[] args) {

       int liczby[] = {
               345,
               123,
               567,
               234,
               888,
               544,
               342,
               111,
               100
       };
       sortowaniePozycyjne(liczby);

       for (int i = 0; i < liczby.length; i++) {
           System.out.print(liczby[i] + " ");
       }
   }
}

Przeczytaj

Dla nauczyciela