Implementacja algorytmu (wersja iteracyjna)
Implementacja algorytmu (wersja iteracyjna)
1. Algorytm znajduje rozwiązanie wykonując 2*(n‑1) porównań (I wersja)
Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny.
Linia 2. using namespace std średnik.
Linia 4. void min podkreślnik max podkreślnik it otwórz nawias okrągły int tablica otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n przecinek int minimum przecinek int maksimum zamknij nawias okrągły otwórz nawias klamrowy.
Linia 5. minimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 6. maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 8. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 9. int element znak równości tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik.
Linia 11. if otwórz nawias okrągły element otwórz nawias ostrokątny minimum zamknij nawias okrągły otwórz nawias klamrowy.
Linia 12. minimum znak równości element średnik.
Linia 13. zamknij nawias klamrowy.
Linia 14. if otwórz nawias okrągły element zamknij nawias ostrokątny maksimum zamknij nawias okrągły otwórz nawias klamrowy.
Linia 15. maksimum znak równości element średnik.
Linia 16. zamknij nawias klamrowy.
Linia 17. zamknij nawias klamrowy.
Linia 19. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Minimum dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny minimum otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik n cudzysłów średnik.
Linia 20. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Maksimum dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny maksimum otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik n cudzysłów średnik.
Linia 21. zamknij nawias klamrowy.
Linia 23. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 24. const int n znak równości 6 średnik.
Linia 25. int tablica otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 4 przecinek 5 przecinek 3 przecinek 7 przecinek 9 zamknij nawias klamrowy średnik.
Linia 27. min podkreślnik max podkreślnik it otwórz nawias okrągły tablica przecinek n przecinek 0 przecinek 0 zamknij nawias okrągły średnik.
Linia 29. return 0 średnik.
Linia 30. zamknij nawias klamrowy.
Jak działa program?
Zaczynamy od pierwszego elementu
Przechodzimy po liście raz
W każdej iteracji aktualizujemy minimum i maksimum
2. Algorytm znajduje rozwiązanie korzystając z efektywniejszego algorytmu min‑max (II wersja)
Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny.
Linia 2. using namespace std średnik.
Linia 4. void min podkreślnik max podkreślnik iter podkreślnik dziel podkreślnik i podkreślnik zwyciezaj otwórz nawias okrągły int tablica otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n zamknij nawias okrągły otwórz nawias klamrowy.
Linia 5. int minimum przecinek maksimum średnik.
Linia 6. int start średnik.
Linia 8. prawy ukośnik prawy ukośnik jeśli tablica ma tylko jeden element.
Linia 9. if otwórz nawias okrągły n znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 10. minimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 11. maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 12. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Minimum dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny minimum otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik n cudzysłów średnik.
Linia 13. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Maksimum dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny maksimum otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik n cudzysłów średnik.
Linia 14. return średnik.
Linia 15. zamknij nawias klamrowy.
Linia 17. prawy ukośnik prawy ukośnik inicjalizacja.
Linia 18. if otwórz nawias okrągły n procent 2 znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 19. if otwórz nawias okrągły tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias ostrokątny tablica otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy.
Linia 20. minimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 21. maksimum znak równości tablica otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik.
Linia 22. zamknij nawias klamrowy else otwórz nawias klamrowy.
Linia 23. minimum znak równości tablica otwórz nawias kwadratowy 1 zamknij nawias kwadratowy średnik.
Linia 24. maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 25. zamknij nawias klamrowy.
Linia 26. start znak równości 2 średnik.
Linia 27. zamknij nawias klamrowy else otwórz nawias klamrowy.
Linia 28. minimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 29. maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik.
Linia 30. start znak równości 1 średnik.
Linia 31. zamknij nawias klamrowy.
Linia 33. prawy ukośnik prawy ukośnik przeglądanie par.
Linia 34. for otwórz nawias okrągły int i znak równości start średnik i otwórz nawias ostrokątny n minus 1 średnik i plus znak równości 2 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 35. int mniejszy przecinek wiekszy średnik.
Linia 37. if otwórz nawias okrągły tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny tablica otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy.
Linia 38. mniejszy znak równości tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik.
Linia 39. wiekszy znak równości tablica otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik.
Linia 40. zamknij nawias klamrowy else otwórz nawias klamrowy.
Linia 41. mniejszy znak równości tablica otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy średnik.
Linia 42. wiekszy znak równości tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik.
Linia 43. zamknij nawias klamrowy.
Linia 45. if otwórz nawias okrągły mniejszy otwórz nawias ostrokątny minimum zamknij nawias okrągły otwórz nawias klamrowy.
Linia 46. minimum znak równości mniejszy średnik.
Linia 47. zamknij nawias klamrowy.
Linia 48. if otwórz nawias okrągły wiekszy zamknij nawias ostrokątny maksimum zamknij nawias okrągły otwórz nawias klamrowy.
Linia 49. maksimum znak równości wiekszy średnik.
Linia 50. zamknij nawias klamrowy.
Linia 51. zamknij nawias klamrowy.
Linia 53. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Minimum dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny minimum otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik n cudzysłów średnik.
Linia 54. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Maksimum dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny maksimum otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów lewy ukośnik n cudzysłów średnik.
Linia 55. zamknij nawias klamrowy.
Linia 57. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 58. const int n znak równości 6 średnik.
Linia 59. int tablica otwórz nawias kwadratowy n zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 4 przecinek 5 przecinek 3 przecinek 7 przecinek 9 zamknij nawias klamrowy średnik.
Linia 61. min podkreślnik max podkreślnik iter podkreślnik dziel podkreślnik i podkreślnik zwyciezaj otwórz nawias okrągły tablica przecinek n zamknij nawias okrągły średnik.
Linia 63. return 0 średnik.
Linia 64. zamknij nawias klamrowy.
Porównanie obu wersji:
I wersja: zwykła wersja iteracyjna 2(n - 1) porównań,
II wersja: około
porównań - ten sam wynik, mniej porównań.