Dodaj do ulubionych

komentarz do zadania z informatyki

11.05.05, 18:12
komentarz do podpunktu a) zaddania 2 w 2 arkuszu z
informatyki.
Chciałbym przytoczyć cytat na temat tego zadania z książki Jon'a Bentley'a
"Perełki Oprogramowania" "Ten program jest skomplikowany i łatwo w nim o
błędy, ale rozwiązuje zadanie w czasie O(n log n)." O(n log n) czyli
najszybciej jak to możliwe, a o taki program pytano w zadaniu. Jon Bentley
jest to jeden z twórców dzisiejszej algorytmiki, jeden z największych umysłów
informatyki, stwierdza on, że to zadanie jest trudne i my je dostajemy na
maturze?
Obserwuj wątek
    • bracishek Re: komentarz do zadania z informatyki 11.05.05, 20:15
      A można było zrobić tabelę o wielkości rozpiętości danych i robić to na hama,
      zwiększając odpowiednie indeksy. Wtedy wychodziła jeszcze prostsza
      złożoność.. :)
      Ja tam robiłem to bardziej na hama -> do tablicy i posortowac.. :)
      Ciekawe tylko co bedzie w kluczu..
    • Gość: Lolo Re: komentarz do zadania z informatyki IP: *.brzesko.net.pl 11.05.05, 20:28
      Chyba pomyliło Ci sie zadanie w tej książce, bo zad2a zrobiłem w Pascalu ze
      zlozonoscia n.

      masz 3 zmienne - t, as i ns
      1.as:=0; ns:=0;
      2.Jesli nie koniec pliku to wczytujesz liczbe do zmiennej t
      3. Dodajesz t do as (as:=as+t)
      4. jeśli as<0 to as:=0 a jak nie to jesli as>ns to ns:=as;
      5. skok do kroku 2

      po zakonczeniu petli w zmiennej ns masz najlepsza sume tego ciagu liczb z
      pliku:) łatwe nie :)
      • salmon2 Re: komentarz do zadania z informatyki 11.05.05, 20:34
        watpie zeby to bylo optymalne i prawidłowe
        • Gość: Lolo Re: komentarz do zadania z informatyki IP: *.brzesko.net.pl 11.05.05, 20:38
          To nie wątp, tylko najpierw sprawdz:)

          jak cos to zagadaj do mnie na gg, wytlumacze Ci :)

          gg:3634405
      • salmon2 Re: komentarz do zadania z informatyki 11.05.05, 20:39
        "Na wejsciu znajduje sie wektor x zawierajacy n liczb rzeczywistych; wyjscie
        stanowi maksymalna suma elementów dowolnego spójnego fragmentu wektora z wejścia"
        Jon Bentley "Perełki Oprogramowania" WNT s.95
        To jest to zadanie
        • Gość: Lolo Re: komentarz do zadania z informatyki IP: *.brzesko.net.pl 11.05.05, 20:53
          Aha, czyli to jeszcze masz robione na wktorach:) No to ja sie nie dziwie, ze
          wolno chodzi.

          Ale spróbuj przpeuścić sobie przez moj alg jakieś dane, i zobaczymy czy dobrze
          działa :) A jestem pewny, że działa, przynajmniej dla danych, które mają chociaż
          1 element dodatni lub jedno zero. Nie przejda tylko takie dane, gdzie sa same
          liczby ujemne, ale to mozna naprawic niewielka modyfikacją algorytmu.
          Podobne zadanie jest w Lidze Zadaniowej Politechniki Śląskiej tu:
          liga.iinf.polsl.gliwice.pl/aktualna/zadania/_termin2/znaczki.html
          tylko troche trudniejsze, więcej danych przede wszystkim :)

Nie masz jeszcze konta? Zarejestruj się


Nakarm Pajacyka