Линейные алгоритмы. Целочисленные типы данных. Системы счисления

Целочисленные типы данных. Системы счисления

План

1. Типы данных для представления целых величин и операции над ними.

2. Разбор программы выделения цифр целого числа.

3. Эксперименты с программой: перевод числа из десятичной системы счисления в двоичную, выяснение сути арифметических операций над данными целого типа, преобразование данных целого типа.

4. Выполнение самостоятельной работы.

5. Материал для чтения

6. Таблица перевода в двоичную, восьмеричную и шестнадцатеричную систему счисления

Представление целых величин

Имеются пять типов данных для представления целых чисел: ShortInt, Integer, Longlnt, Byte, Word. Они отличаются диапазоном значений, а значит, и размером памяти, отводимой для их представления.

Тип	Диапазон значений	Объем памяти
ShortInt	-128 ... 127	1 байт со знаковым битом
Integer	-32 768 ... 32 767	2 байта со знаковым битом
Longlnt	-2 147 483 648 ... 2 147 483 647	4 байта со знаковым битом
Byte	0... 255	1 байт без знакового бита
Word	0 ... 65 535	2 байта без знакового бита

Над величинами целого типа определены следующие операции: сложение (+), вычитание (—), умножение (* ), деление нацело (Div), получение остатка от деления (Mod). Так как на данных целого типа определено отношение порядка, то можно использовать стандартные функции Ord, Succ и Pred.

Примечание: Переменной целого типа присваивать значение результата обычной операции деления "/" нельзя. Убедитесь в этом с помощью модификации программы, которую вы написали на первом занятии. Попробуйте найти объяснение этому факту.

Разбор программы

Перед разбором программы рекомендуется рассмотреть примеры выполнения операций Div и Mod над различными (положительными и отрицательными) числами.

19	Div	4	= 4	19	Mod	4	= 3
-19	Div	4	= - 4	-19	Mod	4	= - 3
19	Div	-4	= - 4	19	Mod	-4	= 3
-19	Div	-4	= 4	-19	Mod	-4	= -3

В данной программе определяются цифры трехзначного числа. Можно ее использовать и для определения цифр двузначного числа, просто цифра сотен в этом случае равна нулю.

Program My7_1;

Var а, one, dec, hun, rez: Integer;

Begin

WriteLn ( ' Введите число ' ) ; ReadLn (a) ;

one :=a Mod 10;

WriteLn ( 'Цифра единиц числа — ' , one) ;

dec := (a Div 10) Mod 10;

WriteLn ( ' Цифра десятков числа — ', dec) ;

hun := a Div 100;

WriteLn ( 'Цифра сотен числа — ',hun );

rez := hun*100+dec*10+one;

WriteLn( ' ? это тоже число — ' ,rez) ;

Write ( ' Enter ' );

ReadLn

End.

Например, если вы введете число 137, то значение переменной one будет равно 7, dec — 3 и hun — 1. Вспомните деление чисел столбиком.

                                                                                                           137     10
                                                                                                                130      13      10
                                                                                                                    7      10   1
                                                                                                                              3

Примечание. Не забудьте сохранить программу под именем PRIM7_1. PAS.

Экспериментальный раздел работы

1. Измените программу Му7_1 для нахождения цифр двузначного числа. Сохраните ее под именем PRIM7_2.PAS.

2. Измените программу My7_1 для нахождения цифр четырехзначного числа. Сохраните ее под именем PRIM7_2.PAS.
3. Деление на 10 и нахождение остатков от деления мы рассмотрели выше. Рассмотрите пример деления столбиком на 2.

                      137 | 2
                                1 68 | 2
                                      0 34 | 2
                                             0 17 | 2
                                                    1 8 | 2
                                                           0 4 | 2
                                                                  0 2 | 2
                                                                         0    1
Наберите следующую программу, отладьте ее и попробуйте дать объяснение полученному результату. Измените программу так, чтобы она правильно работала, например, с числом 115.

Program My7_2;
Var rez : Integer;
Begin
    WriteLn ( ' 137 ' ) ;
    WriteLn ( ' 10001001 ' )
    Rez := l*128+0*64+0*32+0*l6+1*8+0*4+0*2+1*1;
    WriteLn (rez) ;
    ReadLn
End.

4. Наберите следующую программу:

Program My7_3;
Uses Crt;
Var a : Integer;
         b : Word;
         r1 : Integer;
         r2 : LongInt;
Begin
    ClrScr;{Очистка экрана, процедура модуля Crt}
    a := 32000; b := 64000;
    r1 := a+b; WriteLn (r1);
    r2 := a+b; WriteLn (r2);
    ReadLn
End.

После запуска вы увидите, что значение переменной r1 равно 30 464, а значение переменной г2 — 96 000. Если изменить тип переменной r1 на Word, то результат не изменится. Используя информацию из таблицы, приведенной в начале занятия, измените программу так, чтобы проделать аналогичные эксперименты с данными других целых типов. Попробуйте понять, как получаются эти результаты.

5. Добавьте в программу Му7_3 перед ReadLn следующие два оператора:

WriteLn (LongInt (100*a) );
WriteLn (100*LongInt (a) );

Функция LongInt преобразует переменную типа Integer в тип LongInt. В первом случае преобразование осуществляется после умножения, а во втором — перед умножением. В первом случае получается результат, далекий от истины, — отрицательное число — 11 264, во втором — правильный, 3 200 000.
Приведем основные правила, по которым в Паскале осуществляются операции над переменными целых типов.
Перед выполнением бинарных операций над двумя операндами оба операнда преобразуются к общему для них типу. Им является тип с наименьшим диапазоном, включающим все возможные значения обоих типов. Например, общим типом для Integer и Byte будет Integer, для Integer и Word — LongInt. Результат будет общего типа.
Выражение в правой части оператора присваивания вычисляется независимо от размера или типа переменной в левой части!
Перед выполнением любой арифметической операции любой операнд длиной в 1 байт преобразуется в промежуточный операнд длиной в 2 байта, который является совместимым как с Integer, так и с Word.

Задачи для самостоятельного решения

1. Чему равны значения переменных a и b после выполнения последовательности действий:
а := 15 Div (16 Mod 7) ;
b:= 34 Mod a * 5 - 29 Mod 5*2;
a:= 4 * 5 Div 3 Mod 2;
b:= 4 * 5 Div ( 3 Mod 2 ) ;

2. Дано двузначное число. Определить:
— сумму и произведение цифр числа;
— число, образованное перестановкой цифр исходного числа.

3. Дано трехзначное число. Определить:
— сумму и произведение цифр числа;
— число, образованное перестановкой цифр исходного числа;
— число, полученное перестановкой цифр десятков и единиц;
— число, полученное перестановкой цифр сотен и десятков;
— четырехзначное число, полученное приписыванием цифры единиц в качестве цифры тысяч (например, из числа 137 необходимо получить число 7137).
Примечание. Сколько различных чисел можно получить из трехзначного числа путем перестановки цифр?

4. Решить задачу 3 (кроме последнего пункта) для четырехзначных чисел.
Примечание. Предложить максимальное количество разумных модификаций рассматриваемой задачи.
5. Арифметическая прогрессия — это последовательность чисел, в которой разность между двумя соседними элементами постоянна. Последовательность 12, 15, 18, 21, 24,... является арифметической прогрессией, 12 — первый член прогрессии (a1), разность прогрессии равна 3. Любой член прогрессии вычисляется по формуле ап= а1 + d — (п — 1), где d — разность прогрессии, п — номер взятого члена. Даны а1 и d. Найти (экспериментальным путем) п, при котором значение ап выходит за диапазон типа Integer.
6. Сумма первых n членов арифметической прогрессии вычисляется по формуле Sn= (a1 + an) • n / 2. Даны а1 и d. Найти (экспериментальным путем) n, при котором значение Sn выходит за диапазон типа Integer.

Материал для чтения

1. Выражения состоят из операций и операндов. Различают бинарные операции — они выполняются над двумя операндами, и унарные (одноместные) — над одним операндом. Бинарные операций записываются в инфиксной форме (знак операции ставится между операндами), унарные — в префиксной (знак унарной операции предшествует операнду), Порядок выполнения операций в выражении определяется их приоритетами, которые приведены в следующей таблице.

Примечание. Мы включили в таблицу и те операции, которые будут рассмотрены позднее.

Операции	Приоритет	Тип операции
@, Not, +, -, ^	1-й (высший)	унарный
*, /, Div, Mod , And, Shl, Shr	2-й	мультипликативный
+, -, Or, Xor	3-й	аддитивный
=, <>, <, >, <=, >=, In	4-й (низший)	операции отношения

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

3377 = 3 • 1000 + 3 • 100 + 7 • 10 + 7 = 3 •103 + 3 • 102 + 7• 101 + 7 • 100

вклад как цифр 3, так и цифр 7 различен. Это же число в пятеричной системе счисления записывается как 102002

3377= 1• 55 + 0 • 54 + 2 • 53 + 0 • 52 + 0 • 52 + 2 • 50.

Подскажем, что 55= 3125, а 53 = 125. Это же число в двоичной системе счисления записывается как 110100110001

3377 = 1 • 211 + 1 • 210 + 0 • 29 + 1 • 28 + 0 • 27 + 0 • 26 + 1 • 25 + 1 • 24 + 0 • 23 + 0 • 22+ 0 • 21 + 1 • 20.

Приведем значения степеней двойки: 211 = 2048, 210= 1024, 29= 512, 28 = 256, - и т.д. Сформулируем алгоритм перевода целого числа из десятичной системы счисления в двоичную: делим исходное число на 2 нацело в десятичной системе счисления и считаем новым значением числа целую часть частного, остаток от деления, а это 0 или 1 , запоминаем; продолжаем процесс деления до тех пор, пока не будет получен 0. Результат получаем, выписывая остатки в порядке, обратном их нахождению.

Пример:

3377 : 2 = 1688 (1)
1688 : 2 = 844 (0)
844 : 2 = 422 (0)
422 : 2 = 211 (0)
211 : 2 = 105 (1)
105 : 2 = 52 (1)
52 : 2 = 26 (0)
26 : 2 = 13(0)
13 : 2 = 6 (1)
6 : 2 = 3 (0)
3 : 2 = 1 (1)
1 : 2 = 0 (1)

В скобках указано значение остатка от деления. Итак,
3377₁₀= 110100110001₂.

3. Компьютер работает только с данными, представленными в двоичной системе счисления. Не имеет значения, какие это данные: текст, звук, рисунок, целые числа, они должны быть переведены в двоичное представление. Для хранения одной двоичной цифры, а это 0 или 1 , используется один бит (разряд) памяти компьютера. Запомните, что 8 бит называют 1 байтом, 1024 байт — 1 килобайтом (1 Кб), 1024 Кб — 1 мегабайтом (1 Мб), 1024 Мб — 1 гигабайтом (1 Гб). В 2 битах можно хранить 4 различные последовательности из 0 и 1: 00, 01, 10, 11 (22). В 3 битах — 8: 000, 001, 010, 011, 100, 101, 11О, 111 (23). Если перевести эти 8 последовательностей из двоичной системы счисления в десятичную, то получим десятичные цифры от 0 до 7. Если у нас есть 4 бита, а это 16 различных двоичных последовательностей, то мы можем хранить числа из интервала от 0 до 15. Проверьте. А что делать, если необходимо хранить и отрицательные числа? У нас по-прежнему 4 бита памяти компьютера. Естественным шагом является выделение одного бита для хранения знака числа. Получаем, что, например, — 5 хранится как 1101, а 5 — 0101. И диапазон представления чисел в этом случае от — 7 до 7, т.е. 15 различных значений, а у нас есть возможность хранить в 4 битах 16 различных последовательностей. Последовательность 1000 не задействована, или, что еще более неприятно, она может трактоваться как — 0. Давайте научимся выполнять следующие действия: инверсию и прибавление 1 к двоичному числу. Рассмотрим пример.

Число	Двоичное представление	Инверсия	Прибавление 1	Отрицательное число
1	0001	1110	1111	-1
2	0010	1101	1110	-2
3	0011	1100	1101	-3
4	0100	1011	1100	-4
5	0101	1010	1011	-5
6	0110	1001	1010	-6
7	0111	1000	1001	-7
8	1000	0111	1000	-8
0	0000	1111	10000 (пятый, старший, разряд "отбрасываем")	0

В предпоследнем столбце мы получаем двоичное представление отрицательных чисел. Все 16 двоичных последовательностей задействованы, диапазон представления от — 8 до 7 и представление 0 однозначно. Представление отрицательных чисел в том виде, который приведен в таблице, называется дополнительным кодом. Естественно, что представление положительных чисел в дополнительном коде совпадает с их обычным представлением. Сравните полученный результат с диапазоном значений величин целого типа из таблицы, приведенной в начале занятия.

Таблица перевода в двоичную, восьмеричную и шестнадцатеричную систему счисления