Дискретная математика, теория и практика решения задач по информатике, Окулов С.М., 2015

Дискретная математика, Теория и практика решения задач по информатике, Окулов С.М., 2015.

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




Счет и перебор.
Приведем несколько примеров, в которых требуется подсчитать количество объектов определенной природы.
Пример 1.1. Подсчитать количество последовательностей из натуральных чисел от 1 до я, в которые каждое из этих чисел входит по одному разу.
На первое место в последовательности можно записать любое из я чисел; на второе любое из оставшихся я-1 чисел и т. д. Общее количество последовательностей равно произведению 1 • 2 • 3 •... • (n - 1) • n. Это произведение обозначают n! (читается как n факториал).
При n = 7 значение n! = 5040, а при n = 8 — уже 40 320. Для вычисления и хранения чисел такого порядка в компьютере использовать величину типа Integer нельзя. Аналогично и с величинами типа LongInt, так как последнее значение я, для которого можно сохранить значение факториала, равно 12 (13! = 6 227 020 800). Вычисление для больших значений я рассмотрено в книге (20).

Пример 1.2. Подсчитать количество единиц в двоичном представлении целого положительного числа.
Рассмотрим величины типа Word. Длина двоичного представления чисел равна 16 битам (n= 16). Например, в двоичной последовательности 0101101001001001 содержится 7 единиц.
Первый вариант решения
Const n=16;
Var a, cnt, i:Word;
Begin
ReadLn (a); cnt:=0;
For i:=l To n Do
If a And (1 ShL (i-l))=l Then cnt:=cnt+l;
{a ShL b — сдвиг величины а влево на Ь разрядов}
WriteLn(cnt);
End.

Купить .





Теги: учебник по информатике :: информатика :: компьютеры :: Окулов