10 КЛАСС
презентации для самостоятельного изучения
Скачать:
| Вложение | Размер |
|---|---|
 logic.ppt | 619 КБ |
| osnovy_logiki.ppt | 590.5 КБ |
| zakony_logiki.pptx | 806.35 КБ |
 для подготовки к ЕГЭ | 58.8 КБ |
| массив | 185 КБ |
 Практикум по программированию Паскаль | 120.33 КБ |
| info-ege-academiaa-var12-otvet.pdf | 28.25 КБ |
Предварительный просмотр:
Подписи к слайдам:
ФОРМЫ МЫШЛЕНИЯ ЛОГИКА — это наука о формах и законах человеческого мышления и, в частности, о законах доказательных рассуждений. Логика изучает мышление как средство познания объективного мира. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Формальная логика связана с анализом наших обычных содержательных умозаключений, выражаемых разговорным языком. Математическая логика изучает только умозаключения со строго определенными объектами и суждениями, для которых можно однозначно решить, истинны они или ложны. Идеи и аппарат логики используется в кибернетике, вычислительной технике и электротехнике (построение компьютеров основано на законах математической логики). В основе логических схем и устройств ПК лежит специальный математический аппарат, использующий законы логики. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции.
Основные формы мышления Основными формами мышления являются: ПОНЯТИЯ, СУЖДЕНИЯ, УМОЗАКЛЮЧЕНИЯ. ПОНЯТИЕ - форма мышления, в которой отражаются существенные признаки отдельного объекта или класса однородных объектов. Примеры: портфель, трапеция, ураганный ветер. Понятие имеет две стороны: содержание и объем. Содержание понятия составляет совокупность существенных признаков объекта. Чтобы раскрыть содержание понятия, следует найти признаки, необходимые и достаточные для выделения данного объекта из множества других объектов. Например, содержание понятия «персональный компьютер» можно раскрыть следующим образом: «Персональный компьютер — это универсальное электронное устройство для автоматической обработки информации, предназначенное для одного пользователя». Объем понятия определяется совокупностью предметов, на которую оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров. СУЖДЕНИЕ – это форма мышления, в которой что-либо утверждается или отрицается об объектах, их свойствах и отношениях . Суждениями обычно являются повествовательными предложениями, которые могут быть или истинными или ложными. «Берн — столица Франции», «Река Кубань впадает в Азовское море», «2>9», «3×5=10» УМОЗАКЛЮЧЕНИЕ – это форма мышления, посредством которой из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем новое суждение (заключение). Все металлы - простые вещества. Литий - металл.→ Литий - простое вещество. Один из углов треугольника равен 90º. → Этот треугольник прямоугольный.
АЛГЕБРА ВЫСКАЗЫВАНИЙ В основе работы логических схем и устройств персонального компьютера лежит специальный математический аппарат - математическая логика. Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем. Знание логики необходимо при разработке алгоритмов и программ, так как в большинстве языков программирования есть логические операции. Английский математик Джордж Буль (1815 — 1864 г.) создал логическую алгебру, в которой высказывания обозначены буквами. Сочинение Джорджа Буля, в котором подробно исследовалась эта алгебра, было опубликовано в 1854 г. Оно называлось «Исследование законов мысли» («Investigation of the Laws of Thought»). Отсюда ясно, что Буль рассматривал свою алгебру как инструмент изучения законов человеческого мышления, то есть законов логики. Алгебру логики иначе называют алгеброй высказываний. В математической логике суждения называются высказываниями.
ВЫСКАЗЫВАНИЕ - это повествовательное предложение, о котором можно сказать, что оно или истинно или ложно. Например: Земля - планета Солнечной системы . (Истинно) 2+8<5 (Ложно) 5 · 5=25 (Истинно) Всякий квадрат есть параллелограмм (Истинно) Каждый параллелограмм есть квадрат (Ложно) 2 · 2 =5 (Ложно) Не всякое предложение является высказыванием: 1) Восклицательные и вопросительные предложения высказываниями не являются. - “Какого цвета этот дом?” - “Пейте томатный сок!” - “Стоп!” 2) Не являются высказываниями и определения. “Назовем медианой отрезок, соединяющий вершину треугольника с серединой противоположной стороны”. Определения не бывают истинными или ложными, они лишь фиксируют принятое использование терминов. 3) Не являются высказываниями и предложения типа “Он сероглаз” или “ х- 4х + 3=0” - в них не указано о каком человеке идет речь или для какого числа х верно равенство. Такие предложения называются высказывательными формами. Высказывательная форма — это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.
Высказывания могут быть простыми и сложными. Высказывание считается простым, если никакую его часть нельзя рассматривать как отдельное высказывание Некоторые высказывания можно разложить на отдельные части, при этом каждая такая часть будет самостоятельным высказыванием. Например, высказывание “Сегодня в 4 часа дня я был в школе, а к 6 часам вечера пошел на каток” состоит из 2 частей. Высказывание может состоять и из большего количества частей. Высказывание, которое можно разложить на части, будем называть сложным, а неразложимое далее высказывание - простым. Сложное высказывание получается путем объединения простых высказываний логическими связками — НЕ, И, ИЛИ . Значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок. Например, даны простые высказывания: На улице идет дождь. На улице светит солнце. На улице пасмурная погода. Составим из них сложные высказывания: На улице идет дождь и на улице светит солнце. На улице светит солнце или на улице пасмурная погода. Неверно что на улице идет дождь.
В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1 . Если высказывание истинно, то его значение равно 1, если ложно - 0. Простые высказывания назвали логическими переменными и для простоты записи их обозначают латинскими буквами: А, В, С… Луна является спутником Земли . А = 1 Москва – столица Германии . В = 0 Сложные высказывания называются логическими функциями . Значения логической функции также может принимать значения только 0 или 1.
БАЗОВЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ В алгебре высказываний, как и в обычной алгебре, вводится ряд операций. Логические связки И, ИЛИ и НЕ заменяются логическими операциями: конъюнкцией, дизъюнкцией и инверсией. Это основные логические операции, при помощи которых можно записать любую логическую функцию.
1. Логическая операция ИНВЕРСИЯ (ОТРИЦАНИЕ) соответствует частице НЕ обозначается черточкой над именем переменной или знаком ¬ перед переменной Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна. Таблица истинности инверсии имеет вид: A 0 1 1 0
2. Логическая операция ДИЗЪЮНКЦИЯ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ ) соответствует союзу ИЛИ обозначается знаком v или + или ║ Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. А v В v С =0, только если А=0, В=0, С=0. Таблица истинности дизъюнкции имеет следующий вид: A B А V В 0 0 0 0 1 1 1 0 1 1 1 1
3. Логическая операция КОНЪЮНКЦИЯ (ЛОГИЧЕСКОЕ УМНОЖЕНИЕ) соответствует союзу И обозначается знаком & или Λ , или · Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания истинны. Это определение можно обобщить для любого количества логических переменных, объединенных конъюнкцией. А & В & С=1, только если А=1, В=1, С=1. Таблица истинности конъюнкции имеет следующий вид: A B А & В 0 0 0 0 1 0 1 0 0 1 1 1
ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ТАБЛИЦЫ ИСТИННОСТИ Сложные высказывания можно записывать в виде формул. Для этого простые логические высказывания нужно обозначить как логические переменные буквами и связать их с помощью знаков логических операций. Такие формулы называются логическими выражениями. Например: Чтобы определить значение логического выражения необходимо подставить значения логических переменных в выражение и выполнить логические операции. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке: 1. инверсия; 2. конъюнкция; 3. дизъюнкция; 4. импликация и эквивалентность. Для изменения указанного порядка выполнения логических операций используются круглые скобки.
Таблицы истинности Для каждого составного высказывания (логического выражения) можно построить таблицу истинности , которая определяет истинность или ложность логического выражения при всех возможных комбинациях исходных значений простых высказываний (логических переменных). При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий: 1) записать выражение и определить порядок выполнения операций 2) определить количество строк в таблице истинности. Оно равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение (определяется по формуле Q=2 n , где n - количество входных переменных) 3) определить количество столбцов в таблице истинности (= количество логических переменных + количество логических операций) 4) построить таблицу истинности, обозначить столбцы (имена переменных и обозначения логических операций в порядке их выполнения) и внести в таблицу возможные наборы значений исходных логических переменных. 5) заполнить таблицу истинности, выполняя базовые логические операции в необходимой последовательности и в соответствии с их таблицами истинности Теперь мы можем определить значение логической функции для любого набора значений логических переменных.
Например, построим таблицу истинности для логической функции: Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов, а значит и строк Q=2 3 =8 . Количество столбцов равно 6 (3 переменные + 3 операции). Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C , промежуточных результатов и ( B V C ), а также искомого окончательного значения сложного арифметического выражения
A B C B V C
A B C B V C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
A B C B V C 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 Задание. Постройте таблицу истинности для данного логического выражения:
А В 0 0 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 1 0 1 1 Равносильные логические выражения. Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак = . Например:
ЗАПИСЬ ЛОГИЧЕСКОГО ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ Правила построения логического выражения: 1. Для каждой строки таблицы истинности с единичным значением функции построить минтерм . Минтермом называется произведение, в котором каждая переменная встречается только один раз — либо с отрицанием, либо без него. Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 — без отрицания. 2. Объединить все минтермы операцией дизъюнкция (логическое сложение), что даст стандартную сумму произведений для заданной таблицы истинности .
Пример. Дана таблица истинности: X1 X2 X3 F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 Для второй строки X1=0, Х2=0, X3=1. Эту строку описывает минтерм Для третьей строки X1=0, Х2=1, X3=0. Эту строку описывает минтерм Для шестой строки X1=1, X2=0, X3=1. Эту строку описывает минтерм Объединяя термы, получим булево выражение F = В это выражение вошли термы-произведения для строк с единичным значением функции F, а вся сумма соответствует совокупности из трех строк. Для остальных пяти наборов значений входных переменных это выражение равно нулю. Построим логическое выражение для F. Найдем строки, в которых F=1. Это вторая, третья и шестая.
Логические функции Любое логическое выражение (составное высказывание) можно рассматривать как логическую функцию F ( X1 , X2 , ..., Xn ) аргументами которой являются логические переменные X 1, X 2, ..., Х n (простые высказывания). Сама функция как и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0). Выше были рассмотрены функции двух аргументов: логическое умножение F ( A , B ) = A & B , логическое сложение F ( A , B ) = AVB , а также логическое отрицание F ( A ) = ¬ А, в котором значение второго аргумента можно считать равным нулю. Каждая логическая функция двух аргументов имеет четыре возможных набора значений аргументов. Может существовать N = 2 4 = 16 различных логических функций двух аргументов. Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности :
Аргументы Логические функции А В F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 F 9 F 1 0 F 11 F 12 F 13 F 14 F 15 F 16 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Легко заметить, что здесь логическая функция F 2 является функцией логического умножения, F 8 — функцией логического сложения, F 13 — функцией логического отрицания для аргумента А и F 11 — функцией логического отрицания для аргумента В. В обыденной и научной речи кроме базовых логических связок «и», «или», «не» используются и некоторые другие: «если... то...», «... тогда и только тогда, когда...» и др. Некоторые из них имеют свое название и свой символ, и им соответствуют определенные логические функции.
ИМПЛИКАЦИЯ ( ЛОГИЧЕСКОЕ СЛЕДОВАНИЕ ) . Импликация двух высказываний А и В соответствует союзу «ЕСЛИ…ТО». Она обозначается символом → Запись А → В читается как «из А следует В» Импликация двух высказываний истинна всегда, кроме случая, если первое высказывание истинно, а второе ложно. Таблица истинности импликации двух суждений А и В такова: А В А → В 0 0 1 0 1 1 1 0 0 1 1 1 В программировании эту операцию обозначают « IMP ».
ЭКВИВАЛЕНТНОСТЬ (ЛОГИЧЕСКОЕ РАВЕНСТВО, ФУНКЦИЯ ТОЖДЕСТВА) Она обозначается символами ≡ или <=>. («тогда и только тогда»). Запись А ≡ В читается как «А эквивалентно В». Эквивалентность двух высказываний истинна только в тех случаях, когда оба высказывания ложны или оба истинны. Таблица истинности эквивалентности двух суждений А и В такова: А В А ≡ В 0 0 1 0 1 0 1 0 0 1 1 1 В программировании эту операцию обозначают «EQV». В алгебре высказываний все логические функции могут быть сведены путём логических преобразований к трём базовым логическим операциям: инверсии, дизъюнкции и конъюнкции
Логические законы и правила преобразования логических выражений Равносильности формул логики высказываний часто называют законами логики . Законы логики отражают наиболее важные закономерности логического мышления. В алгебре высказываний законы логики записываются в виде формул, которые позволяют проводить эквивалентные преобразования логических выражений в соответствие с законами логики. Знание законов логики позволяет проверять правильность рассуждений и доказательств. Нарушения этих законов приводят к логическим ошибкам и вытекающим из них противоречиям. Перечислим наиболее важные из них:
1. Закон тождества. Всякое высказывание тождественно самому себе: Этот закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует. 2. Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А — истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: Закон непротиворечия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”
3. Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано. “ Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание. 4. Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание: Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание. “ Неверно, что 2× 2¹ 4”
5. Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых «сомножителей» равносильна одному из них: Дизъюнкция одинаковых «слагаемых» равносильна одному: 6 . Законы де Моргана: Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках: отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых; отрицание логического произведения эквивалентно логической сумме отрицаний множителей.
7 . Правило коммутативности. В обычной алгебре слагаемые и множители можно менять местами. В алгебре высказываний можно менять местами логические переменные при операциях логического умножения и логического сложения: Логическое умножение: Логическое сложение: 8 . Правило ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять: Логическое умножение: Логическое сложение:
9 . Правило дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки, как общие множители, так и общие слагаемые: Дистрибутивность умножения относительно сложения: Дистрибутивность сложения относительно умножения: 10. 11. 12. Законы поглощения:
РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ
ЗАДАЧА 1. Разбирается дело Лёнчика, Пончика и Батончика. Кто-то из них нашел и утаил клад. На следствии каждый из них сделал по два заявления. Батончик: «Я не делал этого. Пончик сделал это» Лёнчик: «Пончик не виновен. Батончик сделал это» Пончик: «Я не делал этого. Лёнчик не делал этого» Суд установил, что один из них дважды солгал, другой — дважды сказал правду, третий — один раз солгал, один раз сказал правду. Кто утаил клад? Возможные варианты Высказывания Батончика Высказывания Лёнчика Высказывания Пончика Соответствие условию задачи Б Л П ¬ Б П ¬ П Б ¬ П ¬ Л 1 0 0 0 0 1 1 1 1 - 0 0 1 1 1 0 0 0 1 + 0 1 0 1 0 1 0 1 0 - В первом варианте один солгал дважды, а двое сказали правду дважды, что не соответствует условию задачи. В третьем варианте все один раз сказали правду и один раз солгали, что также не соответствует условию задачи. Во втором варианте один дважды солгал, другой дважды сказал правду, а третий один раз сказал правду, а один раз солгал, что соответствует условию задачи. Следовательно клад утаил Пончик. Решение: Введём обозначения: Б –клад утаил Батончик, П - клад утаил Пончик, Л - клад утаил Лёнчик. Рассмотрим три возможных варианта – виноват Батончик, виноват Пончик, виноват Лёнчик. При таких вариантах получаем следующие значения высказываний трёх обвиняемых.
Задача 2. В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях. Один считает, что первой будет Наташа, а Маша будет второй. Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место. Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на чемпионате заняли Наташа, Маша, Люда, Рита? Высказывания 1-ого болельщика Высказывания 2-ого болельщика Высказывания 2-ого болельщика Соответствие условию задачи Н1 М2 Л2 Р4 Р3 Н2 0 1 0 1 0 1 - 0 1 0 1 1 0 - 0 1 1 0 1 0 - 0 1 1 0 0 1 - 1 0 0 1 0 1 - 1 0 0 1 1 0 - 1 0 1 0 0 1 - 1 0 1 0 1 0 + Из анализа таблицы видно , что условию задачи соответствует только последняя строка, значит первое место заняла Наташа, второе – Люда, третье – Рита, а Маша –четвёртое. Решение: Введём обозначения: Н1 – Наташа на 1 месте, М2 – Маша на 2 месте, Л2 – Люда на 2 месте, Р4 – Рита на 4 месте, Р3 – Рита на 3 месте, Н2 – Наташа на 2 месте. Занесём возможные варианты высказываний трёх болельщиков в таблицу с учётом того, что каждый из болельщиков оказался прав только в одном из своих прогнозов:
Задача 3. Вадим, Сергей и Михаил изучают различные иностранные языки: китайский, японский и арабский. На вопрос, какой язык изучает каждый из них, один ответил: "Вадим изучает китайский, Сергей не изучает китайский, а Михаил не изучает арабский". Впоследствии выяснилось, что в этом ответе только одно утверждение верно, а два других ложны. Какой язык изучает каждый из молодых людей? Возможные варианты высказываний Соответствие условию задачи ВК ¬ СК ¬ МА ВК СК МА 1 0 0 1 1 1 - 0 0 1 0 1 0 + 0 1 0 0 0 1 - Проанализируем строки в трёх последних столбцах. Условию задачи соответствует только вторая строка, значит Сергей изучает китайский язык, Михаил – японский (так как он не изучает арабский), тогда Вадим изучает арабский язык. Решение: Введём обозначения: ВК – Вадим изучает китайский язык, СК – Сергей изучает китайский язык, МА - Михаил изучает арабский язык. Занесём в таблицу возможные варианты значений высказываний с учётом условия задачи, что одно из утверждений верно, а два - ложны:
Задача 4. Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра — единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Определите, кто чем любит заниматься в свободное время и у кого какая профессия. Решение : Здесь исходные данные разбиваются на тройки (имя — профессия — увлечение). Из слов Юры ясно, что он не увлекается туризмом и он не врач. Из слов врача следует, что он турист. Имя Юра Профессия врач Увлечение туризм Буква "а", присутствующая в слове "врач", указывает на то, что Влад тоже не врач, следовательно врач — Тимур. В его имени есть буквы "т" и "р", встречающиеся в слове "туризм", следовательно второй из друзей, в названиях профессии и увлечения которого не встречается ни одна буква его имени — Юра. Юра не юрист и не регбист, так как в его имени содержатся буквы "ю" и "р". Следовательно, окончательно имеем: Имя Юра Тимур Влад Профессия физик врач юрист Увлечение бег туризм регби Ответ . Влад — юрист и регбист, Тимур — врач и турист, Юра — физик и бегун.
Задачи для самостоятельного решения Задача 1. Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок. — Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл. — Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым. Питер, к которому обратился Ник, возмутился: — Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину. По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки? Задача 2. В спортивных соревнованиях принимали участие пять команд: "Вымпел", "Метеор", "Нептун", "Старт" и "Чайка". Об их итогах соревнования имеется пять высказываний: 1) Второе место занял "Вымпел", a "Cтарт" оказался на третьем. 2) Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место. 3) Да нет же, "Чайка" заняла только третье место, а "Нептун"- был последним. 4) Первое место по праву завоевал "Cтарт", а "Метеор" был 4-м. 5) Да, "Метеор", действительно, был четвертым, а "Вымпел" был 2-м. Известно, что команды не делили места между собой и что в каждом высказывании одно утверждение правильное, а другое нет. Как распределились места между командами? Задача 3 Три дочери писательницы Дорис Кей — Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств — пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что: Джуди живет не в Париже, а Линда — не в Риме; парижанка не снимается в кино; та, кто живет в Риме, певица; Линда равнодушна к балету. Где живет Айрис, и какова ее профессия?
ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА
Логические элементы В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Знания из области математической логики можно использовать для конструирования различных электронных устройств. Нам известно, что 0 и 1 в логике не просто цифры, а обозначение состояний какого-то предмета нашего мира, условно называемых "ложь" и "истина". Таким предметом, имеющим два фиксированных состояния, может быть электрический ток. Были созданы устройства управления электричеством - электронные схемы, состоящие из набора полупроводниковых элементов. Такие электронные схемы, которые преобразовывают сигналы только двух фиксированных напряжений электрического тока стали называть логическими элементами . Логические элементы — это электронные устройства, которые преобразуют проходящие через них двоичные электрические сигналы по определенному закону . Логические элементы имеют один или несколько входов, на которые подаются электрические сигналы, обозначаемые условно 0 , если отсутствует электрический сигнал, и 1 , если имеется электрический сигнал. Также логические элементы имеют один выход, с которого снимается преобразованный электрический сигнал. Было доказано, что все электронные схемы компьютера могут быть реализованы с помощью трёх базовых логических элементов И, ИЛИ, НЕ.
Логический элемент НЕ (инвертор) Простейшим логическим элементом является инвертор , выполняющий функцию отрицания (инверсию). У этого элемента один вход и один выход. На функциональных схемах он обозначается: вход выход 1 0 0 1 Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот.
Логический элемент ИЛИ (дизъюнктор) Логический элемент, выполняющий логическое сложение, называется дизъюнктор . Он имеет, как минимум, два входа. На функциональных схемах он обозначается: Если хотя бы на один вход поступает сигнал 1, то на выходе будет сигнал 1. вход 1 вход 2 выход 0 0 0 0 1 1 1 0 1 1 1 1
Логический элемент И (конъюнктор) Логический элемент, выполняющий логическое умножение, называется конъюнктор. Он имеет, как минимум, два входа. На функциональных схемах он обозначается: На выходе этого элемента будет сигнал 1 только в том случае, когда на все входы поступает сигнал 1. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль. Другие логические элементы построены из трех простейших базовых элементов и выполняют более сложные логические преобразования информации. вход 1 вход 2 выход 0 0 0 0 1 0 1 0 0 1 1 1
Рассмотрим еще два логических элемента, которые играют роль базовых при создании более сложных элементов и схем . Логический элемент И-НЕ выполняет логическую функцию штрих Шеффера (И-НЕ), он имеет, как минимум, два входа. На функциональных схемах он обозначается: Логический элемент ИЛИ-НЕ выполняет логическую функцию стрелка Пирса (И-НЕ), он имеет, как минимум, два входа. На функциональных схемах он обозначается: . Логический элемент И-НЕ Логический элемент ИЛИ-НЕ вход 1 вход 2 выход 0 0 1 0 1 0 1 0 0 1 1 0 вход 1 вход 2 выход 0 0 1 0 1 1 1 0 1 1 1 0
Функциональные схемы Сигнал, выработанный одним логическим элементом, можно подавать на вход другого элемента, это дает возможность образовывать цепочки из отдельных логических элементов — функциональные схемы . Функциональная (логическая) схема – это схема, состоящая из логических элементов, которая выполняет определённую функцию. Анализируя функциональную схему, можно понять, как работает логическое устройство, т.е. дать ответ на вопрос: какую функцию она выполняет. Ясно, что элемент “И” осуществляет логическое умножение значений ¬А и В. Над результатом в элементе “НЕ” осуществляется операция отрицания, т.е. вычисляется значение выражения: Таким образом структурной формулой данной функциональной схемы является формула: Важной формой описания функциональных схем является структурная формула. Покажем на примере, как выписывают формулу по заданной функциональной схеме.
Таблица истинности функциональной схемы Для функциональной схемы можно составить таблицу истинности, то есть таблицу значений сигналов на входах и выходах схемы, по которой можно понять какую функцию выполняет данная схема. Таблица истинности - это табличное представление логической (функциональной) схемы в котором перечислены все возможные сочетания значений входных сигналов вместе со значением выходного сигнала для каждого из этих сочетаний. Составим таблицу истинности для данной логической схемы: А (вход 1) В (вход 2) С (выход) 0 0 0 1 1 0 1 1 Начертим таблицу: количество столбцов = количество входов + количество выходов, количество строк = 2 количество входов . В данной таблице 3 столбца и 4 строки. Заполним первые столбцы всеми возможными вариантами входных сигналов
Рассмотрим первый вариант входных сигналов: А=0, В=0. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу. Рассмотрим второй вариант входных сигналов: А=0, В=1. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=0), запишем в таблицу. Рассмотрим третий вариант входных сигналов: А=1, В=0. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу.
Рассмотрим четвёртый вариант входных сигналов: А=1, В=1. Проследим по схеме, как проходят и преобразуются входные сигналы. Результат, полученный на выходе (С=1), запишем в таблицу. В результате получаем таблицу истинности данной логической схемы: А (вход 1) В (вход 2) С (выход) 0 0 1 0 1 0 1 0 1 1 1 1 Задание. Построить таблицу истинности для данной логической схемы и записать формулу для данной схемы:
Логическая реализация типовых устройств компьютера Обработка любой информации на компьютере сводится к выполнению процессором различных арифметических и логических операций. Для этого в состав процессора входит так называемое арифметико-логическое устройство (АЛУ). Оно состоит из ряда устройств, построенных на рассмотренных выше логических элементах. Важнейшими из таких устройств являются триггеры, полусумматоры, сумматоры, шифраторы, дешифраторы, счетчики, регистры . Выясним , как из логических элементов разрабатываются логические устройства.
Этапы конструирования логического устройства. Конструирование логического устройства состоит из следующих этапов: 1. Построение таблицы истинности по заданным условиям работы проектируемого узла (т.е. по соответствию его входных и выходных сигналов). 2. Конструирование логической функции данного узла по таблице истинности, ее преобразование (упрощение), если это возможно и необходимо. 3. Составление функциональной схемы проектируемого узла по формуле логической функции. После этого остается только реализовать полученную схему.
Задание. Построить логическую схему для заданной таблицы истинности: А В С F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 Запишем логическую функцию по данной таблице истинности: Упростим полученное логическое выражение: Построим логическую схему для данного выражения:
Попробуем, действуя по этому плану, сконструировать устройство для сложения двух двоичных чисел (одноразрядный полусумматор). Пусть нам необходимо сложить двоичные числа А и В . Через P и S обозначим первую и вторую цифру суммы: A + B = P S . Вспомните таблицу сложения двоичных чисел. 1. Таблица истинности, определяющая результат сложения, имеет вид: Слагаемые Перенос Сумма А В Р S 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 2. Сконструируем функции P( A , B ) и S ( A , B ) по этой таблице: Преобразуем вторую формулу, пользуясь законами логики:
3. Теперь можно построить функциональную схему одноразрядного полусумматора: Чтобы убедиться в том, как работает схема, проследите за прохождением сигналов в каждом из четырёх случаев и составьте таблицу истинности данной логической схемы. Условное обозначение одноразрядного сумматора:
Одноразрядный двоичный сумматор на три входа и два выхода называется полным одноразрядным сумматором . Логика работы одноразрядного сумматора на три входа или полного сумматора приведена в таблице, где А, В - суммируемые двоичные цифры , Pо - перенос из младшего разряда, S - образующаяся сумма данного разряда и осуществляет перенос P в следующий старший разряд. Полный одноразрядный сумматор . Слагаемые Перенос из младшего разряда Сумма Перенос А B P 0 S P 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 Формула переноса: . Формула для вычисления суммы:
После преобразования формул ы переноса и суммы принима ю т вид: Теперь можно построить схему полного одноразрядного сумматора с учётом переноса из младшего разряда .
Сумматор - это электронная логическая схема, выполняющая суммирование двоичных чисел поразрядным сложением. Сумматор является центральным узлом арифметико-логического устройства процессора. Находит он применение и в других устройствах компьютера. В реальных электронных схемах сумматор изображается так: Сумматор выполняет сложение многозначных двоичных чисел . Он представляет собой последовательное соединение одноразрядных двоичных сумматоров , каждый из которых осуществляет сложение в одном разряде. Если при этом возникает переполнение разряда, то перенос суммируется с содержимым старшего соседнего разряда. На рисунке показано, как из N сумматоров можно составить устройство для сложения двух N-разрядных двоичных кодов, это схема многоразрядного сумматора.
ТРИГГЕР Триггер - электронная схема, применяемая для хранения значения одноразрядного двоичного кода. Воздействуя на входы триггера, его переводят в одно из двух возможных состояний (0 или 1). С поступлением сигналов на входы триггера в зависимости от его состояния либо происходит переключение, либо исходное состояние сохраняется. При отсутствии входных сигналов триггер сохраняет свое состояние сколь угодно долго. Термин триггер происходит от английского слова trigger - защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop , что в переводе означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в другое. Существуют разные варианты исполнения триггеров в зависимости от элементной базы (И-НЕ, ИЛИ-НЕ) и функциональных связей между сигналами на входах и выходах ( RS, JK, T, D и другие). Самый распространённый тип триггера - это RS -триггер ( S и R соответственно от английских set - установка, и reset - сброс). Условное обозначение RS -триггера:
RS-триггер RS-триггер построен на 2-х логических элементах: ИЛИ - НЕ либо И – НЕ. Как, правило, триггер имеет 2 выхода: прямой и инверсный Q и . Как он работает? Пусть на вход элемента №1 подан сигнал 1, а на вход элемента № 3 - 0. На выходе элемента №1 независимо от того, какой второй сигнал поступит на вход, будет 1, т.к. это элемент ИЛИ (по свойствам дизъюнкции). Пройдя через элемент № 2 сигнал примет значение 0 (Q=0). Следовательно, и на втором входе элемента № 3 установится сигнал 0. На выходе элемента №3 - 0. Пройдя через элемент № 4 сигнал изменится на 1. Следовательно, = 1. Убедимся, что данное устройство сохраняет информацию. Запомните, что S=0, R=1, Q=0, =1. В момент прекращения входных сигналов (S=0, R=0) на выходе =1. Это напряжение подается на вход элемента № 1. На выходе элемента №1 сохраняется 1, и на Q - сигнал 0. На входах элемента №3 - 0, следовательно =1. Таким образом, при отсутствии на внешних входах сигналов 1 триггер поддерживает постоянное напряжение на своих выходах. Чтобы изменить напряжение на выходах триггера, надо подать сигнал 1 на вход элемента № 3. Тогда Q=1, =0.
RS -триггер Вход Выход Режим работы S R Q 0 0 0 0 Хранение 1 0 1 0 Запись 1 0 1 0 1 Запись 0 1 1 Х Х Запрещение ( )
РЕГИСТРЫ РЕГИСТРЫ. Функциональная схема компьютера, состоящая из триггеров, предназначенная для запоминания многоразрядных кодов и выполнения над ними некоторых логических преобразова ни й называется регистром. Упрощенно регистр можно представить как совокупность ячеек, в каждой из которых может быть записано одно из двух значений: 0 или 1, то есть один разряд двоичного числа. С помощью регистров можно выполнять следующие операции: установку, сдвиг, преобразование. Основными типами регистров являются параллельные и последовательные (сдвигающие). Совокупность регистров, используемых ЭВМ для запоминания программы работы, исходных и промежуточных результатов называется оперативной памятью (ОП). Регистры содержатся в различных вычислительных узлах компьютера - процессоре, периферийных устройствах и т.д. Регистр - это устройство, предназначенное для хранения многоразрядного двоичного числового кода, которым можно представлять и адрес, и команду, и данные.
РЕГИСТРЫ Существует несколько типов регистров, отличающихся видом выполняемых операций. Некоторые важные регистры имеют свои названия, например: сдвиговый регистр - предназначен для выполнения операции сдвига; счетчики - схемы, способные считать поступающие на вход импульсы. К ним относятся Т -триггеры (название от англ. tumble - опрокидываться). Этот триггер имеет один счетный вход и два выхода. Под действием сигналов триггер меняет свое состояние с нулевого на единичное и наоборот. Число перебрасываний соответствует числу поступивших сигналов; счетчик команд - регистр устройства управления процессора (УУ), содержимое которого соответствует адресу очередной выполняемой команды; служит для автоматической выборки программы из последовательных ячеек памяти; регистр команд - регистр УУ для хранения кода команды на период времени, необходимый для ее выполнения. Часть его разрядов используется для хранения кода операции, остальные - для хранения кодов адресов операндов. В ЭВМ применяются регистры 8, 16, 32, 48 и 64 разрядов.
ШИФРАТОРЫ И ДЕШИФРАТОРЫ Шифратор и дешифратор являются типовыми узлами ЭВМ. Шифратор (кодер) - это логическое устройство, которое преобразует единичный сигнал на одном из входов в n- разрядный двоичный код. Наибольшее применение он находит в устройствах ввода информации (например в клавиатуре), для преобразования десятичных чисел в двоичную систему счисления. Дешифратор (декодер) - это логическое устройство, преобразующее двоичный код, поступающий на его входы, в сигнал только на одном из его выходов. Дешифраторы широко применяются в устройствах управления, в системах цифровой индикации с газоразрядными индикаторами, для построения распределителей импульсов по различным цепям и т.д. Схема используется для перевода двоичных цифр в десятичные. Дешифратор двоичного n -разрядного кода имеет 2 n выходов, т.к. каждому из 2 n значений входного кода должен соответствовать единичный сигнал на одном из выходов дешифратора.
Предварительный просмотр:
Подписи к слайдам:
ЛОГИКА НАУКА О ФОРМАХ И СПОСОБАХ МЫШЛЕНИЯ
МЫШЛЕНИЕ осуществляется через: Понятия Высказывания Умозаключения
ПОНЯТИЕ форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их друг от друга (Пример: Прямоугольник - геометрическая фигура у которой все углы прямые и противоположные стороны равны)
ВЫСКАЗЫВАНИЕ формулировка своего понимания окружающего мира (повествовательное предложение в котором что-либо утверждается или отрицается) (Пример: Париж – столица Франции)
ВЫСКАЗЫВАНИЕ ИСТИННОЕ ЛОЖНОЕ (Пример: Буква «А» - (Пример: Компьютер гласная) был изобретен до нашей эры)
УМОЗАКЛЮЧЕНИЕ форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение (знание или вывод) (Пример: любая теорема)
АЛГЕБРА ЛОГИКИ наука об общих операциях, аналогичных сложению и умножению, которые выполняются над высказываниями
Понятия алгебры логики: Логическая переменная – это простое высказывание, содержащее только одну мысль Обозначение: латинская буква (А, В, Х …) Значение: ИСТИНА (1) или ЛОЖЬ (0) Логическая функция – это составное высказывание, которое содержит несколько простых мыслей, соединенных между собой с помощью логических операций Обозначение: F Логические операции – логическое действие
Базовые логические операции Название Обозначение Союз в естественном языке Пример А – «Число 10 – четное» В – «Число 10 – отрицательное» Конъюнкция (логическое умножение) А ^ B или A & B И «Число 10 четное и отрицательное» - ЛОЖЬ Дизъюнкция (логическое сложение) A v B ИЛИ «Число 10 четное или отрицательно» - ИСТИНА Инверсия (отрицание) ¬ A или Ā НЕ «Число 10 нечетное» – ЛОЖЬ «Число 10 – не отрицательное» - ИСТИНА Импликация логическое следование) А → В ЕСЛИ … ТО …; КОГДА …. ТОГДА …. «Если число 10 – четное, то оно отрицательное» - ЛОЖЬ Эквивалентность (логическое равенство) А В или А ↔ В … ТОГДА И ТОЛЬКО ТОГДА, КОГДА … «Число 10 – четное тогда и только тогда, когда оно отрицательное» - ЛОЖЬ
Таблица истинности таблица определяющая значение сложного высказывания при всех возможных значениях простых высказываний
Таблица истинности для конъюнкции А В А ^ В 0 0 0 0 1 0 1 0 0 1 1 1 Вывод: Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны
Таблица истинности для дизъюнкции А В А v В 0 0 0 0 1 1 1 0 1 1 1 1 Вывод : Результат будет ложным тогда и только тогда, когда оба исходных высказывания ложны, и истинным во всех остальных случаях
Таблица истинности для инверсии А Ā 0 1 1 0 Вывод : Результат будет ложным, если исходное высказывание истинно, и наоборот.
Таблица истинности для импликации А В А → В 0 0 1 0 1 1 1 0 0 1 1 1 Вывод : Результат будет ложным тогда и только тогда, когда из истинного основания (А) следует ложное следствие (В)
Таблица истинности для эквивалентности А В А ↔ В 0 0 1 0 1 0 1 0 0 1 1 1 Вывод : Результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны
Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится ЛОГИЧЕСКОЕ ВЫРАЖЕНИЕ истина ложь
Порядок выполнения логических операций: Действия в скобках Инверсия Конъюнкция Дизъюнкция Импликация Эквивалентность
ПРИМЕР: Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдет на рыбалку» Это составное высказывание состоит из простых высказываний: А = «Петя поедет в деревню» В = «Будет хорошая погода» С = «Он пойдет на рыбалку» Записываем высказывание в виде логического выражения, учитывая порядок действий F = A ^ (B → C)
Упражнения: Есть два простых высказывания: А = «Число 10 четное» В = Волк – травоядное животное» Составьте из них все возможные составные высказывания и определите их истинность Запишите следующие высказывания в виде логических выражений: Неверно, что корова – хищное животное На уроке физики ученики выполняли лабораторную работу и сообщали результаты учителю. Если Маша – сестра Саши, то Саша - брат Маши.
Предварительный просмотр:
Подписи к слайдам:
Логика – это наука о формах и способах мышления. Основы формальной логики заложил Аристотель, который впервые отделил логические формы мышления (речи) от его содержания. 2
Мышление осуществляется в следующих формах: 3
Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта. Пример : Понятие «компьютер» объединяет множество электронных устройств, которые предназначены для обработки информации и обладают монитором и клавиатурой. 4
Высказывание – это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними. Алгебра высказываний определяет истинность или ложность составных высказываний 5
Умозаключение - прием мышления, позволяющий на основе одного или нескольких суждений-посылок получить новое суждение (знание или вывод). Примерами умозаключений являются доказательства теорем в геометрии. Теорема Пифагора 6
Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания. Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй высказываний. 7
Логическое выражение - это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками ) . Логические связки - это слова, которые подразумевают определённые логические связи между высказываниями - это “и”, “или”, “не”, “если ... то”, “либо ... либо” и другие 8
В булевой алгебре простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Существуют разные варианты обозначения истинности и ложности переменных: 9
Инверсия - это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным . Знаки операции инверсии: НЕ; ¬ 10
11 Таблица истинности операции инверсия
Объединение двух или более высказываний в одно при помощи союза «И» называется операцией логического умножения или конъюнкцией . Логическое выражение (конъюнкция) истинно только тогда, когда истинны входящие в него простые высказывания. Знаки операции конъюнкции: &; И; ˄ 12
13 Таблица истинности операции конъюнкция
14 Объединение двух или более высказываний в одно при помощи союза «ИЛИ» называется операцией логического сложения или дизъюнкцией. Выражение дизъюнкции истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний . Знаки операции дизъюнкции: &; ИЛИ; ˅
15 Таблица истинности операции дизъюнкции
16 Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием . Знаки операции импликации: если…, то … ; =>
17 Таблица истинности операции импликации Импликация (логическое следование) - соответствует речевому обороту ЕСЛИ... ТО
Эквиваленция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны. 18
19 Таблица истинности эквиваленции :
20 Порядок выполнения логических операций в сложном логическом выражении: Инверсия; Конъюнкция; Дизъюнкция; Импликация; Эквивалентность.
Задание 1 : Запишите высказывание “ если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог ”, используя знаки логических операций. 21 ОТВЕТ: (A v B) -> C
Задание 2 :определить результат логического выражения при заданных параметрах 22 ¬( ¬B & ¬C ) ¬( ¬A & ¬C ) , при А=1, В=1, С=1 ( А ( А & В) ) & ( А & (А В) ) , при А=1, В=1
Задание 3 : Для какого имени истинно высказывание : ¬ ( Первая буква имени гласная → Четвертая буква имени согласная )? 23 1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР
Предварительный просмотр:
Пример 1 (№ 13535)
По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А — 11, B — 101, C — 0. Укажите кодовое слово наименьшей возможной длины, которое можно использовать для буквы F. Если таких слов несколько, укажите то из них, которое соответствует наименьшему возможному двоичному числу. Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование
Решение: Будем строить граф, причем слева будут нули, а справа единицы
Ответ : 1000
Пример 2 (№ 1102)
Для кодирования букв Д, X, Р, О, В решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ХОРОВОД таким способом и результат запишите восьмеричным кодом.
Решение:
Сначала следует представить данные в условии числа в двоичном коде для этого воспользуемся таблицей триад и тетрад:
№п/п | |||||
0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 1 |
2 | 2 | 0 | 0 | 1 | 0 |
3 | 3 | 0 | 0 | 1 | 1 |
4 | 4 | 0 | 1 | 0 | 0 |
5 | 5 | 0 | 1 | 0 | 1 |
6 | 6 | 0 | 1 | 1 | 0 |
7 | 7 | 0 | 1 | 1 | 1 |
8 | 8 | 1 | 0 | 0 | 0 |
9 | 9 | 1 | 0 | 0 | 1 |
10 | A | 1 | 0 | 1 | 0 |
11 | B | 1 | 0 | 1 | 1 |
12 | C | 1 | 1 | 0 | 0 |
13 | D | 1 | 1 | 0 | 1 |
14 | E | 1 | 1 | 1 | 0 |
15 | F | 1 | 1 | 1 | 1 |
Красным цветом на соответствие букв и цифр
Д | Х | Р | О | В |
0 | 1 | 2 | 3 | 4 |
00 | 01 | 10 | 11 | 100 |
ХОРОВОД — 011110111001100. Теперь разобьём это представление по три цифры справа налево и переведём полученный набор чисел в десятичный код, затем в восьмеричный (восьмеричное предствление совпадает с десятичным при разбиении тройками) 011 110 111 001 100 — 3 6 7 1 4
Ответ: 36714
Пример 3 (№ 7441)
Для кодирования некоторой последовательности, состоящей из букв А, Б, В,Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:
А — 0; Б — 100; В — 1010; Г — 111; Д — 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
1) для буквы В — 101
2) это невозможно
3) для буквы В — 010
4) для буквы Б — 10
Решение:
Для однозначного декодирования получившееся в результате сокращения кодовое слово не должно быть началом никакого другого. Первый вариант ответа подходит. Третий вариант не подходит, поскольку код буквы А является началом кода буквы В. Четвёртый вариант ответа не подходит, т. к. в таком случае код буквы Б является началом кода буквы В.
Ответ: Правильный ответ указан под номером: 1.
Пример 4 (№ 15100)
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
Буква | Кодовое слово |
А | 11 |
Б | 0010 |
Г | 100 |
Е | 0011 |
Буква | Кодовое слово |
И | |
М | 01 |
Р | 000 |
Т |
Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Решение: Ветки будет две одну начнем с нуля другую с единицы
Ответ: 1010
Пример 5 (№ 3682)
Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.
Закодируйте таким образом изображение и запишите результат в восьмеричной системе счисления.
Решение:
Код первой строки: 10101.
Код второй строки: 11000.
Код третьей строки: 01010.
Запишем коды по порядку в одну строку: 101011100001010. Теперь разобьём это представление на тройки справа налево и переведём полученный набор чисел в десятичный код (восьмеричное предствление совпадает с десятичным при разбиении тройками).
101 011 100 001 010 — 5 3 4 1 2
Ответ: 53412
- Анонс событий
- НОВОСТИ
- Для 2 класса
- Для 3 класса
- Для 4 класса
- Для 5 класса
- Для 6 класса
- Для 7 класса
- Для 8 класса
- Для 9 класса
- Для 10 класса
- Для 11 класса
- Готовимся к ОГЭ
- Готовимся к ЕГЭ
- Полезные ссылки
- Методические материалы
- Расписание занятий на 2018-2019 уч.год
Об авторе
Получать статьи почтой
Статистика
Предварительный просмотр:
2.4. Массивы
Часто в программах бывает надо работать с большим количество однотипных переменных. Например, пусть вам надо записать рост каждого человека в классе — это много целых чисел. Вы можете завести по одной переменной на каждого ученика, но это очень не удобно. Специально для этого придуманы массивы.
2.4.1. Общее представление о массиве
Массив — это переменная, в которой хранится много значений. (В питоне еще принято название «список», это то же самое, хотя в других языках программирования «список» и «массив» — это разные вещи.) Массив можно представлять себе в виде такой последовательности ячеек, в каждой из которых записано какое-то число:
Такие ячейки нумеруются последовательно, начиная с нуля. На картинке выше числа внутри квадратиков — это значения, хранящиеся в массиве (еще говорят «элементы» массива, а числа под квадратиками — номера этих элементов (еще говорят «индексы» элементов). Например, элемент с индексом 2 имеет значение -3. Обратите внимание, что в массиве 6 элементов, но последний имеет номер 5, т.к. нумерация начинается с нуля. Это важно!
Соответственно, переменная теперь может хранить целиком такой массив. Создается такой массив, например, путем перечисления значений в квадратных скобках:
a = [7, 5, -3, 12, 2, 0]
Теперь переменная a хранит этот массив. К элементам массива можно обращаться тоже через квадратные скобки: a[2] — это элемент номер 2, т.е. в нашем случае это -3. Аналогично, a[5] — это 0. В квадратных скобках можно использовать любые арифметические выражения и даже другие переменные: a[2*2-1] — это 12, a[i] обозначает «возьми элемент с номером, равным значению переменной i», аналогично a[2*i+1] обозначает «возьми элемент с номером, равным 2*i+1», или даже a[a[4]] обозначает «возьми элемент с номером, равным четвертому элементу нашего массива» (в нашем примере a[4] — это 2, поэтому a[a[4]] — это a[2], т.е. -3).
Если указанный номер слишком большой (больше длины массива), то питон выдаст ошибку (т.е. в примере выше a[100] будет ошибкой, да и даже a[6] тоже). Если указан отрицательный номер, то тут действует хитрое правило. Отрицательные номера обозначают нумерацию массива с конца: a[-1] — это всегда последний элемент, a[-2] — предпоследний и т.д. В нашем примере a[-6] равно 7. Слишком большой отрицательный номер тоже дает ошибку (в нашем примере a[-7] уже ошибка).
С элементами массива можно работать как с привычными вам переменными. Можно им присваивать значения: a[3] = 10, считывать с клавиатуры: a[3] = int(input()), выводить на экран: print(a[3]), использовать в выражениях: a[3+i*a[2]] = 3+abs(a[1]-a[0]*2+i) (здесь i — какая-то еще целочисленная переменная для примера), использовать в if’ах: if a[i]>a[i-2]:, или for a[2] in range(n) и т.д. Везде, где вы раньше использовали переменные, можно теперь использовать элемент массива.
2.4.2. Обход массива
Но обычно вам надо работать сразу со всеми элементами массива. Точнее, сразу со всеми как правило не надо, надо по очереди с каждым (говорят: «пробежаться по массиву»). Для этого вам очень полезная вещь — это цикл for. Если вы знаете, что в массиве n элементов (т.е. если у вас есть переменная n и в ней хранится число элементов в массиве), то это делается так:
for i in range(n):
... что-то сделать с элементом a[i]
например, вывести все элементы массива на экран:
for i in range(n):
print(a[i])
или увеличить все элементы массива на единицу:
for i in range(n):
a[i] += 1
и т.п. Конечно, в цикле можно и несколько действий делать, если надо. Осознайте, что это не магия, а просто полностью соответствует тому, что вы знаете про работу цикла for.
Если же у вас нет переменной n, то вы всегда можете воспользоваться специальной функцией len, которая возвращает количество элементов в массиве:
for i in range(len(a)):
...
Функцию len, конечно, можно использовать где угодно, не только в заголовке цикла. Например, просто вывести длину массива — print(len(a)).
2.4.3. Операции на массиве
Еще ряд полезных операций с массивами:
- a[i] (на всякий случай повторю, чтобы было легче найти) — элемент массива с номером i.
- len(a) (на всякий случай повторю, чтобы было легче найти) — длина массива.
- a.append(x) — приписывает к массиву новый элемент со значением x, в результате длина массива становится на 1 больше. Конечно, вместо x может быть любое арифметическое выражение.
- a.pop() — симметричная операция, удаляет последний элемент из массива. Длина массива становится на 1 меньше. Если нужно запомнить значение удаленного элемента, надо просто сохранить результат вызова pop в новую переменную: res = a.pop().
- a * 3 — это массив, полученный приписыванием массива a самого к себе три раза. Например, [1, 2, 3] * 3 — это [1, 2, 3, 1, 2, 3, 1, 2, 3]. Конечно, на месте тройки тут может быть любое арифметическое выражение. Самое частое применение этой конструкции — если вам нужен массив длины n, заполненный, например, нулями, то вы пишете [0] * n.
- b = a — присваивание массивов. Теперь в b записан тот же массив, что и в a. Тот же — в прямом смысле слова: теперь и a, и b соответствуют одному и тому же массиву, и изменения в b отразятся в a и наоборот. Еще раз, потому что это очень важно. Присваивание массивов (и вообще любых сложных объектов) в питоне не копирует массив, а просто обе переменные начинают ссылаться на один и тот же массив, и изменения массива через любую из них меняет один и тот же массив. При этом на самом деле тут есть многие тонкости, просто будьте готовы к неожиданностям.
- b = a[1:4] («срез») — делает новый массив, состоящий из элементов старого массива начиная со первого (помните про нумерацию с нуля!) и заканчивая третьим (т.е. до четвертого, но не включительно, аналогично тому, как работает range); этот массив сохраняется в b. Для примера выше получится [5, -3, 12]. Конечно, на месте 1 и 4 может быть любое арифметическое выражение. Более того, эти индексы можно вообще не писать, при этом автоматически подразумевается начало и конец массива. Например, a[:3] — это первые три элемента массива (нулевой, первый и второй), a[1:] — все элементы кроме нулевого, a[:-1] — все элементы кроме последнего (!), а a[:] — это копия всего массива. И это именно копия, т.е. запись b = a[:] именно копирует массив, получающиеся массивы никак не связаны, и изменения в b не влияют на a (в отличие от b = a).
2.4.4. Ввод-вывод массива
Как вам считывать массив? Во-первых, если все элементы массива задаются в одной строке входного файла. Тогда есть два способа. Первый — длинный, но довольно понятный:
a = input().split() # считали строку и разбили ее по пробелам
# получился уже массив, но питон пока не понимает, что в массиве числа
for i in range(len(a)):
a[i] = int(a[i]) # прошли по всем элементам массива и превратили их в числа
Второй — покороче, но попахивает магией:
a = list(map(int, input().split()))
Может показаться страшно, но на самом деле map(int, input().split()) вы уже встречали в конструкции
x, y = map(int, input().split())
когда вам надо было считать два числа из одной строки. Это считывает строку (input()), разбивает по пробелам (.split()), и превращает каждую строку в число (map(int, ...)). Для чтения массива все то же самое, только вы еще заворачиваете все это в list(...), чтобы явно сказать питону, что это массив.
Какой из этих двух способов использовать для чтения данных из одной строки — выбирать вам, особой разницы нет.
Обратите внимание, что в обоих способах вам не надо знать заранее, сколько элементов будет в массиве — получится столько, сколько чисел в строке. В задачах часто бывает что задается сначала количество элементов, а потом (обычно на следующей строке) сами элементы. Это удобно в паскале, c++ и т.п., где нет способа легко считать числа до конца строки; в питоне вам это не надо, вы легко считываете сразу все элементы массива до конца строки, поэтому заданное число элементов вы считываете, но дальше не используете:
n = int(input()) # больше n не используем
a = list(map(int, input().split()))
Еще бывает, что числа для массива задаются по одному в строке. Тогда вам проще всего заранее знать, сколько будет вводиться чисел. Обычно как раз так данные и даются: сначала количество элементов, потом сами элементы. Тогда все вводится легко:
n = int(input())
a = [] # пустой массив, т.е. массив длины 0
for i in range(n):
a.append(int(input())) # считали число и сразу добавили в конец массива
Более сложные варианты — последовательность элементов по одному в строке, заканчивающаяся нулем, или задано количество элементов и сами элементы в той же строке — придумайте сами, как сделать (можете подумать сейчас, можете потом, когда попадется в задаче). Вы уже знаете всё, что для этого надо.
Как выводить массив? Если надо по одному числу в строку, то просто:
for i in range(len(a)):
print(a[i])
Если же надо все числа в одну строку, то есть два способа. Во-первых, можно команде print передать специальный параметр end=" ", который обозначает «заканчивать вывод пробелом (а не переводом строки)»:
for i in range(len(a)):
print(a[i], end=" ")
Есть другой, более простой способ:
print(*a)
Эта магия обозначает вот что: возьми все элементы массива a и передай их отдельными аргументами в одну команду print. Т.е. получается print(a[0], a[1], a[2], ...).
2.4.5. Двумерные массивы
Выше везде элементами массива были числа. Но на самом деле элементами массива может быть что угодно, в том числе другие массивы. Пример:
a = [10, 20, 30]
b = [-1, -2, -3]
c = [100, 200]
z = [a, b, c]
Что здесь происходит? Создаются три обычных массива a, b и c, а потом создается массив z, элементами которого являются как раз массивы a, b и c.
Что теперь получается? Например, z[1] — это элемент №1 массива z, т.е. b. Но b — это тоже массив, поэтому я могу написать z[1][2] — это то же самое, что b[2], т.е. -3 (не забывайте, что нумерация элементов массива идет с нуля). Аналогично, z[0][2]==30 и т.д.
То же самое можно было записать проще:
z = [[10, 20, 30], [-1, -2, -3], [100, 200]]
Получилось то, что называется двумерным массивом. Его можно себе еще представить в виде любой из этих двух табличек:
Первую табличку надо читать так: если у вас написано z[i][j], то надо взять строку №i и столбец №j. Например, z[1][2] — это элемент на 1 строке и 2 столбце, т.е. -3. Вторую табличку надо читать так: если у вас написано z[i][j], то надо взять столбец №i и строку №j. Например, z[1][2] — это элемент на 2 столбце и 1 строке, т.е. -3. Т.е. в первой табличке строка — это первый индекс массива, а столбец — второй индекс, а во второй табличке наоборот. (Обычно принято как раз обозначать i первый индекс и j — второй.)
Когда вы думаете про таблички, важно то, что питон на самом деле не знает ничего про строки и столбцы. Для питона есть только первый индекс и второй индекс, а уж строка это или столбец — вы решаете сами, питону все равно. Т.е. z[1][2] и z[2][1] — это разные вещи, и питон их понимает по-разному, а будет 1 номером строки или столбца — это ваше дело, питон ничего не знает про строки и столбцы. Вы можете как хотите это решить, т.е. можете пользоваться первой картинкой, а можете и второй — но главное не запутайтесь и в каждой конкретной программе делайте всегда всё согласованно. А можете и вообще не думать про строки и столбцы, а просто думайте про первый и второй индекс.
Обратите, кстати, внимание на то, что в нашем примере z[2] (массив, являющийся вторым элементом массива z) короче остальных массивов (и поэтому на картинках отсутствует элемент в правом нижнем углу). Это общее правило питона: питон не требует, чтобы внутренние массивы были одинаковой длины. Вы вполне можете внутренние массивы делать разной длины, например:
x = [[1, 2, 3, 4], [5, 6], [7, 8, 9], [], [10]]
здесь нулевой массив имеет длину 4, первый длину 2, второй длину 3, третий длину 0 (т.е. не содержит ни одного элемента), а четвертый длину 1. Такое бывает надо, но не так часто, в простых задачах у вас будут все подмассивы одной длины.
(На самом деле даже элементы одного массива не обязаны быть одного типа. Можно даже делать так: y = [[1, 2], 3, 4], здесь нулевой элемент массива z — сам является массивом, а еще два элемента — просто числа. Но это совсем редко бывает надо.)
2.4.6. Операции над двумерным массивом
Собственно, никаких новых операций над двумерными массивами нет. Вы всегда работаете или с внешним массивом, или с каким-то внутренним массивом, и можете использовать все операции, которые знаете для одномерных массивов. Например, len(z) — это длина «внешнего» массива (в примере выше получается 3, т.к. z содержит три элемента, и не важно, что каждый из них тоже массив), а len(z[2]) — длина внутреннего массива на позиции 2 (т.е. 2 в примере выше). Для массива x выше (того, у которого каждый подмассив имеет свою длину) получим len(x)==5, и, например, len(x[3])==0.
Аналогично работают все остальные операции. z.append([1,2]) приписывает к «внешнему» массиву еще один «внутренний» массив, а z[2].append(3) приписывает число 3 к тому «внутреннему» массиву, который находится на позиции 2. Далее, z.pop() удаляет последний «внутренний» из «внешнего» массива, а z[2].pop() удаляет последний элемент из «внутреннего» массива на позиции 2. Аналогично работают z[1:2] и z[1][0:1] и т.д. — все операции, которые я приводил выше.
2.4.7. Обход двумерного массива
Конечно, чтобы обойти двумерный массив, надо обойти каждый его «внутренний» массив. Чтобы обойти внутренний массив, нужен цикл for, и еще один for нужен, чтобы перебрать все внутренние массивы:
for i in range(len(z)):
# будем теперь обходить массив z[i]
for j in range(len(z[i])):
...что-то сделаем с элементом z[i][j]
2.4.8. Создание двумерного массива
Неожиданно нетривиальная операция на двумерных массивах — это создание двумерного массива определенного размера, заполненного, например, нулями. Вы помните, что одномерный массив длины n можно создавать как [0] * n. Возникает желание написать a = [[0] * m] * n, чтобы создать двумерный массив размера n x m (мы хотим, чтобы первый индекс массива менялся от 0 до n-1, а второй индекс до m-1, поэтому это именно [[0] * m] * n, а не [[0] * n] * m). Но это сработает не так, как вы можете думать. Дело опять в том, что в питоне массивы по умолчанию не копируются полностью, поэтому то, что получается — это массив длина n, в котором каждый элемент соответствует одному и тому же массиву длины m. В итоге, если вы будете менять, например, a[1][2], то так же будет меняться и a[0][2], и a[3][2] и т.д. — т.к. все внутренние массивы на самом деле соответствуют одному и тому же массиву.
Поэтому массив размера n x m делается, например, так:
a = []
for i in range(n):
a.append([0] * m)
мы вручную n раз приписали к массиву a один и тот же массив.
Или еще есть магия в одну строчку:
a = [[0] * m for i in range(n)]
Я пока не буду объяснять, как это работает, просто можете запомнить. Или пользоваться предыдущим вариантом.
Обратите внимание, что тут важный момент — хотим мы, чтобы n соответствовало первому индексу или второму. В примерах выше n — размер первого индекса (т.е. размер «внешнего» массива), a m — размер второго индекса (т.е. размер каждого «внутреннего» массива). Если вы хотите, то можно делать и наоборот, но это вы сами должны решить и делать согласованно во всей программе.
2.4.9. Ввод-вывод двумерного массива
Обычно двумерный массив вам задается как n строк по m чисел в каждой, причем числа n и m вам задаются заранее. Такой двумерный массив вводится эдакой комбинацией двух способов ввода одномерного массива, про которые я писал выше:
n, m = map(int, input().split()) # считали n и m из одной строки
# m дальше не будет нужно
a = []
for i in range(n):
a.append(list(map(int, input().split())))
Мы считываем очередную строку и получаем очередной «внутренний» массив: list(map(int, input().split())), и приписываем его (append) ко внешнему массиву.
Обратите внимание, что здесь мы уже четко решили, что первый индекс нашего массива соответствует строкам входного файла, а второй индекс — столбцам, т.е. фактически мы уже выбрали левую из двух картинок выше. Но это связано не с тем, как питон работает с двумерными массивами, а с тем, как заданы входные данные во входном файле.
Вывод двумерного массива, если вам его надо вывести такой же табличкой, тоже делается комбинацией способов вывода одномерного массива, например, так:
for i in range(len(a)):
print(*a[i])
или так:
for i in range(len(a)):
for j in range(len(a[i])):
print(a[i][j], end=" ")
print() # сделать перевод строки
2.4.10. Многомерные массивы
Аналогично двумерным, бывают и трехмерные и т.д. массивы. Просто каждый элемент «внутреннего» массива теперь сам будет массивом:
a = [[[1, 2], [3, 4]], [[5, 6], [7, 8]]]
Здесь a[0] — это двумерный массив [[1, 2], [3, 4]], и a[1] — двумерный массив [[5, 6], [7, 8]]. Например, a[1][0][1] == 6.
Многомерные массивы в простых задачах не нужны, но на самом деле бывают полезны и не представляют из себя чего-то особо сложного. С ними все аналогично тому, что мы обсуждали про двумерные массивы.
2.4.11. Примеры решения задач
Приведу несколько примеров задач, аналогичных тем, которые встречаются на олимпиадах и в моем курсе.
Задача 2.13:
В классе N школьников. На уроке физкультуры тренер говорит «на первый-второй рассчитайтесь». Выведите, что скажут ученики — сначала сформируйте массив с числами, а потом его вывдите.
Входные данные: Вводится одно целое число — количество человек в классе.
Входные данные: Выведите последовательность чисел 1 и 2, в том порядке, как будут говорить школьники.
Пример:
Входные данные:
5
Выходные данные:
1 2 1 2 1
Это в некотором плане искусственная задача, потому что массивы тут на самом деле не нужны. Но давайте представим себе, что нам действительно надо сформировать такой массив. Для этого есть два подхода.
Во-первых, мы можем сразу заготовить «пустой» массив длины N. Точнее, конечно, не пустой, а заполненный чем-то, не важно, чем, пусть, для примера, числами −1:
n = int(input())
a = [-1] * n
Далее нам надо собственно установить в массиве элементы в правильные значения. Для этого надо сделать какие-то действия с каждым элементом массива, т.е. надо написать цикл:
for i in range(len(a)):
На каждой итерации цикла нам надо решить, что делать с текущим, т.е. i-м, элементом массива. В зависимости от четности i надо записать туда или 1, или 2:
if i % 2 == 0:
a[i] = 1
else:
a[i] = 2
Ну и наконец вывести массив, чтобы вывести в одну строку, надо написать
print(*a)
Итоговый код:
n = int(input())
a = [-1] * n
for i in range(len(a)):
if i % 2 == 0:
a[i] = 1
else:
a[i] = 2
print(*a)
Альтернативное решение — создать сначала пустой массив, а дальше приписывать к нему числа по одному:
n = int(input())
a = []
for i in range(n):
if i % 2 == 0:
a.append(1)
else:
a.append(2)
print(*a)
Задача 2.14:
Дан массив из N чисел. Выведите их в обратном порядке.
Входные данные: На первой строке вводится одно целое число N. На второй строке вводятся N чисел — заданный массив.
Входные данные: Выведите массив в обратном порядке.
Пример:
Входные данные:
5
10 30 20 40 50
Выходные данные:
50 40 20 30 10
Во-первых, считаем массив. Тут задается сначала число элементов, на следующей строке — сами элементы массива. В питоне нам число элементов не нужно, мы можем использовать функцию len, но считать число элементов все равно надо, потому что оно есть во входных данных:
n = int(input())
a = list(map(int, input().split()))
Далее надо вывести элементы в обратном порядке. Это можно сделать разными способами.
Например, можно взять срез, дающий элементы в обратном порядке, сохранить в другой массив и вывести:
b = a[::-1]
print(*b)
или сразу, без промежуточной переменной:
print(*a[::-1])
Полный код:
n = int(input())
a = list(map(int, input().split()))
print(*a[::-1])
Альтернативный вариант — сделать цикл по убыванию и выводить числа:
for i in range(len(a) - 1, -1, -1):
print(a[i])
Единственная проблема — этот цикл выводит числа «в столбик», а не в одну строку. Во многих задачах в реальных тестирующих системах это не так страшно, но если важно, можно попросить print не переводить строку после вывода числа, а просто выводить пробел: print(a[i], end=' ').
Полный код:
n = int(input())
a = list(map(int, input().split()))
for i in range(len(a) - 1, -1, -1):
print(a[i], end=' ')
Задача 2.15:
В вагоне поезда N мест, занумерованных от 1 до N. Всего в этот вагон продано K билетов, занумерованных от 1 до K. В каждом билете указано место, на котором поедет пассажир, в разных билетах указаны разные места. Занумеруем пассажиров в соответствии с их билетами от 1 до K. Для каждого места выведите номер пассажира, который на нем поедет.
Входные данные: На первой строке вводятся два целых числа — N и K. На второй строке вводятся K чисел — номера мест, указанные в билетах (начиная с первого билета и заканчивая K-м).
Входные данные: Выведите N чисел — для каждого места от 1 до N выведите номер пассажира, который поедет на этом месте, или 0, если место останется пустым.
Пример:
Входные данные:
5 3
2 5 1
Выходные данные:
3 1 0 0 2
Сначала, конечно, считаем данные:
n, k = map(int, input().split())
a = list(map(int, input().split()))
Дальше самый простой способ состоит в следующем. Заведем новый массив для ответов, сразу длины N, заполненный нулями (как будто пока все места пустые):
b = [0] * n
Далее, пройдем по массиву билетов и каждого пассажира посадим на его место, т.е. прямо в массив b на нужное место запишем номер пассажира:
for i in range(len(a)):
b[a[i] - 1] = i + 1
Что здесь происходит? a[i] — это номер места, на котором едет i-й пассажир, соответственно, это индекс в массиве b, куда надо поставить номер этого пассажира. Только одна проблема — по условию, места нумеруются начиная с 1, а в массиве индексы нумеруются начиная с 0, поэтому на самом деле нужный индекс в массиве b равен не a[i], а a[i]−1.
Соответственно, в этот элемент массива b, т.е. в b[a[i]−1], записываем номер пассажира, т.е. i. Тут опять-таки проблема с тем, что по условию пассажиры нумеруются начиная с 1, а в программе получается нумерация с нуля, поэтому надо записывать не i, а i+1.
Остается только вывести массив b. Полный код:
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * n
for i in range(len(a)):
b[a[i] - 1] = i + 1
print(*b)
Альтернативное решение могло быть следующим: не будем создавать массив b, а просто для каждого места будем заново проходить по всему массиву a и искать, кто же едет на этом месте:
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
p = 0
for j in range(k):
if a[j] == i + 1:
p = j + 1
print(p, end=' ')
но это решение значительно дольше, потому что оно каждый раз заново бегает по массиву.
Задача 2.16:
Дан массив из N чисел. Переставьте элементы прямо в этом массиве в обратном порядке. Дополнительные массивы использовать запрещается.
Я не буду в этой задаче указывать формат входных и выходных данных, потому что не в них суть. Надо придумать, как, имея уже готовый массив, поменять его так, чтобы элементы шли в обратном порядке, но в целом в этом же массиве (а не в новом). Естественно, можно использовать дополнительные переменные, но не массивы.
Решение этой задачи я тут писать не буду, напишу только подсказку, как решение можно придумать.
Представьте себе автомобильную паркову на N мест в ряд. На ней стоят N разных автомобилей. Эта парковка — ваш массив, а автомобили — элементы массива. Вам надо переставить их в обратном порядке, чтобы автомобиль, стоящий на первом месте, оказался бы на последнем, и т.д. Вы можете передвигать любой автомобиль, но при этом у вас нет никаких помощников, вы должны все делать в одиночку (т.е., например, вы не можете одновременно двигать два автомобиля). Зато у вас есть свободная площадка снаружи — дополнительные переменные. Вы не можете туда перегнать все автомобили сразу (потому что это значит использовать новый массив), но по 1-2 автомобиля перегонять туда вы можете.
Если в уме сложно придумать, найдите дома несколько (4-5) игрушечных машинок, и поэкспериментируйте на них. Если нет машинок, возьмите другие однотипные элементы — ручки, карандаши и т.п.
Задача 2.17:
Соревнования по фигурному катанию судят N судей. В соревнованиях участвуют K спортсменов. Каждый судья выставляет оценку каждому спорстмену. Итоговый балл каждого спортсмена равен сумме его N оценок. По данным оценкам определите итоговый балл каждого спортсмена.
Входные данные: На первой строке вводятся два целых числа — N и K. Далее следуют N строк по K чисел в каждой — оценки каждого судьи.
Входные данные: Выведите K чисел — суммарный балл каждого спорстмена.
Пример:
Входные данные:
2 3
1 2 3
2 3 1
Выходные данные:
3 5 4
Здесь надо уже работать с двумерными массивами. Давайте сначала считаем массив:
n, k = map(int, input().split())
a = []
for i in range(n):
a.append(list(map(int, input().split())))
(Обратите внимание, что нам повезло, что первое из введенных чисел равно количеству строк во входных данных дальше, а второе — количеству столбцов. Так чаще всего двумерные массивы и задаются. Но бывает и по-другому, например, вполне могло бы сначала задаваться количество спортсменов, а потом количество судей, а дальше оценки в том же формате. Тогда надо было бы аккуратно суметь не перепутать N и K.)
Далее заведем массив для итоговых баллов каждого спортсмена:
b = [0] * k
Изначально массив заполнен нулями.
Дальше пройдемся по массиву a, и каждую оценку прибавим к баллу соответствующего спорстмена.
Обходить двумерный массив можно так:
for i in range(n):
for j in range(k):
Теперь мы стоим в клетке (i,j), т.е. работает с элементом a[i][j]. Здесь i — номер судьи, а j — номер спортсмена (порядок индексов именно такой, потому что мы так вводили массив). Значит, эту оценку надо прибавить к баллу j-го спортсмена, т.е. к b[j]:
b[j] += a[i][j]
Итоговый код получается такой:
n, k = map(int, input().split())
a = []
for i in range(n):
a.append(list(map(int, input().split())))
b = [0] * k
for i in range(n):
for j in range(k):
b[j] += a[i][j]
print(*b)