Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

C++ - Algorytm zachlanny, ukladanie planu zajec

yashioo 12 Gru 2014 16:48 1446 5
  • #1 12 Gru 2014 16:48
    yashioo
    Poziom 7  

    Hej, mam do napisania taki program, ale zupelnie nie mam pomyslu na algorytm zachłanny ktory ukladalby sprawdzal ten plan, bez pomyslu na ten algorytm nie wiem do konca w jaki sposob stworzyc najlepiej klase itp. Moglby mi ktos podpowiedziec cos w jaki sposob zrobic taki algorytm ?


    Tutaj cale polecenie (Programowanie Obiektowe w C++)

    Spoiler:

    Napisać program wspomagający układanie planu lekcji dla szkoły.
    Dane wejściowe, czytane z pliku .txt:
    — lista przedmiotów (np.: fizyka, chemia, biologia)
    — lista klas oraz wymagań, np.:
    1A: fizyka (4 godz.),
    chemia (2 godz.),
    biologia (1 godz.);
    1B fizyka (4 godz.),
    chemia (3 godz.),
    biologia (2 godz.);
    2A fizyka (8 godz.),
    chemia (6 godz.),
    biologia (0 godz.);
    Założenia dodatkowe:
    — dany przedmiot nie może być prowadzony o tej samej godzinie w dwu różnych klasach;
    — nauka trwa 5 dni w tygodniu, w każdym dniu może się odbywać nie więcej niż 8 lekcji.
    W wyniku działania programu powinno uzyskać się informację, czy da się ułożyć plan lekcji przy
    założonych danych wejściowych, a jeśli tak — to jedno z możliwych rozwiązań.
    Najprościej użyć algorytmu zachłannego (greedy algorithm) do wyszukiwania rozwiązania. Można
    również zaproponować inny algorytm.

    0 5
  • Pomocny post
    #2 12 Gru 2014 17:52
    wacuu
    Poziom 11  

    Sam algorytm spoko; bierzesz pierwszą klasę, układasz po kolei w planie(umieszczasz godziny przewidziane wg założeń), a następne klasy jakby sprawdzają czy jest wolne miejsce; bierzesz sobie pierwszą godzinę z wymagań kolejnej klasy i przechodzisz po całym planie, sprawdzając czy jest wolne miejsce. Cały algorytm zachłanny: po prostu lokalnie wyszukujesz miejsce pasujące do twoich wymagań.

    Implementacja może być gorsza. Potrzebujesz tablicy 5x8, w której będziesz trzymał inty. Każdy przedmiot ma dostać swój identyfikator: inta. Przechodząc przez pole w tablicy będzie dodawał się do tego co będzie wpisane w to pole. jeśli suma w polu osiągnie pewną wartość, to będzie znaczyło, że żadna lekcja się już tam nie zmieści. Zagadka dla Ciebie: jakie liczby muszą być, żeby każda 'suma przedmiotów' była inna. To sprawdzi czy istnieje kombinacja, która pasuje. No i na początku warto postawić pytanie czy w założeniach nie ma zbyt dużej liczby godzin, że upakować je w całym tygodniu.

    0
  • #3 16 Gru 2014 00:47
    yashioo
    Poziom 7  

    Nie potrafie rozwiazac tej zagadki ;)
    Mógłbyś trochę to jeszcze wyjaśnić?

    0
  • Pomocny post
    #4 16 Gru 2014 06:25
    wacuu
    Poziom 11  

    Algorytm zachłanny to taki, który wyszukuje chwilowo najbardziej optymalne rozwiązanie. W tym przypadku będzie szukał pierwszej możliwej godziny lekcyjnej, gdzie:
    -dany przedmiot lub nie wystąpił jeszcze w ogóle
    -czy nie przekraczasz dopuszczalnej ilości godzin
    Czyli najbliższej opcji na tyle optymalnej, żeby zamieścić tam kolejną lekcję.

    W implementacji moim zdaniem można zrobić tak, że każdy przedmiot będzie miał przyporządkowaną wartość liczbową. Zanim to jeszcze kształt samego planu. Wyobraź sobie tydzień jako tablicę o rozmiarze 5x8. Zanim zaczniemy układać plan, musimy ją całą wyzerować. A teraz z zagadki: przyporządkujmy przykładowo fizyce 1, chemii 2 i biologi 4. Skorzystajmy teraz z twoich danych wejściowych: 'biorę' klasę 1a. Mają mieć 4 fizyki. Idąc od początku planu, czyli od pierwszego pola tablicy pakuję 1 do kolejnych pól pierwszego dnia. Następna ma być chemia. zaczynając od kolejnej godziny po fizyce, w podobny sposób układam zajęcia, tylko że zamiast 1 daję 2. Potem przechodzę do klasy 1b. wchodzę na pierwsze pole tygodnia. wpisana tu jest 1, którą program umieścił tam przy poprzednim przejściu. i dlatego, że jest 1, nie mogę tam wsadzić fizyki. i tak samo z pozostałymi przedmiotami. a liczby wzięły się stąd, że po dodaniu różnych kombinacji są różne wyniki.
    1+2(fizyka i chemia)
    1+4(fizyka i biologia)
    2+4(chemia i biologia)
    1+2+4(wszystko)
    Czyli odpowiedzi są po prostu jednoznaczne. na koniec trzeba by zczytać właśnie te wyniki i wypisać ładnie. haczyk taki, że to bedzie miało dużą złożoność czasową

    0
  • #5 16 Gru 2014 15:20
    yashioo
    Poziom 7  

    A w jaki sposób stwierdzić że 1 + 4 to fizyka klasy 1a i biologia klasy 1b ?
    W sensie w jaki sposob odczytac do jakiej klasy jest przypisana dana lekcja?

    0
  • Pomocny post
    #6 16 Gru 2014 16:24
    wacuu
    Poziom 11  

    ... no to jest wła$nie problem takiej implementacji. W sumie, chociaż głowy nie dam, można wziąć wymagania danej klasy i przejść ponownie po całym planie, tym razem sprawdzając, czy dane pole ma odpowiednią ilo$ć 'punktów' i, jeśli tak, to wtedy należy poinformować, że lekcja może się odbyć i odjąć punkty w zależności od przedmiotu. Problem 1:nie dam se ręki uciąć, że zadziała, ale powinno. Problem 2: nie wiem, jak dokładnie jest w specyfikacji, ale istnieje przypadek, w którym która$ klasa do szkoły będzie chodzić mniej niż 5 dni. Wiele takich przypadków.

    0