algorytm tn: Trvial: ciekawe zadanie: witam, mam takie zadanie z zeszłorocznej OI (I etap). To zadanie to Przekładanka: http://main.edu.pl/pl/archive/oi/18/prz jest ono dla mnie trudne, zupełnie nie wiem jak je ugyźć, z czym powinienem się zapoznać, co poczytać, aby być gotowym do podjęcia się tego zadania?

Mateusz: Przede wszystkim trzeba nauczyc się myślec algorytmicznie(nie jest to trudne ) no i trzeba znać dobrze język programowania w ktorym się deklarujesz pisac program(bo tak chyba trzeba zrobic nie wiem) no i znajomosc roznych algorytmów tez pomaga np problem wież Hanoi prawie podobny do twojej przekładanki tyko inne sa dane i inne ograniczenia, algorytmy sortujące, czy np metoda Monte Carlo Ale kluczowa hest znajomosc języka czy języków programowania a problem algorytmiczny to mniejszy pikuś muszisz próbowac ,zrozumiec nawet zrob sobie doswiadczenie kombinuj az znajdziesz rozwiązanie bo za ciebie nikt nie rozwiąże

Trivial: Ja bym zaczął od kartki i analizy problemu

Trivial: Mam pewną teorię odnośnie tego zadania.

tn: ja wiem, proszę tylko o wskazówkę − nie o rozwiazanie

Mateusz: Wiem ze nie prosisz o rozwiązanie tyle ze tam ci podali wskazówki nawet to jak program ma działac ale ok niech Trivial poda te teorie nie bede psuł zabawy a na razie probuj sam kombinowac to jest dobra nauka.

Trivial: Zastanów się jak można zmienić wejście tylko instrukcją a. Możemy przestawić ostatni element na początek. Potem znowu i znowu itd. Z kolei instrukcja b działa tylko na pierwszych trzech liczbach − zmienia ich kolejność nie zmieniając kolejności pozostałych. Zastanów się jakie trójelementowe tablice mogą zostać 'posortowane' tylko przy użyciu instrukcji b (do tego to się sprowadza). Trudno podpowiedzieć więcej bez podawania rozwiązania.

tn: Trivial − na weekendzie zapewne podejdę do zadania, dzięki za rady. W jaki sposób doskonalić swoją zdolność myślenia algorytmicznego ?

Mateusz: Analizowac rozwiązywane problemy ale tez probowac wymyslec swoje lepsze o ile sie da np niedawno na forum pewna osoba miała takie zadanie: https://matematykaszkolna.pl/forum/104577.html kliknij w ten link ktory podała będziesz miał schemat blokowy algorytmu sprawdzajacego czy liczba z przedziału <1,100> jest parzysta i sprobuj zaproponowac lepszą wersje−wydajniejszą prawda ze ta wersja algorytmyu zostanie tez szybko zrealizowana przez przeciętny komputer ale to jest tez dobre cwiczonko podpowiem ze oba są niemalze identyczne trzeba zmienic tylko jedną skrzynke

Trivial: Są książki, kursy na youtube (w języku angielskim), no i można na własną rękę też (ale nie polecam). Wystarczy zapoznawać się z coraz to większą liczbą algorytmów, metodami ich analizy i kilkoma technikami tworzenia nowych. Trzeba również próbować tworzyć własne rozwiązania (np. problem sortowania, szukania w tablicy, ...). Najlepsza według mnie książka 'od podstaw' to wprowadzenie do algorytmów Cormena, ale ona wymaga duuuuuuuuuużej wiedzy matematycznej (cały czas jakieś dowody, analiza złożoności itd.). Są też książki Knutha i Wirtha (algorytmy + struktury danych = programy), ale ich nie czytałem. Linki do kursów: 1. MIT. Jeden z prowadzących to współautor książki Cormena, a drugi człowiek, który jest profesorem od 20 roku życia Poziom matmy wysoki. http://www.youtube.com/watch?v=JPyuH4qXLZ0&feature=list_related&playnext=1&list=SP8B24C31197EC371C 2. Richard Buckland. Luźna atmosfera − wykłady szalenie ciekawe. Matma potrzebna na poziomie szkoły średniej. http://www.youtube.com/watch?v=RpRRUQFbePU&feature=list_related&playnext=1&list=SPE621E25B3BF8B9D1 Good luck.

tn: hmm, poprawienie sytuacji dla trzech pierwszych liczb ciągu można dokonać tylko w jednej sytuacji: a b c a > b ⋀ a > c ⋀ b < c ale jest inny problem skąd mogę mieć pewność, że w pewnej chwili nie pojawi się potrzeba taka,aby tylko raz wykonać b − > co potem da sens wykonania? bo jeśli chcę przesortować trzy pierwsze to musi zachodzi ten warunek oraz wykonać 2b

Trivial: Dam podpowiedź. Trzeba przeanalizować liczbę inwersji względem liczby elementów. Inwersją nazywamy każdą parę (i,j), taką że i>j (są w 'niewłaściwej' kolejności). Przykład Mając tablicę 1432 inwersje to: 43 42 32. Naszym celem jest posortowanie tablicy, czyli wyeliminowanie inwersji. Oznaczmy przez N liczbę elementów tablicy. Przeanalizujmy, co się dzieje z inwersjami przy operacji a. Załóżmy, że na samym końcu mamy element, który w posortowanej tablicy powinien być na k−tym miejscu. Mamy dokładnie N−k liczb, które są większe od naszego elementu, a nasz element jest na samym końcu − tworzy więc N−k inwersji. Po wykonaniu operacji a będzie tworzył inwersje z dokładnie k−1 liczbami (nie tworzy inwersji z samym sobą). Zatem: przed operacją a: N−k po operacji a: k−1. Teraz! Zauważmy, że jeżeli N − nieparzyste, operacja a nie zmienia parzystości liczby inwersji, a naszym celem jest doprowadzenie tej liczby do zera, które jest przecież parzyste. Stąd nasz pierwszy, ale jakże ważny wniosek. Wniosek 1 1. Jeżeli N − nieparzyste to operacja a nie zmienia parzystości liczby inwersji. 2. Jeżeli N − parzyste to operacja a zmienia parzystość liczby inwersji za każdym razem. Przejdziemy teraz do analizy operacji b. Zauważmy, że operacja b jest tak naprawdę operacją a dla N=3. Zatem: Wniosek 2 Operacja b nie zmienia parzystości liczby inwersji. Skąd błyskawicznie nasuwa się na myśl kolejny wniosek, który jest kluczowy do rozwiązania zadania. Skoro liczba inwersji ma być zerem (parzyste), to z wniosku 1 i 2 wynika: Wniosek 3 Jeżeli N − nieparzyste, a liczba inwersji jest parzysta to takiej tablicy nie można posortować operacjami a i b. Na tym poprzestałem dalszą analizę problemu. Wpadłem na pomysł, który działał dla każdego przykładu, ale nie jestem w stanie go udowodnić. Prawdopodobnie, każdą inną sytuację niż we wniosku 3 da się rozwiązać.

Trivial: Do wniosku 3 wkradł się błąd. Oczywiście powinno być: Wniosek 3 Jeżeli N − nieparzyste, a liczba inwersji jest nieparzysta, to takiej tablicy nie można posortować operacjami a i b.

Trivial: Teraz masz już tyle podpowiedzi, że nad resztą możesz pomyśleć sam.

tn: dzięki − potem to przeanalizuję, nigdy bym na to nie wpadł, jednak wielkie dzięki za pomoc. powiedz jak na to wpadłeś?

Trivial: Samo wpadło do głowy, kiedy analizowałem przykłady.

tn: nigdy bym na to nie wpadł od zawsze potrafiłeś tak rozwiązywać zadania, czy przyszło z czasem? wnet wczytam się w to i skombinuję całość

Trivial: Miałem przedmiot z tym związany, przerobiłem tamte dwa kursy, które podałem wyżej i z połowę Cormena. Kurs MIT, bo dobrze tłumaczyli (a miałem poprawkę do zaliczenia...), kurs drugi − dla przyjemności − mają na nim nastrój burzy mózgów i rozwiązują ciekawe problemy.