Лабораторная работа
8 фак\'п,п'т, 1 курс, T $шестр, 2(111,12 учебный год
Лабораторная работа №9 по курсу информатики
Цедя работы. — составление и отладка простейшей программы на языке С итеративного харатйрнра с це-
лочисленными рНкуррептпьти соотношениями, задающими некоторое регулярное дишнвиие точки в це-
лочисленной системе координат (z. j) с дискретным временем к и динамическим параметром двидЛния /.
Результатом работы программы должно быть сообщение об итоге движения: попадание в чадаииуЙ
области плсЙЛости не более чем за 50 шагов и время попадания (номер шага. итерации) или сообщение
о промаха: также в результат надо вкдючить время окояч;р|ияо движения. конечные координаты точки
и значение динамического пщлгмет^-Движеция. Начальные данный движения и пдрамргцМ соотношений
задаются в виде констант нр?>г|>8йим+.1.
Варианты заданий для соответствующих областей прибытия:
I. Кольцо, ограниченное двумя окружностями с центром в точке (10.10), радиус внутренней
окружности равен 5, а радиус внешней равен 10
io = 0. jo = -3,/q = -7
1. !:()=rft..7o = -9i/() = 5
%-+i = ik inax(j/,. /а) mod 30 + jk 1ши(ц.. /д.) mod 20 + k,
jk+i = niin(tA-; шах(д... miu^maxfy - lk-jk - Ja))))-
й+i = sign(A; - 10) |ц - jk + h - Ы
|'Д ~ Д-+^|
3 — sign(?*. — jk + i)
\i-k+jk ~-u|
3 - statii(j/. - ц. + k)
+ 10.
+ 10,
й+i = iM*ASh&M(k +'l) mod 40
3.	io = 1. jo = —30. /о = 1
++i = inax(min(i/1 + jk — Ik — k, ik — jk +//,• — k). miii(Ai + ik — jk — Ik, к ~ >k — jk + //, ))•
jk+i = jk + Ik sign ji, mod 20 + A;sigiit/,. mod 10,
lk+i = |U - jk + h- ~ A'| signik signja-
4.	jo = 26. jo = 8. /о = —3
<A+i = iniii(tA- + jk-,ik + кк)(к + 1) mod 30.
jA+i = jk + Ik SignjA, mod 20 + к signtA- mod 10.
Ja+i = 1йах(*А-.?А-, bdkjjkjk) mod 80
5.	Ц) = -1.Д) = -1./о = -9
+'+1 = inax(jA- — к. Ik — к) mod 30 + inax(»A- + Ik- jk + к) mod 20.
Д+1 = (|+- - /a-| Vgn(jk + A) + |+ - k\(jh + A;)) mod 20,
h+i = (ik+kjUk ~ ifj^k + A') mod 25
II. Квадрат с длиной стороны 10, стороны квадрата параллельны осям координат, центр
квадрата в точке (10. —10)
6. /о = 22. jo = 10. /о = Ю	7. /о = И- Jo = 13. /о = Ю
Z ач-1 = 1шп(/а- mod 5. ikk mod 5) + jk + к/3.	i-k+i = | A’ — 151 — или(аа/3. (j'a- + Ik) mod 10) — 20.
jk+i = max(-3ifr. 2j'a.)/5 - \ jk - /а-I-	j'e+i = -(j/,- + k)/5 + \iklk mo(^|.
ifr+i = jk +lk mod 7 + к sign ik mod 10	lk+1 = inax((iA- 4*$/r) mod 15. (/a- +£') mod 14)
8.	zo = -11. jo = -6./о = -5
H+i = ('4' + 5’- +	+ 1) nl°4 25 — lkjkh-(k + 2) mod 10 + 10.
Ja+1 = iiiiii((<A- + jk + h)(k + 3) mod 25r ikjkh^k + 4) mod 25) + 10.
//,•+1 = 2 signal®. + jk + h )(k + 5) mod 10 — ikjkh-(k + 6) mod 25|
9.	io = 10. jo = 20. /о = —1
z-A+i = (| iiia«(iA' (A- + 5). jk(k + 6))| - | miiiOjS + 7). й (4й+ 8))|) mod 20.
jA+i = (3 - sign(i£ - j'a-))| iiiiii(zA-/A- + 5-jklk ~ 3tikjk + 6)| mod 25 - 7.
/а^й = ik mod 10 + jk mod 10 + Ik mod 10
10.	z:o = 24.jo = -14./o = 9
»»+i = (+ + k)(jk - k)(lk + к) mod 25,
Д+i = iniii(zA- + к, тах(д,- — к. Ik — к)) mod 30,
h.-+k = \jk ~ h | sign ik ~ |*| - к,-1 sign jk
1
Лабораторная работа .\’"9
8 (}>ai\yjit>Tj^r, 1 курс, Т реместр, 2()11 12 учебный г&д
III. Лунка, являющаяся пересечением двух кругов радиуса 10, центр первого круга — в точке
(—10. —10), центр второго — в точке (—20. —20)
И. io = 5.jo = 5./o = 4
ц.+1 = ц-/3 - |Z/, - А| sign(Z/, - .у».
jk+i = jk mod 10 — inax(7/r. //,.) mod (A* + 1).
/*+i = h + jkk mod -5 + lfk/5 + 3
12. io = —22. /о = 29^ Zo = 4
Ц-+1 = signniin(»A.. j7) тцх((ц. + A') mod 20. {jk + Ik) mod 20).
jkyi = |тах(-тА...д.)| - kinni{jk-lk)-
Zfr+i = (A' — Z/, )/((ZA. + ji,- + Z/,-)(t7- + jk + h) mod 5 + 1)
13. i0 = 13, JO =-9. Zo =-4
Ц-+1 = {{h+jlj mod 30)/(|Z,| mod 5 + 1) + ((»A. + Z/,) mod 30)/(|jA-| mod -5 + 1),
jk+i = iriax(Ai'/,. (A; + 1)7'/,) mod fip - \jk - ZA|/10.
A* I i = 1.71- — jEI/10 + miu((tA. + Ik) mod 20. jkk mod 20) — 10
Г4. io = 6. jo = 27. Zo = —15
*J+i = (»д. — J)’ + //’ — A) mod 20.
7^+1 = nnn(ikjkjk —	— k.jklf. — k) mod 30.
Z,fr+1 = in$x(ikjkj* ~ k,ij.lk ~ hiikll ~ k) mod 30
15.	£() = 7.7o = -4.Zo = -10
ik-fi = fnto(47<* mod 25. niin(47£# mod 30. 47Z/,- mod 30)) — к mod 15.
7/, I i = niin(inax(47?A mod 2-5, U/i mod 2-5). 471/,• mod 30) + A' mod 5,
Z./,.+i = ‘17ikjklk mod 25 + A' mod 5
IV. Полоса, ограниченная прямыми i+j + 10 = 0 и i+j + 20 = 0
16.	Zo = —30.7'0 = —4. Zo = 12
Z*.+i = \ik — fc| + 11li11( //,. mod 10. Z/,A mod 10) — 20.
77+1 = max(A — ik, 111111(77,. max(tA — h-, jk — hj)) mod 30.
Z.A-+1 = ]‘j. mod 20 — шах(ц../I-) mod (A + 1)
17.	Z() = 13,70 = 19;Z0 = 14
+ i) ll^i - -Z/,-1 - |й - /а-11 •
7T-+1 = jk mod 20 + iriaxp/,- mod 20.111111(77 — k,h ~ к)) ~ 10,
/+1 1 = k(tk + l)(j/,- + 2) (Z/, + 3) mod 20
18.	Zo = 12,70 = 4. Zo = 3
Ч.-+1 = ('*’aJa/(|/a- | + 1) + 71Z/?/(l'l'l + 1) +fc.-W(l.7A'l + 1)) mod 30.
Ja- 1 1 = ik max(j7-. Ik) mod 20 + ji, iiiiii(ZA. hj mod 30 — A,
Z./-+1 = тах(гл.^. ikh-jkhj mod 30 + 20
19.	Zo =-22.70 = 14.Z0 =-14
//,•+1 = (7- min(77,-. Ik) + jk 111111(4*-. Z>) + к2) mod 20.
,/fr+i = (’7- mod 10 — A:)(j'*. mod 10 + Aj)(Z/,- mod 10 — к) mod 26.
lk+i = niax(niiii(i> + jk,'iir +>fc ) mod 2-5, niaigH + h-,jk + A') mod 20) + 10
20.	Zo = —25.7'0 = —9. Zo = —8
Za-> = (|Za- - j7|fei - |7>- - Z*.IZ*. + \ik - h \jk) mod 20 - A',
jk+i — iiiin(ZA-.fffx ) inax(77-. Ik) inni(ika.lk) mod 25 + 5sigii“Z/f + A.
!-k+i = |/a-I fen(Zi' - jk) ~ IZ*.I sigii(jA. - Ik) + |ja-I sigii(ZA- - к)
V. Треугольник с вершинами в точках (—10.0), (0.10), (—10.20)
21
Zo — —I2. 70 — —22. Zo — 11
i,k+i = max(niin(Z/. — jk-jk — hj mod 20. niin(ZA. — h-jk — A') mod 20) + 10.
7>+i = sign(tA — 77.) niin(Zfr jflod 20. jk mod 20) — niax(|Z> — Z/,-|. |A — 20|) mod 20 + 20,
к+L = (h mod 10)(7/, mod 10) + Z/,- mod 10
2
Лабораторная работа
8 (}>ai\yjit>Tj^r, 1 курс, 1 реместр, 2()11 12 учебный г&д
22.	io — 8. jo — 15. Jo — 10
ih+i = ((jk +ljk) mod (| niin(j/,• “ ii-- //,• “ A)| + 1) - A;) mod 20 + 10.
%+i = max((iA. + ji,)/(2 + si^n(j7,.Z/,. - i/Д')). (.'//.. + Z/,.)/(2 + sigii(-ifrj'fr - Z/Л))) - 10.
//,•+1 = 1ВДх(*/£ j/, ) ini1. Za) mod 30
23.	to = 29. jo = —6. Zo = 1
t/,,+i = iiiin(niax(iiiin(/5- — jk,ik — lk)-jk — Ik)- h — ti) mod 30.
,7/. । i = max(iiiin(nitLx(Z/. — j/,.. ik — lk)-jk — h-)- h- — A.) mod 30.
Z/,+i = tfr mod 30 — j/г mod 3ll +j/,. mod 30 — A' mod 30
24.	to = 20. jo = 0. Zo = 11
U+I = ((ч - A') max{jk-lk) + (./a- “ k) min(t/,.. Z/,.) + (Z/,. - А'.) тйх(-Ц ja-)) mod 23.
j7,+1 = -(« - A) min(j7,.. Z/f) + (j/,. - A) пдифц-. Za) + (Ik ~ A) 111111(1/..^)) mod 27.
lk+i = \i-k + jk ~ Ik ~ A'| sign(tA. - j/,. + Z/,. - A)
25.	to = —8. jo = —5. Zo = 12
t/,-+i = (Zj./(Ija — g| + A' + 1) — jk/(\ik — h \ + At+1)) mod 30.
%+i = sfciiZ/,- min(nj j't ) - signj/, niax(iA.. lk) + A,
A/,+i = (i'k — jk)(jk — h-)(h- — h) mod 20
VI. Эллипс с центром в точке (20.0) и проходящий через точки (10. О), (30. О), (20. 5) и (20. —5)
26.	io — —10. jo — —10. Zo — 6 t*+i = | max(min(i/. + j/,., z> + Za) mod 30, inax(t/. + lk,jk +i) mod 25)|. jk+i = |Zfr + A'| mod 10 + |jt + A | mod 10 + |Za- + A' mod 10. 4*+i = (*£.+ j/J + if. — Aj) mod 35
27.	io = —24. jo = 4. Zo = —3 *11 1 = |(tfr + Al® + 2A;)(Z/. + 3A)| mod 35, jk+i = si"ninax(t^‘jA) min((fc + ly) mod 20. (jY + h-) mod 20). i+1 = »+/3 - |t/,- - A'l sign(Z/. - jr)
28.	io = —29. jo = 3, Zo = 9 ik+i = Ik max(j/,.. Z/, ) mod 20 +7/,- niiii(iT- Ik) mod 30 + A, j/r+i = |*+ — ji, + Ik — A;| sign! A' — 10) mod 20. A/r+i = (|ifr — jk\lk ~ \jk ~ lk\i-k + |’+ — lk\jk) ifiod 20 — A'
29.	io = -7.jo = -19.Zo = 4 t/«+i = max(i/,.j/,.. iidk- Jkl-k) mod 30 + A'. jk+i = \jk - //-I sign «а- - |Ф - ZA.| sigiij/,.. Z/,+1 = 111111(4.. max(.7/r. miii(Z/,.. inax(4. - Z/,.,5/, - J*.))))
30.	io = — 1-Jo = 2. Zo = —1 i/,+i = | sign((A. - jk)lk - sign(j7,. - lk)ik + sign(tfr - l$jk - A:| mod 35, .Д+1 = i/,- niax(jA., Z/,.) mod 30 + j/,- inin(i/. . h,.) mod 20 — A, lk+i = (Ч + li)(jk ~ A;)(Z/,. + A-) mod 25
Примечания
1. Следу»!» различать операции деления ио модулю и нахождения остана. Деление*ио модулю обычно
обозначают modulo, а остаток от деления — I'&trtcwuler. при этом re'iwi‘iulor(u. b) = а — [я/Zi] х b и
modulofa. b) = а — [а/1>\ х 1>. т.е. отличие 1ак.тюча( тся в ойеряции целочисленного деления, .которая
может быть определена iEk [я/ZiJ. ГДС L®J = floor(.r) (пол) —наибольшее целое, меньшее или равное
д) или как [а//?]. где [.г] = Z/'u//c(;r) — целая часть д. В Питоне оператор % находит inodulo (т. к.
целочисленное деление определено через floor), а в Си — remaindi г. В Scheme и Common Lisp-e
(диалекту Лиспа) евгь оба оператора» Например, в Scheme (modulo — 2 3) вернет 1. a (remainder —
2 3)-----2. Cai. и. 3.4 киши В. Грэхема,К цуга и О. Паташника «Конщютная матемадика». Кстати,
в MS Excel целое удаление оиреде. к по через отброс дробиОй части.
С другой стороны, при программировании иа Паскале, ес ш Ж! itlin j отрицательны, формула
делимое = частное х делитель + остаток м&жвт дать неожиданные результаты: 5 mod 3 = 2. 5 mod
3
Забораторная работа .УД
8 (}>ai\yj№>Tj^r, 1 курс, 1 реместр, 2Q11,12 учебный гвд
—3 = —1. —5 mod 3 = 1 и —5 mod —3 = —2t «согласно стандарту1 я*ьп<аПаскаль ISO 718’5, возникают
ошибка — отказ от выполнения операции целочисленного деления, тадой же. как при делении на
дуДгь.
2. Стандарт языка. С ISO 1ЕС 9899:1999 четко определяет поведение при дедедии цддых чисел:
When integers are divided, the result of the / operator is the algebraic quotient with any
fractional part discarded. If the quotient a/b is represent<jble. the expression (a/b)*b + a'Zb
shall equal a.
Стандарт языка, CH—г ISO IEC 14882:2003 следуют» стандарту С в вопросах выполнения деления
целых чисел.
При оосггадлепии программы необходим^ обосновать выбранный для реализации тин оператора
рассмотрела. инварианты цш^а, пред- и постусловия и имупи Средства доказательства его з^зершимости
и кИррей^ности (теоретические' аиайив урдвиещш движения, метод математической ийдукции ио числу
повторений цик. ±а и др. и практические: вычерчиваииетраектории на кднтчадой [J'Mare иДи визуализация
с применением ЭВМ).
Дополнительные задания
1.	Вывести траекторию движения в выходной текстовый файл для визуализации gnuplot.
2.	Решить олимпиадную задачу «Бильярд» (проф. Титов В. К.. 1983 г.):
'Бильярд представтяет собой кл< точный прямоугольник in х п. В клетке с координатами (i.J) иа-
Лдигся шар. В переменной к задано значение. определяющее направление ио диагонали, в кото-
ром начинает двигаться ш;н|. Направление кодируются следующим образом: 1 — вправо-вверх, 2 —
вправо-вниз, 3 — влево-вниз, 4 — влево-вверх. Шар движется по диагонали до стенки бильярда и от-
ражается от нее. продолжая движение по перпендикулярному диагональному нащййзяениЮ. Движе-
ние 11i;S|)а заканчиваются выходом ив бильярда^ если он попадает в одну из его луз (угловых клеток).
Треютётся по заданным m.n.i.j.k определить, выйдет ди ш^р ва край бильярда, и если выйдет.
тсЕюрез какой угол и за скоп ко ударйв о стенку бильяцда. Если шар не выйдют за пределы би-
льярда, надо проследить его ;движе»ц£ до попадания в иачальиуф точку с начальны»! направление»!
движения и подсчитать число ударов в одном щжрй-з^)авюторш1.
Составленная программа должна обрабатыва гь тесты вплоть до конца файла.
Исходные данные: Й каышой строке входного файл;^ задается отдельный тест: 5 целых чисел, раз-
деленных пробелами: четыре двузначных чиблй и одно однозначное. Исходные данные корректны
in. п 2. 1 < i < in. 1 С ./ С п- 1 С к С 4. Результат-для каждого теста должен содержать число
ударов о Стенку и названий угла,. *яи шар попадает в лунку.
3.	Прочитать книгу Г.-Г. Кориолиса «Математитж:кая теория явлений бильярдной игры». IS1IN 5-
88988-030-6. Первое издание на русском языке —М.: ГИТТЛ, 1956.
4.	Ознакомиться с современными достижениями математической бил ш 'рдистики (ио изданиям РАН).
5.	Оттестировать программу в системе аигоматичбекого тестирования test9 J . строго соблюдая Задан-
ный формат ввода и вывода..
Для выполнения задания также весьма нулезиа книга 1'. Уоррена-мл. Алгоритмические «трюки ддя
программистов. —М.: Вильямс, 2004.
ЗнОагие чп"Шошони./и: проф. Зпцщ. 13. Е., проф). Тинюа 11. К., ()оц. Сопгппкоа Д. В , ст. преп. Каличчип
А. Л., Лебедев А. В. v Перетяг ин И. А.
4