Математика и информатика. Решение логико-познавательных задач

ǵǪǯȈȌȖȝȐȕȈ
ǴȈȚȍȔȈȚȐȒȈ
ȐȐȕȜȖȘȔȈȚȐȒȈ
ǸȍȠȍȕȐȍ
ȓȖȋȐȒȖ-ȗȖȏȕȈȊȈȚȍȓȤȕȣȝ
ȏȈȌȈȟ
ǸȍȒȖȔȍȕȌȖȊȈȕȖǻȟȍȉȕȖ-ȔȍȚȖȌȐȟȍșȒȐȔȞȍȕȚȘȖȔ
©ǷȘȖȜȍșșȐȖȕȈȓȤȕȣȑțȟȍȉȕȐȒªȊȒȈȟȍșȚȊȍțȟȍȉȕȖȋȖȗȖșȖȉȐȧ
ȌȓȧșȚțȌȍȕȚȖȊȊȣșȠȐȝțȟȍȉȕȣȝȏȈȊȍȌȍȕȐȑ
ǸȍȒȖȔȍȕȌȖȊȈȕȖǵȈțȟȕȖ-ȐșșȓȍȌȖȊȈȚȍȓȤșȒȐȔȐȕșȚȐȚțȚȖȔ
ȖȉȘȈȏȖȊȈȕȐȧȐȕȈțȒȐȊȒȈȟȍșȚȊȍțȟȍȉȕȖȋȖȗȖșȖȉȐȧ
ȌȓȧșȚțȌȍȕȚȖȊȊȣșȠȐȝțȟȍȉȕȣȝȏȈȊȍȌȍȕȐȑ
ǴȖșȒȊȈ2017

ÏbÇ
ÈÈÇ
d
è n | n t o n t z €
rjtlqljzzn}tq·nxrq}tjyrÇÇÈvéoytvk
ojutj·jstqrjÏËÊÇÊÒ
ÎvxrvkxrvmvytqknéxqznzjÎÆbèvxxqqquntqƉÇqrvz¹
rjtlqljzzn}tq·nxrq}tjyrlv|ntz¬ËÍévrvwntrv
tj·rj{nlé€qt{véuj|qvttvrvuwíznét€}zn}tvsvmqpkln¹znstvxzqÌÆb
Ènsmvévlxrvmvíéqlq·nxrvmvqtxzqzyzjÎÆbèvxxqq
rjtlqljzzn}tq·nxrq}tjyrÎÍbyiqtqt
lv|ntzrj{nlé€qt{véuj|qvtt€}zn}tvsvmqpywéjksntq¹
vémjtjuqktyzénttq}lns¬rjlnuqqywéjksntq¹ÎÆbèvxxqq
-sjkt€pénljrzvéqoljznsxzkjËbêéqj¡kqsq
rjtlqljzíéqlq·nxrq}tjyrlvrzvéërvtvuq·nxrq}tjyrwév{nxxvé
sjyénjzwénuqqÍéjkqznsxzkjèÐkvisjxzqtjyrqqzn}tqrq
djlv}qtjËqtjÆsjlquqévktj
d
Îjznujzqrj
q
qt{véujzqrj
èn¡ntqn
svmqrv
wvotjkjznst€}ojlj·y·niwvxviqnls¹xzylntzvkkyovk
ËÆdjlv}qtj²ÎìËÊÒÊb¬Ë¬7²x
,6%1
¬mntzxzkv&,3è-È
èjxxujzéqkjnzx¹ én¡ntqn svmqrvwvotjkjznst€} ojlj· v}kjz€kjí
q} kxn kj tnp¡qn éjolns€ y·nitvp lqx|qwsqt€ ©Îjznujzqrj q qt
{véujzqrjªrvlqévkjtqnqwénlxzjksntqnqt{véuj|qqkêÆÎutv n
xzkjësnuntz€ujznujzq·nxrvpsvmqrqkknlntqnkznvéqíknév¹ztvxznp
Íéqkvlqzx¹tnvi}vlqu€puqtquyuznvénzq·nxrq}otjtqpÍéquné€xv
wévkv ljízx¹ qssíxzéj|q¹uq x}nujuq q zjisq|juq wvokvs¹íquq
tn{véujstv yxkvqz ujznéqjs wvuvmjíqp éjokqzqí u€xsqznst€}
xwvxvitvxznpxzylntzvk
Íéqkvl¹zx¹ojljtq¹ls¹xjuvxzv¹znstvmvén¡ntq¹
bs¹ryéxjtzvkxzylntzvkqxsy¡jznsnpwév}vl¹q}viy·ntqnkéju
rj} lqx|qwsqt ©Îjznujzqrjq qt{véujzqrjª ©Êt{véujzqrj q qt{vé
uj|qvtt€n zn}tvsvmqq k wév{nxxqvtjstvp ln¹znstvxzqª ©Îjznujzq
rjª j zjr n ls¹ kxn} qtznénxyíq}x¹ én¡ntqnu ojlj· {véuqéyíq}
ryszyéysvmq·nxrvmvu€¡sntq¹
ÈÈÇ
,6%1
‹Êdb¬ÒcÉhfÒÆÌìËÊÒÊb¬Ë¬
Íéqtjlsn qzqxrsí·qznstvnwéjkvtjqxwvsovkjtqnqéjxwévxzéjtntqnqolj
tq¹Ðdvzjwéns¹mðÐdÆvxwévqoknlntqnkxnprtqmqqsqsíivp
nn·jxzqsíi€uqxénlxzkjuqqsqkrjrvpsqiv{véunojwénjnzx¹inowqxunt
tvmvéjoén¡ntq¹qoljznsxzkj

ǶǺ ǨǪǺǶǸǨ 
Современное российское общество ставит перед высшей школой 
задачу подготовки высокоинтеллектуальных специалистов, не только 
вооружив их новейшими достижениями науки и техники и совершенными методами научного исследования, но и сформировав у них высокую культуру логического мышления. Формирование культуры логического мышления становится важнейшим аспектом в подготовке 
будущих специалистов, так как помогает выпускникам вузов совершенствовать формальный аппарат мышления, систематизировать и 
классифицировать эмпирические знания, а также правильно оценивать истинную сущность явлений и процессов, в современном обществе. 
Известно, что способность логически мыслить формируется в 
процессе жизнедеятельности человека и для ее полноценного развития необходимы специальные условия. 
Изучение формирования культуры логического мышления проводится учеными — педагогами, психологами, математиками — на протяжении многих лет. Анализ этих исследований показал, что при традиционном обучении и средняя, и высшая школа недостаточно вооружает обучающихся приемами логического мышления. 
В настоящее время знания и умения как единицы результата образовательного процесса необходимы, но не достаточны для успешного 
решения задач, которые ставит перед человеком современное информационное общество. Особое значение приобретает способность человека применять обобщенные знания и умения для разрешения проблемных ситуаций, которые регулярно возникают в профессиональной деятельности любого специалиста. 
Лучшим примером проблемной ситуации может служить логикопознавательная задача, при решении которой обучающийся самостоятельно пытается преодолеть ситуацию «интеллектуального затруднения», то есть разрешить проблемную ситуацию, а не получить готовое 
решение. 
Логико-познавательные задачи, рассматриваемые в пособии, охватывают важнейшие темы учебной дисциплины «Математика и информатика». Данная дисциплина в большей степени, чем другие учебные дисциплины, влияет на формирование и развитие логического 
мышления, так как учебный материал этой дисциплины имеет высокий уровень систематизации и алгоритмизации, а также изобилует 
логическими конструкциями и формализованными моделями. 
Задачи, представленные в данном пособии, варьируются по степени сложности. Так, задачи первого уровня достаточно просты и тре 
3

буют базового объема знаний. Для их решения применяются известные алгоритмы, и интеллектуальный поиск заключается в анализе и 
синтезе исходных данных, в обобщении, классификации, систематизации исследуемых объектов и выборе метода решения. При систематическом решении такого рода задач формируются логические приемы мыслительной деятельности, овладев которыми, можно справиться с заданиями следующего уровня. Каждый следующий уровень углубляет и обобщает содержание предыдущего. К задачам средней 
сложности относятся нетиповые задачи, при решении которых необходимо применять дедуктивные, индуктивные методы, метод моделирования и др. К наиболее сложным относятся задачи с неполными 
исходными данными, и тогда первоочередным действием становится 
расширение информационного поля задачи преобразованием исходной информации. 
Логико-познавательные задачи стимулируют мышление студентов, приближают их учебную деятельность к научному поиску, знакомят с методами научного познания и, безусловно, готовят обучающихся к их будущей профессиональной деятельности. Они могут быть 
использованы на лекциях, семинарах, практических занятиях и консультациях. Именно учебные задачи являются одной из основных 
форм развития логического мышления в образовательном процессе. 
 
 
 
4

ǫȓȈȊȈ 1 
DzǶǬǰǸǶǪǨǵǰǭ ǰ ǷǸǭǬǹǺǨǪdzǭǵǰǭ  
ǰǵǼǶǸǴǨǾǰǰ Ǫ ȅǪǴ 
1.1. ǷȖȕȧȚȐȍ «ȒȖȌȐȘȖȊȈȕȐȍ» 
Компьютер с точки зрения пользователя работает с самой разной 
информацией: числовой, графической, звуковой, текстовой и пр. Чтобы работать с данными различных видов, необходимо унифицировать 
форму их представления. Это можно сделать с помощью кодирования.  
Кодирование информации — это процесс ее построения определенным образом. Более узкий смысл термина «кодирование» часто 
означает представление информации в такой форме, которая является 
более удобной для хранения, передачи или обработки. Знаки или символы, используемые для создания информационных сообщений, называют кодами, их полный набор составляет алфавит кодирования. 
Простейший алфавит, с помощью которого можно записать какуюлибо информацию, — это алфавит из двух символов, описывающих 
два его альтернативных состояния («да» — «нет», «+» — «–», «0» или 
«1» и т.п.). 
Любое информационное сообщение можно передать символами 
того или иного алфавита или, иначе говоря, получить ту или иную 
форму представления. Например, музыкальную композицию можно 
воспроизвести на инструменте (закодировать и передать с помощью 
звуков), записать, используя ноты, на бумаге (кодами являются ноты) или на магнитном диске (коды — электромагнитные сигналы). 
Способ кодирования зависит от того, с какой целью оно применяется 
(для сокращения записи, засекречивания (шифровки) информации 
или, напротив, достижения взаимопонимания). Примерами различных способов кодирования являются система дорожных знаков, 
флажковая азбука на флоте, азбука Морзе, азбука Брайля, специальные научные языки и символы — химические, математические, медицинские. 
В компьютерных системах применяется своя система кодирования — 
двоичное кодирование. Любая информация (числовая, текст, графика, 
звук и т.д.) кодируется двумя видами символов — 0 и 1, составляющими основу двоичной системы счисления. Количество информации, 
кодируемое двоичной цифрой — 0 или 1, называется битом (от англ. 
 
5

binary digit — двоичная цифра). С помощью набора битов можно 
представить любой символ: число, букву или знак. Каждый символ 
представляется восьмиразрядными комбинациями битов — байтами 
(т.е. 1 байт = 8 бит), поэтому основной единицей измерения информации является байт. Однако кодирование в двоичной системе счисления может быть очень громоздким. Поэтому для записи и хранения 
закодированной двоичной информации могут использоваться восьмеричная и шестнадцатеричная системы счисления. 
1.2. ǷȖȏȐȞȐȖȕȕȣȍ Ȑ ȕȍȗȖȏȐȞȐȖȕȕȣȍ  
        șȐșȚȍȔȣ șȟȐșȓȍȕȐȧ 
Система счисления — способ записи чисел посредством определенного набора знаков (цифр).  
Основание системы счисления — число знаков (цифр), с помощью 
которых записываются числа. 
Алфавит системы счисления — набор знаков.  
Все системы счисления можно разделить на два класса: непозиционные и позиционные. 
В непозиционных системах счисления на значение (вес) цифры в 
числе не влияет ее позиция в записи числа.  
Например, непозиционной системой счисления является единичная система, которая имела хождение еще у первобытных людей. Любое число в этой системе образуется путем повторения одного знака, 
символизирующего единицу. Отголоски единичной системы счисления встречаются и сегодня (счетные палочки для обучения счету; полоски, нашитые на рукава курсантов, означающие курс, на котором 
они учатся и т.п.).  
В качестве примера непозиционной системы счисления можно 
привести римскую систему счисления, в которой вместо цифр используются латинские буквы. Ниже приведены примеры, иллюстрирующие общие правила записи чисел в римской система счисления 
(табл. 1.1). 
 
ǺȈȉȓȐȞȈ 1.1 
I 
III 
V 
VII 
IX 
X 
L 
C 
D 
M 
1 
3 
5 
7 
9 
10 
50 
100 
500 
1000 
 
Цифры в числе обычно записываются слева направо в порядке 
убывания, при этом нельзя записывать рядом более трех одинаковых 
 
6

цифр. Величина числа определяется как сумма или разность цифр в 
числе. Если меньшая цифра стоит справа от большей, то она прибавляется. 
 
Пример 1. VII
5
2
 

. 
 
Пример 2. MCCXXXVI
1000 100 100 10 10 10
5 1
1236
 






  
. 
Если меньшая цифра стоит слева от большей, то она вычитается. 
 
Пример 3. IX
10 1
 
 . 
Такой способ записи чисел приводит к очень сложным правилам 
арифметики, поэтому в настоящее время римская система счисления 
применяется не по прямому назначению, например при нумерации 
глав в литературных произведениях и научных изданиях, в серийных 
номерах документов и т.п. 
В позиционных системах счисления значение (вес) каждой цифры 
в числе зависит от ее позиции в записи числа.  
Заметим, что позиция цифры в записи числа называется разрядом 
этого числа. 
 
Пример 4. Рассмотрим число 7461, представленное в десятичной 
системе. Предварительно пронумеруем разряды данного числа. Нумерация разрядов в целых числах идет справа налево, начиная с нуля: 
3
2
1
0
2
0
3
1
7 4 6 1
7 10
4 10
6 10
1 10
 
˜

˜
 ˜
 ˜
. 
Мы получили число 7461 в виде многочлена по степеням основания десятичной системы (той системы, в которой оно представлено). 
Очевидно, что каждая цифра, которая входит в запись числа 7461, означает определенное количество. В свою очередь, количество, которое несет каждая цифра, зависит от ее позиции в числе. 
Такой вид представления чисел называют также развернутым видом. 
 
Пример 5. Представим десятичное число 456,92 в развернутом 
виде. Предварительно пронумеруем разряды данного числа. Нумерация разрядов идет справа налево, начиная с нуля — для целой части 
числа, и слева направо — для дробной: 
2
1
0
1
2


 
˜
 ˜
 ˜
 ˜

˜
. 
2
2
1 0
1
4 5 6, 9 2
4 10
5 10
6 10
9 10
2 10


 
7

Теоретически существует бесконечное множество позиционных 
систем счисления. Приведем примеры систем счисления с различным 
основанием (табл. 1.2). 
 
ǺȈȉȓȐȞȈ 1.2 
Система счисления 
Основание 
Алфавит 
Двоичная 
2 
01 
Троичная 
3 
012 
Восьмеричная 
8 
01234567 
Десятичная 
10 
0123456789 
Двенадцатеричная 
12 
0123456789AB 
Шестнадцатеричная 
16 
0123456789ABCDEF 
 
˜

˜


˜

˜

˜

...
X
x
q
x
q
x
q
x
q
х
q






n
n
q
n
n
 
Число в любой позиционной системе счисления с основанием q 
может быть представлено в виде многочлена по степеням основания 
q. В общем виде это правило запишем так:  
1
2
1
0
1
1
2
1
0
1

˜


˜
 
x
q
x
q
...
,




k
k
2
2
где 
q
X  — запись числа в системе счисления с основанием q; 
i
x  — цифры, входящие в запись числа (всегда меньше q); 
n  — число разрядов целой части; 
k  — число разрядов дробной части. 
 
Пример 6. Представим число 12101, записанное в троичной системе, в виде многочлена по степеням основания q=3. Чтобы не ошибиться, пронумеруем разряды числа 
3
12101 справа налево, начиная с 
нулевого: 
4
3
2
1
0
3
3
4 3 2
0
1
12101
(12101)
1 3
2 3
1 3
0 3
1 3
 
 ˜

˜
 ˜
 ˜
 ˜
. 
 
Замечание 1. Основание системы счисления числа обычно обозначается нижним индексом и пишется всегда в десятичной системе. 
Важно, что основание любой позиционной системы счисления определяет: 
• 
название системы счисления; 
 
8

• 
число цифр в этой системе счисления; 
• 
то, во сколько раз вклад цифры в позиции числа больше вклада такой же цифры в предыдущей позиции. 
Например, в числе 
10
554
 вклад цифры 5, стоящей в первой позиции, равен 500, что в 10 раз больше вклада, который вносит цифра 5, 
стоящая во второй позиции. 
Для более наглядного выявления различий между позиционной и 
непозиционной системами счисления рассмотрим пример сравнения 
двух чисел. В позиционной системе счисления сравнение двух чисел, 
имеющих одинаковое число цифр, проводится следующим образом: в 
рассматриваемых числах слева направо сравниваются цифры, стоящие в одинаковых позициях. Большая цифра соответствует большему 
значению числа. Например, для чисел 521 и 215 5 больше 2, поэтому 
число 521 больше, чем число 215. В непозиционной системе счисления это правило не действует. Примером может служить сравнение 
двух чисел IX и VI. Несмотря на то, что I меньше, чем V, число IX 
больше, чем число VI. 
Далее мы будем рассматривать только позиционные системы 
счисления. 
 
Пример 7. Какое минимальное основание системы счисления может иметь число 
32
A
? Очевидно, что для записи данного числа необходимо одиннадцать цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, А. Поэтому система 
счисления, в которой может быть записано число
32
A
, должна иметь 
минимальное основание 11. 
 
Пример 8. Найдем минимальное основание системы счисления, 
если в ней записаны все следующие числа: 132, 120, 11, 10101, 2331. 
Очевидно, что для записи всех этих чисел необходимо четыре цифры: 
0, 1, 2, 3. Поэтому система счисления должна иметь минимальное основание 4. 
 
Пример 9. Найдем минимальное основание системы счисления, 
если в ней записаны все следующие числа: 732, 2E, 109, 111, 989. Очевидно, что для записи всех этих чисел необходимо пятнадцать цифр: 
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E. Поэтому система счисления 
должна иметь минимальное основание 15. 
 
 
 
9

1.3. ǬȊȖȐȟȕȈȧ, ȊȖșȤȔȍȘȐȟȕȈȧ Ȑ ȠȍșȚȕȈȌȞȈȚȍȘȐȟȕȈȧ  
       șȐșȚȍȔȣ șȟȐșȓȍȕȐȧ 
В процессе работы на ЭВМ наиболее интересны системы счисления с основаниями 2, 8 и 16. В ЭВМ применяется двоичная система 
счисления, так как она имеет ряд преимуществ перед другими системами:  
• 
с помощью двоичной системы счисления просто реализуются 
электронные схемы с двумя устойчивыми состояниями (есть 
ток — 1, нет тока — 0);  
• 
становится возможным применение алгебры логики для выполнения логических преобразований информации (в алгебре логики всего два возможных результата: истина — 1 и  
ложь — 0);  
• 
двоичная арифметика проще десятичной (двоичные таблицы 
сложения и умножения предельно просты).  
Арифметические действия в двоичной системе выполняются по 
тем же правилам, что и в десятичной. Однако в двоичной системе 
счисления единицы чаще переносятся в старший разряд, чем в десятичной. Вот как выглядят таблицы сложения и умножения в двоичной 
системе (табл. 1.3).  
ǺȈȉȓȐȞȈ 1.3 
0 + 0 = 0 
0 × 0 = 0 
1 + 0 = 1 
0 × 1 = 0 
0 + 1 = 1 
1 × 0 = 0 
1 + 1 = 10 
1 × 1 = 1 
 
Замечание 2. В двоичной системе счисления нет других цифр, 
кроме 0 и 1, поэтому при сложении двух единиц переходим в следующий, старший разряд: 
2
1 1
10
  
 (называется не «десять», а «один 
— ноль», т.е. перечисляются названия цифр слева направо). 
В связи с тем, что в двоичной системе запись числа длиннее, чем в 
десятичной примерно в 3,3 раза, для облегчения восприятия двоичного числа было решено разбивать его на группы разрядов (например, 
по три или четыре разряда). Это оказалось удачным решением, так как 
последовательность из 3 бит имеет 8 комбинаций, а последовательность из 4 бит — 16. Числа 8 и 16 являются степенями двойки, поэто 
10