Паскаль реализация целочисленной арифметики

Целочисленная арифметика языка Паскаль (например, в версии Turbo Pascal 7.0) основана на использовании пяти стандартных целых типов: Byte, Word, ShortInt, Integer, LongInt.

Широко распространённой формой внутренней  (аппаратной)  реализации этих типов в Паскале, является дополнительный код.

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

Cо всеми  целыми типами  связан набор из пяти основных арифметических операций: +, -, *, div, mod.

Первые три, из перечисленных операций, имеют обычный смысл сложения, вычитания и умножения, соответственно, а последние две  определяются так: A div B - частное от деления нацело, A mod B - остаток от  деления нацело двух целых чисел A и B.

При этом, для неотрицательных А и В (В‡0), частное  A div B показывает, сколько раз делитель - число B, содержится в делимом - числе A; в то же время, остаток  A mod B показывает, сколько останется, если из делимого - числа А, вычесть все вхождения в него делителя - числа В.

Например.

15 div 6 = 2 (здесь 2 - частное. Оно показывает, сколько раз делитель - число 6, содержится в делимом - числе 15).

15 mod 6 = 3 (здесь  3 - остаток. Он показывает, сколько останется, если из числа 15, вычесть все вхождения в него числа 6).

В общем случае, когда  А и В - произвольные целые (которые могут быть и отрицательными),  при определении операций div и mod, как указано выше,  рассматриваются их модули, а знак результата учитывается отдельно.

В Паскале принято, что знак частного от целочисленного деления (А div В) определяется как и при обычном алгебраическом делении, а знак остатка (A mod B) - совпадает со знаком А.

В дальнейшем, для краткости, в данной статье, ограничимся рассмотрением только неотрицательных целых. 

Для целых, неотрицательных  A и B, операции div и mod (не путать их!) связаны простым соотношением: A mod B =A - (A div B)*B.

В качестве полезного для усвоения div и mod упражнения, проверьте это соотношение, например, на следующих парах чисел (А, В):    (13, 5), (40,2), (40,6), (6,40), (1,1).

Большая часть учебных задач целочисленной арифметики построена на свойствах делимости и решается именно с применением операций div и mod.

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

  • (А mod B=0) - условие делимости целого A на целое B;
  • (A mod 2 =0) - условие чётности целого A (впрочем, в Паскале, это же условие правильней задать выражением not odd(A), которое может вычисляться быстрее);
  • (A mod 10) - значение последней цифры в десятичной записи целого  А (например, 1234 mod 10 =4);
  • (A div 10) - число, десятичная запись которого получится отбрасыванием последней цифры в десятичной записи целого числа А (например, 1234 div 10 =123);
  • (A mod p) - значение последней цифры в p-ичной записи целого  А (например, при p=2, A mod 2 - последняя цифра записи А в двоичной системе счисления);
  • (A div p) - число, p-ичная запись которого получится отбрасыванием последней цифры в p-ичной записи целого числа А (например, 510=1012;  510 div 2 =210=102; т.е. из 1012 получили 102);
  • Выражения в последних двух пунктах (для произвольной p-ичной с.с.) обобщают, соответственно,  два выражения в предшествующих им двух пунктах (которые представляют частный случай, когда p=10);
  • Последовательно и многократно вычисляя A mod p  и  A div p,  т.е. начав с А и, далее, находя и отбрасывая справа каждый раз очередную p-ичную цифру Аp, можно найти полное представление целого А в p-ичной с.с.;
  •  Если a0, a1, ..., an - найденные p-ичные цифры (см.предыдущий пункт), то для вывода записи Ap, можно представить эту запись в виде десятичного числа C=an*10n + ...+a1*101+a0, которое затем и вывести обычным образом. Например, чтобы показать на дисплее 101составим  десятичное число B=1*100+0*10+1 и выведем его (такой приём не сработает, при p>10. Почему?).

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

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

Задача1. Дано трёхзначное в десятичной записи натуральное число. Составить Паскаль-программу, печатающую число, которое получается записью цифр исходного числа в обратном (реверсном) порядке.

  1. //Решение 1. Выделяем цифры и печатаем их в обратном порядке
  2. program Revers1;
  3.    var a, sotni,desiatki,edinici: Byte;
  4. begin
  5.    a:=154;  // пример исходного значения
  6.    edinici:=a mod 10; //4
  7.    desiatki:=(a div 10) mod 10;  //5
  8.    sotni:=a div 100; //1
  9.    Writeln('Исходное число: ', a); //154
  10.    Writeln('Полученное число: ', edinici,desiatki,sotni) //451
  11. end.
  1. //Решение 2. Выделяем цифры, составляем из них новое число и печатаем
  2. program Revers2;
  3.    var a, b, sotni,desiatki,edinici: Byte;
  4. begin
  5.    a:=154;
  6.    edinici:=a mod 10; //4
  7.    desiatki:=(a div 10) mod 10; //5
  8.    sotni:=a div 100;  //1
  9.    b:= edinici*100 + desiatki*10 + sotni; //451
  10.    Writeln('Исходное число: ', a); //154
  11.    Writeln('Полученное число: ', b) //451
  12. end.

В приведённых выше решениях, переменная a получает начальное значение в результате выполения оператора присваивания (a:=154 ), а не оператора ввода ( Readln(a) ), что было бы реалистичней. Это сделано только для того,чтобы Вам было удобней проследить за изменением значений переменных по мере выполнения соответствующих  программ.

Задача2. Дано однозначное в десятичной записи натуральное число. Составить Паскаль-программу, печатающую двоичное его представление.

Предварительное замечание. Т.к. наибольшее удовлетворяющее условию задачи исходное число 9 содержит в двоичном представлении 4 цифры (910=10012), результирующее число так же будем считать четырёхзначным.

С учётом этого замечания, можно записать следующую программу.

  1. //Выделяем дв. циф. и собираем в обратном порядке в 10-тичн. число
  2. program DesToDv;
  3.    var A, B,C: Word;
  4. begin
  5.    А:=5; // здесь мог бы быть оператор Readln(A)
  6.    Writeln('Исходное число в десятичном представлении: ', A); //5
  7.    С:=1;  // 1
  8.    B:=0;
  9.    B:= B + C*(A mod 2); // 1
  10.    A:= A div 2; // 2
  11.    C:= C*10;  // 10
  12.    B:= B + C*(A mod 2);  // 01
  13.    A:= A div 2; // 1
  14.    C:= C*10;  // 100
  15.    B:= B + C*(A mod 2); // 101
  16.    A:= A div 2;  // 0
  17.    C:= C*10;  // 1000
  18.    B:= B + C*(A mod 2);  // 0101
  19.    Writeln('Его двоичная запись: ', B) // 0101
  20. end.

 

Задача3. Дано четырёхзначное в двоичной записи натуральное число. Составить Паскаль-программу, печатающую  его десятичное представление.

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

Исходное число, хотя по смыслу и является двоичным, будет нами представляться в десятичной системе счисления, но при этом с использованием только цифр 0 и 1. Например, вместо (невозможного в Паскале) ввода числа восемь в виде 10002 будем вводить идентичное требуемому,  по форме записи, десятичное число 1000 (тысяча).

Заметьте, что проблема визуализации  двоичных выходных данных в предыдущей задаче здесь теперь стала проблемой визуализации двоичных входных данных. И решаются эти проблемы одинаково.

  1. //Выделяем "дв. цифры" и, умножая на степени двойки, складываем
  2. program DvToDes;
  3.    var A, B, stpn2: Word;
  4. begin
  5.    А:=1011; // здесь мог бы быть оператор Readln(A)
  6.    Writeln('Исходное число в двоичном представлении: ', A);
  7.    stpn2:=1;          // нулевая степень двойки
  8.    B:=0;              //начальная сумма
  9.    B:= B + (A mod 10)*stpn2;    // учли в сумме последн. разряд
  10.    A:= A div 10;                // отрезали, получив 101
  11.    stpn2:= stpn2*2;             // первая степень двойки
  12.    B:= B + (A mod 10)*stpn2;    // учли предпоследний разряд
  13.    A:= A div 10;                // отрезали, получив 10
  14.    stpn2:= stpn2*2;             // вторая степень двойки
  15.    B:= B + (A mod 10)*stpn2;    // учли разряд 0
  16.    A:= A div 10;                // отрезали, получив 1
  17.    stpn2:= stpn2*2;             // третья степень двойки
  18.    B:= B + (A mod 10)*stpn2;    //учли перв. разряд исходного числа
  19.    Writeln('Его десятичная запись: ', B)  // 11
  20. end.

4.833335
Your rating: Нет Average: 4.8 (18 votes)

Комментарии

Добрый вечер!

Валерий Шахамболетович,поясните пожалуйста,неравенство chr (65) < 'D' правильно записано?или наоборот,так нельзя?(из сегодняшней лекции)

При вводе числа 10000,

При вводе числа 10000, программа выводит 1, хотя число не палиндром. А при вводе 00001, работает верно, выводит ноль.

задача следующая на

задача следующая на БНФ
задача следующая на БНФ определить язык состоящий из чётного количества нулей и нечётного количества единиц, например: 00111, 10101, 0001110
<слово>::= 1 | {00}<слово>{00} | {11}<слово>{11} | 01<слово>01 | 10<слово>10 | 0<слово>0 | 1<слово>1

Стоп, дело в скобках.

Стоп, дело в скобках. Выражение: (10 + 1) div (0 + 1) и (0 + 1) div (10 + 1) необходимо взять в скобки. Вот так работает верно: Writeln( ( ( (L+1) div (R1+1)) )*( ( (R1+1) div (L+1)) ) );

Сурен

Ваше решение верно. Включайтесь в текущие задачи.

Андрей.

Так как всё же, работает или нет? Ведь скобки-то у меня все стоят ...

Валерий Шахамболетович, да,

Валерий Шахамболетович, да, действительно, у Вас все скобки на месте. Видимо я неудачно скопировал или что-то отредактировал у себя. Но, если записать так Writeln( ((L+1) div (R1+1))*((R1+1) div (L+1)) ); , т.е. убрать выделенные скобки, то программа выводит 1, в случае ввода числа 10000 и компилятор совершенно не ругается на непарность скобок, хотя непарности там нет, получается другая их расстановка. Ваша программа работает верно, неверный результат выдавал мой т.н. "аналог" Вашей программы.

OK, Андрей ...

OK, Андрей.
Ухожу ... Всем доброй ночи.

Спасибо большое,Валерий

Спасибо большое,Валерий Шахамболетович!Наконец-то разобралась

проба пера...

  1. program chislo;
  2.   var x, A : Integer;
  3.   begin
  4.   writeln ("Введите число A="); readln (A);
  5.    x:= A*A

хотя нет, получится А в

хотя нет, получится А в квадрате..не то....

Да, действительно, если

Да, действительно, если просто сделать Writeln(n, n), то получим два числа написанных слитно, которые визуально выглядят, как одно число. Предлагаю свой вариант решения данной задачи.

  1. var a, b : Integer;
  2. begin
  3.    Writeln('Vvedite chislo');
  4.    Readln(a);
  5.      b := (a div 10) * 1000;
  6.      b := b + ((a mod 10) * 100) + a;
  7.    Writeln(b);
  8.    Readln
  9. end.

Вопрос: Валерий Шахамболетович, с точки зрения опытного программиста, это нормальное решение задачи или плохо читаемая билибирда? Меня интересует именно написание кода программы.

Задача 2. var a, b, c, d :

Задача 2.

  1. var a, b, c, d : Byte;
  2. begin
  3.    Writeln('Vvedite chislo');
  4.    Readln(a);
  5.      b := (a and 1) + (a and 4) + (a and 16) + (a and 64) + (a and 256);// Получаем сумму чётных битов.
  6.      c := (a and 2) + (a and 8) + (a and 32) + (a and 128);// Получаем сумму нечётных битов.
  7.      d := c - b;// Их разность.
  8.    Writeln(d);
  9.    Readln
  10. end.

Валерий Шахамболетович,

Валерий Шахамболетович, спасибо за ответ, буду работать над собой. По поводу вопроса об отрицательной разности, в типе Byte нет отрицательных чисел. Я должен был это каким-то образом предусмотреть?

Андрей, Богдан

Да, Анндрей, достаточно было бы описать d как shortint.
Верно, Богдан, но задача уже решена чуть выше по тексту Викторией.

6. Дано значение типа Word не

6. Дано значение типа Word не превосходящее 15. Написать ТП-код, преобразующий это значение в соответствующую 16-ричную цифру (представленную как char). Например, 12 должно конвертироваться в 'C'.

  1.  var n: Word;
  2. begin
  3.       write('chislo=');
  4.       readln(n);
  5.       if (n>=0) and (n<16) then;
  6.       case n of
  7.       0: write('0');
  8.       1: write('1');
  9.       2: write ('2');
  10.       3: write('3');
  11.       4: write('4');
  12.       5: write('5');
  13.       6: write('6');
  14.       7: write('7');
  15.       8: write('8');
  16.       9: write ('9');
  17.       10: write('A');
  18.       11: write('B');
  19.       12: write('C');
  20.       13: write('D');
  21.       14: write('E');
  22.       15: write('F');
  23.       end;
  24.       readln
  25. end.

Никита, Зарина

Задача3. Никита, мне гораздо больше нравится тот вариант проверок, что указан в комментариях. Логически не корректно опираться в программе на не принципиальные, технические вещи, к которым относятся конкретные числа, кодирующие символы. Можно представить себе реализацию ТП, где способ кодирования иной. И там Ваша программа посыпется.

Задача6. Зарина. Хвалю, но сдержанно. Давайте поищем более изящное решение. Ну, для начала, например, такое, в котором нет 16 повторов оператора вывода. А знание case-оператора Вы продемонстрировали (правда неясно, почему Word, а не Byte).

Честно говоря,почему-то не

Честно говоря,почему-то не подумала...каюсь,логичнее использовать Byte,т.к. размер 1 байт..

Владислав,

Ещё менее изящное чем у Зарины и, более того, неверное решение. Шестнадцатеричными цифрами являются ASCII-символы: '0','1', ... 'F', а не стринги типа '0000'.

Зарина, Вика

Не вымогайте у меня информацию о значениях A и B. И никаких ЕСЛИ, Зарина. Приведённое мной выражение имеет вполне определённое значение!

Так 5-ая задача у меня

Так 5-ая задача у меня неправильная?

Повторюсь, Зарина: выражение

Повторюсь, Зарина: выражение имеет вполне определённое (и естественно, одно) значение!
Разве Вы не видите, что у Вас таких значений два?

5. Пусть A и B булевы

5. Пусть A и B булевы переменные. Вычислить значение булевского выражения (((not A) and (not B) ) = not (A or B)) xor true. Мой ответ TRUE.

Задача№6, а что если вот так ?

  1. var c:Char;
  2.     a:word;
  3. begin
  4.     readln(a);
  5.     if(a>=0)and (a<=15)then
  6.         begin
  7.           if a<10 then
  8.           c:=chr(ord('0')+a)
  9.         else c:= chr(ord('A')+a-10);
  10.         write(c);
  11.          readln
  12.         end
  13.          else write('osshibka');
  14.          readln
  15. end.

все

всем спокойной ночи!

Задача 5.) Пусть A и B булевы

Задача 5.) Пусть A и B булевы переменные. Вычислить значение булевского выражения (((not A) and (not B) ) = not (A or B)) xor true. Решение: А = TRUE, В = FALSE. Выражение (((not TRUE) and (not FALSE) ) = not (TRUE or FALSE)) xor TRUE вернёт FALSE, слева от знака равенства получаем FALSE, справа TRUE. FALSE, как известно, не равно TRUE.

Как я поняла ты имеешь в

Как я поняла ты имеешь в виду, что false xor true=false????

false xor true=true по-идее)

false xor true=true по-идее)

Вот я о том же))

Вот я о том же))

так у Андрея вроде все верно)

так у Андрея вроде все верно) только что перепроверила...

Валерий Шахамболетович

Валерий Шахамболетович рассудит

Зарина

not(TRUE or FALSE) = FALSE -> FALSE xor TRUE = TRUE. FALSE = TRUE -> FALSE. Словами очень длинно расписывать. Если так не понятно, могу всё же попробовать, если нужно))

Я поняла,что ты имел ввиду

Я поняла,что ты имел ввиду

Зарина

Всё ещё уверена в том, что ответ TRUE или всё-таки согласна с тем, что ответ FALSE?)

Андрей

при А=true,В=false,как ты рассматриваешь,получается так (((not true) and (not false) ) = not (true or false)). Все ЭТО выражение =false,следовательно FALSE xor true,т.е. ВСЕ ВЫРАЖЕНИЕ В УСЛОВИИ,=troue.
Или это не так?

Зарина

Я вижу, что ты не поняла. Попробую объяснить. В задаче под символами А и В предполагалось, что А — это одно значение, а В — ему противоположное. Для удобства обозначим их через TRUE и FALSE, и подставим их вместо А и В. Далее, берём выражение стоящее слева от знака равенства и вычисляем его значение: ((not TRUE) and (not FALSE)), вычислив его получим FALSE и запомним, что слева от знака равно у нас стоит значение FALSE. Теперь берём выражение стоящее справа от знака равенства и вычисляем его значение: not (TRUE or FALSE) xor TRUE — в скобочках получаем TRUE, теперь делаем отрицание этого значения и получаем FALSE, далее FALSE xor TRUE возвращает нам TRUE, всё, справа получили значение равное TRUE. А теперь вопрос на засыпку, какое значение вернёт операция: FALSE = TRUE?

Зарин, действия выполненны не

Зарин, действия выполненны у тебя не в том порядке походу) нужно рассматривать левую и правую часть равенства, а не вычислять значение выражения (((not true) and (not false) ) = not (true or false)) и рассматривать его относительно последнего True))

Сегодня зайду поздно.

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

Пока!

пробую найти ошибку...это

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

Валерий Шахамболетович

Верный ответ FALSE, почему же она мне не поддалась?))

Задача 5. Разобрался. Даны

Задача 5. Разобрался. Даны две булевские переменные А и В, и им не присвоено ни одно из двух возможных значений, а раз не присвоено, то они хранят значение FALSE по умолчанию. Тогда имеем: (((not FALSE) and (not FALSE) ) = not (FALSE or FALSE)) xor TRUE. Значением выражения стоящего слева будет TRUE, справа: в скобочках получаем FALSE, далее отрицание этого значения, что даёт TRUE и TRUE xor TRUE, даёт нам FALSE и тогда операция TRUE = FALSE вернёт нам FALSE. Хочу попросить прощения у Зарины за то, что ввёл в заблуждение своими неверными рассуждениями по поводу этой задачи.

я и этот случай

я и этот случай рассматривала,когда А= false и В=false , так же А=true и В= false...Андрей и этот и тот решение дает

Зарина

Я думаю тут важен не сам ответ, а его обоснование, т.е. почему FALSE, как это получается. Да, FALSE получается и в том, и в дугом случае, но предположение, что А = TRUE, а В = FALSE, не верно, поэтому и решение не было принято. Хотя это лично моё мнение, на вопрос почему первое решение не верно нам ответит Валерий Шахамболетович.

в первом случае получается

в первом случае получается false,а во втором true.Проверь еще раз

Андрей,объясни пожалуйста

Андрей,объясни пожалуйста, почему по умолчанию берется FALSE ..а не TRUE?))

Ok, пошагово. Из условия

Ok, пошагово. Из условия задачи нам известно, что булевским переменным не присвоено никакого значения, значит они обе хранят значение FALSE.
(((not FALSE) and (not FALSE)) — это выражение слева от знака равно, оно возвращает TRUE.
not (FALSE or FALSE)) xor TRUE — это выражение стоящее справа от знака равно, оно возвращает FALSE.
TRUE = FALSE -> FALSE.

Ксения

Проверял в компиляторе, булевская переменная, которой не присвоено никакого значения, хранит FALSE. Почему? Наверно так принято, значение по дефолту, если угодно. Например, переменная типа Integer хранит 0, если ей не присвоили никакого значения.

логично)) спасибо)

логично)) спасибо)

Да не за что))

Да не за что))

о я не знала,что если ниче не

о я не знала,что если ниче не присвоенно,то false)