{"id":"informator-maturalny-informatyka-2015/zad/14","paper_id":"informator-maturalny-informatyka-2015","number":"14","points":null,"ptype":"open","subject":"informatyka","category":"informator-maturalny","year":2015,"month":null,"level":null,"text":"Zadanie 14. Fani (0-9)\nFani spotykają się z ulubionymi gwiazdami filmowymi w sali, której podłoga ma kształt\nkwadratu. Podłogę podzielono pionowymi i poziomymi liniami na mniejsze kwadraty\nrozmiaru 1x1. Zaproszona gwiazda zawsze siada w środku sali. Fani zajmują miejsca w sali\nna przecięciach linii. Jedno miejsce może zająć co najwyżej jedna osoba.\nPo wejściu na salę wypełniają oni kolejno strefy zaznaczone na Rys.2. kwadratami, każdą\nstrefę maksymalnie, jak się da. Fani zajmują tylko te miejsca, z których gwiazda jest\nwidoczna, co oznacza, że na odcinku łączącym ich miejsce z miejscem zajmowanym przez\ngwiazdę nie ma żadnej innej osoby. Na potrzeby zadania fanów i gwiazdę utożsamiamy\nz punktami, które zajmują. Na Rys. 1. przedstawione jest przykładowe rozmieszczenie\nwszystkich osób zgodnie z opisem. Na Rys. 2. pokazany jest przykładowe całkowite\nwypełnienie sali w 3 strefach. Jak widać w I strefie zasiądzie 8 fanów, w II strefie - 8, a w III\naż 16.\n14.1 Uzupełnij poniższą tabelę\nStrefa\nMaksymalna liczba\nfanów w kwadracie\nPrzyrost fanów w stosunku\ndo poprzedniego poziomu\nI\n8\nII\n16\n8\nIII\n32\n16\nIV\nV\nVI\n26 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\n14.2 Potraktuj salę (Rys. 1.) jako układ kartezjański, przyjmując pozycję gwiazdy jako punkt\n(0,0), a pozycje fanów jako punkty kratowe o określonych współrzędnych (x,y),\nodpowiedz na pytania:\na) W której strefie znajduje się pozycja o współrzędnych (17-18)?\nb) Podaj dwie pozycje, najbliżej położone względem pozycji (4,3), zasłaniane przez\nfana stojącego na tej pozycji.\nc) Podaj współrzędne dwóch miejsc, których zajęcie przez fanów uniemożliwi\noglądanie gwiazdy przez fana znajdującego się w polu (8; 12).\nd) Czy fan może stanąć na każdej pozycji, której jedna ze współrzędnych jest równa 1?\ne) Czy fan może stanąć w miejscu o współrzędnych (13; 39)? Odpowiedź uzasadnij.\n14.3 Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku\nprogramowania) sprawdzający, czy fan może stanąć w miejscu o danych współrzędnych\n(x,y).\nSpecyfikacja\nDane: x,y - liczby całkowite określające położenie fana względem gwiazdy\nWynik: Komunikat TAK, jeżeli fan widzi gwiazdę lub komunikat NIE, jeżeli fan gwiazdy nie\nwidzi.\nPrzykładowe zadania z rozwiązaniami 27\nAlgorytm\nWymagania ogólne\nIII. Rozwiązywanie problemów i podejmowanie\ndecyzji z wykorzystaniem komputera, z zastosowaniem\npodejścia algorytmicznego.\nWymagania szczegółowe\n5. Rozwiązywanie problemów i podejmowanie decyzji\nz wykorzystaniem komputera, stosowanie podejścia\nalgorytmicznego.\nZdający:\n1) analizuje, modeluje i rozwiązuje sytuacje\nproblemowe z różnych dziedzin,\n5) posługuje się podstawowymi technikami\nalgorytmicznymi,\n6) ocenia własności rozwiązania algorytmicznego\n(komputerowego), np. zgodność ze specyfikacją,\nefektywność działania,\n11) opisuje podstawowe algorytmy.\n28 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nSchemat punktowania\nNr\npodpunktu\nCzynność\nLiczba\npunktów\nza\npodpunkt\nLiczba\npunktów\nza\nzadanie\n14.1.\nZa poprawną uzupełnienie tabeli - 3 punkty.\nZa poprawnie uzupełnienie każdego wiersza - 1 punkt.\n3\n9\n14.2.\nZa poprawne podanie odpowiedzi do każdego\npodpunktu - 1 punkt; razem 4 punkty.\n4\n14.3.\nZa poprawny algorytm - 2 punkty.\nW przypadku algorytmu z błędnymi warunkami\nbrzegowymi - 1 punkt.\n2\nZadanie 14. Fani (0-9)- rozwiązanie\nFani spotykają się z ulubionymi gwiazdami filmowymi w sali, której podłoga ma kształt\nkwadratu. Podłogę podzielono pionowymi i poziomymi liniami na mniejsze kwadraty rozmiaru\n1x1. Zaproszona gwiazda zawsze siada w środku sali. Fani zajmują miejsca w sali na\nprzecięciach linii. Jedno miejsce może zająć co najwyżej jedna osoba.\nPo wejściu na salę wypełniają oni kolejno strefy zaznaczone na Rys. 2. kwadratami, każdą\nstrefę maksymalnie, jak się da. Fani zajmują tylko te miejsca, z których gwiazda jest widoczna,\nco oznacza, że na odcinku łączącym ich miejsce z miejscem zajmowanym przez gwiazdę nie ma\nżadnej innej osoby. Na potrzeby zadania fanów i gwiazdę utożsamiamy z punktami, które\nzajmują. Na Rys. 1. przedstawione jest przykładowe rozmieszczenie wszystkich osób zgodnie\nz opisem. Na Rys. 2. pokazany jest przykładowe całkowite wypełnienie sali w 3 strefach. Jak\nwidać w I strefie zasiądzie 8 fanów, w II strefie - 8, a w III aż 16.\nPrzykładowe zadania z rozwiązaniami 29\n14.1. Uzupełnij poniższą tabelę\nStrefa\nMaksymalna liczba\nfanów w kwadracie\nPrzyrost fanów w stosunku\ndo poprzedniego poziomu\nI\n8\nII\n16\n8\nIII\n32\n16\nIV\n48\n16\nV\n80\n32\nVI\n96\n16\n14.2.Traktując salę (Rys.1.) jako układ kartezjański, przyjmując pozycję gwiazdy jako punkt\n(0,0), a pozycje fanów jako punkty kratowe o określonych współrzędnych (x,y) odpowiedź\nna pytania:\na) W której strefie znajduje się pozycja o współrzędnych (17; -18)?\nXVIII…(max z |x| lub |y|)\nb) Podaj dwie pozycje, najbliżej położone względem pozycji (4,3), zasłaniane przez fana\nstojącego na tej pozycji.\n(8; 6) oraz (12; 9)\nc) Podaj współrzędne dwóch miejsc, których zajęcie przez fanów uniemożliwi oglądanie\ngwiazdy przez fana znajdującego się w polu (8; 12).\n(2; 3) oraz (4; 6)\nd) Czy fan może stanąć w każdym punkcie, którego jedna ze współrzędnych jest równa 1?\nTAK\ne) Czy fan może stanąć w miejscu o współrzędnych (13; 39)? Odpowiedź uzasadnij.\nNIE. Współrzędne x i y fana muszą być liczbami względnie pierwszymi.\n14.3.Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku\nprogramowania) sprawdzający, czy fan może stanąć w miejscu o danych współrzędnych\n(x,y).\nSpecyfikacja\nDane: x,y - liczby całkowite określające położenie fana względem gwiazdy\nWynik: komunikat TAK, jeżeli fan widzi gwiazdę lub komunikat NIE- jeżeli fan gwiazdy nie\nwidzi\nAlgorytm\nPoniżej zamieszczony jest algorytm zapisany w języku programowania C:\nint nwd(int a, int b)\n{ while (a != b)\nif (a > b) a -= b; else b -=a;\nreturn a;\n}\nint main()\n{\ncin>>x>>y;\n30 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015\nif (x<0)x=-x; if(y<0)y=-y; //sprowadzenie problemu do liczb\n//nieujemnych\nif (((x==0)&&(y==0))cout<<”NIE”; else\nif ((x==0)&&(y!=1)||(x!=1)&&(y==0))) cout<<”NIE”; else\nif (((x==0)&&(y==1))||((y==0)&&(x==1))) cout<<”TAK”;else\nif (nwd(x,y)==1) cout<<”TAK”; else\ncout<<”NIE”;\n}\nKomentarz\nKluczem do poprawnego sformułowania algorytmu jest spostrzeżenie, że fani mogą zająć tylko\nte punkty kratowe o współrzędnych (x, y) , które nie zostaną przesłonięte przez żaden inny punkt\nkratowy. Inaczej, na odcinku, łączącym punkt (0, 0) i punkt kratowy (x, y), który ma zająć fan,\nnie może wystąpić żaden inny punkt o współrzędnych całkowitych. Punktami spełniającymi ten\nwarunek są punkty, których NWD(x, y)=1, czyli takie, których współrzędne są liczbami\nwzględnie pierwszymi. Dlaczego? Gdyby współrzędne (x, y) nie były względnie pierwsze, to\nznaczyłoby, że na wymienionym odcinku musiałby się znaleźć punkt o współrzędnych\ncałkowitych (x / NWD(x, y), y/ NWD(x, y)), który zasłaniałby gwiazdę.\nDla uproszczenia algorytmu można sprowadzić warunki zadania do przypadku, gdy x> 0\ni y>0, ponieważ NWD(x,y)=NWD(|x|,|y|). Jeżeli którakolwiek współrzędna jest równa zero, to\nmożna wykorzystać fakt, że NWD(x, 0)=|x|.\nPunkt 14.1 oraz 14.2 z podpunktami od a) do e) pomagają w analizie problemu przed\nsformułowaniem i zapisaniem algorytmu. Po poprawnym uzasadnieniu odpowiedzi z punktu\n14.2.e) zapisanie algorytmu nie powinno przysporzyć trudności zdającym.\nPrzykładowe zadania z rozwiązaniami 31","answer":null,"answer_text":null,"solution":null,"image":"img/informator-maturalny-informatyka-2015/zad-14.webp","solution_image":null,"topics":null,"page_from":25,"source":"ocr","answer_source":null,"answer_text_source":null,"solution_source":null,"text_source":"ocr","source_label":"Informatyka · Informator maturalny · 2015","subject_label":"Informatyka","category_label":"Informator maturalny","text_html":"

Zadanie 14. Fani (0-9)
Fani spotykają się z ulubionymi gwiazdami filmowymi w sali, której podłoga ma kształt
kwadratu. Podłogę podzielono pionowymi i poziomymi liniami na mniejsze kwadraty
rozmiaru 1x1. Zaproszona gwiazda zawsze siada w środku sali. Fani zajmują miejsca w sali
na przecięciach linii. Jedno miejsce może zająć co najwyżej jedna osoba.
Po wejściu na salę wypełniają oni kolejno strefy zaznaczone na Rys.2. kwadratami, każdą
strefę maksymalnie, jak się da. Fani zajmują tylko te miejsca, z których gwiazda jest
widoczna, co oznacza, że na odcinku łączącym ich miejsce z miejscem zajmowanym przez
gwiazdę nie ma żadnej innej osoby. Na potrzeby zadania fanów i gwiazdę utożsamiamy
z punktami, które zajmują. Na Rys. 1. przedstawione jest przykładowe rozmieszczenie
wszystkich osób zgodnie z opisem. Na Rys. 2. pokazany jest przykładowe całkowite
wypełnienie sali w 3 strefach. Jak widać w I strefie zasiądzie 8 fanów, w II strefie - 8, a w III
aż 16.
14.1 Uzupełnij poniższą tabelę
Strefa
Maksymalna liczba
fanów w kwadracie
Przyrost fanów w stosunku
do poprzedniego poziomu
I
8
II
16
8
III
32
16
IV
V
VI
26 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
14.2 Potraktuj salę (Rys. 1.) jako układ kartezjański, przyjmując pozycję gwiazdy jako punkt
(0,0), a pozycje fanów jako punkty kratowe o określonych współrzędnych (x,y),
odpowiedz na pytania:
a) W której strefie znajduje się pozycja o współrzędnych (17-18)?
b) Podaj dwie pozycje, najbliżej położone względem pozycji (4,3), zasłaniane przez
fana stojącego na tej pozycji.
c) Podaj współrzędne dwóch miejsc, których zajęcie przez fanów uniemożliwi
oglądanie gwiazdy przez fana znajdującego się w polu (8; 12).
d) Czy fan może stanąć na każdej pozycji, której jedna ze współrzędnych jest równa 1?
e) Czy fan może stanąć w miejscu o współrzędnych (13; 39)? Odpowiedź uzasadnij.
14.3 Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku
programowania) sprawdzający, czy fan może stanąć w miejscu o danych współrzędnych
(x,y).
Specyfikacja
Dane: x,y - liczby całkowite określające położenie fana względem gwiazdy
Wynik: Komunikat TAK, jeżeli fan widzi gwiazdę lub komunikat NIE, jeżeli fan gwiazdy nie
widzi.
Przykładowe zadania z rozwiązaniami 27
Algorytm
Wymagania ogólne
III. Rozwiązywanie problemów i podejmowanie
decyzji z wykorzystaniem komputera, z zastosowaniem
podejścia algorytmicznego.
Wymagania szczegółowe

\n
  1. Rozwiązywanie problemów i podejmowanie decyzji
\n

z wykorzystaniem komputera, stosowanie podejścia
algorytmicznego.
Zdający:

\n
  1. analizuje, modeluje i rozwiązuje sytuacje
\n

problemowe z różnych dziedzin,

\n
  1. posługuje się podstawowymi technikami
\n

algorytmicznymi,

\n
  1. ocenia własności rozwiązania algorytmicznego
\n

(komputerowego), np. zgodność ze specyfikacją,
efektywność działania,

\n
  1. opisuje podstawowe algorytmy.
\n

28 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
Schemat punktowania
Nr
podpunktu
Czynność
Liczba
punktów
za
podpunkt
Liczba
punktów
za
zadanie
14.1.
Za poprawną uzupełnienie tabeli - 3 punkty.
Za poprawnie uzupełnienie każdego wiersza - 1 punkt.
3
9
14.2.
Za poprawne podanie odpowiedzi do każdego
podpunktu - 1 punkt; razem 4 punkty.
4
14.3.
Za poprawny algorytm - 2 punkty.
W przypadku algorytmu z błędnymi warunkami
brzegowymi - 1 punkt.
2
Zadanie 14. Fani (0-9)- rozwiązanie
Fani spotykają się z ulubionymi gwiazdami filmowymi w sali, której podłoga ma kształt
kwadratu. Podłogę podzielono pionowymi i poziomymi liniami na mniejsze kwadraty rozmiaru
1x1. Zaproszona gwiazda zawsze siada w środku sali. Fani zajmują miejsca w sali na
przecięciach linii. Jedno miejsce może zająć co najwyżej jedna osoba.
Po wejściu na salę wypełniają oni kolejno strefy zaznaczone na Rys. 2. kwadratami, każdą
strefę maksymalnie, jak się da. Fani zajmują tylko te miejsca, z których gwiazda jest widoczna,
co oznacza, że na odcinku łączącym ich miejsce z miejscem zajmowanym przez gwiazdę nie ma
żadnej innej osoby. Na potrzeby zadania fanów i gwiazdę utożsamiamy z punktami, które
zajmują. Na Rys. 1. przedstawione jest przykładowe rozmieszczenie wszystkich osób zgodnie
z opisem. Na Rys. 2. pokazany jest przykładowe całkowite wypełnienie sali w 3 strefach. Jak
widać w I strefie zasiądzie 8 fanów, w II strefie - 8, a w III aż 16.
Przykładowe zadania z rozwiązaniami 29
14.1. Uzupełnij poniższą tabelę
Strefa
Maksymalna liczba
fanów w kwadracie
Przyrost fanów w stosunku
do poprzedniego poziomu
I
8
II
16
8
III
32
16
IV
48
16
V
80
32
VI
96
16
14.2.Traktując salę (Rys.1.) jako układ kartezjański, przyjmując pozycję gwiazdy jako punkt
(0,0), a pozycje fanów jako punkty kratowe o określonych współrzędnych (x,y) odpowiedź
na pytania:
a) W której strefie znajduje się pozycja o współrzędnych (17; -18)?
XVIII…(max z |x| lub |y|)
b) Podaj dwie pozycje, najbliżej położone względem pozycji (4,3), zasłaniane przez fana
stojącego na tej pozycji.
(8; 6) oraz (12; 9)
c) Podaj współrzędne dwóch miejsc, których zajęcie przez fanów uniemożliwi oglądanie
gwiazdy przez fana znajdującego się w polu (8; 12).
(2; 3) oraz (4; 6)
d) Czy fan może stanąć w każdym punkcie, którego jedna ze współrzędnych jest równa 1?
TAK
e) Czy fan może stanąć w miejscu o współrzędnych (13; 39)? Odpowiedź uzasadnij.
NIE. Współrzędne x i y fana muszą być liczbami względnie pierwszymi.
14.3.Zapisz algorytm (w postaci listy kroków, schematu blokowego lub w wybranym języku
programowania) sprawdzający, czy fan może stanąć w miejscu o danych współrzędnych
(x,y).
Specyfikacja
Dane: x,y - liczby całkowite określające położenie fana względem gwiazdy
Wynik: komunikat TAK, jeżeli fan widzi gwiazdę lub komunikat NIE- jeżeli fan gwiazdy nie
widzi
Algorytm
Poniżej zamieszczony jest algorytm zapisany w języku programowania C:
int nwd(int a, int b)
{ while (a != b)
if (a > b) a -= b; else b -=a;
return a;
}
int main()
{
cin>>x>>y;
30 Informator o egzaminie maturalnym z informatyki od roku szkolnego 2014/2015
if (x<0)x=-x; if(y<0)y=-y; //sprowadzenie problemu do liczb
//nieujemnych
if (((x==0)&&(y==0))cout<<”NIE”; else
if ((x==0)&&(y!=1)||(x!=1)&&(y==0))) cout<<”NIE”; else
if (((x==0)&&(y==1))||((y==0)&&(x==1))) cout<<”TAK”;else
if (nwd(x,y)==1) cout<<”TAK”; else
cout<<”NIE”;
}
Komentarz
Kluczem do poprawnego sformułowania algorytmu jest spostrzeżenie, że fani mogą zająć tylko
te punkty kratowe o współrzędnych (x, y) , które nie zostaną przesłonięte przez żaden inny punkt
kratowy. Inaczej, na odcinku, łączącym punkt (0, 0) i punkt kratowy (x, y), który ma zająć fan,
nie może wystąpić żaden inny punkt o współrzędnych całkowitych. Punktami spełniającymi ten
warunek są punkty, których NWD(x, y)=1, czyli takie, których współrzędne są liczbami
względnie pierwszymi. Dlaczego? Gdyby współrzędne (x, y) nie były względnie pierwsze, to
znaczyłoby, że na wymienionym odcinku musiałby się znaleźć punkt o współrzędnych
całkowitych (x / NWD(x, y), y/ NWD(x, y)), który zasłaniałby gwiazdę.
Dla uproszczenia algorytmu można sprowadzić warunki zadania do przypadku, gdy x> 0
i y>0, ponieważ NWD(x,y)=NWD(|x|,|y|). Jeżeli którakolwiek współrzędna jest równa zero, to
można wykorzystać fakt, że NWD(x, 0)=|x|.
Punkt 14.1 oraz 14.2 z podpunktami od a) do e) pomagają w analizie problemu przed
sformułowaniem i zapisaniem algorytmu. Po poprawnym uzasadnieniu odpowiedzi z punktu
14.2.e) zapisanie algorytmu nie powinno przysporzyć trudności zdającym.
Przykładowe zadania z rozwiązaniami 31

","solutions":[]}