У васи есть два способа

У Васи есть набор из 4n строк одинаковой длины, состоящих только из строчных латинских букв « a », « b », « c », « d » и « e », причем они разбиты на n групп по 4 одинаковые строки. У Васи также есть одна особая строка a той же длины, состоящая только из букв « a ».

Вася хочет получить из строки a некоторую заданную строку b , для этого он может использовать имеющиеся у него строки в любом порядке. При использовании некоторой строки x каждый из символов строки a заменяется на следующий в алфавите столько раз, каким по счету в алфавите является соответствующий символ строки x , считая с нуля. При этом следующей для буквы « e » является буква « a ».

Например, если некоторая буква строки a равна « b », а буква на той же позиции строки x равна « c », то буква строки a становится равной « d », так как « c » — второй символ алфавита, считая с нуля. Если же в строке a была буква « e », а в строке x — « d », то буква в строке a заменится на « c ». Например, если строка a была равна « abcde », а строка x — « baddc », то строка a станет равной « bbabb ».

После использовании строки она исчезает, но Вася может несколько раз использовать равные строки.

Васю интересует для q заданных строк b , сколько существует способов получить из строки a строку b заданным набором из 4n строк? Два способа считаются различными, если количество строк, использованных из какой-то группы из 4 строк, различно. Помогите Васе, посчитайте ответы на эти вопросы по модулю 10 9 + 7 .

В первой строке через пробел записаны два целых числа: n и m ( 1 ≤ n, m ≤ 500 ) — количество четверок строк в наборе, и длина каждой из них.

В каждой из следующих n строк находится строка s длины m , состоящая только из строчных латинских букв « a », « b », « c », « d » и « e ». Это означает, что очередная четверка строк в наборе Васи равна строке s .

В следующей строке находится одно целое число q ( 1 ≤ q ≤ 300 ) — количество строк b , интересных Васе.

В каждой из следующих q строк находится строка b длины m , состоящая только из строчных латинских букв « a », « b », « c », « d » и « e » — строка, интересующая Васю.

Для каждой интересной Васе строки выведите количество способов получить ее из строки a по модулю 10 9 + 7 .

Источник

У васи есть два способа

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

Если вариант задан учителем, вы можете вписать или загрузить в систему ответы к заданиям с развернутым ответом. Учитель увидит результаты выполнения заданий с кратким ответом и сможет оценить загруженные ответы к заданиям с развернутым ответом. Выставленные учителем баллы отобразятся в вашей статистике.

Информационное сообщение объемом 2.5 Кбайт передается со скоростью 2560 бит/мин. За сколько минут будет передано данное сообщение?

Объём информации вычисляется по формуле Q = q * t, где t — время передачи q — cкорость передачи данных. Поэтому

t = 2,5 * 2 13 бит : (2 8 бит/мин * 10с) = 0, 25 * 2 5 = 8 мин.

У Кати есть доступ в Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2 20 бит в секунду. У Сергея нет скоростного доступа в Интернет, но есть возможность получать информацию от Кати по телефонному каналу со средней скоростью 2 13 бит в секунду. Сергей договорился с Катей, что она скачает для него данные объёмом 9 Мбайт по высокоскоростному каналу и ретранслирует их Сергею по низкоскоростному каналу. Компьютер Кати может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Катей данных до полного их получения Сергеем? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Нужно определить, сколько времени будет передаваться файл объемом 9 Мбайт по каналу со скоростью передачи данных 2 13 бит/с; к этому времени нужно добавить задержку файла у Кати (пока она не получит 1024 Кбайт данных по каналу со скоростью 2 20 бит/с).

Переведём объём информации из Мб в биты: Q = 9 Мб = 9 * 2 20 байт = 9 * 2 23 бит.

Время задержки: = 1024 кб / 2 20 бит/с = 2 (10 + 10 + 3) — 20 c = 2 3 c.

Время скачивания данных Сергеем: = 9 * 2 23 бит / 2 13 бит/с = 9 * 2 10 c.

Полное время: =9 * 2 10 c + 2 3 c = (9216 + 8) c = 9224 c.

Сколько секунд потребуется модему, передающему сообщения со скоростью 28800 бит/с, чтобы передать растровое изображение размером пикселей, при условии, что в палитре цветов?

С помощью N бит можно закодировать 2 N вариантов. Количество цветов 2 24 , следовательно, один цвет кодируется 24 битами. Один цвет занимает один пиксел.

Время t вычисляется по формуле t = Q / q, где Q — объем файла, q — cкорость передачи данных.

Q = 800 * 600 * 24 бит = 480 000 * 24 бит.

t = 480 000 * 24 бит / 28 800 бит/с = 400 с.

У Васи есть доступ к Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения им информации 2 18 бит в секунду. У Пети нет скоростного доступа в Интернет, но есть возможность получать информацию от Васи по низкоскоростному телефонному каналу со средней скоростью 2 14 бит в секунду. Петя договорился с Васей, что тот будет скачивать для него данные объемом 6 Мбайт по высокоскоростному каналу и ретранслировать их Пете по низкоскоростному каналу. Компьютер Васи может начать ретрансляцию данных не раньше, чем им будут получены первые 512 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах), с момента начала скачивания Васей данных, до полного их получения Петей? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Нужно определить, сколько времени будет передаваться файл объемом 6 Мбайт по каналу со скоростью передачи данных 2 14 бит/с; к этому времени нужно добавить задержку файла у Васи (пока он не получит 512 Кбайт данных по каналу со скоростью 2 18 бит/с).

Переведём объём информации в Мб в биты: Q = 6 Мб = 6 * 2 20 байт = 6 * 2 23 бит.

Время задержки: = 512 кб / 2 18 бит/с = 2 (9 + 10 + 3) — 18 c = 2 4 с = 16 c.

Время скчивания данных Петей: = 6 * 2 23 бит / 2 14 бит/с = 6 * 2 9 с = 3072 c.

Полное время: = (3072 + 16) c = 3088 c.

Скорость передачи данных через ADSL-соединение равна 256000 бит/c. Передача файла через это соединение заняла 2 минуты. Определите размер файла в килобайтах.

Объём информации вычисляется по формуле Q = q * t, где t — время передачи q — cкорость передачи данных. Поэтому

У Васи есть доступ к Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения им информации 2 19 бит в секунду. У Пети нет скоростного доступа в Интернет, но есть возможность получать информацию от Васи по низкоскоростному телефонному каналу со средней скоростью 2 15 бит в секунду. Петя договорился с Васей, что тот будет скачивать для него данные объемом 10 Мбайт по высокоскоростному каналу и ретранслировать их Пете по низкоскоростному каналу. Компьютер Васи может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах), с момента начала скачивания Васей данных, до полного их получения Петей? В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Нужно определить, сколько времени будет передаваться файл объемом 10 Мбайт по каналу со скоростью передачи данных 2 15 бит/с; к этому времени нужно добавить задержку файла у Васи (пока он не получит 1024 Кбайт данных по каналу со скоростью 2 19 бит/с).

Переведём объём информации в Мб в биты: Q = 10 Мб = 10 * 2 20 байт = 10 * 2 23 бит.

Время задержки: = 1024 кб / 2 19 бит/с = 2 (10 + 10 + 3) — 19 c = 2 4 c.

Время скачивания данных Петей: = 10 * 2 23 бит / 2 15 бит/с = 10 * 2 8 c.

Полное время: = 10 * 2 8 c + 2 4 c = (256 * 10 + 16) c = 2576 c.

Источник

У васи есть два способа

Урок 11. Логические элементы. Решение логических задач.

Решение логических задач

Рассмотрим несколько способов решения логических задач.

Задача 1. Коля, Вася и Серёжа гостили летом у бабушки. Однажды один из мальчиков нечаянно разбил любимую бабушкину вазу. На вопрос, кто разбил вазу, они дали такие ответы:

Серёжа: 1) Я не разбивал. 2) Вася не разбивал.

Вася: 3) Серёжа не разбивал. 4) Вазу разбил Коля.

Коля: 5) Я не разбивал. 6) Вазу разбил Серёжа.

Бабушка знала, что один из её внуков, назовём его правдивым, оба раза сказал правду; второй, назовём его шутником, оба раза сказал неправду; третий, назовём его хитрецом, один раз сказал правду, а другой раз — неправду. Назовите имена правдивого, шутника и хитреца. Кто из внуков разбил вазу?

Решение. Пусть К = «Коля разбил вазу», В = «Вася разбил вазу», С = «Серёжа разбил вазу». Составим таблицу истинности, с которой представим высказывания каждого мальчика 1 .

1 С учётом того, что ваза разбита одним внуком, можно было составлять не всю таблицу, а только её фрагмент, содержащий следуюнще наборы входных переменных: 001, 010, 100.

Исходя из того, что знает о внуках бабушка, следует искать в таблице строки, содержащие в каком-либо порядке три комбинации значений: 00, 11, 01 (или 10). Таких строк в таблице оказалось две (они отмечены галочками). Согласно второй из них, вазу разбили Коля и Вася, что противоречит условию. Согласно первой из найденных строк, вазу разбил Серёжа, он же оказался хитрецом. Шутником оказался Вася. Имя правдивого внука — Коля.

Задача 2. В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположения о возможных победителях:

Сима будет первой, Валя — второй;
Сима будет второй, Даша — третьей;
Алла будет второй, Даша — четвёртой.

По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое ложно. Какое место на соревнованиях заняла каждая из девушек, если все они оказались на разных местах?

Решение. Рассмотрим простые высказывания:

C₁ = «Сима заняла первое место»;

В₂ = «Валя заняла второе место»;

С₂ = «Сима заняла второе место»;

Д₃ = «Даша заняла третье место»;

А₂ = «Алла заняла второе место»;

Д₄ = «Даша заняла четвёртое место».

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

Логическое произведение истинных высказываний будет истинным:

На основании распределительного закона преобразуем левую часть этого выражения:

Высказывание С₁ • С₂ означает, что Сима заняла и первое, и второе места. Согласно условию задачи, это высказывание ложно. Ложным является и высказывание В₂• С₂. Учитывая закон операций с константой 0, запишем:

Дальнейшее преобразование левой части этого равенства и исключение заведомо ложных высказываний дают:

Из последнего равенства следует, что С₁ = 1, Д₃ = 1, А₂ = 1. Это означает, что Сима заняла первое место, Алла — второе, Даша — третье. Следовательно, Валя заняла четвёртое место.

Познакомиться с другими способами решения логических задач, а также принять участие в Интернет-олимпиадах и конкурсах по их решению вы сможете на сайте «Математика для школьников» (http://www.kenqyry.com/).

На сайте http://www.kaser.com/ вы сможете скачать демонстрационную версию очень полезной, развивающей логику и умение рассуждать логической головоломки Шерлок.

1.3.6. Логические элементы

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

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

На рис. 1.5 приведены условные обозначения (схемы) логических элементов, реализующих логическое умножение, логическое сложение и инверсию.

Рис 1.5.
Логические элементы

Логический элемент И (конъюнктор) реализует операцию логического умножения (рис. 1.5, а). Единица на выходе этого элемента появится только тогда, когда на всех входах будут единицы.

Логический элемент ИЛИ (дизъюнктор) реализует операцию логического сложения (рис. 1.5, б). Если хотя бы на одном входе будет единица, то на выходе элемента также будет единица.

Логический элемент НЕ (инвертор) реализует операцию отрицания (рис. 1.5, в). Если на входе элемента О, то на выходе 1 и наоборот.

Компьютерные устройства, производящие операции над двоичными числами, и ячейки, хранящие данные, представляют собой электронные схемы, состоящие из отдельных логических элементов. Более подробно эти вопросы будут раскрыты в курсе информатики 10-11 классов.

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

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

Таблицу истинности можно построить и по логическому выражению, соответствующему электронной схеме. Последний логический элемент в рассматриваемой схеме — конъюнктор. В него поступают сигналы от входа Л и от инвертора. В свою очередь, в инвертор поступает сигнал от входа В. Таким образом,

Составить более полное представление о логических элементах и электронных схемах вам поможет работа с тренажёром «Логика» (http://kpolyakov. narod. ru/prog/logic. htm).

Самое главное

Высказывание — это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.

Основные логические операции, определённые над высказываниями: инверсия, конъюнкция, дизъюнкция.

Таблицы истинности для основных логических операций:

При вычислении логических выражений сначала выполняются действия в скобках. Приоритет выполнения логических операций:

Вопросы и задания

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

По запросу сомики & гуппи было найдено 0 сайтов, по запросу сомики & меченосцы — 20 сайтов, а по запросу меченосцы & гуппи — 10 сайтов.

Сколько сайтов будет найдено по запросу сомики | меченосцы | гуппи?

Для скольких сайтов рассматриваемого сегмента ложно высказывание «Сомики — ключевое слово сайта ИЛИ меченосцы — ключевое слово сайта ИЛИ гуппи — ключевое слово сайта»?

Смит: «Я не делал этого. Браун сделал это».

Джон: «Браун не виновен. Смит сделал это».

Браун: «Я не делал этого. Джон не делал этого».

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

Объясните, почему следующие предложения не являются высказываниями.
1. Какого цвета этот дом?
2. Число X не превосходит единицы.
3. 4X + 3.
4. Посмотрите в окно.
5. Пейте томатный сок!
6. Эта тема скучна.
7. Рикки Мартин — самый популярный певец.
8. Вы были в театре?
Приведите по одному примеру истинных и ложных высказываний из биологии, географии, информатики, истории, математики, литературы.
В следующих высказываниях выделите простые высказывания, обозначив каждое из них буквой; запишите с помощью букв и знаков логических операций каждое составное высказывание.
1. Число 376 чётное и трёхзначное.
2. Зимой дети катаются на коньках или на лыжах.
3. Новый год мы встретим на даче или на Красной площади.
4. Неверно, что Солнце движется вокруг Земли.
5. Земля имеет форму шара, который из космоса кажется голубым.
6. На уроке математики старшеклассники отвечали на вопросы учителя, а также писали самостоятельную работу.
Постройте отрицания следующих высказываний.
1. Сегодня в театре идёт опера «Евгений Онегин».
2. Каждый охотник желает знать, где сидит фазан.
3. Число 1 есть простое число.
4. Натуральные числа, оканчивающиеся цифрой 0, не являются простыми числами.
5. Неверно, что число 3 не является делителем числа 198.
6. Коля решил все задания контрольной работы.
7. Во всякой школе некоторые ученики интересуются спортом.
8. Некоторые млекопитающие не живут на суше.
Пусть А = «Ане нравятся уроки математики», а В = «Ане нравятся уроки химии». Выразите следующие формулы на обычном языке:
Рассмотрите представленные на рисунке электрические схемы:
Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот её фрагмент:
Постройте таблицы истинности для следующих логических выражений:
Проведите доказательство рассмотренных в параграфе логических законов с помощью таблиц истинности.
Даны три числа в десятичной системе счисления: А = 23, B = 19, С = 26. Переведите А, B и С в двоичную систему счисления и выполните поразрядно логические операции (A ∨ B) & С. Ответ дайте в десятичной системе счисления.
Найдите значения выражений:
Найдите значение логического выражения для указанных значений числа X:
Пусть А = «Первая буква имени — гласная», В = «Четвёртая буква имени согласная». Найдите значение логического выражения для следующих имён:
Разбирается дело Джона, Брауна и Смита. Известно, что один из них нашёл и утаил клад. На следствии каждый из подозреваемых сделал два заявления:
Алёша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:
1. Алеша: «Это сосуд греческий и изготовлен в V веке».
2. Боря: «Это сосуд финикийский и изготовлен в III веке».
3. Гриша: «Это сосуд не греческий и изготовлен в IV веке».
  Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

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

Электронное приложение к уроку

Презентация «Элементы алгебры логики»

Презентация «Элементы алгебры логики» (Open Document Format)

Ссылки на ресурсы ЕК ЦОР

Федеральный центр информационных образовательных ресурсов:

Свободное программное обеспечение:

Элементы теории множеств


Презентации, плакаты, текстовые файлы	Вернуться к материалам урока	Ресурсы ЭОР