Zadanie zaliczeniowe z laboratorium Pascala i C. ZSI I. 01/02
-------------------------------------------------------------
Zadane: 13-14.02.2002, odbiór: 27-28.02.2002, 4 punkty.
Zad 8. (4 pkt)
--------------
Etapy budowy domu.
------------------
Wyobraź sobie, że Twoim zadaniem jest wybudowanie domu. Jednak liczba
związanych z tym prac jest tak duża, że postanowiłeś napisać program,
który pomoże Ci ustalić właściwą kolejność wykonywania poszczególnych
etapów budowy. To co wiesz jest sumą pewnych oczywistych zależności
jak np. to, że dach trzeba budować po wybudowaniu ścian, czy jednak okna
można wstawiać przed założeniem instalacji C.O. ?
To nie jest wcale oczywiste, i dlatego należy napisać program,
który wczyta z pliku tekstowego o zadanej nazwie ciąg
zależności pomiędzy etapami budowy, a następnie zaproponuje pewną
kolejność wykonywania prac, o ile jest to możliwe, lub też wypisze, że
ustalenie takiej kolejności jest niemożliwe z powodu wystąpienia cyklu.
Etapy budowy są ponumerowane od 1 do n.
Plik zawierający zależności między etapami budowy ma następująca postać:
- w pierwszym wierszu jest liczba etapów n (1 <= n <= 1000),
- zależności są opisane w kolejnych m wierszach (0 <= m <= 10000),
- każdą zależność opisuje para liczb Przed Po (oddzielonych jedną spacją)
oznaczającą, że etap Przed należy wykonać przed etapem Po.
Przykładowo dla danych:
6
4 1
5 2
4 3
6 3
2 4
2 3
jeden z możliwych wyników to:
5 2 6 4 3 1
Założenia dotyczżce implementacji:
----------------------------------
Program powinien składać się z trzech części:
* Modułu graf:
Implementującego operacje na strukturze danych przechowującej
zależności między etapami budowy. Postać struktury do zaprojektowania
własnoręcznie. Moduł powinien udostępniać operacje:
- PROCEDURE Inicjuj (n : integer);
Inicjuje strukturę danych zawierającą n etapów (n <= 1000), bez żadnych
zależności;
- PROCEDURE WstawZaleznosc(Po, Przed : integer);
Wstawia zależnosc: etap Przed musi być wykonany przed etapem Po.
- PROCEDURE UsunEtap (E : integer);
Usuń etap E wraz ze wszystkimi zależnościami mówiącymi, że ma on być
wykonany przed lub po jakimś etapie.
- FUNCTION Pierwszy : integer;
Daje numer etapu, który zgodnie z pamiętanymi zależnościami może
być wykonany jako pierwszy. (0 jeśli taki etap nie istnieje.)
- PROCEDURE ZwolnijPamiec;
Zwalnia pamięć zajętą przez strukturę danych.
* Modułu Plik, zawierającego następujące operacje:
- FUNCTION Otworz (nazwapliku : string) : integer;
Otwiera plik z danymi i daje liczbę etapów.
- FUNCTION DajZaleznosc (var Przed, Po : integer) : boolean;
Próbuje wczytać kolejną zależność do zmiennych Przed i Po -
daje true, jeśli w pliku była jeszcze zależność.
Jeśli nie było, to zamyka plik z danymi i daje false.
* Programu głównego