eXtra zadanie - tylko dla orłów?Jednym z zadań trwającego obecnie Mistrzostw w Grach Matematycznych i Logicznych sformułowane zostało następujące zadanie: (patrz zadanie 14):ProblemW grupie złożonej z N osób (gdzie N = 16) każda osoba ma dokładnie trzech znajomych w tej grupie. Czy zawsze można wszystkie osoby z tej grupy ustawić parami tak, aby w każdej parze znalazły się osoby, które się znają ?Zakładamy, że relacja znajomości jest symetryczna, tzn. że jeśli osoba A zna osobę B, to również B zna A. Zadanie programistyczneNapisz program rozwiązujący Problem dla dowolnego parzystego N > 2.Program powinien przeszukiwać wszelkie możliwe grafy powiązań N osób więzami znajomości, w których każda z osób zna dokładnie 3 inne. Po znalezieniu każdego takiego grafu program winien sprawdzić, czy da się w nim połączyć osoby w pary. Jeśli uda się znaleźć taki graf, to program powinien go wydrukować. Jeśli nie istnieje taki graf, to program powinien o tym poinformować po zakończeniu generowania wszelkich możliwych grafów. Dla wygody testowania program powinien umożliwiać wydruki kolejno wygenerowanych grafów znajomości oraz znalezionego ustawienia w pary. Termin składania rozwiązańSamodzielnie stowrzone programy oceniane będą do dnia egzaminu włącznie.Kryteria oceny rozwiązańPodane w kolejności od najbardziej, do najmniej znaczących:
KomentarzZadanie uważam za trudne. Łatwiej będzie, moim zdaniem, zaliczyć ćwiczenia i nauczyć się wykładanego matriału, niż stworzyć satysfakcjonujący program. Tym niemniej, namawiam wszystkich do spróbowania swoich sił. Powodzenia!Kontakt: IPI PAN e-mail: m.bednarczyk@ipipan.gda.pl s-mail: Instytut Podstaw Informatyki, filia Gdańsk, Abrahama 18, 81-825 Sopot 
|