ЕГЭ по информатике: задачи и решения

УДК 372.8
ББК Ч 426.29я73

Печатается по решению ученого совета Забайкальского Государственного Гуманитарно-Педагогического Университета им. Н.Г. Чернышевского



Ответственный за выпуск:



Рецензенты: С.А.Макаров к. ф.-м. н., директор ООО «ЧИТАИНФОРМ»;
В.Б.Венславский к.ф.-м. н., доцент кафедры ИТиМОИ ЗабГГПУ














Содержание

13 TOC \f \h \z 1413 LINK \l "_Toc285536372" 14Решение задач группы А,В 13 PAGEREF _Toc285536372 \h 1461515
13 LINK \l "_Toc285536373" 14Решение логических задач 13 PAGEREF _Toc285536373 \h 1461515
13 LINK \l "_Toc285536374" 14Решение логических задач средствами алгебры логики 13 PAGEREF _Toc285536374 \h 1461515
13 LINK \l "_Toc285536375" 14Решение логических задач табличным способом 13 PAGEREF _Toc285536375 \h 1481515
13 LINK \l "_Toc285536376" 14Решение логических задач с помощью рассуждений 13 PAGEREF _Toc285536376 \h 14111515
13 LINK \l "_Toc285536377" 14Контрольные задания 13 PAGEREF _Toc285536377 \h 14141515
13 LINK \l "_Toc285536378" 14Двоичное кодирование информации 13 PAGEREF _Toc285536378 \h 14151515
13 LINK \l "_Toc285536379" 14Алфавитный подход к определению количества информации 13 PAGEREF _Toc285536379 \h 14161515
13 LINK \l "_Toc285536380" 14Формула Шеннона 13 PAGEREF _Toc285536380 \h 14161515
13 LINK \l "_Toc285536381" 14Контрольные задания 13 PAGEREF _Toc285536381 \h 14191515
13 LINK \l "_Toc285536382" 14Представление и кодирование информации 13 PAGEREF _Toc285536382 \h 14201515
13 LINK \l "_Toc285536383" 14Двоичное кодирование информации в компьютере 13 PAGEREF _Toc285536383 \h 14201515
13 LINK \l "_Toc285536384" 14Представление числовой информации с помощью систем счисления 13 PAGEREF _Toc285536384 \h 14211515
13 LINK \l "_Toc285536385" 14Арифметические операции в позиционных системах счисления 13 PAGEREF _Toc285536385 \h 14241515
13 LINK \l "_Toc285536386" 14Контрольные задания 13 PAGEREF _Toc285536386 \h 14301515
13 LINK \l "_Toc285536387" 14Двоичное кодирование текстовой информации 13 PAGEREF _Toc285536387 \h 14341515
13 LINK \l "_Toc285536388" 14Кодировка символов 13 PAGEREF _Toc285536388 \h 14341515
13 LINK \l "_Toc285536389" 14Контрольные задания 13 PAGEREF _Toc285536389 \h 14351515
13 LINK \l "_Toc285536390" 14Двоичное кодирование графической информации 13 PAGEREF _Toc285536390 \h 14361515
13 LINK \l "_Toc285536391" 14Формирование растрового изображения 13 PAGEREF _Toc285536391 \h 14371515
13 LINK \l "_Toc285536392" 14Установка графического режима 13 PAGEREF _Toc285536392 \h 14381515
13 LINK \l "_Toc285536393" 14Контрольные задания. 13 PAGEREF _Toc285536393 \h 14391515
13 LINK \l "_Toc285536394" 14Решение задач группы С 13 PAGEREF _Toc285536394 \h 14401515
13 LINK \l "_Toc285536395" 14Программирование на языке Pascal 13 PAGEREF _Toc285536395 \h 14401515
13 LINK \l "_Toc285536396" 14Условный оператор 13 PAGEREF _Toc285536396 \h 14401515
13 LINK \l "_Toc285536397" 14Тренировочные упражнения 13 PAGEREF _Toc285536397 \h 14501515
13 LINK \l "_Toc285536398" 14Контрольные задания 13 PAGEREF _Toc285536398 \h 14521515
13 LINK \l "_Toc285536399" 14Оператор выбора (case) 13 PAGEREF _Toc285536399 \h 14521515
13 LINK \l "_Toc285536400" 14Примеры решения задач с использованием оператора выбора 13 PAGEREF _Toc285536400 \h 14531515
13 LINK \l "_Toc285536401" 14Контрольные задания 13 PAGEREF _Toc285536401 \h 14541515
13 LINK \l "_Toc285536402" 14Работа с массивами 13 PAGEREF _Toc285536402 \h 14561515
13 LINK \l "_Toc285536403" 14Двумерные массивы Паскаля – матрицы 13 PAGEREF _Toc285536403 \h 14661515
13 LINK \l "_Toc285536404" 14Описание двумерного массива Паскаля 13 PAGEREF _Toc285536404 \h 14671515
13 LINK \l "_Toc285536405" 14Ввод двумерного массива Паскаля 13 PAGEREF _Toc285536405 \h 14671515
13 LINK \l "_Toc285536406" 14Вывод двумерного массива Паскаля на экран 13 PAGEREF _Toc285536406 \h 14681515
13 LINK \l "_Toc285536407" 14Основные свойства квадратных матриц 13 PAGEREF _Toc285536407 \h 14681515
13 LINK \l "_Toc285536408" 14Примеры решения задач с двумерными массивами Паскаля 13 PAGEREF _Toc285536408 \h 14691515
13 LINK \l "_Toc285536409" 14Тренировочные упражнения 13 PAGEREF _Toc285536409 \h 14731515
13 LINK \l "_Toc285536410" 14Контрольные задания 13 PAGEREF _Toc285536410 \h 14771515
13 LINK \l "_Toc285536411" 14Работа со строками 13 PAGEREF _Toc285536411 \h 14821515
13 LINK \l "_Toc285536412" 14Процедуры и функции для работы со строками 13 PAGEREF _Toc285536412 \h 14831515
13 LINK \l "_Toc285536413" 14Записи в языке Паскаль 13 PAGEREF _Toc285536413 \h 14891515
13 LINK \l "_Toc285536414" 14Классификация типов данных в Паскале. 13 PAGEREF _Toc285536414 \h 14891515
13 LINK \l "_Toc285536415" 14Определение записи. Вариантная часть. 13 PAGEREF _Toc285536415 \h 14891515
13 LINK \l "_Toc285536416" 14Массив записей. Оператор присоединения. 13 PAGEREF _Toc285536416 \h 14911515
13 LINK \l "_Toc285536417" 14Дерево игры. Поиск выигрышной стратегии 13 PAGEREF _Toc285536417 \h 14951515
13 LINK \l "_Toc285536418" 14Пример задания 13 PAGEREF _Toc285536418 \h 14961515
13 LINK \l "_Toc285536419" 14Полное дерево игры, «поиск в ширину» 13 PAGEREF _Toc285536419 \h 14971515
13 LINK \l "_Toc285536420" 14Неполное дерево игры, «поиск в глубину» 13 PAGEREF _Toc285536420 \h 141011515
13 LINK \l "_Toc285536421" 14Графический способ 13 PAGEREF _Toc285536421 \h 141041515
13 LINK \l "_Toc285536422" 14Контрольные задания 13 PAGEREF _Toc285536422 \h 141201515
15 Введение
Издание окажет помощь старшеклассникам при подготовке к ЕГЭ по информатике. Книга поможет быстро и эффективно повторить и обобщить учебный материал. В пособие включен теоретический материал по основным темам ЕГЭ. Вопросы, задания и упражнения помогут закрепить знания.
Представленное пособие «ЕГЭ по информатике: задачи и решения», содержит основные тематические разделы единого государственного экзамена по информатике. Учебное пособие состоит из двух частей: Решение задач группы А, В; Решение задач группы С. Каждая часть представлена несколькими главами основных тематических разделов школьного курса информатики, в конце которых предлагается закрепить материал решением контрольных (тестовых) упражнений.
Материал изложен в доступной форме и может быть использован непосредственно учащимся, без дополнительной помощи педагога, что облегчает процесс подготовки к единому государственному экзамену.
Материалы данного учебного пособия могут быть использованы учителями-практиками при подготовке уроков по темам рассмотренных в пособии, обобщающих уроков или при контроле уровня усвоения знаний.
Издание подготовлено в соответствии с современными требованиями школьной программы среднего (полного) общего образования.

Глава I

Решение задач группы А,В13 TC "Решение задач группы А,В" \f C \l "1" 15

Решение логических задач
13 TC "Решение логических задач" \f C \l "2" 15
Разнообразие логических задач очень велико. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа решения логических задач:
средствами алгебры логики;

табличный;

с помощью рассуждений.

Познакомимся с ними поочередно.

I. Решение логических задач средствами алгебры логики13 TC "Решение логических задач средствами алгебры логики" \f C \l "3" 15
Обычно используется следующая схема решения:
изучается условие задачи;
вводится система обозначений для логических высказываний;
конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
определяются значения истинности этой логической формулы;
из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.
Вот увидишь, Шумахер не придет первым, сказал Джон. Первым будет Хилл.
Да нет же, победителем будет, как всегда, Шумахер, воскликнул Ник. А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?
Решение. Введем обозначения для логических высказываний:
Ш победит Шумахер; Х победит Хилл; А победит Алези.
Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей:
[ Cкачайте файл, чтобы посмотреть картинку ]
Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем и упростим истинное высказывание
[ Cкачайте файл, чтобы посмотреть картинку ]
Высказывание [ Cкачайте файл, чтобы посмотреть картинку ]истинно только при Ш=1, А=0, Х=0.
Ответ. Победителем этапа гонок стал Шумахер.

Пример 2. Некий любитель приключений отправился в кругосветное путешествие на яхте, оснащённой бортовым компьютером. Его предупредили, что чаще всего выходят из строя три узла компьютера a, b, c, и дали необходимые детали для замены. Выяснить, какой именно узел надо заменить, он может по сигнальным лампочкам на контрольной панели. Лампочек тоже ровно три: x, y и z.
Инструкция по выявлению неисправных узлов такова:
если неисправен хотя бы один из узлов компьютера, то горит по крайней мере одна из лампочек x, y, z;
если неисправен узел a, но исправен узел с, то загорается лампочка y;
если неисправен узел с, но исправен узел b, загорается лампочка y, но не загорается лампочка x;
если неисправен узел b, но исправен узел c, то загораются лампочки x и y или не загорается лампочка x;
если горит лампочка х и при этом либо неисправен узел а, либо все три узла a, b, c исправны, то горит и лампочка y.
В пути компьютер сломался. На контрольной панели загорелась лампочка x. Тщательно изучив инструкцию, путешественник починил компьютер. Но с этого момента и до конца плавания его не оставляла тревога. Он понял, что инструкция несовершенна, и есть случаи, когда она ему не поможет.
Какие узлы заменил путешественник? Какие изъяны он обнаружил в инструкции?
Решение. Введем обозначения для логических высказываний:
a  неисправен узел а;   x  горит лампочка х;
b  неисправен узел b;   y  горит лампочка y;
с  неисправен узел с;   z  горит лампочка z.
Правила 1–5 выражаются следующими формулами:
[ Cкачайте файл, чтобы посмотреть картинку ]
Формулы 1–5 истинны по условию, следовательно, их конъюнкция тоже истинна:
[ Cкачайте файл, чтобы посмотреть картинку ]
Выражая импликацию через дизъюнкцию и отрицание (напомним, что [ Cкачайте файл, чтобы посмотреть картинку ]), получаем:
[ Cкачайте файл, чтобы посмотреть картинку ]
Подставляя в это тождество конкретные значения истинности x=1, y=0, z=0, получаем:
[ Cкачайте файл, чтобы посмотреть картинку ]
Отсюда следует, что a=0, b=1, c=1.
Ответ на первый вопрос задачи: нужно заменить блоки b и c; блок а не требует замены. Ответ на второй вопрос задачи получите самостоятельно.

II. Решение логических задач табличным способом13 TC "Решение логических задач табличным способом" \f C \l "3" 15
При использовании этого способа условия, которые содержит задача, и результаты рассуждений фиксируются с помощью специально составленных таблиц.

Пример 3. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе.
Известно, что:
Смит самый высокий;
играющий на скрипке меньше ростом играющего на флейте;
играющие на скрипке и флейте и Браун любят пиццу;
когда между альтистом и трубачом возникает ссора, Смит мирит их;
Браун не умеет играть ни на трубе, ни на гобое.
На каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами?

Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.
Так как музыкантов трoе, инструментов шесть и каждый владеет только двумя инструментами, получается, что каждый музыкант играет на инструментах, которыми остальные не владеют.
Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:
 
скрипка
флейта
альт
кларнет
гобой
труба

Браун
0
0
1
1
0
0

Смит
 
 
0
0
 
0

Вессон
 
 
0
0
 
 

Из таблицы видно, что на трубе может играть только Вессон.
Из условий 1 и 2 следует, что Смит не скрипач. Так как на скрипке не играет ни Браун, ни Смит, то скрипачом является Вессон. Оба инструмента, на которых играет Вессон, теперь определены, поэтому остальные клетки строки "Вессон" можно заполнить нулями:
 
скрипка
флейта
альт
кларнет
гобой
труба

Браун
0
0
1
1
0
0

Смит
0
 
0
0
 
0

Вессон
1
0
0
0
0
1

Из таблицы видно, что играть на флейте и на гобое может только Смит.
 
скрипка
флейта
альт
кларнет
гобой
труба

Браун
0
0
1
1
0
0

Смит
0
1
0
0
1
0

Вессон
1
0
0
0
0
1

Ответ: Браун играет на альте и кларнете, Смит на флейте и гобое, Вессон на скрипке и трубе.

Пример 4. Три одноклассника Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего регби.
Юра сказал, что на туризм ему не хватает времени, хотя его сестра единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги.
Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.
Определите, кто чем любит заниматься в свободное время и у кого какая профессия.
Решение. Здесь исходные данные разбиваются на тройки (имя профессия увлечение).
Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист.
Имя
Юра
 
 

Профессия
 
врач
 

Увлечение
 
туризм
 

Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем:
Имя
Юра
Тимур
Влад

Профессия
физик
врач
юрист

Увлечение
бег
туризм
регби

Ответ. Влад юрист и регбист, Тимур врач и турист, Юра физик и бегун.

Пример 5. Три дочери писательницы Дорис Кей Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго.
Известно, что:
Джуди живет не в Париже, а Линда не в Риме;
парижанка не снимается в кино;
та, кто живет в Риме, певица;
Линда равнодушна к балету.
Где живет Айрис, и какова ее профессия?
Решение. Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание:
Париж
Рим
Чикаго
 
Пение
Балет
Кино

0
 
 
Джуди
 
 
 

 
 
 
Айрис
 
 
 

 
0
 
Линда
 
0
 

Далее рассуждаем следующим образом. Так как Линда живет не в Риме, то, согласно условию 3, она не певица. В клетку, соответствующую строке "Линда" и столбцу "Пение", ставим 0.
Из таблицы сразу видно, что Линда киноактриса, а Джуди и Айрис не снимаются в кино.
Париж
Рим
Чикаго
 
Пение
Балет
Кино

0
 
 
Джуди
 
 
0

 
 
 
Айрис
 
 
0

 
0
 
Линда
0
0
1

Согласно условию 2, парижанка не снимается в кино, следовательно, Линда живет не в Париже. Но она живет и не в Риме. Следовательно, Линда живет в Чикаго. Так как Линда и Джуди живут не в Париже, там живет Айрис. Джуди живет в Риме и, согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина.
В результате постепенного заполнения получаем следующую таблицу:
Париж
Рим
Чикаго
 
Пение
Балет
Кино

0
0
1
Джуди
1
0
0

1
0
0
Айрис
0
1
0

0
0
1
Линда
0
0
1

Ответ. Айрис балерина. Она живет в Париже.

III. Решение логических задач с помощью рассуждений13 TC "Решение логических задач с помощью рассуждений" \f C \l "3" 15
Этим способом обычно решают несложные логические задачи.

Пример 6. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей?
Решение. Имеется три утверждения:
Вадим изучает китайский;
Сергей не изучает китайский;
Михаил не изучает арабский.
Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.
Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.
Остается считать верным третье утверждение, а первое и второе ложными. Следовательно, Вадим не изучает китайский, китайский изучает Сергей.
Ответ: Сергей изучает китайский язык, Михаил японский, Вадим арабский.

Пример 7. В поездке пятеро друзей Антон, Борис, Вадим, Дима и Гриша, знакомились с попутчицей. Они предложили ей отгадать их фамилии, причём каждый из них высказал одно истинное и одно ложное утверждение:
Дима сказал: "Моя фамилия Мишин, а фамилия Бориса Хохлов". Антон сказал: "Мишин это моя фамилия, а фамилия Вадима Белкин". Борис сказал: "Фамилия Вадима Тихонов, а моя фамилия Мишин". Вадим сказал: "Моя фамилия Белкин, а фамилия Гриши Чехов". Гриша сказал: "Да, моя фамилия Чехов, а фамилия Антона Тихонов".
Какую фамилию носит каждый из друзей?
Решение. Обозначим высказывательную форму "юноша по имени А носит фамилию Б" как АБ, где буквы А и Б соответствуют начальным буквам имени и фамилии.
Зафиксируем высказывания каждого из друзей:
ДМ   и   БХ;
АМ   и   ВБ;
ВТ   и   БМ;
ВБ   и   ГЧ;
ГЧ   и   АТ.
Допустим сначала, что истинно ДМ. Но, если истинно ДМ, то у Антона и у Бориса должны быть другие фамилии, значит АМ и БМ ложно. Но если АМ и БМ ложны, то должны быть истинны ВБ и ВТ, но ВБ и ВТ одновременно истинными быть не могут.
Значит остается другой случай: истинно БХ. Этот случай приводит к цепочке умозаключений:   БХ истинно [ Cкачайте файл, чтобы посмотреть картинку ]БМ ложно [ Cкачайте файл, чтобы посмотреть картинку ]ВТ истинно [ Cкачайте файл, чтобы посмотреть картинку ]АТ ложно [ Cкачайте файл, чтобы посмотреть картинку ]ГЧ истинно [ Cкачайте файл, чтобы посмотреть картинку ]ВБ ложно [ Cкачайте файл, чтобы посмотреть картинку ]АМ истинно.
Ответ: Борис Хохлов, Вадим Тихонов, Гриша Чехов, Антон Мишин, Дима Белкин.

Пример 8.Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы:
Россия "Проект не наш, проект не США"; США "Проект не России, проект Китая"; Китай "Проект не наш, проект России".
Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз неправду.
Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.
Решение. Для удобства записи пронумеруем высказывания дипломатов:
Россия "Проект не наш"   (1),   "Проект не США"   (2); США   "Проект не России"   (3),   "Проект Китая"   (4); Китай   "Проект не наш"   (5),   "Проект России"   (6).
Узнаем, кто из министров самый откровенный.
Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.
Если самый откровенный министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.
Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.
Ответ: Откровеннее был китайский министр, осторожнее российский, скрытнее министр США. 

Контрольные задания13 TC "Контрольные задания" \f C \l "2" 15.
№ 1
Четыре ученицы: Мария, Нина, Ольга, Поля участвовали в соревновании и заняли первые 4 места. На вопрос, кто из них какое место занял, 3 девушки ответили: 1. Ольга была вторая, Поля - третья; 2. Ольга была первая, Нина - вторая; 3. Мария была вторая, Поля - четвертая.
В каждом из этих ответов одна часть верна, другая нет. Кто какие места занял в соревнования?
№ 2
При составлении расписания на понедельник в 9-а классе преподаватели высказали просьбы завучу: 1. Учитель математики: “Желаю иметь первый или второй урок” 2. Учитель истории: “Желаю иметь первый или третий урок” 3. Учитель литературы: “Желаю иметь второй или третий урок”
Какое расписание будет составлено?
№ 3
Предстоят спортивные соревнования между четырьмя восьмыми классами одной школы. В учительской живо обсуждаются возможные результаты и высказываются прогнозы. 1). Первое место займет 8-А, а второе - 8-Б,- сказал учитель математики. 2). Да что вы! - сказал учитель географии. - Я недавно ходил с ними в поход и знаю их возможности. 8-А займет второе место, а 8-Г-только третье. 3). А я думаю, что на втором месте будет 8-В,- сказала завуч школы,- а 8-Г будет на последнем месте.
Оказалось, что прогнозы их сбылись только наполовину. Какое место занял каждый класс?
№ 4
Четыре марсианки, оказавшиеся на Земле в 2... году, на вопрос об их возрасте дали ответы: 1. МИ - 22 года, МЕ - 21 год 2. МО - 19 лет, МИ - 21 год 3. МА - 21 года, МО - 18 лет
Все марсианки - разных возрастов, притом только данных: 18, 19, 21 и 22. В каждом ответе одна часть верна, другая - нет. Сколько лет каждой?
Двоичное кодирование информации13 TC "Двоичное кодирование информации" \f C \l "2" 15
За единицу количества информации принимается такое количество информации, которое содержит сообщение, уменьшающее неопределенность в два раза . Такая единица названа "бит".
Если вернуться к опыту бросания монеты, то здесь неопределенность как раз уменьшается в два раза и, следователтно, полученное количество информации равно 1 биту.
Минимальной единицей измерения количества информации является бит, а следующей по величине единицей является байт, причем
1 байт = 8 бит = 23 бит
В информатике система образования кратных единиц измерения информации несколько отличается от принятых большинстве наук. Традиционные метрические системы единиц, например Международнаясистема единиц СИ, в качестве множителей кратких единиц используют коэффициент , где n = 3, 6, 9 и так далее, что соответствуетдесятичным приставкам и так далее.
Компьютер оперирует числами не в десятичной системе счисления, поэтому в кратных единицах единицах измерения количества информации используется коэффициент Так, кратные байту единицы измерения количества информации выводятся следующим образом:

Количество возможных событий и количесто информации. Существует формула, которая связывает между собой количество возможных событий N и количество информации I:

По этой формуле можно легко определить количество возможных событий, если известно количество информации. Например, если мы получили 4 бита информации, то количество возможных событий составляло:
Наоборот, для определения количества информации, если известно количество событий, необходимо решить показательное уравнение относительно I. Например, в игре "Крестики - нолики" на поле 8?8 перед первым ходом существует 64 возможных события (64 различных варианта расположения "крестика"), тогда уравнение принимает вид: Так как то получим: Таким образом, I = 6 битов, то есть количество информации, полученное вторым игроком после первого хода первого игрока, составляет 6 битов.

Алфавитный подход к определению количества информации13 TC "Алфавитный подход к определению количества информации" \f C \l "3" 15

При определении количества информации на основе уменьшения неопределенности наших знаний мы рассматриваем информацию с точки зрения содержания, ее понятности и новизны для человека. С этой точки зрения в опыте по бросанию монеты одинаковое количество информации содержится и в зрительном образе упавшей монеты, и в коротком сообщении "Орел", и длинной фразе "Монета упала на поверхность земли той стороной вверх, на которой изображен орел".
Однако при хранении и передаче информации с помощью технических устройств целесообразно отвлечься от содержания информации и рассматривать ее как последовательность знаков (букв, цифр, кодов цветов точек изображения и так далее).
Набор символов знаковой системы (алфавит) можно рассматривать как различные возможные состояния (события). Тогда, если считать, что появление символов в сообщении равновероятно по формуле можно рассчитать, какое количество информации несет каждый символ.

Так, в русском алфавите, если не использовать букву ё, количество событий (букв) будет равно 32. Тогда : 32=21 откуда I = 5 битов.
Каждый символ несет 5 битов информации (его информационная емкость равна 5 битов). Количество информации в сообщении можно подсчитать, умножив количество информации, которое несет один символ, на количество символов.

Количество информации, которое содержит сообщение, закодированное с помощью знаковой системы, равно количеству информации, которое несет один знак, умноженному на количество знаков.

Формула Шеннона13 TC "Формула Шеннона" \f C \l "3" 15

Существует множество ситуаций, когда возможные события имеют различные вероятности реализации. Например, если монета несимметрична (одна сторона тяжелее другой), то при ее бросании вероятности выпадения "орла" и "решки" будут различаться.
Формулу для вычисления количества информации в случае различных вероятностей событий предложил Клод Шеннон в 1948 году. В этом случае количество информации определяется по формуле:

где I - количество информации; N - количество возможных событий; pi - вероятность i-го события.
Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут равны:

p1 = 1/2, p2 = 1/4, p3 = 1/8, p4 = 1/8.

Тогда количество информации, которое мы получим после реализации одного из них, можно рассчитать по формуле:
I = -(1/2*log21/2 + 1/4*log21/4 + 1/8*log21/8 + 1/8*log21/8) =
= (1/2 + 2/4 + 3/8 + 3/8) битов = 14/8 битов = 1,75 бита

Этот подход к определению количества информации называется вероятностным.
Для частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (pi = 1/N), величину количества информации I можно рассматривать по формуле:



По этой формуле можно определить, например, количество информации, которое мы получим при бросании симметричной и однородной четырехгранной пирамидки:

I = log24 = 2 бита.

Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной (1,75 бита), когда события неравновероятны.

Количество информации, которое мы получаем, достигает максимального значения, если события равновероятны.
Выбор оптимальной стратегии в игре "Угадай число". На получении максимального количества информации строится выбор оптимальной стратегии в игре "Угадай число", в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16) а второй - должен "угадать" задуманное число. Если рассмотреть игру с информационной точки зрения, то начальная начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел).
При оптимальной стратегии интервал чисел всегда должен делиться пополам, тогда количество возможных событий (чисел) в каждом из полученных интервалов будет одинаково и отгадывание интервалов равновероятно. В этом случае на каждом шаге ответ первого игрока ("Да" или "Нет")будет нести максимальное количество информации (1 бит).

Вопрос второго участника
Ответ первого участника
Неопределенность знаний (количество возможных событий)
Полученное количество информации



16


Число больше 8?
Нет
8
1 бит

Число больше 4?
Нет
4
1 бит

Число больше 2?
Да
2
1 бит

Число 3?
Да
1
1 бит


Как видно из таблицы, угадывание числа 3 произошло за четыре шага, на каждом из которых неопределенность знаний второго участника уменьшалась в два раза за счет получения сообщения от первого участника, содержащего 1 бит информации. Таким образом, количество информации, необходимое для отгадывания одного из 16 чисел, составило 4 бита.

Контрольные задания13 TC "Контрольные задания" \f C \l "2" 15.
Какое количество информации получит второй игрок после первого хода первого игрока в игре "Крестики - нолики" на поле размером 4 * 4?
Каково было количество возможных событий, если после реализации одного из них мы получили количество информации, равное 3 битам? 7 битам?
Какое количество информации несет в себе сообщение о том, что нужная вам информация находится на одной из восьми дискет?
Какое количество информации получит второй игрок при игре в крестики-нолики на поле 8*8, после первого хода первого игрока, играющего крестиками?
В рулетке общее количество лунок равно 128. Какое количество информации мы получаем в зрительном сообщении об остановке шарика в одной из лунок?
Происходит выбор одной карты из колоды в 32 карты. Какое количество информации мы получаем в зрительном сообщении о выборе определенной карты?
Вероятность первого события составлет 0,5, а второго и третьего - 0,25. Какое количество информации мы получим после реализации одного из них?
Какое количество информации получит второй игрок в игре "Угадай число" при оптимальной стратегии, если первый игрок загадал число: от 1 до 64? от 1 до 128?
Какое количество вопросов достаточно задать вашему собеседнику, чтобы точно определить день и месяц его рождения?
Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика, если в непрозрачном мешочке хранится:
25 белых, 25 красных, 25 синих и 25 зеленых шариков;
30 белых, 30 красных, 30 синих и 10 зеленых шариков?
Вычислить количество информации, которое будет получено:
при бросании симметричного шестигранного кубика;
при игре в рулетку с 72 секторами;
при игре в шахматы игроком за черных после первого хода белых, если считать все ходы равновероятными;
при игре в шашки.

Представление и кодирование информации13 TC "Представление и кодирование информации" \f C \l "2" 15
Представление информации может осуществляться с помощью языков, которые являются знаковыми системами. Каждая знаковая система строится на основе определенного алфавита и правил выполнения операций над знаками.
В живых организмах информация предается и храниться с помощью объектов различной физической природы (состояние нейрона, нуклеотиды в молекуле ДНК), которые могут рассматриваться как знаки биологических алфавитов.
Кодирование - это операция преобразования знаков или групп знаков одной знаковой системы в знаки или группы знаков другой знаковой системы.

Двоичное кодирование информации в компьютере13 TC "Двоичное кодирование информации в компьютере" \f C \l "3" 15
В компьютере для представления информации используется двоичное кодирование, так как удалось создать надежно работающие технические устройства, которые могут со стопроцентной надежностью сохранять и распознавать не более двух различных состояний (цифр):
электромагнитное реле (замкнуто/разомкнуто), широко использовались в конструкциях первых ЭВМ;
участок поверхности магнитного носителя информации (намагничен/размагничен);
участок поверхности лазерного диска (отражает/не отражает);
триггер может устойчиво находиться в одном из двух состояний, широко используется в оперативной памяти компьютера.

Все виды информации в компьютере кодируется на машинном языке, в виде логических последовательностей нулей и единиц.

Информация в компьютере представлена в двоичном коде, алфавит которого состоит из двух цифр ( 0 и 1 ).
Цифры двоичного кода можно рассматривать как два равновероятных состояния (события). При записи двоичной цифры реализуется выбор одного из двух возможных состояний (одной из двух цифр) и, следовательно, она несет количество информации, равное 1 биту.
Даже сама единица измерения количества информации бит (bit) получила свое название от английского словосочетания BInary digiT (двоичная цифра).
Важно, что каждая цифра машинного двоичного кода несет информацию в 1 бит. Таким образом, две цифры несут информацию в 2 бита, три цифры - в 3 бита и так далее. Количество информации в битах равно количеству цифр двоичного машинного кода.
Каждая цифра машинного двоичного кода несет количество информации, равное одному биту.

Представление числовой информации с помощью систем счисления13 TC "Представление числовой информации с помощью систем счисления" \f C \l "3" 15
Система счисления это совокупность приемов и правил, по которым числа записываются и читаются.
Существуют позиционные и непозиционные системы счисления.

В непозиционных системах счисления вес цифры (т. е. тот вклад, который она вносит в значение числа) не зависит от ее позиции в записи числа. Так, в римской системе счисления в числе ХХХII (тридцать два) вес цифры Х в любой позиции равен просто десяти.

В позиционных системах счисления вес каждой цифры изменяется в зависимости от ее положения (позиции) в последовательности цифр, изображающих число. Например, в числе 757,7 первая семерка означает 7 сотен, вторая 7 единиц, а третья 7 десятых долей единицы.
Сама же запись числа 757,7 означает сокращенную запись выражения

757,7 =700 + 50 + 7 + 0,7 = 7 . 102 + 5 . 101 + 7 . 100 + 7 . 101 = 757,7.

Любая позиционная система счисления характеризуется своим основанием.  
За основание системы можно принять любое натуральное число два, три, четыре и т.д. Следовательно, возможно бесчисленное множество позиционных систем: двоичная, троичная, четверичная и т.д. Запись чисел в каждой из систем счисления с основанием  q  означает сокращенную запись выражения
an-1 qn-1 + an-2 qn-2 + ... + a1 q1 + a0 q0 + a-1 q-1 + ... + a-m q-m,
где  ai  цифры системы счисления;   n и m число целых и дробных разрядов, соответственно. Например:
[ Cкачайте файл, чтобы посмотреть картинку ]

Полезно запомнить запись в этих системах счисления первых двух десятков целых чисел:
10-я
2-я
8-я
16-я

0
0
0
0

1
1
1
1

2
10
2
2

3
11
3
3

4
100
4
4

5
101
5
5

6
110
6
6

7
111
7
7

8
1000
10
8

9
1001
11
9


10-я
2-я
8-я
16-я

10
1010
12
A

11
1011
13
B

12
1100
14
C

13
1101
15
D

14
1110
16
E

15
1111
17
F

16
10000
20
10

17
10001
21
11

18
10010
22
12

19
10011
23
13



Перевод восьмеричных и шестнадцатеричных чисел в двоичную систему очень прост: достаточно каждую цифру заменить эквивалентной ей двоичной триадой (тройкой цифр) или тетрадой (четверкой цифр).
[ Cкачайте файл, чтобы посмотреть картинку ]
Чтобы перевести число из двоичной системы в восьмеричную или шестнадцатеричную, его нужно разбить влево и вправо от запятой на  триады  (для восьмеричной) или  тетрады  (для шестнадцатеричной)  и каждую такую группу заменить соответствующей восьмеричной (шестнадцатеричной) цифрой.
[ Cкачайте файл, чтобы посмотреть картинку ]
Как перевести целое число из десятичной системы в любую другую позиционную систему счисления?
Пример:
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]


Пример. Переведем число 0,36 из десятичной системы в двоичную, восьмеричную и шестнадцатеричную:
[ Cкачайте файл, чтобы посмотреть картинку ]

[ Cкачайте файл, чтобы посмотреть картинку ]

Как перевести число из двоичной (восьмеричной, шестнадцатеричной) системы в десятичную?
Примеpы:
[ Cкачайте файл, чтобы посмотреть картинку ]  
Арифметические операции в позиционных системах счисления
13 TC "Арифметические операции в позиционных системах счисления" \f C \l "3" 15
Рассмотрим основные арифметические операции: сложение, вычитание, умножение и деление. Правила выполнения этих операций в десятичной системе хорошо известны это сложение, вычитание, умножение столбиком   и  деление углом. Эти правила применимы и ко всем другим позиционным системам счисления. Только таблицами сложения и умножения надо пользоваться особыми для каждой системы.

Сложение

Таблицы сложения легко составить, используя Правило Счета.


Сложение в двоичной системе
[ Cкачайте файл, чтобы посмотреть картинку ]
Сложение в восьмеричной системе
[ Cкачайте файл, чтобы посмотреть картинку ]

                 Сложение в шестнадцатеричной системе
[ Cкачайте файл, чтобы посмотреть картинку ] При сложении цифры суммируются по разрядам, и если при этом возникает избыток, то он переносится влево.  
Пример 1. Сложим числа 15 и 6 в различных системах счисления.
[ Cкачайте файл, чтобы посмотреть картинку ]       [ Cкачайте файл, чтобы посмотреть картинку ]
Шестнадцатеричная: F16+616
[ Cкачайте файл, чтобы посмотреть картинку ]
Ответ: 15+6 = 2110 = 101012 = 258 = 1516.  Проверка. Преобразуем полученные суммы к десятичному виду: 101012 = 24 + 22 + 20 = 16+4+1=21,  258 = 2 . 81 + 5 . 80 = 16 + 5 = 21,  1516 = 1 . 161 + 5 . 160 = 16+5 = 21. 

  Пример 2. Сложим числа 15, 7 и 3.
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
Шестнадцатеричная: F16+716+316
[ Cкачайте файл, чтобы посмотреть картинку ]
Ответ: 5+7+3 = 2510 = 110012 = 318 = 1916.  Проверка: 110012 = 24 + 23 + 20 = 16+8+1=25, 318 = 3 . 81 + 1 . 80 = 24 + 1 = 25,  1916 = 1 . 161 + 9 . 160 = 16+9 = 25. 

  Пример 3. Сложим числа 141,5 и 5
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Ответ: 141,5 + 59,75 = 201,2510 = 11001001,012 = 311,28 = C9,416 Проверка. Преобразуем полученные суммы к десятичному виду: 11001001,012 = 27 + 26 + 23 + 20 + 2-2 = 201,25 311,28 = 3 . 82 + 1 . 81 + 1 . 80 + 2 . 8-1 = 201,25 C9,416 = 12 . 161 + 9 . 160 + 4 . 16-1 = 201,25
Вычитание
Пример 4. Вычтем единицу из чисел 102, 108 и 1016       [ Cкачайте файл, чтобы посмотреть картинку ]       [ Cкачайте файл, чтобы посмотреть картинку ]     Пример 5. Вычтем единицу из чисел 1002, 1008 и 10016.       [ Cкачайте файл, чтобы посмотреть картинку ]       [ Cкачайте файл, чтобы посмотреть картинку ]     Пример 6. Вычтем число 59,75 из числа 201,25.
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]   Ответ: 201,2510 - 59,7510 = 141,510 = 10001101,12 = 215,48 = 8D,816. Проверка. Преобразуем полученные разности к десятичному виду: 10001101,12 = 27 + 23 + 22 + 20 + 2-1 = 141,5; 215,48 = 2 . 82 + 1 . 81 + 5 . 80 + 4 . 8-1 = 141,5; 8D,816 = 8 . 161 + D . 160 + 8 . 16-1 = 141,5.
Умножение
Выполняя умножение многозначных чисел в различных позиционных системах счисления, можно использовать обычный алгоритм перемножения чисел в столбик, но при этом результаты перемножения и сложения однозначных чисел необходимо заимствовать из соответствующих рассматриваемой системе таблиц умножения и сложения.
Умножение в двоичной системе
Умножение в восьмеричной системе

[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]

В виду чрезвычайной простоты таблицы умножения в двоичной системе, умножение сводится лишь к сдвигам множимого и сложениям.     Пример 7. Перемножим числа 5 и 6.
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ] Ответ: 5 . 6 = 3010 = 111102 = 368. Проверка. Преобразуем полученные произведения к десятичному виду: 111102 = 24 + 23 + 22 + 21 = 30; 368 = 3*81 + 6*80 = 30.     Пример 8. Перемножим числа 115 и 51.
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ] Ответ: 115 . 51 = 586510 = 10110111010012 = 133518. Проверка. Преобразуем полученные произведения к десятичному виду: 10110111010012 = 212 + 210 + 29 + 27 + 26 + 25 + 23 + 20 = 5865; 133518 = 1 . 84 + 3 . 83 + 3 . 82 + 5 . 81 + 1 . 80 = 5865.
Деление
Деление в любой позиционной системе счисления производится по тем же правилам, как и деление углом в десятичной системе. В двоичной системе деление выполняется особенно просто, ведь очередная цифра частного может быть только нулем или единицей.  
Пример 9. Разделим число 30 на число 6. [ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ] Ответ: 30 : 6 = 510 = 1012 = 58.     Пример 10. Разделим число 5865 на число 115.
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
Восьмеричная: 133518 :1638
[ Cкачайте файл, чтобы посмотреть картинку ] Ответ: 5865 : 115 = 5110 = 1100112 = 638. Проверка. Преобразуем полученные частные к десятичному виду: 1100112 = 25 + 24 + 21 + 20 = 51; 638 = 6 . 81 + 3 . 80 = 51.
Пример 11. Разделим число 35 на число 14.
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
Восьмеричная: 438 : 168
[ Cкачайте файл, чтобы посмотреть картинку ] Ответ: 35 : 14 = 2,510 = 10,12 = 2,48. Проверка. Преобразуем полученные частные к десятичному виду: 10,12 = 21 + 2 -1 = 2,5; 2,48 = 2 . 80 + 4 . 8-1 = 2,5.
Контрольные задания13 TC "Контрольные задания" \f C \l "2" 15
1. Используя Правило Счета, запишите первые 20 целых чисел в десятичной, двоичной, троичной, пятеричной и восьмеричной системах счисления. 2. Какие целые числа следуют за числами:  
а) 12;
е) 18;
п) F16; 

б) 1012;
ж) 78;
м) 1F16;

 в) 1112; 
з) 378;
н) FF16;

г) 11112;
и) 1778;
о) 9AF916; 

д) 1010112;
к) 77778;
п) CDEF16 ?

3. Какие целые числа предшествуют числам:
а) 102;
е) 108;
л) 1016;

б) 10102;
ж) 208;
 м)2016;

в) 10002;
з) 1008;
н) 10016;

г) 100002;
и) 1108;
о) A1016;

д) 101002;
к) 10008;
п) 100016 ?


4. Какой цифрой заканчивается четное двоичное число? Какой цифрой заканчивается нечетное двоичное число? Какими цифрами может заканчиваться четное троичное число?
5. Какое наибольшее десятичное число можно записать тремя цифрами:
а) в двоичной системе;
б) в восьмеричной системе;
в) в шестнадцатеричной системе?

6. В какой системе счисления 21 + 24 = 100? Способ решения: Пусть x искомое основание системы счисления. Тогда 100x = 1 · x2 + 0 · x1 + 0 · x0,    21x = 2 · x1 + 1 · x0,    24x = 2 · x1 + 4 · x0. Таким образом, x2 = 2x + 2x + 5 или x2 - 4x - 5 = 0. Положительным корнем этого квадратного уравнения является x = 5. Ответ. Числа записаны в пятеричной системе счисления.
В какой системе счисления справедливо следующее:
а) 20 + 25 = 100;
б) 22 + 44 = 110?

8. Десятичное число 59 эквивалентно числу 214 в некоторой другой системе счисления. Найдите основание этой системы.

9. Переведите числа в десятичную систему, а затем проверьте результаты, выполнив обратные переводы:  
а) 10110112;
е) 5178;
л) 1F16; 

б) 101101112;
ж) 10108; 
м) ABC16; 

в) 0111000012;
з) 12348;
н) 101016;

г) 0,10001102;
и) 0,348;
о) 0,А416;

д) 110100,112;
к) 123,418;
п) 1DE,C816.


10. Переведите числа из десятичной системы в двоичную, восьмеричную и шестнадцатеричную, а затем проверьте результаты, выполнив обратные переводы:
      а) 12510;      б) 22910;     в) 8810;      г) 37,2510;      д) 206,12510.

11. Переведите числа из двоичной системы в восьмеричную и шестнадцатеричную, а затем проверьте результаты, выполнив обратные переводы:  
а) 1001111110111,01112;
 г) 1011110011100,112;

б) 1110101011,10111012;
д) 10111,11111011112;

в) 10111001,1011001112;
е) 1100010101,110012.


12. Переведите в двоичную и восьмеричную системы шестнадцатеричные числа:
      а) 2СE16;     б) 9F4016;     в) ABCDE16;     г) 1010,10116;     д) ABC,9D16.
13. Выпишите целые числа:
а) от 1011012 до 1100002 в двоичной системе;
б) от 2023 до 10003 в троичной системе;
в) от 148 до 208 в восьмеричной системе;
г) от 2816 до 3016 в шестнадцатеричной системе.

14. Для десятичных чисел 47 и 79 выполните цепочку переводов из одной системы счисления в другую:
[ Cкачайте файл, чтобы посмотреть картинку ]
15. Составьте таблицы сложения однозначных чисел в троичной и пятеричной системах счисления.
16. Составьте таблицы умножения однозначных чисел в троичной и пятеричной системах счисления.
17. Сложите числа, а затем проверьте результаты, выполнив соответствующие десятичные сложения:  
а) 10111012 и 11101112;
д) 378 и 758;
и) A16 и F16;

б) 1011,1012 и 101,0112;
е) 1658 и 378;
к) 1916 и C16;

в) 10112, 112 и 111,12;
ж) 7,58 и 14,68;
л) A,B16 и E,F16;

г) 10112 , 11,12 и 1112;
з) 68, 178 и 78;
м) E16, 916 и F16.

18. В каких системах счисления выполнены следующие сложения? Найдите основания каждой системы:
[ Cкачайте файл, чтобы посмотреть картинку ]
19. Найдите те подстановки десятичных цифр вместо букв, которые делают правильными выписанные результаты (разные цифры замещаются разными буквами):
[ Cкачайте файл, чтобы посмотреть картинку ]                        [ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
20. Вычтите:
а) 1112 из 101002;
д) 158 из 208;
и) 1А16 из 3116;

б) 10,112 из 100,12;
е) 478 из 1028;
к) F9E16 из 2А3016;

в) 111,12 из 100102;
ж) 56,78 из 1018;
л) D,116 из B,9216;

г) 100012 из 1110,112;
з) 16,548 из 30,018;
м) ABC16 из 567816.


21. Перемножьте числа, а затем проверьте результаты, выполнив соответствующие десятичные умножения:  
а) 1011012 и 1012;
д) 378 и 48;

б) 1111012 и 11,012;
е) 168 и 78;

в) 1011,112 и 101,12;
ж) 7,58 и 1,68;

г) 1012 и 1111,0012;
з) 6,258 и 7,128.

22. Разделите 100101102 на 10102 и проверьте результат, умножая делитель на частное.
23. Разделите 100110101002 на 11002 и затем выполните соответствующее десятичное и восьмеричное деление.
24. Вычислите значения выражений:
а) 2568 + 10110,12 . (608 + 1210) - 1F16;
б) 1AD16 - 1001011002 : 10102 + 2178;
в) 101010 + (10616 - 110111012)
128;
г) 10112 . 11002 : 148 + (1000002 - 408).

25. Расположите следующие числа в порядке возрастания:
а) 748, 1100102, 7010, 3816;
б) 6E16, 1428, 11010012, 10010;
в) 7778, 1011111112, 2FF16, 50010;
г) 10010, 11000002, 6016, 1418.
Двоичное кодирование текстовой информации13 TC "Двоичное кодирование текстовой информации" \f C \l "2" 15
Традиционно для кодирования одного символа используется количество информации, равное 1 байту, то есть I = 1 байт = 8 битов.
Для кодирования одного символа требуется 1 байт информации.
Если рассматривать символы как возможные события, то можно вычислить, какое количество различных символов можно закодировать:

Такое количество символов вполне достаточно для представления текстовой информации, включая прописные и строчные буквы русского и латинского алфавита, цифры, знаки, графические символы и пр.
Кодирование заключается в том, что каждому символу ставится в соответствие уникальный десятичный код от 0 до 255 или соответствующий ему двоичный код от 00000000 до 11111111.
Важно, что присвоение символу конкретного кода - это вопрос соглашения, которое фиксируется в кодовой таблице. Во всем мире в качестве стандарта принята таблица ASCII (American Standard Code for Informational Interchange - Американский стандартный код информационного обмена).
Первые 33 кода (с 0 по 32) соответствуют не символам, а операциям (перевод строки, ввод пробела и так далее).
Коды с 33 по 127 являются интернациональными и соответствуют символам латинского алфавита, цифрам, знакам арифметических операций и знакам препинания.
Коды с 128 по 255 являются национальными, то есть в национальных кодировках одному и тому же коду соответствуют различные символы. К сожалению, в настоящее время существуют пять различных кодовых таблиц для русских букв (КОИ8, СР1251, СР866, Мас, ISO), поэтому тексты, созданные в одной кодировке, не будут правильно отображаться в другой.
В настоящее время широкое распространение получил новый международный стандарт Unicode, который отводит на каждый символ не один, а два, поэтому с его помощью можно закодировать не 256 символов, различных символов. Эту кодировку поддерживают последние версии платформы Microsoft Windows&Office (начиная с 1997 года).
Кодировка символов13 TC "Кодировка символов" \f C \l "3" 15.

Контрольные задания13 TC "Контрольные задания" \f C \l "2" 15
Закодируйте с помощью кодировочной таблицы ASCII следующие тексты:
а) Password; б) Windows; в) Norton Commander.
Декодируйте с помощью кодировочной таблицы ASCII следующие тексты, заданные шестнадцатеричным кодом:
а) 54_6F_72_6E_61_64_6F;
б) 49_20_6C_6F_76_65_20_79_6F_75;
в)32_2A_78_2B_79_3D_30.
Перейдите от двоичного кода к десятичному и декодируйте следующие тексты:
а) 01010101_ 01110000_00100000_00100110_00100000_01000100_01101111_01110111_01101110;
б) 01001001_01000010_01001101;
в) 01000101_01101110_01110100_01100101_01110010.
Декодируйте следующие тексты, заданные десятичнымкодом:
а) 087_111_114_100;
б) 068_079_083;
в) 080_097_105_110_116_098_114_117_115_104.
В текстовом режиме экран обычно разбивается на 25 строк по 80 символов в строке. Определите объем текстовой информации, занимающей весь экран монитора.
Первоначально информацию закодировали согласно 16-ти бит стандарт Unicode, а затем перекодировали с помощью кодовой 8-ми битовой таблицы КОИ8, при этом объем информации уменьшился на 512 бит. Какой первоначальный объем информации?

Двоичное кодирование графической информации13 TC "Двоичное кодирование графической информации" \f C \l "2" 15

Пространственная дискретизация. В процессе кодирования изображения производится его пространственная дискретизация. Пространственную дискретизацию изображения можно сравнивать с построением изображения из мозаики (большого количества маленьких разноцветных стекол). Изображение разбивается на отдельные маленькие фрагменты (точки), причем каждому фрагменту присваивается значение его цвета (красный, зеленый, синий и т.д.).

Качество кодирования изображения зависит от двух параметров. Во-первых, качество кодирования изображения тем выше, чем меньще размер точки и соответственно большее количество точек составляет изображение. Во-вторых, чем большее количество цветов, то есть большее количество возможных состояний точки изображения, используется, тем более качественно кодируется изображение (каждая точка несет большее количество информации). Совокупность используемых в наборе цветов образует палитру цветов.

Формирование растрового изображения. Графическая информация на экране монитора представляется в виде растрового изображения, которое формируется из определенного количества строк, которые в свою очередь содержат определенное количество точек (пикселей).
Качество изображения определяется разрешающей способностью монитора, т.е. количеством точек, из которых оно складывается. Чем больше разрешающая способность, то есть чем больше количество строк растра и точек в строке, тем выше качество изображения. В современных персональных компьютерах обычно используются три основные разрешающие способности экрана: 800 * 600,1024 * 768 и 1280 * 1024 точки.
Рассмотрим формирование на экране монитора растрового изображения, состоящего из 600 строк по 800 точек в каждой строке (всего 480 000 точек). В простейшем случае (черно-белое изображение без градаций серого цвета) каждая точка экрана может иметь одно из двух состояний - "черная" или "белая", то есть для хранения ее состояния необходим 1 бит.
Цветные изображения формируются в соответствии с двоичным кодом цвета каждой точки, хранящимся в видеопамяти. Цветные изображения могут иметь различную глубину цвета, которая задается количеством битов, используемым для кодирования цвета точки. Наиболее распространенными значениями глубины цвета являются 8, 16, 24 или 32 бита.

Формирование растрового изображения13 TC "Формирование растрового изображения" \f C \l "3" 15
Видеопамять

№ точки
Двоичный код цвета точки

1
01010101

2
00100101

......


800
11110000

......


480000
11001100


Качество двоичного кодирования изображения определяется разрешающей способностью экрана и глубиной цвета.

Каждый цвет можно рассматривать как возможное состояние точки, тогда количество цветов, отображаемых на экране монитора, может быть вычислено по формуле:

где I - глубина цвета.

Глубина цвета и количество отображаемых цветов

Цветное изображение на экране монитора формируется за счет смешивания трех базовых цветов: красного, зеленого и синего. Такая цветовая модель называется RGB-моделью по первым буквам английских названий цветов (Red, Green, Blue).
Для получения богатой палитры цветов базовым цветам могут быть заданы различные интенсивности. Например, при глубине цвета в 24 бита на каждый из цветов выделяется по 8 бит, то есть для каждого из цветов возможны уровней интенсивности, заданные двоичными кодами (от минимальной - 00000000 до максимальной - 111111111).
Формирование цветов при глубине цвета 24

Графический режим.
Графический режим вывода изображения на экран монитора определяется величиной разрешающей способности и глубиной цвета. Для того чтобы на экране монитора формировалось изображение, информация о каждой его точке (код цвета точки) должна храниться в видеопамяти компьютера. Расчитаем необходимый объем видеопамяти для одного из графических режимов, например, с разрешением 800 * 600 точек и глубиной цвета 24 бита на точку.
Всего точек на экране: 800 * 600 = 480 000.
Необходимый объем видеопамяти:
24 бит * 480 000 = 11 520 000 бит = 1 440 000 = 1406,25 Кбайб = 1,37 Мбайт.
Аналогично расчитывается необходимый объем видеопамяти для других графических режимов.
В Windows предусмотрена возможность выбора графического режима и настройки параметров видеосистемы компьютера, включающей монитор и видеоадаптер.

Установка графического режима13 TC "Установка графического режима" \f C \l "3" 15
В контекстном меню Рабочего стола выбрать пункт Свойства, появится диалоговая панель Свойства: Экран. Выбрать вкладку Параметры, которая информирует нас о марке установленных монитора и видеоадаптера и предоставляет возможность установить графический режим экрана (глубину цвета и разрешающую способность).



Щелкнуть по кнопке Дополнительно, появится диалоговая панель, на которой выбрать вкладку Монитор. С помощью раскрывающегося списка можно выбрать оптимальную частоту обновления экрана.



Контрольные задания.13 TC "Контрольные задания." \f C \l "2" 15
Используются графические режимы с глубинами цвета 8,16, 24 и 32 бита. Вычислить объемы видеопамяти, необходимые для реализации данных глубин цвета при различных разрешающих способностях экрана.
Определить количество цветов в палитре при глубине цвета 4, 8, 16, 24, 32 бита.
Черно-белое (без градаций серого) растровое изображение имеет размер 10*10 точек. Какой объем памяти займет это изображение?
Цветное (с палитрой из 256 цветов) растровое изображение имеет размер 10*10 точек. Какой объем памяти займет это изображение?
В процессе преобразования растрового графического изображения количество цветов уменьшилось с 65536 до 16. Во сколько раз уменьшится объем занимаемой им памяти?
В процессе преобразования растрового графического изображения количество цветов увеличилось с 16 до 4 294 967 296 . Во сколько раз увеличился объем занимаемой им памяти?
256-цветный рисунок содержит 120 байт информации. Из скольких точек он состоит?
Для хранения изображения размером 64*32 точек выделено 64 Кбайт памяти. Определите, какое максимальное число цветов допустимо использовать в этом случае.
Определить соотношение между высотой и шириной экрана монитора для различных графических режимов. Различается ли это соотношение для различных режимов?
а) 640*480; б) 800*600; в) 1024*768; г) 1152*864; д)1280*1024.
Какие графические режимы работы монитора может обеспечить видеопамять объемом в 1 Мбайт
Глава II
Решение задач группы С13 TC "Решение задач группы С" \f C \l "1" 15
Программирование на языке Pascal13 TC "Программирование на языке Pascal" \f C \l "2" 15
Для решения заданий части С единого государственного экзамена по информатике выпускник должен иметь представление хотя бы об одном из языков программирования, а также уметь составить алгоритм либо в виде блок-схемы, либо описав его на естественном языке. От учащегося требуется умение писать правильно небольшие (до 30 – 50 строк) фрагменты программ.
Что необходимо знать, чтобы решить задания типа С1, и на что необходимо обратить внимание
Правила построения программы на одном из языков программирования.
Правила работы с переменными.
Алгоритмическую структуру «ветвление».
Алгоритмическую структуру «цикл».
Правила построения вложенных условных операторов.
Умение составлять сложное условие при помощи логических операций (and, or).
Знания из курса математики (решение уравнений, графики функций, области допустимых значений, тригонометрические функции и т.д.)

Условный оператор
13 TC "Условный оператор" \f C \l "3" 15
Условный оператор позволяет проверить некоторое условие и в зависимости от результатов проверки выполнить то или иное действие. Таким образом, условный оператор - это средство ветвления вычислительного процесса.
Структура условного оператора имеет следующий вид:

IF <условие> THEN <оператор1> ELSE <оператор2>;

где IF, THEN, ELSE - зарезервированные слова (если, то, иначе); <условие> - произвольное выражение логического типа; <оператор1>, <оператор2> - любые операторы языка Турбо Паскаль.
Условный оператор работает по следующему алгоритму:
Вначале вычисляется условное выражение <условие>. Если результат есть TRUE (истина), то выполняется <оператор1>, а <оператор2> пропускается; если результат есть FALSE (ложь), наоборот, <оператор1> пропускается, а выполняется <оператор2>.
Например:
var
х, у, max: Integer;
begin
.......
if x > max then
max:=x else
max:=y ;
Рассмотрим четыре варианта записи оператора IF:
If <условие> then P1 else P2;
If <условие> then P1;
If (<условие1>) or (<условие2>) then P1 else P2;
If (<условие1>) and (<условие2>) then P1 else P2;
В первом случае если условие истинно, то выполняется оператор P1, если ложно – то P2.
Во втором варианте записана краткая форма оператора.
В третьем и четвертом примерах два условия объединены служебными словами or (или) и and (и).
Рассмотрим некоторые примеры задач с использованием условного оператора.
Задание 1. Написать программу, которая вводит с клавиатуры координаты точки на плоскости (x, y – действительные числа) и определяет принадлежность точки заштрихованной области, включая ее границы.

Решение:
Необходимо написать условие, которому должны отвечать точки, попавшие в выделенную область
Заштрихованная область ограничена по координате x, она находится справа от оси y, что равносильно условию x>=0 (с учетом границы здесь и далее получаем нестрогие неравенства)
Cлева от первого максимума функции y=sin(x); из математики мы знаем, что эта функция достигает максимума при x=13 EMBED Equation.3 1415, поэтому получаем второе условие 13 EMBED Equation.3 1415заштрихованная область ограничена с двух сторон по координате y: она находится ниже линии y=1, откуда следует третье условие y<=1, выше линии y=sin(x), что дает четвертое условие y>=sin(x)
Итак, точка находится в заданной области, если все эти четыре условия выполняются одновременно; можно предположить, что в программе нужно использовать четыре вложенных условных оператора или один условный оператор, в котором четыре простых условия (отношения x>=0, 13 EMBED Equation.3 1415 , y<=1 и y>=sin(x) ) связаны с помощью логической операции and
(«И», одновременное выполнение всех условий)
отметим на рисунке область, где выполняются все нужные условия, кроме 13 EMBED Equation.3 1415 (красная зона);
Для всех точек, которые находятся в «красной» зоне программа выдаст сообщение «принадлежит», хотя в самом деле эти точки не принадлежит заданной области; одна из таких точек имеет координаты 13 EMBED Equation.3 1415
Program Prim1_1;
var x,y: real;
begin
readln(x,y);
if (x >= 0) and (x <= pi/2) and
(y <= 1) and (y >= sin(x)) then
write('принадлежит')
else write('не принадлежит');
end.

Задание 2. Написать программу, которая вводит с клавиатуры координаты точки на плоскости (x, y – действительные числа) и определяет принадлежность точки заштрихованной области, включая ее границы.

13 SHAPE \* MERGEFORMAT 1415

Теоретические сведения, необходимые для выполнения задания.
Уравнение окружности радиуса r>0 с центром в точке (a,b) в прямоугольной системе координат имеет вид: (x-a)2+(y-b)2=r2. Если точка с координатами (x, y) лежит вне круга, границей которого является окружность, то (x-a)2+(y-b)2 > r2
Прямая ax + by + c =0 разбивает всю координатную плоскость на две полуплоскости, в одной из которых ax + by + c > 0, а в другой – ax + by + c < 0. Для того, чтобы узнать, какая именно из плоскостей задаётся данным неравенством, следует взять не лежащую на ней точку M(x,y) и проверить выполнимость неравенства. Если неравенство истинно в точке M, а если нет, то противоположная полуплоскость.

Сначала напишем программу, которая вводит с клавиатуры координаты точки на плоскости ( x, y – действительные числа) и определяет принадлежность точки заштрихованной на рис. 4 области, включая её границы. После этого выполним анализ текста программы задания и укажем на допущенные ошибки.

Решение.
В заштрихованную область попадают точки II четверти координатной плоскости, лежащие вне круга x2 + y2 =4 и справа от прямой x=-2 и ниже прямой y= -x.

Следовательно, заштрихованной в условии задании области будут принадлежать точки, координаты которых удовлетворяют условиям:

x2 + y2 >= 4, y >= 0, x <= 0 (точки II четверти координатной плоскости, лежащие вне круга);
x >= -2 (точки, лежащие в правой полуплоскости от прямой x = -2);
y <= -x (точки, лежащие в нижней полуплоскости от прямой y = -x).
Учитывая, что 0
· y и y
· -x, условие x
· 0 можно не записывать (избыточное условие), так как оно следует из свойства транзитивности неравенств: если a < b и b < c, то a < c.
Таким образом, условие попадания точки в заштрихованную область можно записать следующим образом : (x2 + y2 >= 4) и (x >= -2) и (0
· y
· -x).

Соответствующий алгоритм имеет вид:


Программа на Паскале:

Program Prim1_2;
var x, y: real;
begin
readln(x, y);
if x*x+y*y>=4
then if x>=-2
then if (y>=0) and (y<=-x)
then write (принадлежит’ ) else write(не принадлежит’)
else write(не принадлежит’);
end.
С использованием составного условия алгоритм примет вид:


Программа на Паскале:
Program Prim1_2;
var x,y:real;
begin
readln(x,y);
if (x*x+y*y>=4) and (x>=-2) and (y<=-x)
then write(принадлежит’) else write( не принадлежит’) ;
end.



Разбор задания.
Ответ на вопрос 1. Условие принадлежности точки заштрихованной области, включая её границы, в программе задания записано в виде: (x2 + y2
· 4) и (x
· -2) и (y
· -x).
Этому условию соответствуют точки II, III и IV четвертей координатной плоскости, изображённые на рис.5. Заштрихованная в соответствии с этими условиями область не соответствует представленной в задании на рис.3. Допущенная ошибка – отсутствие ограничения на y: y
·0.
Таким образом, в качестве примера чисел x, y, при которых программа неверно решает поставленную задачу, можно привести координаты точек плоскости, для которых (x2 + y2
· 4) и (x
· -2) и (y
· -x) и (y < 0), например x=-1, y=-3.
Ответ на вопрос 2. Программа задания содержит ошибку – неправильное использование алгоритмической конструкции при проверке первого и второго условий: сокращённой формы условного оператора if.then вместо полной формы ifthenelse. В случае невыполнения первого или второго условия отсутствует ветвь иначе (else), и, следовательно, программа не выдаёт сообщений о непринадлежности точки заштрихованной области в случае ложности этих условий.
Примеры тренировочных заданий.
Напишите программу, которая вводит с клавиатуры координаты точки на плоскости (x,y – действительные числа) и определяет принадлежность точки заштрихованной области, включая её границы.
Задание 3. Написать программу, которая определяет, имеется ли среди введённых с клавиатуры целых чисел a и b хотя бы одно чётное.
Была написана следующая программа:
Program Prim1_3;
var a,b : integer;
begin
writeln (Введите 2 числа’);
readln(a,b);
a:=a mod 2;
if a>0 then b:=b mod 2;
if b>0 then writeln (чётных чисел нет’) else writeln(чётное число есть’);
end.
Известно, что программа написана с ошибками.
Последовательно выполните три задания:
Приведите примеры таких чисел a и b, при которых программа неверно решает поставленную задачу.
Укажите, как, по вашему мнению, нужно доработать программу, чтобы не было случаев её неправильной работы.
Укажите, как можно доработать программу с использованием операции OR.
Решение.
Операция a mod b определяет остаток от деления первого числа на второе. Если остаток от деления равен 0 (a mod b=0), тогда говорят, что второе число является делителем первого числа.
Для решения поставленной задачи необходимо проверить, делится ли хотя бы одно из чисел a или b на 2 без остатка, т.е. a mod 2 = 0 или b mod 2 = 0
Возьмём a=4, b=6 и проверим правильность работы программы для данных значений. Анализируя данные, получаем, что оба числа чётные, т.е. программа должна выдавать сообщение «чётное число есть». Как же происходит на самом деле в этой программе?


Проверим программу пошагово:
1. a:=a mod 2;
То есть
a:=4 mod 2
Откуда a=0.
2. if a>0 then b:=b mod 2;
Так как a=0, проверяем условие 0>0. Условие не выполняется, следовательно, не вычисляя значение переменной b, переходим к проверке второго условия.
3. if b>0 then writeln (чётных чисел нет’) else writeln (чётное число есть’);
Проверяем условие 6 > 0. Условие выполняется, значит, должна быть выполнена команда, находящаяся в программе после then, т.е. выводится сообщение «чётных чисел нет». Это противоречит действительности, так как числа 4 и 6. Если внимательно пранализировать программу, то можно прийти к выводу, что программа неверно решает поставленную задачу при любых числах a и b.
Доработаем программу.

Program Prim1_3;
var a, b : integer
begin
writeln (Введите 2 числа’);
readln(a,b);
a:=a mod 2;
if a>0 then begin
b:=b mod 2;
if b>0 then
writeln (чётных чисел нет’) else
writeln(чётное число есть’);
end
else writeln(чётное число есть’);
end.

Напишем программу, используя OR:

Program Prim1_3;
var a, b : integer
begin
writeln (Введите 2 числа’);
readln(a,b);
if (a mod 2=0) or (b mod 2=0) then writeln(чётное число есть’)
else writeln(чётных чисел нет’);
end.
Задание 4. Написать программу решения неравенства Ax > B (где А и В – любые числа).

Программист торопился и написал программу неправильно:
var a,b :real;
begin
writeln(Введите a и b’);
readln(a,b);
if a>0 then write (x>’,b/a)
else write (x<’, b/a);
end.

Последовательно выполните следующее:
Приведите примеры таких чисел a и b, при которых программа работает неправильно.
Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы.
Решение.
Решим неравенство Ax > b математически:
если a>0, то x > b/a;
если a<0, то x < b/a;
если a=0, то неравенство принимает вид 0x > B: оно не имеет решений, если b
· 0, и верно при любом значении x, если b<0.
Из вышеизложенного можно увидеть, что программист не учёл третий случай в своей программе. Значит, можно привести такие примеры чисел a и b, при которых программа будет работать неверно:
при a = 0 и b = -4 результат должен быть следующим: «x – любое число»,
при a = 0 и b = 4 результат должен быть следующим: «решений нет».
Доработаем программу:

Program Prim1_4;
var a, b : real;
begin
writeln(введите a и b’);
readl(a,b);
if a>0 then write (x>’,b/a)
else if a<0 then write (x<’,b/a)
else if b>=0 then write (решений нет’)
else write(x – любое число’);
end.
Задание 5. Самостоятельно написать программу, которая решает уравнение y=ax+b относительно x для любых чисел a и b, введенных с клавиатуры. Все числа считаются действительными. Программист торопился и написал программу неправильно:
Program Prim1_5;
var a, b, x: real;
begin
readln(a,b);
if a=0 then
if b = 0 then
write('любое число')
else write('нет решений')
else
if b/a > 0 then
write('x=',b/a, ' или x=',-b/a)
else
if b=0 then write('x=0')
else write('нет решений');
readln;
end.
Исправить ошибки.
Тренировочные упражнения13 TC "Тренировочные упражнения" \f C \l "4" 15
Задание 1.Какая запись на языке Паскаль соответствует высказыванию «Число a кратно 7 и кратно 3»?
if 7if (a>1) and (a<2) then writeln (Число удовлетворяет условию’);
if (a mod 7=0) and (a mod 3 =0) then writeln(Число удовлетворяет условию’);
if (a mod 7=0) or (a mod 3 =0) then writeln(Число удовлетворяет условию’);
Задание 2.Какая запись на языке Паскаль соответствует высказыванию «Число b кратно 9 и чётное»?
if 9if (b mod 9=0) and (b mod 2=0) then writeln (Число удовлетворяет условию’);
if (b mod 9=0) and (a mod 2 =0) then writeln(Число удовлетворяет условию’);
if (b mod 9=0) or (b mod 2 =0) then writeln(Число удовлетворяет условию’);
Задание 3.Какая запись на языке Паскаль соответствует высказыванию «Число b чётное и меньше 2»?
if 2<и<2 then writeln (Число удовлетворяет условию’);
if (b mod 2 = 0) and (b<2) then writeln (Число удовлетворяет условию’);
if (b mod 2=0) and (b<2 =0) then writeln(Число удовлетворяет условию’);
if (b mod 2=0) and (b<2) then writeln(Число удовлетворяет условию’);
Задание 4.Какая запись на языке Паскаль соответствует высказыванию «Число b кратно 5 и больше 4»?
if 4if (b div 2 = 5) and (b>4) then writeln (Число удовлетворяет условию’);
if (b mod 5=0) and (4if (b mod 5=0) and (b>4) then writeln(Число удовлетворяет условию’);
Задание 5.Какая запись на языке Паскаль соответствует высказыванию «Сумма двух чисел a и b кратна 5 или кратна 4»?
if 5if (a mod 5 = 0) and (b mod 4 = 0) then writeln (Сумма двух чисел удовлетворяет условию’);
if (a + b mod 5=0) and (a+b mod 4 =0) then writeln(Сумма двух чисел удовлетворяет условию’);
if ((a+b mod 5=0) or ((a+b) mod 4 = 0) then writeln(Сумма двух чисел удовлетворяет условию’);

Задание 6.
Какая запись на языке Паскаль соответствует высказыванию «Если значение переменной x больше 1, но меньше 2, то уменьшить значение x на 3»?
if 1if (x>1) and (x<2) then x:=x-3;
if x>1 and x<2 then x:=x-3;
if (x>1) or (x<2) then x:=x-3;
Задание 7.
Какая запись на языке Паскаль соответствует высказыванию «Если значение переменной x больше 1 и чётное, то уменьшить значение x на 3»?
if 1if ( x>1 ) and ( x mod 2 ) then x:=x-3;
if ( x>1 ) or ( x mod 2 =0 ) then x:=x-3;
if ( x>1 ) or ( x mod 2 = 0 )
Задание 8.
В программе использован оператор ветвления:
if x>=3 then write(зачёт’) else write (незачёт’);
Какой из перечисленных ниже строк можно заменить данную строку так, чтобы программа работала по-прежнему (если их несколько, то указать все)?
1) if x<3 then write(незачёт’) else write (зачёт’);
2) if not (x<3) then write(зачёт’) else write (незачёт’);
3) if not (x>=3) then write(незачёт’) else write (зачёт’);
4) if not (x>3) then write(незачёт’) else write (зачёт’);
Контрольные задания13 TC "Контрольные задания" \f C \l "4" 15
1. Написать программу, которая определяет, лежит ли точка А(х0,у0) внутри треугольной области, ограниченной осями координат и прямой 13 EMBED Equation.3 1415 («внутри» понимается в строгом смысле, т.е. случай, когда точка А лежит на границе области, недопустим). В результате программа должна выводить соответствующее текстовое сообщение.
2. Написать программу, которая решает уравнение 0=ax2+bx+c относительно х для действительных чисел а, b, с, введенных с клавиатуры, о которых заведомо известно, что а(0, b(0 и c(0.
3. Написать программу, которая определяет, лежит ли точка А(х0,у0) внутри треугольной области, ограниченной осями координат и прямой y=2-x («внутри» понимается в строгом смысле, т.е. случай, когда точка А лежит на границе области, недопустим). В результате программа должна выводить соответствующее текстовое сообщение.
4. Написать программу, которая определяет, имеется ли среди введенных с клавиатуры положительных целых чисел а и b хотя бы одно четное.
5. Написать программу, которая определяет, можно ли построить треугольник из отрезков с длинами х, у, z. Программа должна выводить соответствующее текстовое сообщение.
6. Написать программу, которая определяет, лежит ли точка А(х,у) внутри некоторого кольца («внутри» понимается в строгом смысле, т.е. случай, когда точка А лежит на границе кольца, недопустим). Центр кольца находится в начале координат. Для кольца заданы внутренний и внешний радиусы r1, r2; известно, что r1 отлично от r2, но неизвестно, r1 > r2 или r2 > r1. В том случае, когда точка А лежит внутри кольца, программа должна выводить соответствующее сообщение, в противном случае никакой выходной информации не выдается.
2. Оператор выбора (case)13 TC "Оператор выбора (case)" \f C \l "3" 15
Предназначен для ветвления программ на два или несколько направлений.
Case <ключ выбора> of <список выбора> else P end;
<ключ выбора> - идентификатор целого или символьного типа,
<список выбора> - включает в себя две или более конструкций следующего вида:
<константа выбора> : <оператор>;
<константа выбора> - это идентификатор того же типа, что и <ключ выбора>
Примеры решения задач с использованием оператора выбора13 TC "Примеры решения задач с использованием оператора выбора" \f C \l "4" 15:
Пример 1. Написать программу на языке Паскаль, которая по введённому номеру дня недели w (целое число от 1 до 7) и по известной переменной  d  ( целое число от 1 до 31) – номеру месяца в году выводит сообщение о названии этого дня.
Program Prim2_1;
var d, w1, w:integer;
begin
  readln(w1, d);
  w:=(d+w1-1) mod 7;
  case w of
  1:writeln(’понедельник’);
  2:writeln(’вторник’);
  3:writeln(’среда’);
  4:writeln(’четверг’);
  5:writeln(’пятница’);
  6:writeln(’суббота’);
  0:writeln(’воскресенье’);
  end
end.
Пример 2. Для 100 целых значений x рассчитать значение [ Cкачайте файл, чтобы посмотреть картинку ].
Составить два варианта программ: с помощью условного оператора if и c помощью оператора выбора Case.
Program Prim2_2;
Var x,y:integer;
Begin
For x:=1 to 100 do
Begin
If x mod 2 =0 then y:=2*x else y:=2+x;
Writeln(x,y);
End;
End.

2 способ решения

Program Prim2_2;
Var x,y:integer;
Begin
For x:=1 to 100 do
Begin
Case x mod 2 of
0: y:=2*x;
1: y:=2+x;
end;
Writeln(x,y);
End;
End.
Контрольные задания13 TC "Контрольные задания" \f C \l "4" 15
1. Дан номер месяца (1 январь, 2 февраль, ...). Вывести название соответствующего времени года («зима», «весна» и т.д.). 
2. Дан номер месяца (1 январь, 2 февраль, ...). Вывести число дней в этом месяце для невисокосного года. 
3. Дано целое число в диапазоне 0 – 9. Вывести строку название соответствующей цифры на русском языке (0 «ноль», 1 «один», 2 «два», ...). 
4. Дано целое число в диапазоне 1 – 5. Вывести строку словесное описание соответствующей оценки (1 «плохо», 2 «неудовлетворительно», 3 «удовлетворительно», 4 «хорошо», 5 «отлично»). 
5. Арифметические действия над числами пронумерованы следующим образом: 1 сложение, 2 вычитание, 3 умножение, 4 деление. Дан номер действия и два числа A и B (В не равно нулю). Выполнить над числами указанное действие и вывести результат. 
6. Единицы длины пронумерованы следующим образом: 1 дециметр, 2 километр, 3 метр, 4 миллиметр, 5 сантиметр. Дан номер единицы длины и длина отрезка L в этих единицах (вещественное число). Вывести длину данного отрезка в метрах. 
7. Единицы массы пронумерованы следующим образом: 1 килограмм, 2 миллиграмм, 3 грамм, 4 тонна, 5 центнер. Дан номер единицы массы и масса тела M в этих единицах (вещественное число). Вывести массу данного тела в килограммах. 
8. Робот может перемещаться в четырех направлениях («С» север, «З» запад, «Ю» юг, «В» восток) и принимать три цифровые команды: 0 продолжать движение, 1 поворот налево, –1 поворот направо. Дан символ C исходное направление робота и число N посланная ему команда. Вывести направление робота после выполнения полученной команды. 
9. Локатор ориентирован на одну из сторон света («С» север, «З» запад, «Ю» юг, «В» восток) и может принимать три цифровые команды: 1 поворот налево, –1 поворот направо, 2 поворот на 180 градусов. Дан символ C исходная ориентация локатора и числа N1 и N2 две посланные ему команды. Вывести ориентацию локатора после выполнения данных команд. 
10. Элементы окружности пронумерованы следующим образом: 1 радиус (R), 2 диаметр (D), 3 длина (L), 4 площадь круга (S). Дан номер одного из этих элементов и его значение. Вывести значения остальных элементов данной окружности (в том же порядке). В качестве значения Pi использовать 3.14. 
11. Элементы равнобедренного прямоугольного треугольника пронумерованы следующим образом: 1 катет (a), 2 гипотенуза (c), 3 высота, опущенная на гипотенузу (h), 4 площадь (S). Дан номер одного из этих элементов и его значение. Вывести значения остальных элементов данного треугольника (в том же порядке). 
12. Элементы равностороннего треугольника пронумерованы следующим образом: 1 сторона (a), 2 радиус вписанной njpsfmnqrh (R1), 3 радиус описанной окружности (R2), 4 площадь (S). Дан номер одного из этих элементов и его значение. Вывести значения остальных элементов данного треугольника (в том же порядке). 
13. Даны два целых числа: D (день) и M (месяц), определяющие правильную дату невисокосного года. Вывести значения D и M для даты, предшествующей указанной. 
14. Даны два целых числа: D (день) и M (месяц), определяющие правильную дату невисокосного года. Вывести значения D и M для даты, следующей за указанной. 
15. Дано целое число в диапазоне 20 – 69, определяющее возраст (в годах). Вывести строку словесное описание указанного возраста, обеспечив правильное согласование числа со словом «год», например: 20 «двадцать лет», 32 «тридцать два года», 41 «сорок один год».
16. Дано целое число в диапазоне 100 – 999. Вывести строку словесное описание данного числа, например: 256 «двести пятьдесят шесть», 814 «восемьсот четырнадцать».
17. В восточном календаре принят 60-летний цикл, состоящий из 12- летних подциклов, обозначаемых названиями цвета: зеленый, красный, желтый, белый и черный. В каждом подцикле годы носят названия животных: крысы, коровы, тигра, зайца, дракона, змеи, лошади, овцы, обезьяны, курицы, собаки и свиньи. По номеру года вывести его название, если 1984 год был началом цикла годом зеленой крысы.


Работа с массивами13 TC "Работа с массивами" \f C \l "3" 15
Что необходимо знать, чтобы решить задания типа С2
Понятие массива (одномерный, двумерный массивы).
Заполнение массива элементами.
Обработка числового массива (поиск наименьшего или наибольшего элемента; поиск элемента, удовлетворяющего условию; сортировка массива; нахождение суммы элементов массива; нахождение произведения элементов массива; нахождение среднего арифметического элементов массива
МАССИВ - это упорядоченный по номерам набор значений, объединенных общим типом и именем. Упорядоченность заключается в том, что элементы массива располагаются в последовательных, пронумерованных ячейках памяти. Массив имеет фиксированные: имя, тип и количество значений. Массиву выделяется место в памяти.
Элементы массива - это переменные с индексами. Индексы можно вычислять.

Массивы, как и простые переменные, подлежат описанию в разделе переменных:

VAR <имя>: ARRAY[] OF <тип элементов>;

array – размерность, массив of - из.
Тип индексов - любой скалярный тип кроме real.
Тип элементов - любой для данной версии языка.
[min..max] - размер массива. min - нижняя, max –верхняя границы индексов. min<=max. Границы можно задать с помощью переменных.

Можно задавать постоянный массив:
const x: array [1..10] of integer=(4,6,3,5,2,1,7,8,9,13);
const x: array [1..8] of char=('a','b','c','d','e','f','g','h');
Элементы таких массивов являются константами.

Если массивы одинаковы и отличаются лишь именами, то их можно описать в одной строке:
var a,b,c :array[1..n] of real; , где n -верхняя граница индекса и n описывается в разделе констант.

ВИДЫ МАССИВОВ :

Одномерные - ряд элементов. B[5] - 5-ый элемент массива.
Двумерные - таблицы. B[3,5] - элемент таблицы B ,стоящий в 3 строке и в 5 столбце.
Многомерные - ряд таблиц (изучаютя в ВУЗе).

Приведём примеры работы с одномерными массивами:
1. Заполнить и вывести на экран одномерный массив целых чисел.

Program Prim3_1;
uses crt;
var a: array[1..5] of integer;
i: integer;
Begin
clrscr;

{******* заполнение массива c клавиатуры *******}
for i:=1 to 5 do
begin
write('a[',i,']='); readln(a[i]);
end;
clrscr;

{***** вывод массива на экран *****}
Write(Массив А: ’); for i:=1 to 5 do write(a[i],’ );

readkey;
End.

2. Заполнить и вывести на экран одномерный массив символов.

Program Prim3_2;
uses crt;
const a: array[1..5] of char=('a','b','c','d','e');

procedure Print(n: integer);
var i: integer;
begin
for i:=1 to n do write (a[i]:2)
end;

Begin
clrscr;
write('Массив А: '); Print(5);
readkey;
End.

3. Дан одномерный массив. Найти сумму элементов одномерного массива. Найти среднее арифметическое.

Program Prim3_3;
uses crt;
const n=5;
var a: array[1..n] of integer;
m,i,s: integer; Автоматическое заполнение
случайными числами от1 до20

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·'Массив целых чисел А: ');
for i:=1 to n do write(' ',a[i])
writeln; writeln; { пропуск строки}
end;
procedure Sum( m: integer);
begin
s:=0;
for i:=1 to m do s:=s+a[i];
end;
Begin
ClrScr;
Input; { заполнение массива из 5 элементов}
ClrScr;
Print; { печать заполненного массива}
write('Сколько элементов суммировать: '); readln(m);
Sum(m); writeln; { суммирование m элементов массива}
writeln('Сумма ',m,' элементов массива равна: ', s);
{ суммирование всех элементов массива }
Sum(n); writeln;
writeln('Сумма всех ',n,' элементов массива равна: ', s);
Write ('Среднее арифметическое всех элементов равно ', s/n);
Readkey;
End.

4. Заполнить и вывести одномерный массив на экран. Найти сумму элементов массива, меньших заданного числа u и вывести на экран результат.

Program Prim3_4;
uses crt;
const a: array[1..10] of integer=(3,5,2,1,6,3,8,7,5,9);
var i, s, u: integer;

procedure Su;
begin
s:=0;
for i:=1 to 10 do if a[i] write('Сумма элементов меньших ',u,' равна ',s);
end;

Begin
ClrScr;
Print;
writeln;
writeln;
write('Введите условие суммирования : '); readln(u);
Su;
Readkey;
End.

5. В упорядоченном по возрастанию одномерном массиве, методом двоичного поиска найти индекс элемента, значение которого равно K. Описать три результата работы программы:
1)     если массив не является упорядоченным по возрастанию, то программа должна сообщать, что данные некорректны и закончить работу;
2)     если элемент, равный K, в упорядоченном по возрастанию массиве присутствует, то программа должна выдавать его индекс (номер в массиве);
3)     если искомого элемента в упорядоченном по возрастанию массиве нет, то программа должна выдать число 0.

Program Prim3_5;
Var a:array[1..1000] of integer;
    K,L,R,m,i,n:integer;
    b:boolean;
begin
  readln(K);
  readln(n);
  for i:=1 to n do read(a[i]);
  b:=true;
  for i:=2 to n do
    if a[i-1]>=a[i] then b:=false;
  if not b then
    writeln(’данные некорректны’)
  else
  begin
    L:=1; R:=n;
    b:=false;
    while (L<=R)and not b do
    begin
      m:=(L+R)div 2;
      b:=(a[m]=K);
      if a[m]                else R:=m-1
    end;
    if b then writeln(m)
         else writeln(0)
  end
end.

6. Опишите на языке Pascal алгоритм поиска трех последовательных элементов, сумма которых максимальна, в числовом массиве из 30 элементов.

Program Prim3_6;
const N=30;
var a:array[1..N] of integer;
    Max, Trio, i: integer;
begin
 Trio:=a[1]+a[2]+a[3];
 Max:=Trio;
 for i:=4 to N do
  begin
   Trio:=Trio+a[i]-a[i-3];
   if Trio>Max then Max:=Trio;
  end;
  writeln(Max);
end.
7. Опишите на языке Pascal алгоритм подсчета числа элементов равных максимальному элементу в числовом массиве из 30 элементов.
Program Prim3_7;
C
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Опишите на языке Pascal алгоритм поиска второго по величине (т.е. следующего по величине за максимальным) элементом в числовом массиве из 30 различных элементов.

Program Prim3_8;
const N=30;
var a:array[1..N] of real;
    Max1, Max2, i: real;
begin
 Max1:
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Опишите на языке Pascal алгоритм поиска номера первого из двух последовательных элементов в целочисленном массиве из 30 элементов, сумма которых максимальна (если таких пар несколько, то можно выбрать любую из них).

Program Prim3_9;
const N=30;
var a:arra
·y[1..N] of integer;
MaxSum, MaxNum, i: integer;
begin
MaxNum:=1;
MaxSum:=a[1]+a[2];
for i:=2 to N-1 do
begin
if a[i]+a[i+1]>MaxSum then
begin
MaxNum:=i;
MaxSum:=a[i]+a[i+1];
end
end;
writeln(MaxNum);
end.

10. Опишите на языке Pascal алгоритм получения из заданного целочисленного массива размером 30 элементов другого массива, который будет содержать модули значений элементов первого массива (не используя специальной функции, вычисляющей модуль числа).

Program Prim3_10;
const N=30;
var a, b:array[1..N] of integer;
i: integer;
begin
for i:=1 to N do
if a [i] < 0
then b[i]:= - a[i]
else b[i]:= a[i];
end.

11. Опишите на языке Pascal алгоритм подсчета максимального количества подряд идущих совпадающих элементов в целочисленном массиве длины 30.
Program Prim3_11;
const N =30;
var a: array[1..N] of integer;
i, k, kMax: integer;
begin
for i:=1 to N do readln(A[i]);
k := 1;
kMax := 1;
for i:=2 to N do begin
if a[i] = a[i-1] then
k := k + 1
else k := 1;
if k > kMax then kMax := k;
end;
writeln(kMax);
end.

12. В одномерном массиве удалить максимальный элемент.
Program Prim3_12;
Const n=10;
Var a:array[1..n] of integer;
Max, I, k : integer;
Begin
Randomize;
For i:=1 to n do
A[i]:=-20+ random(60);
For i:=1 to n do
Write(a[i]:4);
Writeln;
Max:=a[1];
For i:=1 to n do
If a[i]>=max then begin
Max:=a[i];
K:=I;
end;
For i:=k to 9 do
A[i]:=a[i+1];
For i:=1 to n-1 do
Write(a[i]:4);
Writeln;
End.
13. В одномерном массиве вставить после минимального элемента число 10.
Program Prim3_13;
Const n=10;
Var a:array[1..n+1] of integer;
Min, I, k:integer;
Begin
Randomize;
For i:=1 to n do
a[i]:=-20+random(60);
For i:=1 to n do
Write(a[i]:4);
Writeln;
Min:=a[1];
For i:=1 to n do
If a[i]<=min then begin
Min:=a[i];
K:=I;
End;
For i:=n+1 downto k+2 do
a[i]:=a[i-1];
a[k+1]:=10;
for i:=1 to n+1 do
write(a[i]:4);
writeln;
end.

14. Дан одномерный массив из чётного количества элементов. Поменять местами первый элемент со вторым, третий с четвёртым и т.д.
Program Prim3_14;
Const n=10;
Var a:array[1..n] of integer;
t,i : integer;
Begin
Randomize;
For i:=1 to n do
a[i]:=-20+random(60);
For i:=1 to n do write(a[i]:4);
Writeln;
For i:=1 to n do begin
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
i:=i+1;
end;
For i:=1 to n do
Write(a[i]:4);
Writeln;
End.

15. В одномерном массиве вставить число 100 перед первым отрицательным элементом.

Program Prim3_15;
Const n=10;
Var a: array[1..n+1] of integer;
i, k : integer;
Begin
Randomize;
For i:=1 to n do
a[i]:=-20+random(60);
For i:=1 to n do
If a[i]<0 then begin
k:=i; i:=n;
End;
For i:=n+1 downto k+1 do
a[i]:=a[i-1];
a[k]:=100;
For i:=1 to n+1 do
Write(a[i]:4);
Writeln;
End.

16. Удалить из массива все элементы, стоящие перед максимальным элементом

Program Prim3_16;
Const n=10;
Var
a:array[1..n] of integer;
max, i, k: integer;
begin
randomize;
for i:=1 to n do a[i]:=-20+random(60);
max:=a[1];
for i:=1 to n do
if a[i]>=max then begin
max:=a[i];
k:=I;
end;
for i:=1 to n-k+1 do
a[i]:=a[i+k-1] do
write(a[i]:4);
writeln;
end.

17. Дан массив из 6 целых чисел. Найти чётные элементы массива. Если таких нет, вывести об этом сообщение. Результатом работы программы является список индексов (номеров) элементов и их значений, удовлетворяющих данному условию, выведённых каждой с новой строки. Массив заполняется с клавиатуры. Использовать оператор for.

Program Prim3_17;
Var
A:array[1..6] of integer;
I, k:integer;
Begin
Writeln(Введите элементы массива’);
For i:=1 to 6 do read(a[i]);
K:=0;
For i:=1 to 6 do
If a[i] mod 2 = 0 then begin
Writeln(a[, I , ]=’, a[i], – чётный’ );
K:=k+1;
End;
If k=0 then writeln (чётных элементов нет’);
End.

18. Составить программу, выводящую целое число n в системе счисления с основанием 12. Целое число вводится с клавиатуры. Использовать одномерный массив для хранения цифр числа и оператор fordownto для их вывода на экран
Program prim3_18;
Var
A:array[0..10] of integer;
i , j , n: integer;
begin
read(n);
i:=1;
while n>0 do begin
a[i]:=n mod 12;
n:=n div 12;
i:=i+1;
end;
for j:=i-1 downto 1 do begin
if a[i]=11 then write(b’)
else if a[j]=10 then write(a’)
else write(a[j]);
end;
end.
19. Дан массив из 10 элементов типа Boolean. Каждый элемент массива равен true, если синус его индекса больше или равен нулю, в противном случае элемент имеет величину false. Вывести массив в одну строку.

Program Prim3_19;
Var
A: array[1..10] of Boolean;
I:integer;
Begin
For i:=1 to 10 do a[i]:=(sin(i)>=0);
For i:=1 to 10 do write(a[i], );
End.


Двумерные массивы Паскаля – матрицы13 TC "Двумерные массивы Паскаля – матрицы" \f C \l "3" 15
Двумерный массив в Паскале трактуется как одномерный массив, тип элементов которого также является массивом (массив массивов). Положение элементов в двумерных массивах Паскаля описывается двумя. Их можно представить в виде прямоугольной таблицы или матрицы.
Рассмотрим двумерный массив Паскаля размерностью 3*3, то есть в ней будет три строки, а в каждой строке по три элемента:
[ Cкачайте файл, чтобы посмотреть картинку ]
Каждый элемент имеет свой номер, как у одномерных массивов, но сейчас номер уже состоит из двух чисел – номера строки, в которой находится элемент, и номера столбца. Таким образом, номер элемента определяется пересечением строки и столбца. Например, a [2,1] – это элемент, стоящий во второй строке и в первом столбце.
Описание двумерного массива Паскаля13 TC "Описание двумерного массива Паскаля" \f C \l "4" 15.
Существует несколько способов объявления двумерного массива Паскаля.
Рассмотрим следующее описание типов и переменных:
Пример описания двумерного массива Паскаля
Type Vector = array [1..5] of <тип_элементов>; Matrix= array [1..10] of vector; Var m: matrix;
Мы объявили двумерный массив Паскаля m, состоящий из 10 строк, в каждой из которых 5 столбцов. При этом к каждой i -й строке можно обращаться m [ i ], а каждому j -му элементу внутри i -й строки – m [ i , j ].
Определение типов для двумерных массивов Паскаля можно задавать и в одной строке:
Type Matrix= array [1..5] of array [1..10] of < тип элементов >; или: Type matrix = array [1..5, 1..10] of <тип элементов>;
Единственное действие, которое можно осуществить над однотипными матрицами целиком – это присваивание. Т.е., если в программе у нас описаны две матрицы одного типа, например,
Type matrix = array [1..5, 1..10] of integer; var    a , b : matrix ;
то в ходе выполнения программы можно присвоить матрице a значение матрицы b (a := b)

Все остальные действия выполняются поэлементно, при этом над элементами можно выполнять все допустимые операции, которые определены для типа данных элементов массива.
Это означает, что если массив состоит из целых чисел, то над его элементами можно выполнять операции, определенные для целых чисел, если же массив состоит из символов, то к ним применимы операции, определенные для работы с символами.
Ввод двумерного массива Паскаля13 TC "Ввод двумерного массива Паскаля" \f C \l "4" 15.
Рассмотрим пример ввода двумерного массива Паскаля с клавиатуры:
Пример программы ввода двумерного массива Паскаля с клавиатуры
type    matrix= array [1..5, 1..10] of integer; var    a, : matrix;    i, j: integer; { индексы массива } begin    for i :=1 to 5 do {цикл для перебора всех строк}       for j :=1 to 10 do {перебор всех элементов строки по столбцам}          readln ( a [ i , j ]); {ввод с клавиатуры элемента, стоящего в i -й строке и j -м столбце}
Двумерный массив Паскаля можно заполнить случайным образом, т.е. использовать функцию random (N), а также присвоить каждому элементу матрицы значение некоторого выражения. Способ заполнения двумерного массива Паскаля выбирается в зависимости от поставленной задачи, но в любом случае должен быть определен каждый элемент в каждой строке и каждом столбце.
Вывод двумерного массива Паскаля на экран13 TC "Вывод двумерного массива Паскаля на экран" \f C \l "4" 15.
Вывод элементов двумерного массива Паскаля также осуществляется последовательно, необходимо напечатать элементы каждой строки и каждого столбца. При этом хотелось бы, чтобы элементы, стоящие в одной строке, печатались рядом, т.е. в строку, а элементы столбца располагались один под другим. Для этого необходимо выполнить следующую последовательность действий (рассмотрим фрагмент программы для массива, описанного в предыдущем примере):
Пример программы вывода двумерного массива Паскаля
for i :=1 to 5 do {цикл для перебора всех строк} begin    for j :=1 to 10 do {перебор всех элементов строки по столбцам}       write ( a [ i , j ]:4); {печать элементов, стоящих в i -й строке матрицы в одной экранной строке, при этом для вывода каждого элемента отводится 4 позиции}    writeln ; {прежде, чем сменить номер строки в матрице, нужно перевести курсор на начало новой экранной строки} end ;
Основные свойства квадратных матриц13 TC "Основные свойства квадратных матриц" \f C \l "4" 15:
1. Квадратные матрицы имеют главную и побочные диагонали. Например, для матрицы А на главной диагонали лежат элементы 1,5 и 9, а на побочной – 3, 5 и 7.
[ Cкачайте файл, чтобы посмотреть картинку ].
Если:
i=j – элементы расположены на главной диагонали; i> j – элементы расположены ниже главной диагонали; i n+1– элементы расположены под побочной диагональю;
2. Квадратная матрица, у которой все элементы, исключая элементы главной диагонали, равны нулю, называется диагональной матрицей.
3. Диагональная матрица, у которой все элементы, стоящие на главной диагонали, равны 1 , называется единичной матрицей

4. Если в матрице A (m,n) поменять местами строки и столбцы, то получится матрица At (m,n), которая называется транспонированной матрицей.
[ Cкачайте файл, чтобы посмотреть картинку ][ Cкачайте файл, чтобы посмотреть картинку ]
Примеры решения задач с двумерными массивами Паскаля13 TC "Примеры решения задач с двумерными массивами Паскаля" \f C \l "4" 15
Приведём примеры работы с двумерными массивами:
1. Найти произведение ненулевых элементов матрицы.
Program Prim4_1; Type    Matrix=array [1..10, 1..10] of integer; Var    A: matrix;    N, m, i, j: byte;    P: integer; Procedure vvod (var m: matrix); Var k , h : byte ; Begin    For i :=1 to n do {переменная n для процедуры является глобальной, а значит «известной»}       For j :=1 to m do {переменная m для процедуры является глобальной, а значит «известной»}          M[i,j]:= random(10); End; Procedure print (m: matrix); Var k, h: byte; Begin    For i:=1 to n do    begin       For j:=1 to m do          Write (M[i, j]: 4);       Writeln;    end ; End ; Begin {начало основной программы}    Writeln (Введите размерность матрицы:’);    Readln(N, M);    Vvod(a);    Print(a);    P:=1;    For i:=1 to N do       For j:=1 to M do          If a[i, j]<>0 then p:=p*a[i, j];    Writeln ( p ); End .
2.Дана таблица действительных чисел. Сосчитайте сумму всех чисел в таблице.
Procedure Summa(A : MyArray; n, m: integer; Var S: real); Var   i, j : integer; Var   i, j , Summa : integer; Begin   S:= 0;     for i := 1 to n do       for j := 1 to m do         S := S+A[i,j]; End.
3. Рассмотрим задачу нахождение сумм элементов строк матрицы на примере задачи подсчета итогов футбольного чемпионата. Пусть задана таблица результатов игр 5 команд футбольного чемпионата размера 5х5. На диагонали таблицы стоят значения 0, другие элементы таблицы равны 0, 1 или 2, где 0 баллов соответствует проигрышу команды в игре, 1 балл - ничьей, 2 балла - выигрышу. Определить сумму баллов каждой команды по результатам чемпионата.
Для построения матрицы R результатов игр достаточно ввести лишь стоящую выше (или ниже) главной диагонали половину матрицы, т.к. результаты остальных игр могут быть рассчитаны из известного соотношения: если, например, первая команда обыграла вторую, то элемент R[1,2]=2, а элемент R[2,1]=2-R[1,2]=0; аналогично, если вторая команда сыграла в ничью с третьей, то R[2,3]=1,  R[3,2]=2-R[2,3]=1. Таким образом, нетрудно получить вид взаимосвязи элементов матрицы: R[i,j]+R[j,i]=2, где i и j меняются от 1 до 5 (кроме элементов главной диагонали). На главной диагонали матрицы R по условию задачи всегда стоят числа 0.
Перейдем к написанию программы решения поставленной задачи на языке Pascal.
Program Prim4_3;;
Type tab=array[1..5,1..5] of integer;
Var r:tab;
       i,j,s:integer;
begin
{ввод стоящих выше диагонали элементов матрицы}
for i:=1 to 4 do
for j:=i+1 to 5 do
begin
writeln (Введите результат игры ,i,'-й команды с ',j,' -й:  0, 1 или 2 балла');
readln(r[i,j]);
end;
{заполнение стоящих на диагонали элементов нулями}
for i:=1 to 5 do r[i,i]:=0;
{вычисление стоящих ниже диагонали элементов матрицы}
for i:=2 to 5 do
for j:=1 to i-1 do r[i,j]:=2-r[j,i];
{вывод на экран матрицы результатов игр}
writeln(Таблица чемпионата');
for i:=1 to 5 do
begin
for j:=1 to 5 do write(r[i,j]:4);
writeln;
end;
{вычисление сумм элементов строк матрицы}
for i:=1 to 5 do
begin
s:=0;
for j:=1 to 5 do s:=s+r[i,j];
writeln(i,-ая команда набрала ',s:3,' очков');
end;
end.

Type tab=array[1..5,1..5] of integer;
Var r:tab;
       i,j,s:integer;
begin
{ввод стоящих выше диагонали элементов матрицы}
for i:=1 to 4 do
for j:=i+1 to 5 do
begin
writeln (Введите результат игры ,i,'-й команды с ',j,' -й:  0, 1 или 2 балла');
readln(r[i,j]);
end;
{заполнение стоящих на диагонали элементов нулями}
for i:=1 to 5 do r[i,i]:=0;
{вычисление стоящих ниже диагонали элементов матрицы}
for i:=2 to 5 do
for j:=1 to i-1 do r[i,j]:=2-r[j,i];
{вывод на экран матрицы результатов игр}
writeln(Таблица чемпионата');
for i:=1 to 5 do
begin
for j:=1 to 5 do write(r[i,j]:4);
writeln;
end;
{вычисление сумм элементов строк матрицы}
for i:=1 to 5 do
begin
s:=0;
for j:=1 to 5 do s:=s+r[i,j];
writeln(i,-ая команда набрала ',s:3,' очков');
end;
end.
4. Дан целочисленный квадратный массив 10 х 10. Опишите на языке Pascal алгоритм вычисления суммы максимальных элементов из каждой строки. Напечатать значение этой суммы. Предполагается, что в каждой строке такой элемент единственный.
Program Prim4_4;
const N=10;
var A: array[1..N,1..N] of integer;
i, k, max, Sum: integer;
begin
{ ввод матрицы N на N }
Sum := 0;
for i:=1 to N do begin
max := A[i,1];
for k:=2 to N do
if A[i,k] > max then max := A[i,k];
Sum := Sum + max;
end;
writeln(Sum);
end.

5. Рассматривается стандартная шахматная доска размером 8х8. Примем, что i – номер вертикали (может принимать значения от 1 до 8), j – номер горизонтали (также может принимать значения от 1 до 8). В левом нижнем углу, т.е. на поле i=1, j=1 (это поле черного цвета) стоит черный король. Напомним, что король может ходить на 1 клетку в любом направлении (по горизонтали, вертикали или диагонали). В правом нижнем углу, т.е. на поле i=8, j=1 (это поле белого цвета) стоит белый король. Введены обозначения: P(i,j) минимальное число ходов, за которое черный король может попасть на поле (i,j); V(i,j)минимальное число ходов, за которое белый король может попасть на поле (i,j).
Программист написал программу, в которой требовалось определить все такие поля (i,j), для которых P(i,j)=V(i,j), и выдать на экран соответствующие значения i,j.
Program Prim4_5;
var i,j: integer;
begin
writeln('искомые поля');
for j:=5 to 8 do
for i:=1 to 8 do
begin
if (i=9-j) OR (i=j)
then writeln('i=',i, 'j=',j);

end;
end.

Тренировочные упражнения13 TC "Тренировочные упражнения" \f C \l "4" 15
Задание 1. Напишите программу, которая выводит на экран массив из десяти элементов, являющихся степенями двойки (2,4,8,16,32,64,128,256,512,1024)

Program tren1;
var
a:array[1..10] of integer;
i:integer;
begin
a[1]:=2;
for i:=2 to 10 do
a[i]:=a[i-1]*2;
for i:=1 to 10 do
write(a[i]:7);
end.

Задание 2. Напишите программу, которая в заданном целочисленном массиве из 15 элементов находит наибольший и наименьший элементы.

Program tren2;
var
a:array[1..15] of integer;
i, min, max:integer;
begin
for i:=1 to 15 do
read(a[i]);
min:=a[1];
max:=a[1];
for i:=2 to 15 do begin
if a[i]>max then max:=a[i];
if a[i]end;
write(max=’,max,’min=’,min);
end.

Задание 3. Напишите программу, определяющую сумму элементов, стоящих на местах, кратных трём.
Program tren3;
var
a:array[1..50] of integer;
i, n, s :integer;
begin
read(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
if I mod 3=0 then s:=s+a[i];
write(s =’, s);
end.

Задание 4. Напишите программу, определяющую сумму минимального и максимального элементов массива.

Program tren4;
const n=10;
var
a: array [1..n] of integer;
i, min, max, s :integer;
begin
for i:=1 to n do
read(a[i]);
min:=a[1];
max:=a[1];
for i:=2 to n do begin
if min>a[i] then min:=a[i];
if maxend;
s:=min+max;
write( s= ’, s);
end.

Задание 5. Напишите программу, которая определяет позицию первого отрицательного элемента некоторого целочисленного массива.

Program tren5;
const n=10;
var
a: array [1..n] of integer;
i, min, max, s :integer;
begin
for i:=1 to n do
read(a[i]);
for i:=1 to n do begin
if a[i]<0 then begin
write(Позиция первого отрицательного элемента - ’, i);
i:=n+1;end;end;
writeln;
end.

Задание 6. Дана последовательность из n вещественных чисел. Вычислите сумму тех элементов последовательности, номера которых совпадают со значениями элементов последовательности.

Program tren6;
var
a:array[1..100] of real;
i, n, :integer; s:real;
begin
s:=0;
writeln(Введите количество элементов в массиве: ’);
readln(n);
for i:=1 to n do
read(a[i]);
for i:=1 to n do
if a[i]=i then s:=s+a[i];
write(s =’, s);
end.

Задание 7. Даны натуральное число n и последовательность А1, А2, А3 , . . АN. В данной последовательности определить число соседств двух положительных чисел.

Program tren7;
var
a:array[1..100] of integer;
i, n, k :integer;
begin
readln(n);
for i:=1 to n do
read(a[i]);
k:=0;
for i:=1 to n do
if (a[i]>0) and (a[i+1]>0) then k:=k+1;
writeln(Количество соседств двух положительных чисел - ’, k);
end.

Задание 8. Найти сумму всех элементов квадратной матрицы, расположенных по главной диагонали и выше её.

Program tren8;
var
a:array[1..30,1..30] of integer;
i, j, s, n :integer;
begin
readln(n);
randomize;
for i:=1 to n do
for j:=1 to n do
a[i,j]:=random(5);
for i:=1 to n do begin
for j:=1 to n do write(a[i,j]:3);
writeln;
end;
for i:=1 to n do
for j:=i+1 to n do write(a[i,j]:3);


Задание 9. Дана вещественная матрица размером n * m. вывести номера столбцов, содержащих отрицательные элементы. Если таких столбцов нет, то выводить сообщение «В столбце с данным номером отрицательных элементов нет или не все элементы «отрицательные».

Program tren9;
const n=10; m=10;
var
a: array [1..n,1..m] of integer;
I , j, y :integer;
begin
for i:=1 to n do
for j:=1 to m do
a[i,j]:=random(100)-55;
for j:=1 to m do begin
y:=0;
for i:=1 to n do
if a[I,j]<0 then inc(y);
if y=n then writeln(Номер столбца, в котором все элементы отрицательные, = , = j) else writeln(В столбце ’, j , нет отрицательных элементов или не все элементы отрицательные ’);
end; end.

Задание 10. Найти сумму элементов третьего столбца некоторой матрицы.

Program tren10;
var
a:array[1..30,1..30] of integer;
i, j, s, n, m :integer;
begin
readln(n, m);
randomize;
for i:=1 to n do
for j:=1 to m do
a[i,j]:=-random(9)+5;
for i:=1 to n do begin
for j:=1 to m do write(a[i,j]:3);
writeln;
end;
for i:=1 to n do
s:=s+a[i,j];
writeln( s= , s);
end.

Контрольные задания13 TC "Контрольные задания" \f C \l "4" 15
Задание 1. Поменяйте местами наибольший и наименьший элементы одномерного массива.

Program k1;
const n=10;
var
a:array[1..n] of integer;
min, max, t, I , Nmin, Nmax: integer;
begin
for i:=1 to n do
read(a[i]);
min:=a[1];
Nmin:=1;
max:=a[1];
Nmax:=1;
for i:=2 to n do
begin
if min>a[i] then begin
min:=a[i];
Nmin:=I;
end;
if maxmax:=a[i];
Nmax:=I;
end;
end;
t:=a[Nmin];
a[Nmin]:=a[Nmax];
a[Nmax]:=t;
for i:=1 to n do
write(a[i]);
end.

Задание 2. Найдите сумму элементов одномерного массива, расположенных за максимальным элементом.

Program k2;
const n=10;
var
a: array [1..n] of integer;
max, Nmax, i: integer;
s: longint;
begin
for i:=1 to n do read(a[i]);
max:=a[1];
Nmax:=1;
for i:=2 to n do
if max max:=a[i];Nmax:=I;
end;
if Nmax=n then s:=0 else
for i:=Nmax+1 to n do s:=s+a[i];
writeln(s);
end.

Задание 3. Найдите сумму элементов одномерного массива, заключённых между наибольшим и наименьшим элементами массива. Предполагается, что массив содержит только один минимальный и только один максимальный элементы.

Program k3;
const n=10;
var
a: array [1..n] of integer;
max, Nmax, i, min, Nmin: integer;
s: longint;
begin
for i:=1 to n do read(a[i]);
min:=a[1];
Nmin:=1;
max:=a[1];
Nmax:=1;
for i:=2 to n do begin
if min > a[i] then begin
min:=a[i];Nmin:=i;
end;
if maxend;
end;
if abs (Nmin-Nmax)=1 then s:=0 else
if Nmin>Nmax then
for i:=Nmax+1 to Nmin-1 do s:=a[i]
else
for i:=Nmin+1 to Nmax-1 do s:=s+a[i];
write(s);
end.

Задание 4. Дан массив ненулевых целых чисел. определите, сколько раз меняется знак элементов при его просмотре. Например, в массиве {-1, 6, 67, -9, -2, 34} знак меняется три раза.

Program k4;
const n=10;
var
a: array [1..n] of integer;
i, s: integer;
begin
for i:=1 to n do
read(a[i]);
for i:=1 to n-1 do
if (a[i]*a[i+1]<0) then inc(s);
write(s);
end.


Задание 5. Дан целочисленный массив температур за месяц. Определите дни, когда температура была выше средней температуры месяца.
Program k5;
const n=30;
var
t: array [1..n] of integer;
i, s: integer; sr:real;
begin
s:=0;
for i:=1 to n do begin
read(t[i]);
s:=s+t[i];
end;
sr:=s/n;
for i:=1 to n-1 do
if t[i]>sr then writeln(i);
end.

Задание 6. Дан целочисленный массив температур за месяц. Определите день, когда температура была наиболее близкой к средней температуре месяца.

Program k6;
const n=30;
var
t: array [1..n] of integer;
i, s? min, Nmin: integer;
sr:real;
begin
s:=0;
for i:=1 to n do begin
read(t[i]);
s:=s+t[i];
end;
sr:=s/n;
for i:=1 to n do
t[i]:=abs(t[i]) - sr;
min:=t[1];
Nmin:=1;
for i:=2 to n do
if min>t[i] then begin
min:=t[i];
Nmin:=I;
end;
write(В ’, Nmin, -й день температура была близка к средней’)4
write(s);
end.


Задание 7. Дан целочисленный массив из 30 элементов. Элементы массива могут принимать значения от -100 до 100. Найти среднее значение элементов массива, превышающих значение 45.

Program k7;
const n=30;
var
a: array [1..n] of integer;
i, x, y : integer; s:real;
begin
x:=0;
y:=0;
for i:=1 to n do begin
readln(a[i]);
if a[i]>45 then begin
x:=x+a[i];
inc(y);
end;
end;
s:=x/y;
write(s=’, s:0:2);
end.


Задание 8. Дан массив целых чисел из n элементов (n>6). Найти четыре подряд идущих элемента, сумма, которых максимальна.
Program k8;
const n=30;
var
a: array [1..n] of integer;
i, Nmax: integer; max, s:longint;
begin
for i:=1 to n do
read(a[i]);
max:=a[1]+a[2]+a[3]+a[4];
Nmax:=1;
for i:=2 to n-3 do begin
s:=a[i]+a[i+1]+a[i+2]+a[i+3];
if max max:=s;Nmax:=i;
end;
end;
for i:=Nmax to Nmax+3 do
write(i,’ );
end.

Задание 9. Заданы значения элементов массива из N элементов. Элементы могут принимать значения от -40 до 80. Найти максимальный по модулю элемент массива.

Program k9;
const n=10;
var
a: array [1..n] of integer;
i, max, Nmax: integer;
begin
for i:=1 to n do
read(a[i]);
max:=abs(a[1]);
Nmax:=1;
for i:=2 to n do
if maxmax:=abs(a[i]);
Nmax:=I;
end;
writeln(a[Nmax]);
end.

Задание 10. Найти максимальное значение из сумм строк массива n*n.
Program k10;
const n=5;
var
a: array [1..n,1..n] of integer;
i, s, j, max: integer;
begin
for i:=1 to n do
for j:=1 to n do read(a[i,j]);
for i:=1 to n do begin
for j:=1 to n do write(a[i,j]:6);
writeln;
end;
for i:=1 to n do begin
s:=0;
for j:=1 to n do
s:=s+a[i,j];
if maxend;
writeln(max=’,max);
end.

Работа со строками13 TC "Работа со строками" \f C \l "3" 15

Особое место в языке ПАСКАЛЬ занимают массивы символов. Стандартный ПАСКАЛЬ допускает два способа хранения символьных массивов в памяти ЭВМ: распакованный и упакованный. Распакованные массивы символов хранятся в памяти ЭВМ по одному символу в машинном слове, упакованные по одному символу в байте. При описании упакованного массива символов используют служебное слово PACKED, например:

var MAS: Packed Array[1..20] of Char;

Описание распакованного массива символов имеет вид:

var M: Array[1..20] of char;

Для преобразования символьного массива из распакованной формы в упакованную и наоборот, из упакованной в распакованную, в язык ПАСКАЛЬ введены две стандартные функции Pack, UnPack.
Упакованный массив символов образует символьную строку. Символьная строка может быть либо строковой константой, либо строковой переменной. Строковая константа, или строка, представляет собой совокупность символов, заключенную в апострофы.
Строка - это элементарная конструкция языка ПАСКАЛЬ. Строковые константы могут входить в состав выражений. Как и числовые константы, они могут быть описаны в разделе описания констант.
Строковые переменные - это одномерные упакованные массивы символов, для описания которых в TURBO PASCAL введен тип String.
Например, если строка содержит до 30 символов, ее тип будет определен как
type s= String[30];

Длина строки не может содержать более, чем 255 символов.
В TURBO PASCAL определено понятие строки переменной длины, в этом случае ее описание задается как
type s= String;

Тип String без указания длины совместим со всеми типами строк. Особенностью строковых переменных является то, что к ним можно обращаться как к скалярным переменным, так и к массивам. Во втором случае применяется конструкция «переменная с индексом», что обеспечивает доступ к отдельным символам строки. При этом нижняя граница индекса равна 1. Отдельный символ строки совместим с типом Char. В памяти ЭВМ строка занимает количество байтов, на единицу большее ее длины. Нулевой байт строки содержит ее длину. Для строк определены операции присваивания, слияния (конкатенации) и сравнения.
Для сравнения строк применяются все операции отношения. Сравнение строк происходит посимвольно, начиная с первого символа. Строки равны, если имеют одинаковую длину и посимвольно эквивалентны. Строки могут быть элементами списка ввода - вывода, при этом записывается имя строки без индекса. При вводе строковых переменных количество вводимых символов может быть меньше, чем длина строки. В этом случае вводимые символы размещаются с начала строки, а оставшиеся байты заполняются пробелами. Если количество вводимых символов превышает длину строки, лишние символы отбрасываются.
Инициализация строк может производиться как с помощью типизированных констант:

const sName: String[9]= 'IBM PC/AT';

так и с использованием второй разновидности функции FillChar:

FillChar( var V; NBytes: Word; C: Char );

например:

FillChar(A, SizeOf(A), '0');

Для работы со строками в TURBO PASCAL включены процедуры и функции, которые обеспечивают редактирование и преобразование строк.

Процедуры и функции для работы со строками13 TC "Процедуры и функции для работы со строками" \f C \l "3" 15
При работе со строками, как правило, возникает необходимость выполнять их копирование, вставку, удаление или поиск. Для эффективной реализации этих действий в Паскале предусмотрены стандартные процедуры и функции. Они кратко описаны ниже.
Функция Concat (s1, s2, ..., sn) возвращает строку, являющуюся слиянием строк s1, s2, ..., sn.
Функция Copy (s, start, len) возвращает подстроку длиной len, начинающуюся с позиции start строки s.
Процедура Delete (s, start, len) удаляет из строки s, начиная с позиции start, подстроку длиной len.
Процедура Insert (subs, s, start) вставляет в строку s подстроку subs, начиная с позиции start.
Функция Length (s) возвращает фактическую длину строки s, результат имеет тип byte.
Функция Pos (subs, s) ищет вхождение подстроки subs в строку s и возвращает номер первого символа subs в s или нуль, если subs не содержится в s.
Процедура Str (x, s) преобразует числовое значение x в строку s, при этом для x может быть задан формат, как в процедурах вывода write и writeln.
Процедура Val (s, x, errcode) преобразует строку s в значение числовой переменной x, при этом строка s должна содержать символьное представление числа. В случае успешного преобразования переменная errcode равна нулю. Если же обнаружена ошибка, то errcode будет содержать номер позиции первого ошибочного символа, а значение x не определено.
Рассмотрим на данную тему, наиболее часто предлагаемую задачу, которую решим несколькими способами:
Задача.
Написать программу, которая подсчитывает во введенной с клавиатуры строке текста, сколько раз встречается каждый из символов.
Решение.
Решение представим на языке программирования Паскаль.
Способ 1.
В поставленной задаче основная проблема – избежать повторного подсчета при очередном проходе уже подсчитанных символов. Поэтому очевидно, что введенную строку текста можно сначала отсортировать по возрастанию, а уже затем подсчитывать символы. В отсортированной строке необходимо будет отслеживать тот момент, когда следующий сравниваемый символ будет отличаться от текущего,- в этом случае выводим текущий символ и число его встречаемости. После этого переходим к следующему символу и т.д.
Program Prim5_1;
Uses Crt;
var
St, vSt: string;
S, I, j; integer;
Ch:char;
begin
clrscr;
writeln(Введите строку текста’);
readln(St);
vSt:=St;
for i:=1 to length(St) do
for j:=1 to length(St) do
if vSt[i]begin
ch:=vSt[j];
vSt[j]:=vSt[i];
vSt[i]:=Ch;
end;
Ch:=vSt[1];
s:=1;
for i:=2 to length(St) do
if Ch=vSt[i] then S:=S+1 else
begin
writeln(Ch,’ - ,S);
Ch:=vSt[i];
S:=1;
end;
writeln(Ch,’ - ,S);
while not KeyPressed do;
end.
Способ 2.
Берём символ (исходный, позиция i) и ищем такой же среди всех последующих. Как только таковой находится, удаляем его из найденной позиции и записываем целиком с исходным символом. ,При этом необходимо иметь в виду, что очередной проход строки нужно будет начинать с символа, который расположен в позиции, относительно позиции исходного символа на число его встречаемости.
Program Prim5_2;
Uses Crt;
var
St: string;
S, I, j; integer;
begin
clrscr;
writeln(Введите строку текста’);
readln(St);
i:=1;
j:=2;
while i<=length(St) do
begin
s:=1;
while j<= length(St) do
begin
if St[i]=St[j] then’
begin
S:=S+1;
Delete(St,j,1);
Insert(St[i],St,i+1);
end;
j:=j+1;
end;
writeln(St[i],’ - ,S);
i:=i+1;
j:=j+1;
end;
writeln(St);
while not KeyPressed do;
end.
Способ 3.
Берём символ (исходный, позиция i) и ищем такой же среди всех последующих. Как только таковой находится, считаем его и удаляем из найденной позиции. В итоге после первого прохода в строке не останется символов, аналогичных исходному (и самого исходного символа тоже). После этого процесс повторяется, пока строка не станет нулевой длины, т.е. не будут подсчитаны все символы.
Program Prim5_3;
Uses Crt;
var
St: string;
S, i: integer;
VSt:char;
begin
clrscr;
writeln(Введите строку текста’);
readln(St);
while length(St)>0 do begin
s:=0;
i:=1;
vSt:=St[1];
while i<=length(St) do
if vSt=St[i] then begin
S:=S+1;
Delete(St,I,1);
end
else i:=i+1;
if S>0 then writeln(vSt,’ - ,S);
end;
while not KeyPressed do;
end.
Способ 4
Здесь предлагается для очередного исходного символа вначале проверять, были ли такие же символы в позициях левее исходной. Если такие символы были (k=1) значит, они уже были подсчитаны на предыдущих проходах и исходный символ нужно пропустить. Если же таких символов не было (k=0), значит, исходный символ ещё не был подсчитан и его необходимо подсчитать – начиная с его позиции до конца строки.
Program Prim5_4;
Uses Crt;
var
St: string;
S, i, j,k: integer;
begin
clrscr;
writeln(Введите строку текста’);
readln(St);
for i:=1 to length(St) do
begin
k:=0;
for j:=1 to i-1 do
if St[i]=St[j] then k:=1;
if k=0 then
begin
S:=0;
for j:=i to length(St) do
if St[i]=St[j] then S:=S+1;
writeln(St[i],’ - ,S);
end;
end;
while not KeyPressed do;
end.
Способ 5
В данном случае для учёта того факта, что символ уже подсчитан, используется вспомогательный массив из 255 элементов. Первоначально такой массив заполнен нулями. В ходе подсчёта элемент массива с индексом, равным позиции подсчитываемого символа заменяется единицей. При этом при подсчёте символов смотрим, каково значение элемента массива с индексом, равным позиции текущего символа. Если значение равно 0, значит, символ ещё не был подсчитан и его необходимо подсчитать; в противном случае символ пропускается.
Program Prim5_5;
Uses Crt;
var
St: string;
S, i, j,k: integer;
mas:array[1..255] of byte;
begin
clrscr;
writeln(Введите строку текста:’);
readln(St);
for i:=1 to 255 do
mas[i]:=0;
S:=0;
for j:=i to length(St) do begin
if (St[i]=St[j]) and (mas[j]=0) then begin
S:=S+1;
mas[j]:=1;
end;
if S<>0 then begin
writeln(St[i],’ - ,S);
S:=0;
end;
end;
while not KeyPressed do;
end.

Способ 6.
Данный способ является самым простым и оптимальным. Однако его используют крайне редко. Способ не требует дополнительного комментария и в приведённой ниже реализации.
Program Prim5_6;
Uses crt;
Var i, S :integer;
St, Chr :string;
Begin
Clrscr;
writeln(Введите строку текста:’);
readln(St);
for i:=1 to 255 do begin
S:=0;
for j:=1 to length(St) do
if Chr[i]=St[j] then S:=S+1;
if s<>0 then writeln (Chr[i],’ - ,S);
end;
while not KeyPressed do;
end.

7. Ввести строку из n символов латинского алфавита (n<30). Расположить их по алфавиту. Воспользуемся тем, что буквы латинского алфавита 'A' – 'Z', 'a' –'z' имеют коды, значения которых возрастают. При этом для решения задачи можно применять алгоритм сортировки «пузырьком». Program Prim5_7;
var  s : string;  sr : char;  n, i, k : integer; Begin  writeln('Введите строку');  readln(s);  n := length(s);  for k := 1 to n-1 do   for i := 1 to n-k do     if s[i]>s[i+1]then       begin         sr :=s[i];         s[i] := s[i+1];         s[i+1] := sr;      end;  writeln('Строка с упорядоченными символами:');  writeln(s); End.
6. Записи в языке Паскаль13 TC "Записи в языке Паскаль" \f C \l "3" 15
Классификация типов данных в Паскале.13 TC "Классификация типов данных в Паскале." \f C \l "4" 15  
Все типы данных языка Паскаль условно можно разделить на стандартные и пользовательские в соответствии с тем, как они определены. Стандартные типы являются встроенными, зависят от реализации языка и не требуют описания в разделе типов. Пользовательские определяются программистом на основе стандартных типов и предназначаются для решения какой-либо конкретной задачи.
Кроме того, все типы можно разделить на простые и структурированные.
Переменные простых типов могут в каждый момент времени принимать только одно значение, определенное множеством значений типа. К простым типам относятся integer(+ все разновидности), real, boolean, char.  
Структурированные типы характеризуются тем, что переменные, относящиеся к ним, принимают сложное, составное значение, представляющее собой набор значений одного или нескольких типов. К сложным типам относятся string (набор значений типа char), array (набор значений базового типа), file или text (набор значений одного или разных типов) и record.  
Определение записи. Вариантная часть.13 TC "Определение записи. Вариантная часть." \f C \l "4" 15  
Запись – это сложный, структурированный тип, который представляет собой совокупность данных различного типа, имеющих прямое и характеризующее отношение к какому-либо объекту. Запись есть единица информации о предмете с точки зрения его существенных свойств.  
Количество элементов записи строго фиксировано. Каждый элемент записи называется полем. Чаще всего при задании типа запись поля принадлежат разным типам (в противном случае использование записи теряет смысл, т.к. можно вполне обойтись массивом). Названия полей в одной записи должны быть различны, но имена полей внутри различных записей могут совпадать.  
В языке Паскаль для обозначения типа записей служит идентификатор record.  
<идентификатор типа> = record     <поле 1> : <тип значений поля 1>;     . . .     <поле k> : <тип значений поля k>;     [вариантная часть]     end;
Пример.  
1. Составить описание книг по следующим характеристикам: код классификации, автор, название, аннотация, год издания, стоимость, количество страниц.  


 type book = record     kod : string[15];     avtor, nazvanie, annot : string;     god : word;     stoim : real;     stranic ; integer;     end;
2. Составить описание а) любой даты календаря; б) личных данных человека (имя, фамилия, дата рождения, место рождения); в) личных данных гражданина иностранного государства.  

   type date = record     year : word;     month : 1..12;     day : 1..31;     end;     person_ros = record     imya, fam : string[40];     data_r : date;     mesto_r : string;     end;     person_ino = record    imya, fam : string[40];     data_r : date;     strana : string[30];     data_entry : date;     data_exit : date;     end;
Если затем в программе объявить следующие переменные:  
var x : date; y: person_ros; z : person_ino;     


то в теле программы в разделе операторов будут доступны следующие переменные: x. year;      y. imya;      z. imya; x. month;   y. fam;      z. fam; x. day;   y. data_r;      z. data_r;    y. mesto_r;      z. strana;                z. data_entry;                z. data_exit; Система никогда не перепутает переменные y.data_r и z.data_r, т.к. переменные y и z принадлежат к разным типам. Кроме того, в программе будут известны переменные: y.data_r.year; y.data_r.month и т.д.
Идентификаторы полей внутри записи могут быть использованы в качестве имен других переменных, т.е. в программе могут быть объявлены переменные data_r, fam, day и т.п., которые будут абсолютно самостоятельными.  
3. Во втором примере можно существенно упростить описание второго и третьего типов, если использовать записи с вариантной частью:  
person = record           imya, fam : string[40];   описание фиксированной части (всегда располагается вначале)       data_r : date;             case citizen : boolean of   | |вариантная часть в каждой записи |может быть только одна. Обычно |задается оператором варианта case. |          true : mesto_r : string;             false : strana : string[30];             data_entry : date;             data_exit : date;          end;   однозначно действует на окончание описания типа и на окончание case.   
Массив записей. Оператор присоединения.13 TC "Массив записей. Оператор присоединения." \f C \l "4" 15  
Запись, как единица информации, описывает один объект. Решение конкретных задач, как правило, требует объединения информации в более крупные множества. В таких случаях используются более сложные структуры типа массив записей или файл записей.  
Массив записей представляет собой массив, базовым типом элементов которого является запись.
Пример.   
Описание студентов одной группы может выглядеть следующим образом:  
type gruppa = array[1..30] of person_ros; var student: gruppa; k : integer; . . . k:=3; for i:=a to b do    begin    gotoxy(1,k); readln(sdudent[i].imya);    gotoxy(15,k); readln(sdudent[i].fam);    gotoxy(41,k); readln(sdudent[i].mesto_r);    k:=k+3;    end; Этот фрагмент программы может быть записан иначе, если использовать оператор присоединения: k:=3; for i:=a to b do    with student[i] do    begin    gotoxy(1,k); readln(imya);    gotoxy(15,k); readln(fam);    gotoxy(41,k); readln(mesto_r);    k:=k+3;    end;
Если один оператор или группа операторов, процедур, функций и т.д. обрабатывает одну переменную типа запись, то можно не указывать каждый раз имя этой переменной, а указывать только имена полей, если   эта группа операторов обрамлена оператором сокращенной записи (или оператором присоединения).
   with <список идентификаторов> do    <оператор>;
Список идентификаторов может содержать произвольное число переменных комбинированного типа запись. Если имена полей этих переменных уникальны, то никаких проблем не возникает. В противном случае действует правило:
запись with <имя 1>, <имя 2>, , <имя n> do <оператор>; эквивалентна конструкции    with <имя 1> do    with <имя 2> do    . . .       with <имя n> do    <оператор>;
Примеры задач с использованием комбинированного типа «Запись»
1. Сформировать базу данных, состоящую из 10 записей по 4 поля в каждой: фамилия, имя, год рождения и телефон. Вывести на экран записи, в которых содержатся сведения об Иванове.
Program Prim6_1;
Uses crt;
Type Person=record
Sname,name:string[14];
gr:integer;
Tele:string[8];
End;
Var spisok:array[1..10] of person;
I:integer;
Begin
For i:=1 to 10 do begin
With spisok[i] do
Begin
Writeln(Фамилия’);
Readln(sname);
Writeln(Имя’);
Readln(name);
Writeln(Год рождения’);
Readln(gr);
Writeln(Телефон’);
Readln(tele);
End;
Writeln(Список Фамилия Имя Год рождения Телефон’);
For i:=1 to 10 do begin
With spisok[i] do
If sname=’Иванов’ then
Writeln(sname:15,name:10,gr:8,tele:10);
Writeln;
End;
Readln;
End.
2. Из ведомости 3-х студентов с их оценками ( порядковый  номер,  Ф.И.О. и три оценки) определить количество отличников и средний балл каждого студента.
Program Prim6_2; Type wed = record {Тип wed включает 3 поля: n, fio, bal} n : integer ; fio : string[40] ; bal : array [1..3] of integer {Поле bal – массив из 3 оценок } end; Var spisok : wed ; {Запись spicok типа wed} i, j, kol, s : integer; sr : real; Begin kol:=0; {kol- количество отличников} With spisok do {with присоединяет имя записи spisok ко всем } For i:=1 to 3 do { полям внутри цикла For по i } begin n:=i; Write (' Vvedite FIO # ', i ,' '); Readln (fio); s:=0; For j:= 1 to 3 do begin write ( 'Vvedite ocenky: ' ); readln ( bal [j] ); s := s+ bal [j]; end; if s=15 then kol:=kol+1; {подсчет количества отличников} sr := s/3; writeln ( fio, ', Sredniy bal = ', sr:4:1); end; writeln ( ' Kolichestvo otlichnikov = ', kol ); readln; end.
3. В массиве хранятся данные об учениках класса: школа, фамилия, класс. Вывести список учеников, которые учатся в восьмом классе.
Program Prim6_3; Uses   Crt; Type Uchenik=record       Shkola : integer;       Fam : string[15];       Klass : integer;     end; Var   I,n,a,j : integer;   Massiv : array[1..100] of Uchenik; Рrocedure Poisk; Begin   for i:=1 to n do     if massiv[i].klass=8       then         with massiv[i] do           writeln(Shkola:4,' ',Fam:15,' ',klass); End; Begin   ClrScr;   writeln('Введите число учеников ');   write('->');   read(n);   for i:=1 to n do     begin       writeln('Введите через пробел номер школы и фамилию ученика ');       write('->');       with massiv[i] do         begin           readln(Shkola,Fam);           write('Введите класс ученика (только число) ->');           read(Klass);         end;     end;   writeln('Ученики 8-ых классов:');   writeln('Школа Фамилия Класс');   writeln('---------------------------------');   Poisk;
Readln;
End.
7. Дерево игры. Поиск выигрышной стратегии13 TC "Дерево игры. Поиск выигрышной стратегии" \f C \l "2" 15.
Что нужно знать:
в простых играх можно найти выигрышную стратегию, просто перебрав все возможные варианты ходов соперников
для примера рассмотрим такую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку
первый игрок может убрать одну спичку (в этом случае их останется 4), или сразу 2 (останется 3), эти два варианта можно показать на схеме:
13 SHAPE \* MERGEFORMAT 1415
если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:
13 SHAPE \* MERGEFORMAT 1415
если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:
13 SHAPE \* MERGEFORMAT 1415
простроенная схема называется «деревом игры», она показывает все возможные варианты, начиная с некоторого начального положения (для того, чтобы не загромождать схему, мы не рисовали другие варианты, если из какого-то положения есть выигрышный ход)
в любой ситуации у игрока есть два возможных хода, поэтому от каждого узла этого дерева отходят две «ветки», такое дерево называется двоичным (если из каждого положения есть три варианта продолжения, дерево будет троичным)
проанализируем эту схему; если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока
кто же выиграет при правильной игре? для этого нужно ответить на вопросы: 1) «Может ли первый игрок выиграть, независимо от действий второго?», и 2) «Может ли второй игрок выиграть, независимо от действий первого?»
ответ на первый вопрос – «да»; действительно, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу
ответ на второй вопрос – «нет», потому что если первый игрок сначала убрал одну спичку, второй всегда проиграет, если первый не ошибется
таким образом, при правильной игре выиграет первый игрок; для этого ему достаточно первым ходом убрать всего одну спичку
в некоторых играх, например, в рэндзю (крестики-нолики на бесконечном поле) нет выигрышной стратегии, то есть, при абсолютно правильной игре обоих противников игра бесконечна (или заканчивается ничьей); кто-то может выиграть только тогда, когда его соперник по невнимательности сделает ошибку
полный перебор вариантов реально выполнить только для очень простых игр; например, в шахматах сделать это за приемлемое время не удается (дерево игры очень сильно разветвляется, порождая огромное количество вариантов)
в демо-вариантах ЕГЭ рекомендуется записывать дерево в виде таблицы (фактически, повернув его «на бок»), так получается более компактно:

1 игрок
2 игрок
1 игрок

5
4
3
1



2
1


3
1


Пример задания13 TC "Пример задания" \f C \l "3" 15:
Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение (вариант 1, полное дерево игры, «поиск в ширину»13 TC "полное дерево игры, \«поиск в ширину\»" \f C \l "4" 15):
из каждой ситуации в этой игре возможно три продолжения, поэтому дерево получается троичным
по теореме Пифагора расстояние L от точки с координатами (x,y) до начала координат – это квадратный корень из суммы квадратов координат: 13 EMBED Equation.3 1415; чтобы избавиться от вычисления квадратного корня, нужно перейти от заданного условия 13 EMBED Equation.3 1415 к равносильному условию в целых числах: 13 EMBED Equation.3 1415
в начальный момент 13 EMBED Equation.3 1415, условие не выполнено

I игрок

(5,2) 29
(8,2) 68


(5,5) 50


(5,6) 61

первый игрок имеет три варианта хода, запишем их в таблицу, указывая для каждого положения координаты (в скобках) и значение 13 EMBED Equation.3 1415(мелким шрифтом);
видим, что одним ходом первый игрок никак не может выиграть (для всех вариантов 13 EMBED Equation.3 1415)
построим следующий столбец таблицы (ход второго игрока):

I игрок
II игрок

(5,2) 29
(8,2) 68
(11,2) 125



(8,5) 89



(8,6) 100


(5,5) 50
(8,5) 89



(5,8) 89



(5,9) 106


(5,6) 61
(8,6) 100



(5,9) 106



(5,10) 125


второй игрок тут тоже никак не может выиграть (для всех вариантов 13 EMBED Equation.3 1415);
обратите внимание на варианты, выделенные в таблице серым фоном: они уже встречались выше в этом же столбце (хотя получены в результате другой последовательности ходов), поэтому дальше не стоит их рассматривать отдельно
строим таблицу для третьего хода (I-й игрок); для сокращения записи не будем выписывать все возможные ходы, если мы нашли выигрышный ход из этой позиции (выделен синим фоном):

I игрок
II игрок
I игрок

(5,2) 29
(8,2) 68
(11,2) 125
(14,2) 200



(8,5) 89
(11,5) 146




(8,8) 128




(8,9) 145



(8,6) 100
(11,6) 157




(8,9) 145




(8,10) 164


(5,5) 50
(8,5) 89




(5,8) 89
(5,12) 169



(5,9) 106
(5,12) 169


(5,6) 61
(8,6) 100




(5,9) 106




(5,10) 125
(5,13) 196

видим, что в некоторых случаях первый игрок может выиграть уже на втором ходу, однако это не гарантируется, значит, нельзя утверждать, что первый игрок всегда выиграет
легко проверить, что во всех оставшихся позициях (если первый не выиграл) второй игрок выигрывает своим следующим ходом:

I игрок
II игрок
I игрок
II игрок

(5,2) 29
(8,2) 68
(11,2) 125
(14,2) 200




(8,5) 89
(11,5) 146
(14,5) 221




(8,8) 128
(11,8) 185




(8,9) 145
(11,9) 202



(8,6) 100
(11,6) 157
(14,6) 232




(8,9) 145





(8,10) 164
(11,10) 221


(5,5) 50
(8,5) 89





(5,8) 89
(5,12) 169




(5,9) 106
(5,12) 169



(5,6) 61
(8,6) 100





(5,9) 106





(5,10) 125
(5,13) 196


теперь осталось выполнить самое главное – сделать анализ этой таблицы и определить, кто же выиграет, если оба играют лучшим для себя образом
из таблицы следует, что второй игрок выигрывает (своим вторым ходом), если ему удастся свести ситуацию к положению (8,5) или (8,6)
далее замечаем, что при любом ходе первого игрока второй может добиться нужной ему позиции (показаны варианты в зависимости от первого хода):
(8,2)(8,5)
(8,2)(8,6)
или
(5,5)(8,5)
или
(5,6)(8,6)

и выиграть вторым ходом
таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть.
Возможные ловушки и проблемы:
нужно уметь правильно считать, часто в работах встречаются арифметические ошибки, которые приводят к неверному решению
таблица получается довольно громоздкой, чтобы не запутаться, лучше оставлять в ней только те данные, которые действительно влияют на решение (как мы делали выше)
обнаружив, что первый игрок выигрывает в некоторых вариантах на 2-ом ходу, можно обрадоваться и записать неверный ответ (помните, что факт выигрыша в каких-то случаях, еще не означает, что этот игрок выиграет всегда)
необходимо проверить, при любом ли ходе первого игрока второй игрок (в нашей задаче) может получить нужную для себя ситуацию; например, мог быть вариант, когда для первого хода (5,5) при любом ходе второго игрока выигрывал первый, это означало бы, что при правильной игре первый всегда победит известные примеры задач ЕГЭ этого типа показывают, что второй игрок почему-то выигрывает чаще (, но на это нельзя рассчитывать, именно в вашем варианте может быть все по-другому
Как правильно оформить решение:
нужно обязательно написать ответ СЛОВАМИ, например, «Выиграет игрок, который делает второй ход»
нужно обязательно привести ВСЕ варианты ходов первого игрока и доказать, что во всех случаях у второго (в данной задаче!) есть выигрышный ход
в решении должна быть СЛОВАМИ описана стратегия игры второго игрока «как он должен играть, чтобы выиграть)
рекомендуется записывать ходы в таблицу, точно совпадающую с той, которая приводится в официальном решении демо-варианта; для эксперта этот вариант будет гарантированно понятен и привычен
Итак, у нас получилось, что выигрывает второй игрок. В ответе на каждом ходу нужно привести все возможные ходы первого игрока, и на каждый из этих ходов дать выигрышный ответ второго. В первом столбце стандартной таблицы записываем начальную позицию. Из этого положения у I-ого игрока есть 3 варианта хода, записываем их во второй столбец:

1-й ход
2-й ход
3-й ход
4-й ход

стартовая позиция
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход

(5,2) 29
(8,2) 68





(5,5) 50





(5,6) 61




Обратите внимание, что мы перечислили все возможные ходы I-ого игрока, как и требуется.
Теперь на каждый возможный ход I-ого игрока во втором столбце записываем выигрышный ответ II-ого, то есть, такой ответ, который приводит второго к выигрышу, и подчеркиваем его (или как-то выделяем по-другому, чтобы показать, что это выигрышный ход):

1-й ход
2-й ход
3-й ход
4-й ход

стартовая позиция
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход

(5,2) 29
(8,2) 68
(8,5) 89




(5,5) 50
(8,5) 89




(5,6) 61
 (8,6) 100



В четвертом столбце нужно перечислить все варианты (обязательно все!) второго хода I-ого игрока в ответ на указанный выигрышный ход второго:

1-й ход
2-й ход
3-й ход
4-й ход

стартовая позиция
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход

(5,2) 29
(8,2) 68
(8,5) 89
(11,5) 146





(8,8) 128





(8,9) 145



(5,5) 50
(8,5) 89
(11,5) 146





(8,8) 128





(8,9) 145



(5,6) 61
 (8,6) 100
(11,6) 157





(8,9) 145





(8,10) 164


Остается добавить в последний столбец (один!) выигрышный ход II-ого игрока. Обратите внимание, что для выигрывающего игрока достаточно указать только один выигрышный ход, а для проигравшего нужно рассмотреть все ходы на каждом шаге.

1-й ход
2-й ход
3-й ход
4-й ход

стартовая позиция
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход
I-й игрок (все варианты хода)
II-ой игрок, выигрышный ход

(5,2) 29
(8,2) 68
(8,5) 89
(11,5) 146
(14,5) 221




(8,8) 128
(11,8) 185




(8,9) 145
(11,9) 202


(5,5) 50
(8,5) 89
(11,5) 146
(14,5) 221




(8,8) 128
(11,8) 185




(8,9) 145
(11,9) 202


(5,6) 61
 (8,6) 100
(11,6) 157
(14,6) 232




(8,9) 145
(11,9) 202




(8,10) 164
(11,10) 221

После таблицы обязательно необходимо описать стратегию игры словами:
«Выигрывает игрок, который делает второй ход. Таблица содержит все варианты хода первого игрока. Из нее видно, что при любом ходе первого игрока у второго есть ход, приводящий к победе».
За что снимают баллы:
если вы правильно указали выигрывающего игрока, но не привели никакого обоснования, эксперт поставит 0 баллов
не описана стратегия выигрывающего игрока (как именно ему нужно ходить)
не проведен полный анализ возможных ходов обоих игроков (рассмотрены не все случаи ответных ходов)

Решение (вариант 2, неполное дерево игры, «поиск в глубину»13 TC "неполное дерево игры, \«поиск в глубину\»" \f C \l "4" 15):
в отличие от предыдущего способа, будем строить дерево «в глубину», то есть доходить до выигрыша одного из игроков, и только потом переходить к следующей ветке
рассмотрим первый ход первого игрока:


I игрок

(5,2) 29
(8,2) 68

теперь рассматриваем первый возможный ответ второго игрока (увеличение x на 3):

I игрок
II игрок

(5,2) 29
(8,2) 68
(11,2) 125




видим, что в этой ситуации следующим ходом I-й игрок выигрывает:

I игрок
II игрок
I игрок

(5,2) 29
(8,2) 68
(11,2) 125
(14,2) 200




таким образом, эту ветку дерева мы рассмотрели до конца
теперь анализируем второй возможный ответ II-ого игрока:

I игрок
II игрок
I игрок

(5,2) 29
(8,2) 68
(11,2) 125
(14,2) 200



(8,5) 89






перебор вариантов показывает, что следующим ходом первый игрок никак не может выиграть, таблице перечислены все его возможные ходы:

I игрок
II игрок
I игрок

(5,2) 29
(8,2) 68
(11,2) 125
(14,2) 200



(8,5) 89
(11,5) 146




(8,8) 128




(8,9) 145







в то же время своим следующим ходом II-й игрок выигрывает при любом ответе I-ого, увеличивая координату x на 3:

I игрок
II игрок
I игрок
II игрок

(5,2) 29
(8,2) 68
(11,2) 125
(14,2) 200




(8,5) 89
(11,5) 146
(14,5) 221




(8,8) 128
(11,8) 185




(8,9) 145
(11,9) 202







таким образом, если II-й игрок свел ситуацию к позиции (8,5), он выиграет, потому что при любом ответе I-го игрока у второго есть выигрышный ход; поэтому (8,5) – это выигрышный ход второго игрока в том случае, когда первый игрок походил (8,2)
заметим, что в позиции (8,2) у второго игрока есть еще один ход – (8,6), но его уже можно не рассматривать, поскольку мы уже нашли один выигрышный ход – (8,5), этого достаточно
теперь рассматриваем второй возможный ход первого игрока в исходной позиции:

I игрок

(5,2) 29
(5,5) 50




сразу замечаем, что второй игрок, увеличив y на 3, может своим ходом сразу свести игру к позиции (8,5), которая обеспечивает его выигрыш (см. выше), поэтому дальше эту ветку можно не рассматривать

I игрок
II игрок

(5,2) 29
(5,5) 50
(8,5) 89




остается третий возможный ход первого игрока из начального положения: (5,6)

I игрок

(5,2) 29
(5,6) 61




видим, что из положения (5,6) не удается свести игру к уже рассмотренной выигрышной позиции (8,5), поэтому нужно проверить все возможные ответы второго игрока и попытаться найти среди них выигрышный ход
чтобы максимально сократить перебор, сначала рассмотрим вариант хода второго игрока, который ближе всего к известной выигрышной позиции (8,5) – это ход (8,6):

I игрок
II игрок

(5,2) 29
(5,6) 61
(8,6) 100




проверяем все возможные ответы первого игрока и выясняем, что он не может выиграть сразу, одним ходом:

I игрок
II игрок
I игрок

(5,2) 29
(5,6) 61
(8,6) 100
(11,6) 157




(8,9) 145




(8,10) 164






а второй игрок своим следующим ходом всегда выигрывает, увеличивая x на 3:

I игрок
II игрок
I игрок
II игрок

(5,2) 29
(5,6) 61
(8,6) 100
(11,6) 157
(14,6) 232




(8,9) 145
(11,9) 202




(8,10) 164
(11,10) 221






поэтому (8,6) – это выигрышный ход второго игрока в ответ на первый ход (5,6)
таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть
остается только записать ответ в виде таблицы и текстового пояснения, как показано выше

Рекомендации:
этот способ решения позволяет очень удобно записывать промежуточные результаты на листике, даже не строя громоздкую таблицу
0 I игрок II игрок I игрок II игрок
(5,2) 29 (8,2) 68 (11,2) 125 (14,2) 200
(8,5) 89 (11,5) 146 (14,5) 221
(8,8) 128 (11,8) 185
(8,9) 145 (11,9) 202
(5,5) 50 (8,5) 89
(5,5) 50 (8,6) 100 (11,6) 157 (14,6) 232
(8,9) 145 (8,9) 202
(8,10) 164 (8,10) 221
тем не менее, окончательный ответ для эксперта желательно записать в виде «стандартной» таблицы и (обязательно!) следующего за ней текстового комментария

Решение (вариант 3, графический способ13 TC "графический способ" \f C \l "4" 15):
в задачах на движение фишки можно применить графический метод, немного измененный и упрощенный, в сравнении с оригинальным вариантом
обозначим начальное положение точки на плоскости белым кружком:

поскольку при каждом ходе координаты увеличиваются, можно рассматривать только первый квадрант плоскости; задача – очередным ходом выйти за границу, обозначенную красной линией
нанесем на плоскость точки, куда можно попасть за один ход, и обозначим их черными кружками:
13 SHAPE \* MERGEFORMAT 1415
дальше отметим все точки, в которые можно «допрыгнуть» за два хода; некоторые из этих точек позволяют следующим ходом «выпрыгнуть» за красную границу (или хотя бы на красную линию, например, в точку (12,5)), такие точки обозначим кружками с двойной границей – это выигрышные позиции
13 SHAPE \* MERGEFORMAT 1415
теперь отмечаем все новые (неотмеченные) точки, куда можно «допрыгнуть» за один ход из черных точек; все эти позиции выигрышные, то есть, следующим ходом очередной игрок выигрывает
13 SHAPE \* MERGEFORMAT 1415
ключевой момент: находим на плоскости черные точки, из которых ВСЕ ходы ведут к выигрышным позициям; в данном случае это точки (8,5) и (8,6) – это проигрышные позиции, поскольку ЛЮБОЙ очередной ход приводит в выигрышную позицию; обводим эти точки на рисунке рамкой:
13 SHAPE \* MERGEFORMAT 1415
теперь отмечаем двойной линией все точки, из которых можно сразу (за 1 ход) перейти (перевести игру) в одну из проигрышных (для соперника) позиций, это точки (5,5), (5,6) и (8,2)
13 SHAPE \* MERGEFORMAT 1415
все черные точки использованы, и получилось так, что ВСЕ возможные ходы первого игрока в начальной ситуации ведут в выигрышные позиции, то есть начальная позиция (5,2) – проигрышная, ее тоже можно обвести в красную рамку
таким образом, при правильной игре выиграет второй игрок, для этого при любом ходе первого игрока ему достаточно свести ситуацию к положению (8,5) или (8,6); такая возможность у него есть
теперь для каждого хода первого игрока нужно указать выигрышный ход второго, который переводит игру в проигрышную позицию

I игрок
II игрок

(5,2)
(8,2)
(8,5)


(5,5)
(8,5)


(5,6)
(8,6)

дальше, как и в предыдущих способах решения, обязательно нужно расписать все возможные ответы первого игрока (3-й ход) и выигрышные ходы второго игрока для этих вариантов
Возможные проблемы:
нужна клетчатая бумага
у вас может не быть циркуля, поэтому строить окружность придется по точкам
легко ошибиться, если есть точки на самой окружности или очень близко к ней
неудобно использовать при большом радиусе окружности (например, 35)
неудобно отмечать точки разными значками, легко запутаться
Пример2:Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или увеличивает на 4 число камней в одной из куч. Игрок, после хода которого общее число камней в двух кучах становится не менее 25, проигрывает. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение:
обратите внимание на выделенное слово в условии задачи – тот, кто получил 25 или больше камней в обоих кучках, проигрывает
как вынудить противника набрать 25 камней или больше? за 1 ход число камней увеличивается по меньшей мере на 3 (если в первой кучке еще 3 камня) или даже на 4, поэтому требуется своим очередным ходом сделать в двух кучках количество камней 22, 23 или 24 (если первая кучка уже содержит более 3-х камней, то можно и 21!)
применим «поиск в глубины», будем рассматривать возможные ходы, начиная с тех, при которых получается бульшая сумма (чтобы ветка быстрее закончилась)
рассмотрим первый ход первого игрока:

I игрок

(3,4) 7
(7,4) 11

теперь рассматриваем первый возможный ответ второго игрока:

I игрок
II игрок

(3,4) 7
(7,4) 11
(14,4) 18




в этой ситуации у I-го игрока есть выигрышный ход – такой, при котором все ответы II-го приводят к его проигрышу:

I игрок
II игрок
I игрок
II игрок

(3,4) 7
(7,4) 11
(14,4) 18
(14,8) 22
(28,8) 36 (
(18,8) 26 (
(14,16) 30 (
(14,12) 26 (






таким образом, эту ветку дерева мы рассмотрели до конца
теперь анализируем второй возможный ответ II-ого игрока и все ответы I-ого:

I игрок
II игрок
I игрок

(3,4) 7
(7,4) 11
(14,4) 18
(14,8) 22



(11,4) 15
(22,4) 26 (
(15,4) 19
(11,8) 19

из таблицы видим, что при ответе (22,4) игрок I проигрывает сразу; однако на два других хода II-й игрок может ответить так, что сам он не проиграет (сумма равна 23), а I-й игрок проиграет следующим ходом:

I игрок
II игрок
I игрок
II игрок
I игрок

(3,4) 7
(7,4) 11
(14,4) 18
(14,8) 22





(11,4) 15
(22,4) 26 (






(15,4) 19
(15,8) 23
(30,8) 38 (
(19,8) 27 (
(15,16) 31 (
(15,12) 27 (




(11,8) 19
(11,12) 23
(11,24) 35 (
(22,12) 34 (
(11,16) 27 (
(15,12) 27 (

из приведенной таблицы следует, что при первом ходе I-ого игрока (7,4) выиграет II-й – у него есть ход (11,4), который приводит к выигрышу (остальные возможные ответы можно уже не рассматривать!)
итак, I-й игрок не может ходить (7,4), поскольку при этом он проиграет; посмотрим, что будет при первом ходе (6,4): II-й может ответить (12,4), при одном из вариантов I-й проиграет сразу же:

I игрок
II игрок
I игрок

(3,4) 7
(6,4) 10
(12,4) 16
(24,4) 28 (
(16,4) 20
(12,8) 20

на оставшиеся два варианта ответа I-го игрока у II-го есть ход (16,8), который вынуждает I-го проиграть на следующем ходу

I игрок
II игрок
I игрок
II игрок
I игрок

(3,4) 7
(6,4) 10
(12,4) 16
(24,4) 28 (






(16,4) 20
(16,8) 24
(32,8) 40 (
(20,8) 28 (
(16,16) 32 (
(16,12) 26 (




(12,8) 20



таким образом, при первом ходе (6,4) также выигрывает II-й игрок
у I-го игрока остался еще один возможный первый ход – (3,8), проверим его; если этот ход окажется выигрышным, то в игре победит I-й игрок, если нет – то второй
если на (3,8) второй отвечает (3,16), I-й игрок может получить 23 камня в обеих кучах ходом (3,20) и выиграет:

I игрок
II игрок
I игрок
II игрок

(3,4) 7
(3,8) 11
(3,16) 19
(3,20) 23
(3,40) 43 (
(3,24) 27 (
(7,20) 27 (
(6,20) 26 (

однако, ответ II-ого (3,12) приводит к тому, что при любом ответе I-ого он проигрывает сразу или через один ход:

I игрок
II игрок
I игрок
II игрок
I игрок

(3,4) 7
(3,8) 11
(3,16) 19
(3,20) 23





(3,12) 15
(3,24) 27 (






(3,16) 19
(6,16) 22
(6,32) 38 (
(6,20) 26 (
(12,16) 28 (
(10,16) 26 (




(6,12) 18
(12,12) 24
(12,24) 36 (
(12,16) 28 (
(24,12) 36 (
(16,12) 28 (




(7,12) 19
(11,12) 23
(11,24) 35 (
(11,16) 27 (
(22,12) 34 (
(15,12) 27 (

таким образом, выигрывает II-й игрок; своим первым ходом ему нужно свести игру к позиции (11,4), (12,4) или (3,12), а вторым ходом – к одной из позиций (15,8), (16,8), (11,12), (12,12) или (6,16).
итоговая таблица, в которой указаны выигрышные ходы II-го игрока и все возможные ответы I-го игрока:

I игрок
II игрок
I игрок
II игрок
I игрок

(3,4) 7

(3,8) 11
(3,12) 15
(3,24) 27 (






(3,16) 19
(6,16) 22
(6,32) 38 (
(6,20) 26 (
(12,16) 28 (
(10,16) 26 (




(6,12) 18
(12,12) 24
(12,24) 36 (
(12,16) 28 (
(24,12) 36 (
(16,12) 28 (




(7,12) 19
(11,12) 23
(11,24) 35 (
(11,16) 27 (
(22,12) 34 (
(15,12) 27 (


(7,4) 11
(11,4) 15
(22,4) 26 (






(15,4) 19
(15,8) 23
(30,8) 38 (
(19,8) 27 (
(15,16) 31 (
(15,12) 27 (




(11,8) 19
(11,12) 23
(11,24) 35 (
(22,12) 34 (
(11,16) 27 (
(15,12) 27 (


(7,4) 11
(11,4) 15
(22,4) 26 (






(15,4) 19
(15,8) 23
(30,8) 38 (
(19,8) 27 (
(15,16) 31 (
(15,12) 27 (




(11,8) 19
(11,12) 23
(11,24) 35 (
(22,12) 34 (
(11,16) 27 (
(15,12) 27 (

Задачи для тренировки:
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, первой из которых 1, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 4, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в первой из которых 2, во второй – 3, в третьей – 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет по два камня в каждую из куч. Выигрывает игрок, после хода которого либо в одной из куч становится не менее 15 камней, либо общее число камней во всех трех кучах становится не менее 25. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Даны три кучи камней, содержащих соответственно 2,3 и 4 камня. За один ход разрешается или удвоить количество камней в меньшей куче (если их две – то в каждой из них), или добавить по 1 камню в каждую из всех трех куч. Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 4 камня. У каждого игрока неограниченно много камней. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число камней в 2 раза, или добавляет в какую-то кучку 3 камня. Выигрывает тот игрок, после хода которого общее число камней в двух кучках становится не менее 23. Кто выиграет – игрок, делающий ход первым, или игрок, делающий второй ход?
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, во второй – 3 камня. У каждого игрока неограниченное количество камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает число камней в какой-то куче в 3 раза, или добавляет 3 камня в любую из куч. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 33. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Даны две горки фишек, содержащих соответственно 2 и 4 фишки. За один ход разрешается или удвоить количество фишек в какой-нибудь горке, или добавить по две фишки в каждую из двух горок. Выигрывает тот игрок, после чьего хода в двух горках суммарно становится не менее 24 фишек. Игроки ходят по очереди. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Два игрока играют в следующую игру. Перед ними лежат две кучки фишек, в первой из которых 3, а во второй – 5 фишек. У каждого игрока неограниченно много фишек. Ходят игроки по очереди. Делая очередной ход, игрок или увеличивает в какой-то кучке число фишек в 2 раза, или добавляет в какую-то кучку 2 фишки. Выигрывает тот игрок, после хода которого общее число фишек в двух кучках становится не менее 21. Кто выиграет – игрок, делающий ход первым, или игрок, делающий второй ход?
Даны три кучи камней, содержащие соответственно 3, 4 и 5 камней. За один ход разрешается или удвоить количество камней в меньшей куче (если таких две – то лишь в одной из них), или добавить 2 камня в большую из куч (если таких две – то лишь в одну из них). Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок.
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (0;1) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+3) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 10 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (-2;-1) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+4) или (x+2,y+2). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 9 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (3;-5) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+4) или (x,y+5). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) не меньше 10 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (-3;2) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+5;y), (x,y+4) или (x+3,y+3). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 12 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (0;-4) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+4;y), (x,y+4) или (x+4,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 12 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым.
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (2;3) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (2x;y), (x,2y) или (x,y+2). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 3 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 24 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 5, а во второй – 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 2 раза число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 22 камней. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (1;0) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+3) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Два игрока играют в следующую игру. На координатной плоскости в точке с координатами (1;2) стоит фишка. Игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: (x+3;y), (x,y+3) или (x,y+4). Выигрывает тот игрок, после хода которого расстояние по прямой от фишки до начала координат (0,0) больше 13 единиц. Кто выигрывает – игрок, делающий ход первым, или игрок, делающий ход вторым?
Пример задачи 2005 года.
В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

A
B
C
D

A

4

5

B
4

3
6

C

3



D
5
6





Пример задачи
В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

A
B
C
D
E

A

1
4

1

B
1


3


C
4



2

D

3




E
1

2









Общие методические рекомендации по решению заданий такого рода.
1. Не надо пытаться рисовать граф по таблице. Таблица определяет только количество вершин и наличие связей между ними, но не определяет взаимное расположение вершин. Нарисовав «свой» граф по таблице, ученик может и не найти его среди вариантов ответа.
Примером являются следующие два графа, которые внешне различны, но при этом описываются одной и той же таблицей:


2. Проводим первичный анализ таблицы: определяем, со сколькими вершинами связана каждая из вершин. Для этого достаточно подсчитать количество непустых клеток в каждой строке (столбце). В задании 2005 г. количество связей: у A – 2, у B – 3, у C – 1, у D – 2.
В задании 2006 г. количество связей: у A – 3, у B – 2, у C – 2, у D – 1,у E – 2.
3. Анализируем варианты ответов и отбрасываем те из них, которые не соответствуют этим значениям. В задании 2005г. это ответы 1 и 3 (по вершине B). осталось проанализировать два варианта ответа – 2 и 4. В задании 2006 г. это ответ 4 (тоже по вершине B). осталось проанализировать три варианта ответа – 1,2,3.
4. Анализируем оставшиеся графы и проверяем соответствие рёбер вершинам. В задании 2005 г.: и в ответе 2, и в ответе 4 рёбра соединяют одни и те же вершины.
В задании 2006 г.: в ответе 3 вершина E соединена с вершинами A и D, а по таблице должна быть соединена с вершинами A и C.
В обоих заданиях осталось выбрать один ответ из двух.
5. Проверяем числовые характеристики рёбер в оставшихся вариантах ответов. Делаем окончательный выбор.
В задании 2005 г.: ответ 4 (по вершине D)
В задании 2006 г.: ответ 2 (по вершине A)
6. В качестве проверки (особенно в случае сомнений) по графу выбранного варианта ответа строим таблицу. Она строится по графу однозначно, и это точно позволит избежать ошибки.
Пример 2007 г. (модификация условия заключалась в том, что для поиска ответа целесообразно построить граф по таблице).
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечении строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в В не больше 6».
Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

A
B
C
D
E

A


3
1


B


4

2

C
3
4


2

D
1





E

2
2





A
B
C
D
E

A


3
1
1

B


4



C
3
4


2

D
1





E
1

2





A
B
C
D
E

A


3
1


B


4

1

C
3
4


2

D
1





E

1
2



1) 2)

A
B
C
D
E

A



1


B


4

1

C

4

4
2

D
1

4



E

1
2




3) 4)
При разборе задания с учащимися следует обратить внимание на то, что «путь минимальной стоимости (длины, времени и т.д.)» и «путь, проходящий через минимальное количество вершин» - это не одно и то же.
Ответ можно найти и без построения графов – достаточно тщательно проанализировать таблицы. Но, лучше воспользоваться формальным способом решения.
Для каждой таблицы строим свой граф, отмечая веса рёбер.

Определяем возможные пути из начальной вершины (А) в конечную (В) и подсчитываем их стоимость.
1) 2) 3) 4)
A-C-B
A-C-B
A-C-B
A-D-C-B

3+4=7
3+4=7
3+4=7
1+4+4=9

A-C-E-B
A-E-C-B
A-C-E-B
A-D-C-E-B

3+2+2=7
1+2+4=7
3+2+1=6
1+4+2+1=8

Заметим, что при небольшой тренировке построение графов и их анализ займут не больше времени, чем тщательный анализ таблиц, а вероятность допустить ошибку меньше.
В демо-версии 2008г. особенность заключалась в том, что граф надо было построить не по таблице, а по словесному описанию. При этом рёбра имели не по одной, а по две характеристики – расстояние и время движения, зависящее от качества дороги.
Пример 2008 года
Грунтовая дорога проходит последовательно через населённые пункты A,B,C,D. При этом длина дороги между A и B равна 80 км, между B и C – 50 км, между C и D – 10 км. Между A и C построили новое асфальтовое шоссе длиной 40 км.
Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/ч, по шоссе – 40 км/ч.
1) 1 час 2) 1,5 часа 3) 3,5 часа 4) 4 часа
При решении задач подобного рода целесообразно приучить школьников отмечать рёбра разного «качества» разными графическими образами (например, сплошной, пунктирной, волнистой линиями).

Рекомендуемый способ решения.
Строим граф на основании данных условия задачи:


13 SHAPE \* MERGEFORMAT 1415


Определяем возможные пути из начальной вершины (А) в конечную (В). Их всего два: А-В (80 км. грунтовой дороги) и А-С-В (40 км асфальтовой дороги и 50 км. грунтовой).
Для каждого пути рассчитываем время движения:
Для А-В: 13 EMBED Equation.3 1415
Для А-С-В: 13 EMBED Equation.3 1415
Ответ. Минимально возможное время движения велосипедиста из пункта А в пункт В – 3,5 ч (вариант 3).
Конечно, в задании проверяется не столько умение работать с графовыми моделями, сколько математические навыки. Возможно, поэтому в реальные варианты ЕГЭ 2008г. были включены задания на работу с табличными моделями.
Пример – задача, аналогичная реальному варианту ЕГЭ 2008г.
Между четырьмя железнодорожными станциями – Гир, Мар, Рем, Тул – ежедневно выполняют рейсы электрички. Известно расписание движения:
Станция отправления
Станция назначения
Время отправления
Время прибытия на станцию назначения

Гир
Маар
02:30
03:45

Рем
Гир
03:15
04:55

Гир
Рем
11:10
12:35

Гир
Тул
12:15
15:00

Тул
Рем
12:30
14:05

Тул
Гир
12:30
15:15

Маар
Тул
13:00
14:45

Рем
Тул
13:15
14:30

Тул
Маар
14:40
17:00

Мар
Гир
19:20
20:40

Турист находится на станции Гир в час ночи (01:00). Определите самое раннее время, когда он сможет оказаться на станции Тул.
1) 14:30 2)14:45 3)15:00 4)15:15
Конечно, простая внимательность и наблюдательность могут помочь ученику найти правильный ответ и без применения приёмов моделирования. Но лучше построить схему по таблице, отмечая только те данные, которые соответствуют заданию.

Прибытие Отправление Прибытие

Мар Мар(13:00 Тул(14:45)

Гир(1:00) Рем(12:35) Рем(13:15) Тул(14:30)

Тул(15:00)

Туристу надо ехать через Рим, и тогда он будет в Туле в 14:30.
При составлении схемы важно проследить, чтобы время прибытия на промежуточный пункт не превышало времени отправления.
Например, если бы в расписании третья строка была такой:
Гир
Рем
11:10
13:25



то туристу лучше было бы добираться через Маар и ответ был бы 14:45.
В качестве проверки можно порекомендовать учащимся для каждого варианта ответа, начиная с наиболее раннего по времени и далее по возрастанию времени:
найти соответствующее значение в последнем столбце таблицы;
попробовать восстановить путь от этого пункта к исходному;
если такой вариант возможен и нет никаких накладок со временем прибытия-отправления, то этот вариант и будет правильным ответом.
Контрольные задания13 TC "Контрольные задания" \f C \l "4" 15.
Задание 1.
В таблице приведена стоимость перевозки грузов между населёнными пунктами. Укажите схему, соответствующую таблице.



A
B
C
D

A


1
2

B


2
3

C
1
2

5

D
2
3
5


13 SHAPE \* MERGEFORMAT 1415
Задание 2
В таблице приведена стоимость перевозки одной партии груза между населёнными пунктами. определите минимальную стоимости перевозки двух партий груза из пункта В в пункт С.


A
B
C
D
E

A

3

3
1

B
3

4

5

C



2
4

D
3

2

1

E
1
5
4
1










1) 7 2) 8 3)10 4) 14
Ответ. Вариант 4. Соответствующий граф представлен на приведённом рисунке. Минимальный по стоимости путь B – A – E – D – C. Стоимость перевозки одной партии
3 + 1 + 1 + 2 = 7. Стоимость перевозки двух партий – 14.




Задание 3.
В таблицах приведено среднее время передачи сообщения между компьютерами. Пустая ячейка таблицы означает, что между соответствующими компьютерами нет прямого канала связи. Сообщение не может дважды проходить через один и тот же компьютер.
Укажите номер таблицы, для которой выполняется условие: «Максимальное время передачи сообщения от B к D не больше 5»



A
B
C
D

A

1
3
6

B
1

2
4

C
3
2

5

D
6
4





A
B
C
D

A

1
2
1

B
1

2


C
2
2

4

D
1

4










A
B
C
D

A

2

2

B
2

4
3

C

4

4

D
2
3
4




A
B
C
D

A

2
1
1

B
2

4


C
1
4

1

D
1

1











Ответ. Вариант 2
Для первой таблицы максимальное время 4 + 4 = 8 по пути В – С – D.
Для второй таблицы максимальное время 4 + 1 = 5 по пути В – С – D.
Для третьей таблицы максимальное время 1 + 6 = 7 по пути В – А – D.
Для четвёртой таблицы максимальное время 1 + 2 + 4 = 7 по пути В – А – С - D.

Задание 4.

В таблице приведено расписание полётов самолётов между аэропортами А, В, С, Д:

Аэропорт
вылета
Аэропорт
прилёта
Время
вылета
Время
прилёта

A
B
6:30
16:35

B
C
10:20
15:50

C
B
11:35
17:30

D
A
12:10
17:15

A
C
12:45
16:35

B
A
13:20
15:50

C
A
13:40
17:30

C
D
15:30
17:15

A
D
17:35
19:30

D
C
19:40
21:55

Пассажир в 6:00 находится в аэропорту С. Ему надо попасть в А. определите самое раннее время, когда он сможет там оказаться.

1) 14:25 2) 15:50 3) 16:35 4) 17:30

Ответ: Вариант 4. Прямой рейс C – A. Через В пассажир лететь не может, так как прибытие из С в В – 13:30, а вылетит из В в А – 13:20. Через D он может попасть из С в А только на следующий день.
Библиографический список
ЕГЭ 2010. Информатика. Федеральный банк экзаменационных материалов / Авт.-сост. П.Я. Якушкин, С.С.Крылов. М.: Эксмо, 2010. 234 с.
Информатика и ИКТ. Подготовка к ЕГЭ. / Под ред. Н.В.Макаровой. Спб.: Питер, 2007. 160 с.
Казиев В.М., Казиев К.В. Информатика: Задачи и тесты. Профильная школа. М.: Просвещение, 2007. 176 с.
Малясова С. В. Алгоритмизация, программирование и технология программирования // Информатика и образование. 2010. №1. С.23 – 40.
Поляков К. Дерево игры поиск выигрышной ситуации // ЕГЭ по информатике. 2011. URL: http//kpolyakov.narod.ru (дата обращения 16.02.2011).
Ракитина Е.А. ЕГЭ по информатике: Решение задач по моделированию // Информатика и образование. 2009. №1. С.24 – 33.
Сафронов И.К. Готовимся к ЕГЭ. Информатика. Спб.: ВНV, 2007. 256 с.
Якушкин П.А. Единый государственный экзамен: Информатика: Контрольные измерительные материалы: Репетиционная сессия. М.: Вентана-Граф, 2007. 48 с.








13PAGE 15


13PAGE 14215


13 PAGE \* MERGEFORMAT 14115-124




ЕГЭ по информатике: задачи и решения

ЕГЭ по информатике: задачи и решения: учебное пособие / сост.
И.Н. Тирских, И.В.Ладыгина; Забайкал. Гос. Гум.-Пед. Ун-т. – Чита: Изд-во ЗабГГПУ, 2011.-123 с.

ISBN

Материалы учебного пособия могут быть использованы студентами и преподавателями педагогических ВУЗов при изучении дисциплин: Технологии и методика обучения информатике; Практикум решения задач на ЭВМ; Теоретические основы информатики; Информатика и др. Учебное пособие состоит из двух частей: Решение задач группы А,В; Решение задач группы С. Каждая часть представлена несколькими главами основных тематических разделов школьного курса информатики, в конце которых предлагается закрепить материал решением контрольных (тестовых) упражнений.
Учебное пособие окажет практическую помощь учителям, репетиторам и родителям при подготовке учащихся к ЕГЭ по информатике. Материалы могут быть использованы при организации самостоятельной работы учащихся в 10-11-х классах, а также на курсах по подготовке к ЕГЭ.

ISBN
© ЗабГГПУ, 2011



рис. 1

рис. 2

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

13 EMBED Equation.3 1415

рис. 3

y

2

-2

2

0

-2

x

y = -x

x2 + y2 =22

рис. 4

1 игрок

5

4

3

2 игрок

1 игрок

5

4

3

3

2

1

1 игрок

2 игрок

1 игрок

5

4

3

3

2

1

1

1

рассмотрен ранее

X

Y

0

5

7

9

11

13

2

3

5

7

9

11

13

X

Y

0

5

7

9

11

13

2

3

5

7

9

11

13

X

Y

0

5

7

9

11

13

2

3

5

7

9

11

13

X

Y

0

5

7

9

11

13

2

3

5

7

9

11

13

X

Y

0

5

7

9

11

13

2

3

5

7

9

11

13

B

B

А

C

D

40

10

50

80

A

A

A

A

C

D

B

D

C

B

B

B

C

D

C

D

1

1

1

1

55

2

2

5

2

3

3

2

2

5

2

2

5

3

3

1)

2)

3)

4)

1)

2)

3)

4)

3)




Приложенные файлы

  • doc 244104
    Размер файла: 3 MB Загрузок: 0

Добавить комментарий