1 Jak Jaś parował skarpetki Andrzej Majkowski 1 informatyka +

2 Jak Jaś parował skarpetki O efektywności algorytmów

3 Jak Jaś parował skarpetki Jaś miał 14 par skarpet. Każda była w trochę innym kolorze. Jaś często zwlekał z praniem skarpetek do momentu, aż wszystkie były brudne. Po ich wypraniu stawał przed niełatwym zadaniem połączenia skarpet w pary. Jaka była jego metoda (algorytm)?

4 Jak Jaś parował skarpetki Zakładamy, że najbardziej kosztowną (czasochłonną, męczącą, itp.) czynnością jest wyciaganie kolejnej skarpety z kosza. Będziemy zliczać, jak liczba skarpet wyciągana z kosza ma się do całkowitej liczby skarpet!

5 Jak Jaś parował skarpetki Algorytm „naiwny”

6 Jak Jaś parował skarpetki Wyciągamy pierwszą skarpetę z kosza.

7 Jak Jaś parował skarpetki 1 Porównujemy ją z kolejną! Jeśli nie są takie same, to odkładamy tę drugą na spód (w miarę możliwości).

8 Jak Jaś parował skarpetki 2 Porównujemy ją z kolejną!

9 Jak Jaś parował skarpetki 3 Porównujemy ją z jeszcze kolejną!

10 Jak Jaś parował skarpetki Jeśli skarpety pasują do pary, parujemy je i powtarzamy procedurę z kolejną skarpetą.

11 Jak Jaś parował skarpetki 4

12 5

13 6

14 7

15 8

16 9

17 10

18 Jak Jaś parował skarpetki

19 11

20 Jak Jaś parował skarpetki 12

21 Jak Jaś parował skarpetki 13

22 Jak Jaś parował skarpetki 14

23 Jak Jaś parował skarpetki 15

24 Jak Jaś parował skarpetki 16

25 Jak Jaś parował skarpetki 17

26 Jak Jaś parował skarpetki 18

27 Jak Jaś parował skarpetki 19

28 Jak Jaś parował skarpetki 20

29 Jak Jaś parował skarpetki

30 21

31 Jak Jaś parował skarpetki 22

32 Jak Jaś parował skarpetki 23

33 Jak Jaś parował skarpetki

34 24

35 Jak Jaś parował skarpetki 25

36 Jak Jaś parował skarpetki 26

37 Jak Jaś parował skarpetki 27

38 Jak Jaś parował skarpetki 28

39 Jak Jaś parował skarpetki 29

40 Jak Jaś parował skarpetki 30

41 Jak Jaś parował skarpetki 31

42 Jak Jaś parował skarpetki 32

43 Jak Jaś parował skarpetki 33

44 Jak Jaś parował skarpetki 34

45 Jak Jaś parował skarpetki 35

46 Jak Jaś parował skarpetki 36

47 Jak Jaś parował skarpetki 37

48 Jak Jaś parował skarpetki 38

49 Jak Jaś parował skarpetki 39

50 Jak Jaś parował skarpetki 40

51 Jak Jaś parował skarpetki 41

52 Jak Jaś parował skarpetki

53 42

54 Jak Jaś parował skarpetki 43

55 Jak Jaś parował skarpetki 44

56 Jak Jaś parował skarpetki 45

57 Jak Jaś parował skarpetki 46

58 Jak Jaś parował skarpetki 47

59 Jak Jaś parował skarpetki 48

60 Jak Jaś parował skarpetki 49

61 Jak Jaś parował skarpetki 50

62 Jak Jaś parował skarpetki 51

63 Jak Jaś parował skarpetki 52

64 Jak Jaś parował skarpetki 53

65 Jak Jaś parował skarpetki 54

66 Jak Jaś parował skarpetki 55

67 Jak Jaś parował skarpetki 56

68 Jak Jaś parował skarpetki 57

69 Jak Jaś parował skarpetki 58

70 Jak Jaś parował skarpetki 59

71 Jak Jaś parował skarpetki

72 60

73 Jak Jaś parował skarpetki 61

74 Jak Jaś parował skarpetki 62

75 Jak Jaś parował skarpetki 63

76 Jak Jaś parował skarpetki 64

77 Jak Jaś parował skarpetki 65

78 Jak Jaś parował skarpetki 66

79 Jak Jaś parował skarpetki 67

80 Jak Jaś parował skarpetki 69

81 Jak Jaś parował skarpetki 70

82 Jak Jaś parował skarpetki 71

83 Jak Jaś parował skarpetki 72

84 Jak Jaś parował skarpetki

85 73

86 Jak Jaś parował skarpetki 74

87 Jak Jaś parował skarpetki 75

88 Jak Jaś parował skarpetki 76

89 Jak Jaś parował skarpetki 77

90 Jak Jaś parował skarpetki 78

91 Jak Jaś parował skarpetki 79

92 Jak Jaś parował skarpetki 80

93 Jak Jaś parował skarpetki 81

94 Jak Jaś parował skarpetki 82

95 Jak Jaś parował skarpetki

96 83

97 Jak Jaś parował skarpetki 84

98 Jak Jaś parował skarpetki 85

99 Jak Jaś parował skarpetki 86

100 Jak Jaś parował skarpetki 87

101 Jak Jaś parował skarpetki 88

102 Jak Jaś parował skarpetki 89

103 Jak Jaś parował skarpetki 90

104 Jak Jaś parował skarpetki 91

105 Jak Jaś parował skarpetki

106 92

107 Jak Jaś parował skarpetki

108 93

109 Jak Jaś parował skarpetki 94

110 Jak Jaś parował skarpetki 95

111 Jak Jaś parował skarpetki 96

112 Jak Jaś parował skarpetki 97

113 Jak Jaś parował skarpetki

114 98

115 Jak Jaś parował skarpetki 99

116 Jak Jaś parował skarpetki 100

117 Jak Jaś parował skarpetki 101

118 Jak Jaś parował skarpetki

119 102

120 Jak Jaś parował skarpetki

121 103

122 Jak Jaś parował skarpetki Cały proces przebiegał bardzo wolno. Szczególnie na początku...

123 Jak Jaś parował skarpetki Czy można było połączyć skarpety w pary szybciej?

124 Jak Jaś parował skarpetki Algorytm bardziej efektywny

125 Jak Jaś parował skarpetki 1 Po zajęciach z algorytmiki, Jaś zaczął postępować w inny sposób! Wyciągał pierwszą skarpetkę i kładł ją na stole, potem wyciągał następną i porównywał ją z pierwszą.

126 Jak Jaś parował skarpetki 2 Jeśli nie pasowała, kładł ją obok pierwszej.

127 Jak Jaś parował skarpetki 3 Za każdym razem, kiedy wyciągnął nową skarpetkę, porównywał ją z wydłużającym się szeregiem skarpet na stole.

128 Jak Jaś parował skarpetki 4 Jeżeli potrafił dobrać skarpetkę do pary, zwijał ją i wrzucał do szafki.

129 Jak Jaś parował skarpetki 5 Jeśli nie, to dokładał skarpetę do szeregu na stole.

130 Jak Jaś parował skarpetki 6

131 7

132 8

133 9

134 10

135 Jak Jaś parował skarpetki 11

136 Jak Jaś parował skarpetki 12

137 Jak Jaś parował skarpetki 13

138 Jak Jaś parował skarpetki 14

139 Jak Jaś parował skarpetki 15

140 Jak Jaś parował skarpetki 16

141 Jak Jaś parował skarpetki 17

142 Jak Jaś parował skarpetki 18

143 Jak Jaś parował skarpetki 19

144 Jak Jaś parował skarpetki 20

145 Jak Jaś parował skarpetki 21

146 Jak Jaś parował skarpetki 22

147 Jak Jaś parował skarpetki 23

148 Jak Jaś parował skarpetki 24

149 Jak Jaś parował skarpetki 25

150 Jak Jaś parował skarpetki 26

151 Jak Jaś parował skarpetki 27

152 Jak Jaś parował skarpetki 28

153 Jak Jaś parował skarpetki Ten algorytm pozwalał na parowanie skarpetek w znacznie krótszym czasie...

154 Jak Jaś parował skarpetki Jak porównać efektywność obu algorytmów dla n skarpet?

155 Jak Jaś parował skarpetki