ИНФОРМАТИКА

Формулы в Информатике

Оттолкнемся от одной из главных формул информатики – формулы Хартли N=2^i. При ее использовании учащиеся могут еще не знать понятия логарифма, достаточно вначале иметь перед глазами, а затем запомнить таблицу степеней числа 2 хотя бы по 10-й степени.

При этом формула может применяться в решении задач разного типа, если правильно определить систему обозначений.

Выделим в системе задач на количество информации задачи следующих типов:

A. Количество информации при вероятностном подходе;
B. Кодирование положений;
C. Количество информации при алфавитном подходе (кодирование текста);
D. Кодирование графической информации;
E. Кодирование звуковой информации

Все задачи группы A (в случае, если мы имеем дело с равновероятными событиями) решаются непосредственно по формуле Хартли с ее привычными обозначениями:

N – количество равновероятных событий;
i – количество бит в сообщении о том, что событие произошло,

Причем в задаче может быть определена любая из переменных с заданием найти вторую. В случае если число N не является непосредственно числом, представляющим ту или иную степень числа 2, количество бит нам необходимо определить «с запасом». Так для гарантированного угадывания числа в диапазоне от 1 до 100 необходимо задать минимально 7 вопросов (27=128).

Решение задач для случаев неравновероятных событий в этой статье не рассматривается.

Для решения задач групп B-E дополнительно введем еще одну формулу:

Q=k*i

и определим систему обозначений для задач разного типа.

Для задач группы B значение переменных в формуле Хартли таково:

i – количество «двоичных элементов», используемых для кодирования;
N – количество положений, которые можно закодировать посредством этих элементов;
k – количество знаков в сообщении;
Q – количество информации в сообщении (информационный «вес», «объем» сообщения), количество памяти, отведенное для хранения закодированной информации,

Так:

два флажка позволяют передать 4 различных сообщения;
с помощью трех лампочек можно потенциально закодировать 8 различных сигналов;
последовательность из 8 импульсов и пауз при передаче информации посредством электрического тока позволяет закодировать 256 различных текстовых знаков;

и т.п.

Как научиться решать логические задачи?

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

Перед Вами будет поставлены следующие задачи:

- - Познакомиться с основными способами решения логических задач;
  - На примерах конкретных задач выяснить: Какие методы более эффективные?
  - Подготовить презентацию к докладу на тему: Как я решаю логические задачи?
  - Подготовить подборку наиболее интересных задач для стенной газеты в раздел «Конкурс».

Основные приемы и методы решения логических задач

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

- - Метод рассуждений;
  - Метод таблиц;
  - Метод графов;
  - Метод блок-схем;
  - Метод бильярда;
  - Метод кругов Эйлера.

Как написать программу в Паскале?

Составить программу решения следующей задачи.
Саша спросил Сережу: "Сколько тебе лет?" Сережа ответил:
"Если бы число моих лет увеличить в 3 раза, а потом уменьшить на 17, то мне было бы 16 лет". Сколько лет Сереже?

Обычно решение такого типа задач начинается с "конца".
Число лет, которое было бы Сереже, т. е. 16, увеличиваем на 17, получаем
Полученный результат уменьшаем в 3 раза, т.е. делим на получаем 11.
Итак, Сереже было 11 лет.

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

Program Serg;
var a, b, c: integer;
begin
write("Ведите число лет, которое было бы Сереже ");

readln(a);
b := a + 17;
c := b div 3;
writeln("Сереже было ", c, " лет");
end.

Составим несколько правил для создание программ в Паскале:

-имя программы должно начинаться с буквы. В нем не должно быть пробелов, запятых, точек;

-точка с запятой является обязательным разделительным знаком в языке Паскаль;

-слово var - это сокращение от слова variable (переменная),указываются все переменные;

- слово begin (начать), которым начинается новый раздел программы - раздел операторов;

-программа заканчивается служебным словом end, после которого стоит точка.

КОНСТРУКЦИЯ ПРОГРАММЫ на языке
ПАСКАЛЬ

1.Program <имя>;

2.РАЗДЕЛ ОПИСАНИЙ
В нем описываются имена переменных и их типы.

3.Begin

4.РАЗДЕЛ ОПЕРАТОРОВ
Ввод данных, последовательность команд, вывод результатов.

5.end.

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

Как решать задачи с циклами?

1. Цикл с параметром в Паскале - FOR

Цикл FOR задаёт определённое условие по которому программа будет работать до его выполнения, допустим нужно нам 5 (или n) раз зациклить программу, то это легко сделать с помощью данного цикла. У цикла FOR есть характерная черта - счетчик который обычно обозначается буквой i или j.

Внешний вид цикла с параметром в паскале:
for i:= 1 to n do // присваиваем i сначала одному, потом двум, трем, ..., n

После 1-го прохода переменной i присваиваем 1, после второго присваиваем 2 и так до тех пор, пока не дойдем до n. to - это до .. в порядке возрастания, также есть downto - до .. в порядке убывания.

2. Цикл с предусловием в Паскале - WHILE

Оператор цикла с предусловием выполняет действия заранее неизвестное число раз. Выход из цикла осуществляется, если некоторое логическое выражение или его результат окажется ложным. Так как верность логического выражения проверяется в начале, тело цикла может не выполнится ни одного разу.

Структура цикла с предусловием:
- логическое выражение, истинность которого проверяется вначале выполнения циклического оператора;

- любые выполняемые операторы языка.

Порядок выполнения цикла:
Пока условие истинно выполняется тело цикла. Как только условие становится ложно выполнение цикла прекращается.

3. Цикл с постусловием - Repeat - until

Этот оператор аналогичен оператору цикла с предусловием, но отличается от него тем, что проверка условия производится после выполнения тела (действий) цикла. Это обеспечивает его выполнение хотя бы один раз в отличие от ранее разобранных циклов.
Обратите внимание на то, что данный оператор цикла предполагает наличие нескольких операторов в теле цикла, то есть можно выполнять несколько действий, поэтому служебные слова Begin и End не нужны.
Последовательность операторов, входящих в тело цикла выполняется один раз, после чего проверяется соблюдение условия, записанного следом за служебным словом Until. Если условие не соблюдается, цикл завершается. В противном случае - тело цикла повторяется ещё раз, после чего снова проверяется соблюдение условия.

Как решать задачи с ветвлением?

Ветвления в Паскаль позволяют выполнять действия не поочередно, как мы делали в предыдущих программах, а в зависимости от каких - либо условий. Для этого в языке программирования Pascal предусмотрены различные условные операторы. В данном уроке мы рассмотрим как задаются ветвления в Паскаль с помощью конструкции IF...THEN.

Формат записи оператора If имеет 2 формы: неполную (If..Then) и полную (If..Then..Else).

Формат полного оператора ветвления следующий:

if <логическое выражение> then <оператор1>
else <оператор2>

Здесь if - "если", then - "то", else - "иначе".

Как перевести число из двоичной системы в восьмеричную и шестнадцатеричную?

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

1. Разбить двоичное число справа налево на группы по 2 (для четвертичной СС), 3 (для восьмеричной СС) или 4 (для шестнадцатеричной СС) цифры. Если слева не будет хватать цифр для полной группы, нужно дописать необходимое количество незначащих нулей.

2. Заменить каждую группу цифр на ее аналог в соответствующей системе счисления.

ПРИМЕР 1:

Перевести число 111100110 из двоичной системы в четвертичную.

РЕШЕНИЕ: Разбиваем число на группы по 2 цифры справа налево и заменяем каждую группу на аналог в четвертичной системе счисления из таблицы: 111100110 (2СС) = 01 11 10 01 10 = 13212 (4СС)

ПРИМЕР 2:

Перевести число 111100110 из двоичной системы в восьмеричную.

РЕШЕНИЕ: Разбиваем число на группы по 3 цифры справа налево и заменяем каждую группу на аналог в восьмеричной системе счисления из таблицы: 111100110 (2СС) = 111 100 110 = 746 (8СС)

ПРИМЕР 3:

Перевести число 111100110 из двоичной системы в шестнадцатеричную.

РЕШЕНИЕ: Разбиваем число на группы по 4 цифры справа налево и заменяем каждую группу на аналог в шестнадцатеричной системе счисления из таблицы: 111100110 (2СС) = 0001 1110 0110 = 1E6 (16СС)

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

1. Заменить каждую цифру на двоичный аналог, состоящий из 2 (для четвертичной), 3 (для восьмеричной) или 4 (для шестнадцатеричной) цифр. Если нужно, число дополняется нулями слева.

2. Вычеркнуть из числа незначащие нули.

ПРИМЕР 4:

Перевести число 120323 из четвертичной системы в двоичную.

РЕШЕНИЕ: Выполняем замену каждой цифры на группу из 2 цифр в двоичной системе счисления: 120323 (4СС) = 01 10 00 11 10 11 = 11000111011 (2СС)

ПРИМЕР 5:

Перевести число 26475030 из восьмеричной системы в двоичную.

РЕШЕНИЕ: Выполняем замену каждой цифры на группу из 3 цифр в двоичной системе счисления: 26475030 (8СС) = 010 110 100 111 101 000 011 000 = 10110100111101000011000 (2СС)

ПРИМЕР 6: Перевести число 2AC0F74 из шестнадцатеричной системы в двоичную.

РЕШЕНИЕ: Выполняем замену каждой цифры на группу из 4 цифр в двоичной системе счисления: 2AC0F74 (16СС) = 0010 1010 1100 0000 1111 0111 0100 = 10101011000000111101110100 (2СС)