Практическое занятие №2 «Системы счисления»
Теоретическое введение
Когда мы записываем некоторое число, скажем 123, в привычной нам десятичной системе счисления, то понимать эту запись следует так:
123 1 102 |
2 101 3 100 |
100 20 3. |
(1) |
10 |
|
|
|
Обратите внимание на множители вида 102, 101, 100 в этом выражении. Если бы вместо десятичной мы пользовались, скажем, пятеричной системой счисления, то вместо «10» в аналогичной формуле везде фигурировало бы «5». Т.е. число 1235 следует понимать так:
123 1 52 |
2 51 3 50 |
1 25 2 5 3 |
(2) |
5 |
|
|
|
(в этой формуле все, что стоит справа от первого знака «=», записано в десятичной системе).
Основные свойства систем счисления
1.Система счисления по основанию N использует ровно N цифр: от 0 до N-1 (включительно). Например, в десятичной системе используются цифры от 0 до 9, в восьмеричной — от 0 до 7, в двоичной — от 0 до 1. В 16-ричной — от 0 до F, где
A=10, B=11..F=15.
2.n-ый разряд в записи числа в системе по основанию k соответствует n-ой степени k (разряды нумеруются справа налево, начиная с 0-го):
12310 |
1235 |
единицы (x1) |
единицы (x1) |
десятки (x10) |
пятерки (x5) |
сотни (x100) |
25-ки (x25) |
3.В любой системе счисления число, равное основанию системы, выглядит как «10».
Например, 1016=1610, 108=810, 105=510, 102=210.
4.Дописывание справа нуля эквивалентно умножению числа на основание системы счисления, в которой оно записано, вычеркивание младшего разряда — делению на него же. Например, 125=1·5+2=710. Дописываем 0: 1205=1·25+2·5+0=3510 (получилось в 5 раз больше).
5. С помощью n разрядов k-чной системы счисления можно записать k k k kn
n
различных чисел. Как правило, это числа от 0 до kn-1.
Определение числа по его записи в позиционной системе счисления
Задана запись некоторого числа в системе счисления по основанию k. Определить, что это за число.
Задание 1.1. Используя вычисления, аналогичные (1) и (2), определите числа, закодированные следующими записями:
1001102
37348
22315
7AB816
Задание 1.2. Задано число N, равное дате вашего рождения ДДММГГГГ (например, 01012002). Определите числа, закодированные как это число N в системах счисления по основанию 2, 8,16.
1
Задание 2. Составить алгоритм и программу решения задачи перевода числа в 10тичную систему для частного случая, когда исходная запись числа в системе счисления с произвольным основанием содержит ровно три разряда (тестовое задание – формула 2).
Диаграмма потоков данных |
|
||
|
a0 |
|
|
цифры |
a1 |
определение |
N — искомое число |
|
a2 |
|
|
основание |
k |
числа |
|
|
|
||
Рис. 1. Диаграмма потоков данных определения числа по его записи в позиционной системе счисления с произвольным основанием.
Блок-схема
Н
Ввод
a0, a1, a2, k
N a2 k2 a1 k a0
Вывод N
К
Рис. 2. Блок-схема алгоритма определения числа по его записи в позиционной системе счисления с произвольным основанием.
Программа
Элемент блок-схемы |
Соответствующий код на C |
Н
Ввод
a0, a1, a2, k
N a2 k2 a1 k a0
Вывод N
return 0;
К
2
Лабораторная работа №1 «Системы счисления»
(задания для самостоятельного решения)
Задание 3. Выполните свой вариант индивидуального задания №1 (см. приложение). Аналогично рассмотренной выше программе, сначала нарисуйте диаграмму потоков данных, затем блок-схему, и по последней составьте саму программу.
Запись заданного числа в позиционной системе счисления
Решим задачу, обратную заданию 2: некоторое заданное число записать в системе счисления по произвольному основанию k. На этот раз — для произвольной разрядности.
Диаграмма потоков данных
N — исходное число |
a0 |
запись числа |
a1 |
цифрами |
... |
k — основание |
|
|
an |
Рис. 3. Диаграмма потоков данных записи числа в позиционной системе счисления с произвольным основанием.
|
|
|
Н |
|||
а) |
|
|
Ввод: N, k |
|||
|
|
|
||||
|
|
|
|
|
|
|
б) |
Найти макс. n, при |
|||||
котором kn N |
||||||
|
||||||
в) |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
d N/kn |
|
|
||
|
|
|
|
|
|
|
|
|
|
Вывод d |
|||
|
|
|
|
|
||
г) |
|
|
N N d kn |
|
||
|
|
|
n n 1 |
|
||
|
|
|
|
|||
д) |
да |
|||||
|
|
|
n≥0? |
|||
|
|
|
нет |
|||
|
|
|
К |
|||
Рис. 4. Блок-схема алгоритма записи числа в позиционной системе счисления с произвольным основанием.
Внимание! Эта блок-схема не предназначена для составления по ней программы! Она предназначена для интерпретации ее человеком.
3
Ручное выполнение алгоритма, заданного блок-схемой
Проследим на каком-нибудь примере входных данных порядок выполнения блоков данной схемы, а также результаты выполнения каждого из них. Возьмем N=87, k=5 и выполним алгоритм. В процессе выполнения будем заполнять следующую таблицу:
№ |
Блок |
Результат |
Комментарий |
|
шага |
|
|
|
|
1 |
а) |
N=87, k=5 |
ввод исходных данных |
|
2 |
б) |
n=2 |
53=125, 52=25. Т.к. 125>87, а 25<87, выбираем n=2. |
|
3 |
в) |
3 |
87 |
/ 25 = 3 (деление нацело!) |
4 |
г) |
N=12 |
87 |
– 3*25 = 12 |
|
|
n=1 |
n уменьшилось на 1 |
|
5 |
д) |
TRUE |
n=1, поэтому n>=0. Условный переход к блоку в). |
|
6 |
в) |
2 |
12 |
/ 5 = 2 |
7 |
г) |
N=2 |
12 |
– 2*5 = 2 |
|
|
n=0 |
n уменьшилось на 1 и стало равно нулю |
|
8 |
д) |
TRUE |
n=0, а это все еще неотрицательное число; поэтому n>=0 |
|
|
|
|
Переход к в). |
|
9 |
в) |
2 |
2 / 1 = 2 |
|
10 |
г) |
N=0 |
2 – 2*1 = 0 |
|
|
|
n=-1 |
n уменьшилось на 1! |
|
11 |
д) |
FALSE |
n=-1. Условие n>=0 не выполняется. |
|
12 |
К |
-- |
Переход на «К» — конец выполнения. |
|
В результате получаем на выходе 3 цифры: 322 (см. строки, в которых выполняется блок в), отвечающий за вычисление очередной цифры).
Задание 4. Проделайте аналогичные действия (выполните вручную алгоритм и заполните по нему таблицу) для значений N и k, заданных в Вашем индивидуальном задании №2.
Задание 5. Будет ли работать алгоритм на рис. 4, если на его вход подать N=0 (при "хорошем" k: например, k=5)? Модифицируйте блок-схему на рис. 4 так, чтобы сразу после ввода N и k производилась проверка "N=0?", и в случае выполнения этого условия на экран сразу выводился ответ: 0. В противном случае алгоритм должен все делать как раньше. Подробнее о блок-схемах см. 2-ую главу книги Дейтела, пп. 2.1-2.7.
Задание 6. Выполните свой вариант индивидуального задания №3 (см. приложение). Перед тем, как писать код программы, постройте диаграмму потоков данных и блок-схему. По поводу подробностей синтаксиса оператора if обращайтесь к пункту 2.5 книги Дейтела, а также к встроенной справке среды программирования (кнопка F1).
Ниже приведен пример выполнения аналогичного задания нахождения максимального из двух целых чисел.
Диаграмма потоков данных
a |
max |
— |
значение |
нахождение |
наибольшего числа |
||
максимального |
|
|
|
из двух чисел |
max_n — его номер: 1 или 2 |
||
b |
|
|
|
Рис. 5. Диаграмма потоков данных нахождения максимального из двух чисел.
4
Блок-схема
|
Н |
|
|
Вывод: |
|
|
приглашения |
|
|
ввести 2 числа |
|
|
Ввод: |
|
|
a, b |
|
|
нет |
да |
|
a=b? |
|
нет |
да |
Вывод: |
|
a>b? |
|
|
числа равны |
|
|
|
|
Вывод: |
Вывод: |
|
2-е число больше. |
1-е число больше |
|
Вывод b. |
Вывод a. |
|
К
Рис. 6. Блок-схема алгоритма нахождения максимального из двух чисел.
5
Контрольные вопросы
1.Почему позиционная система счисления так называется? Какие вы знаете непозиционные системы?
2.Какие виды блоков применяются при построении блок-схем? Приведите примеры использования самых важных из них.
3.Как оператор взятия остатка от деления ("%") может быть полезен в задаче записи числа в позиционной системе счисления по заданному основанию?
4.Сколько различных чисел можно записать с помощью 32-ух разрядов двоичной системы?
Оценивание
Содержание отчета
1.Условия заданий.
2.Диаграмма потоков данных, блок-схема, исходный код и пример выполнения для заданий 3 и 6.
3.Заполненная таблица задания 4.
4.Блок-схема задания 5.
5.Исходный код и скриншот выполнения программ.
Примечание: блок-схемы и диаграммы потоков данных можно рисовать от руки, фотографировать и вставлять фото в файл отчета. Не надо «мучать Ворд» непроизводительной тратой времени.
Баллы за задания
Задание на практическое занятие |
Баллы |
1.1 |
0.5 |
1.2 |
0.5 |
2 |
1 |
Всего за практическое занятие |
2 |
|
|
Задание на лабораторную работу |
Баллы |
3 |
1 |
4 |
1 |
5 |
1 |
6 |
1 |
Всего |
4 |
Бонусы
Досрочная сдача: +0.5 балла.
Несвоевременная сдача: макс. балл уменьшается на 50%.
6
Приложение 1: индивидуальные задания
Индивидуальное задание №1
1.Дано расстояние L в сантиметрах. Используя операцию деления нацело, найти количество полных метров.
2.Дана масса M в килограммах. Используя операцию деления нацело, найти количество полных тонн.
3.Дан размер файла в байтах. Используя операцию деления нацело, найти количество полных килобайтов, которые занимает данный файл (1 килобайт = 1024 байта).
4.С начала суток прошло N секунд (N — целое). Найти количество полных минут, прошедших с начала суток.
5.С начала суток прошло N секунд (N — целое). Найти количество целых часов, прошедших с начала суток.
6.С начала суток прошло N секунд (N — целое). Найти количество секунд, прошедших с начала последней минуты.
7.С начала суток прошло N секунд (N — целое). Найти количество секунд, прошедших с начала последнего часа.
8.С начала суток прошло N секунд (N — целое). Найти количество полных минут, прошедших с начала последнего часа.
9.Дано двузначное число. Найти сумму и произведение его цифр.
10.Дано двузначное число. Вычислить и вывести число, полученное при перестановке цифр исходного числа.
11.Дано трехзначное число. Вывести на одной строке последнюю цифру (разряд единиц), а на другой — среднюю цифру (десятки).
12.Дано трехзначное число. Найти сумму и произведение цифр заданного числа.
13.Дано трехзначное число. Вывести число, полученное при прочтении исходного числа справа налево.
14.Дано трехзначное число. В числе зачеркнули первую цифру слева и приписали ее справа. Вывести полученное число.
15.Дано трехзначное число. В числе зачеркнули первую цифру справа и приписали ее слева. Вывести полученное число.
16.Дано трехзначное число. Вывести число, полученное при обмене местами разрядов сотен и десятков исходного числа (например, 123 перейдет в 213).
17.Дано трехзначное число. Вывести число, полученное при обмене местами разрядов десятков и единиц исходного числа (например, 123 перейдет в 132).
18.Дни недели пронумерованы следующим образом: 0—воскресенье, 1 — понедельник, 2 — вторник, …, 6 — суббота. Дано целое число K, лежащее в диапазоне 1–365. Определить номер дня недели для K-го дня года, если известно, что в этом году 1 января было понедельником.
19.Дни недели пронумерованы следующим образом: 0—воскресенье, 1 — понедельник, 2 — вторник, …, 6 — суббота. Дано целое число K, лежащее в диапазоне 1–365. Определить номер дня недели для K-го дня года, если известно, что в этом году 1 января было четвергом.
20.Дни недели пронумерованы следующим образом: 1 — понедельник, 2—вторник, …, 6— суббота, 7—воскресенье. Дано целое число K, лежащее в диапазоне 1–365. Определить номер дня недели для K-го дня года, если известно, что в этом году 1 января было вторником.
21.Дни недели пронумерованы следующим образом: 1 — понедельник, 2—вторник, …, 6— суббота, 7—воскресенье. Дано целое число K, лежащее в диапазоне 1–365. Определить номер дня недели для K-го дня года, если известно, что в этом году 1 января было субботой.
7
Индивидуальное задание №2
№ |
Инд.з.№2 |
1 |
N=232k=8 |
2 |
N=417k=8 |
3 |
N=419k=8 |
4 |
N=475k=8 |
5 |
N=229k=8 |
6 |
N=285k=5 |
7 |
N=485k=5 |
8 |
N=43k=3 |
9 |
N=127k=8 |
10 |
N=77k=3 |
11 |
N=78k=3 |
12 |
N=332k=8 |
13 |
N=38k=3 |
14 |
N=153k=8 |
15 |
N=404k=5 |
16 |
N=353k=5 |
17 |
N=331k=8 |
18 |
N=379k=5 |
19 |
N=30k=3 |
20 |
N=260k=8 |
21 |
N=118k=8 |
22 |
N=434k=8 |
23 |
N=337k=5 |
24 |
N=347k=8 |
25 |
N=342k=5 |
26 |
N=369k=5 |
Индивидуальное задание №3
1.Даны три целых числа. Найти количество положительных чисел в исходном наборе.
2.Даны три целых числа. Найти количество положительных и количество отрицательных чисел в исходном наборе.
3.Даны три целых числа. Вывести наибольшее из них.
4.Даны три различных целых числа. Вывести порядковый номер наименьшего из них.
5.Даны три целых числа. Найти сумму двух наибольших из них.
6.Дан номер некоторого года (целое положительное число). Определить соответствующий ему номер столетия, учитывая, что, к примеру, началом 20 столетия был 1901 год.
7.Дано трехзначное число. Проверить его цифры на симметрию (т.е. проверить, совпадает ли количество единиц с количеством сотен).
8.Дано двузначное число. Проверить, как соотносятся между собой сумма и произведение его цифр (больше, меньше или равно).
9.Дано трехзначное число. Проверить, образуют ли его цифры строго возрастающую последовательность.
10.Даны три различных целых числа. Вывести то из них, которое не является ни наибольшим, ни наименьшим среди них (т.е. является "средним").
8
Приложение 2: Формы изображение алгоритмов
словесная (записи на естественном языке);
графическая (изображения из графических символов) – блок-схема;
псевдокоды (полуформализованные описания на условном алгоритмическом языке);
программная (тексты на языках программирования).
Условные обозначения графической записи алгоритма
Начало алгоритма |
Ввод(вывод) данных |
Операция |
Разветвление |
Цикл |
Ссылка |
Соединитель |
Комментарий |
Конец алгоритма |
9