6 komentarzy do “Zadania programistyczne”

1. Jasne, ze potrafimy, tylko nam sie nie chce (dobrze, mowie za sobie).
   Przychodzi n kodow-liczb.
   Numerujemy je od zera do n-1.
   Funkcja rekurencyjana f(n)
   zwraca nam potrzebny numer, w przedziale od zera do n-1.
   Wzor rekurencyjny:
   f(1) = 0
   f(n+1) = ( 3 + f(n) ) mod (n+1).
   —
   Zatem, do zrobienia jest:
   Kodowanie w jakims jezyku powyzszej rekurencji.
   Pobranie tych liczb, (zapewne do jakies tablicy jednowymiarowej)
   zanotowanie ich ilosci
   uruchomienie funkcji rekurencyjnej – obliczenie pozycji
   Odpowiedz – kod-liczba z obliczonej pozycji.
   —
   Jezeli komus sie chce oprogramowac cos takiego np w C lub C++
   i chcialby to kontynuowac, to prosze o kontakt.
   Radek

   1. Wydaje sie ze przy zastosowaniu C dosc latwo to mozna zaprogramowac prosciutka struktura. W C++ tez ale stosowanie STL pewnie skonczy sie duza iloscia kopiowania.

      Naiwna implementacja to pewnie jednokierunkowa lista cykliczna przechowujaca kody. Lista ma po wczytaniu N elementow. Zatem przy wyrzucaniu co trzeciego rozwiazanie dostaniemy w N krokach (w notacji Big-Oh O(N). Zakladajac ze do wyrzucenia kazego elementu trzeba wykonac trzy przesuniecia po liscie to bedzie to 3N przesuniec i N wyrzucen/polaczen.

      Warunek stopu: element listy po ostatnim wyrzuceniu bedzie wskazywal na siebie… i tam bedzie umiejscowiony kod.

      Skorygujcie mnie bo juz nie wiem czy dobrze pamietam cokolwiek… i czy rozumiem zagadnienie poprawnie.

      Wlasnie siedze i robie jakis powtorkowy kurs online ze Stanford Univ. na temat projektowania algorytmow. Idzie ciezko bo jak sie przewala dane z miejasca na miejsce na codzien przez wiele lat to sie zapomina wszystko co ciekawe w programowaniu.

      Na dodatek orlem analizy mat. nie bylem co Radek moze doskonale potwierdzic :-))) Dla wtajemniczonych to szukalem miejsca w pierwszym rzedzie na zajeciach u Radka.

      -Maciek

      1. Poniewaz mamy juz funkcje rekurencyjna,
         wiec nie sa konieczne zadne operacje na liscie.
         Spodziewam sie, ze duza liczba odpowiedzi bedzie te operacje zawierala.
         Rozwiazanie z funkcja rekyrencyjna jest prostsze i szybsze.
         Mamy wiec szanse w konkursie.
         Radek

         1. Zgoda. Tyle ze dane i tak musimy wczytac do pamieci. W zaleznosci od liczebnosci danych mozemy przepelnic stos rekurencja. Dla nieduzych zbiorow pewnie nie ma sprawy (i przy dzisiejszych pamieciach tez pewnie nie ma sprawy).Dla wiekszych zbiorow kiedys sie unikalo rekurencji o ile pamietam. Chyba oszczedzimy tylko na wspolczynniku „3”. W tej rekurencji chyba tez musimy zrobic te N krokow obliczeniowych tyle ze nie operujac na pamieci ale wyliczajac index tablicy (N-1 dodawan i N-1 operacji modulo).

            Co do szybkosci to warto przetestowac obie. Kiedys testowalem taka funkcje dla wyznacznia pewnego identyfikatora bankowego i okazalo sie ze algorytm szybszy teoretycznie byl niestety wolniejszy w praktyce (?).

            Operacja modulo np. w Javie’ np. jest nieefektywna (wlasnie to wytestowalem przy projektowaniu identyfikatora bankowego) co pewnie mialoby inny rezultat gdyby byla implementowana w C.

            Wyniki pewnie beda rozne w zaleznosci kto w czym napisze 😉

            -Maciek

            1. Wzor jest na tyle prosty,
               ze w implementacji nie trzeba rekurencji,
               wystarczy zwykla petla.
               Jezeli funkcja mod jest nieefektywna,
               to (w tym wypadku) wystarczy zwykle if wieksze then x := x – n
               Radek

            2. Pewnie bedzie cos takiego (w C nie programowalem ladnych kilka lat 😉

               int code[N];

               int getCodeIndex(int N) {
               k = 0;
               for(i=1;i

Możliwość komentowania została wyłączona.