-
Notifications
You must be signed in to change notification settings - Fork 0
imatw4r/clearcode_intern
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
# Uwaga. # Kody pisane w wersji Pythona 3.5, kompatybilne z 2.7+ # Zadanie 1 - opis podejścia. Szczerze mówiąc, na samym początku problemem był dobór odpowiedniego sposobu. Najpier uznałem, że najlepiej byłoby stosować operacje bitowe (&), by za ich pomocą iterować po kolejnych bitach liczby N i sprawdzać, czy są one 1 lub 0 (w zależności od tego, czy liczba jest parzysta, czy nie), ale wraz z tym pomysłem pojawił się problem dot. wielkości liczby (z ilu bitów się składa). Ustawienie na sztywno jakiejś konkretnej, np 32 też wydało się bardzo nierozsądne. Uznałem wtedy, że zastosuję funkcję math.log i po prostu w ten sposób ustalę górny limit. Dopiero po jakichś pięciu minutach myślenia nad tym problemem (było już późno, wracałem z uczelni) przypomniałem sobie o wbudowanej funkcji bin(), która dość prosto przekształci dowolną liczbę na postać binarną. W połączeniu z metodą stringów .count() pozwoli wyciągnąć liczbę 0 lub 1, to też wykorzystałem to w ostatecznym rozwiązaniu. # Zadanie 2 - opis podejścia. W zasadzie od razu wiedziałem, że jest to zadanie związane z dynamicznym programowaniem. Wiedziałem, że można do niego podejść na dwa sposoby (jak do wszystkiego) i tak też w tym przypadku podszedłem. Osobiście najpierw myślę nad rozwiązaniem problemu metodą brute-force, a napisanie samego kodu rekurencyjnego nie zajęło mi wiele czasu. Rozpisywałem też działanie kodów na kartce, sprawdzałem możliwości podejścia - co (nie)stety często zdarza mi się robić - i w ten sposób powoli doszedłem do rozwiązania dynamicznego. Już kiedyś przerabiałem podobny problem (znalezienie czworoboku o największym polu, spośród kilku połączonych ze sobą, prezentowanych właśnie na macierzy). Po obliczeniu kosztów dojścia całego pierwszego rzędu i kolumny (dla przypadku, gdzie poruszalibyśmy się innymi ścieżkami, należałoby obliczyć inne pola) wystarczy znaleźć "minimum lokalne" - jak to nazwałem - a następnie sięgnąć po informacje pod odpowiednim indeksem. Na początku obliczałem minimum lokalne dla całej listy (limit rzędów i kolumn ustawiony na len(L)), ale doszedłem do wniosku, że lepiej obliczać tylko tyle, ile jest potrzebne (limit ograniczony do rzędu i kolumny którą chcemy sprawdzić), Zastanawiałem się też nad implementacją, która pozwoliłaby zmniejszyć koszt pamięci, która teraz jest O(n^2), bo tworzę drugą listę, listę kosztów takiego samego rozmiaru co ta wejściowa, ale uznałem, że mogłoby to za nadto skomplikować sprawę. Nie jestem też dumny ze sposobu w który wydobywam informację z pliku, ale muszę przyznać, że wydał mi się on dość prosty. Zakodowałem również obsługę wyjątku wywołania skryptu bez podania argumentu, chociaż nie zakodowałem obsługi błędu dla wypadku w którym ktoś poda złą nazwę ścieżki/pliku, ponieważ ta wbudowana (FileNotFound) wydała mi się całkiem sensowna. W pliku dwie wersje rozwiązania.
About
Code examples for internship test
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published