Задача проектирования «неограниченного» калькулятора, манипулирующего рациональными числами

1 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Эта лекция, как и предыдущие, иллюстрирует процесс проектирования программы. На этот раз рассмотрим задачу проектирования «неограниченного» калькулятора, манипулирующего рациональными числами. Что значит: «неограниченный калькулятор»? Это калькулятор, манипулирующий ЛЮБЫМИ КОНЕЧНЫМИ числами. Ваши знакомыекалькуляторы все ограничены размерами разрядных сеток устройств, на которых они функционируют. Мы намерены создать калькулятор, не зависящий от размера разрядной сетки платформы. А это как?! Вот и давайте подумаем. То, чем мы займёмся сейчас, называется ПОСТАНОВКА ЗАДАЧИ НА ПРОЕКТИРОВАНИЕ. Цель этого предварительного этапа работы: уяснение требований (заказчика) к конечному результату нашей (исполнителя) работы. В реальной жизни программиста очень часто «заказчик» и «исполнитель» СОВМЕЩАЮТСЯ в нём самом. Первый вопрос: что такое КАЛЬКУЛЯТОР? Ответ: это программа, которая преобразует поступающее на её вход арифметическое выражение в число, и выдаёт его на выход. Ничего больше она не делает. Все известные нам калькуляторы манипулируют десятичными дробями. Наш должен манипулировать рациональными числами. Второй вопрос: что это ещё за рациональное число? Ответ (нетрудно найти в Интернете, если не помним школьную математику): это число, которое можно представить обыкновенной дробью: r = m/n, где m – любое целое, а n – натуральное Т.е. с точки зрения программиста (как и математика) рациональное число есть пара чисел {m, n} какого-либо целого типа данных, причём n принадлежит беззнаковому типу, а m – знаковому. Заметим, что для программиста, в отличие от математика, множество значений любого числового типа данных КОНЕЧНО. И как тогда быть с «неограниченностью» нашего калькулятора? 2 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Ответ на этот вопрос поищем позже, а пока разберёмся с операциями арифметики рациональных чисел. Если не помним школьную арифметику, заглянем, например, в Википедию. Операции над рациональными числами. В школе мы складывали/вычитали/умножали/делили обыкновенные дроби. Нетрудно видеть, что на самом деле достаточно определить всего ДВА алгоритма арифметических операций на множестве рациональных чисел: сложение и умножение. Пусть A = {m1, n1} и B ={m2, n2} – два рациональных числа. Вот полный набор арифметических операций над такими числами. Сумма: Разность: Умножение: Деление: A + B = {m1*n2 + m2*n1, n1*n2}. A – B = {m1*n2 – m2*n1, n1*n2} = A + (–B). A*B = {m1*m2, n1*n2}. A/B = {m1*n2, n1*m2} = A*B-1, где B-1 = {n2, m2} (1) (2) Нетрудно видеть, что обе аддитивные операции реализуются алгоритмом сложения, а обе мультипликативные – алгоритмом умножения. Для выполнения вычитания достаточно изменить знак числителя вычитаемого и запустить алгоритм сложения, а для выполнения деления нужно поменять местами числитель и знаменатель делителя и запустить алгоритм умножения. Таким образом, наш калькулятор должен включать две функции, реализующие операции сложения и умножения рациональных чисел. Каждая из них при вызове получает от вызывающей программы два рациональных числа – операнды операции, – и возвращает одно рациональное число – результат операции. О «неограниченности» калькулятора. Вопрос о «неограниченности» калькулятора сводится к вопросу о типе параметров функций и возвращаемых значений. Если параметры функций и возвращаемые значения принадлежат какому-либо числовому типу данных, то множество значений, которыми может манипулировать калькулятор, ограничено максимальным возможным значением этого типа. Снять это ограничение можно единственным способом. Именно, используя для представления чисел СИМВОЛЬНУЮ ЗАПИСЬ. Т.е., калькулятор должен манипулировать не значениями какого-то числового типа данных, а строками цифр, как делаем это мы, выполняя вычисления на бумаге. Тогда его вычислительные возможности будут ограничены только ресурсом оперативной памяти. Есть ещё один аспект «неограниченности» нашего калькулятора. Это степень сложности обрабатываемых выражений. Реальные арифметические выражения могут содержать скобки. Причём, уровни вложенности скобок, вообще говоря, не ограничиваются. 3 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Вопрос: Должен ли наш калькулятор обрабатывать выражения со скобками? Ответ: Думаю, что для учебного проекта это сложновато. Здесь мы ограничимся обработкой бесскобочных выражений. Во всяком случае, в этой лекции. Ещё один аргумент в пользу этого решения. Для того чтобы написать полнофункциональный калькулятор, обрабатывающий сложные выражения, необходимо иметь надёжные функции, выполняющие элементарные операции сложения и умножения рациональных чисел. Вот на этом упрощённом варианте мы эти функции и отработаем. Итак, задача, которую мы ставим перед собой сейчас – это частный случай «Неограниченного калькулятора». Сейчас наша цель – понять, как реализовать операции сложения и умножения рациональных чисел. Внешний интерфейс «упрощённого» калькулятора. После загрузки программа сообщает о готовности к работе и ждёт начала ввода выражения. В процессе ввода воспринимаются только сигналы цифровых и знаковых клавиш и клавиши завершения ввода. Сигналы прочих клавиш игнорируются. После ввода логически завершённого подвыражения отображается его значение. Ввод выражения завершается по нажатию клавиши Enter. На экране отображается значение введённого выражения. Теперь нужно дать Формальное определение понятия «выражение». <выражение> ::= <рац число><оператор><рац число> | <выражение><оператор><рац число> <рац число> ::= <числитель>[“/”<знаменатель>] <числитель> ::= <число> | “–“<число> <знаменатель> ::= <п_число> <п_число> ::= “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9” | <п_число><цифра> <число> ::= <цифра> | <число><цифра> <цифра> ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9” <оператор> ::= “+” | “–” | “*” | “:” Это определение задаёт правила проверки введённой строки. Она является выражением, если удовлетворяет описанным выше правилам. В процессе ввода выражения про- 4 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» грамма должна принимать только сигналы клавиш символов, заключённых в кавычки. Нажатия прочих клавиш игнорируются. Об организации процесса вычисления. Поскольку мы договорились обрабатывать только бесскобочные выражения, процесс вычисления выглядит так, как нас учили в третьем классе. Т.е., если все операции одного ранга, они выполняются в порядке следования. При этом результат предыдущей операции является левым операндом текущей. Если же выражение содержит как аддитивные, так и мультипликативные операции, то сначала вычисляется значение мультипликативного подвыражения, а потом выполняется предшествовавшая ему аддитивная операция. Строгое описание алгоритма вычисления значения бесскобочного арифметического выражения выполните самостоятельно. Вы его «знаете руками». О реализации операций над рациональными числами. Операции определены выше формулами (1) и (2). Если мы располагаем функциями, выполняющими сложение и умножение целых чисел, представленных строками цифр, то реализовать эти операции над рациональными числами сможем легко. Поэтому сейчас займёмся разработкой этих функций. Начнём с операции сложения целых чисел. 5 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» ФУНКЦИЯ summer() – ОПЕРАЦИЯ СЛОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ Функция использует “строковую” арифметику. Значения операндов могут быть любыми целыми числами. АЛГОРИТМ СЛОЖЕНИЯ (минимальная детализация) Входные данные : expr строка - арифметическое выражение. Выходные данные : RES строка - значение выражения. Рабочие переменные : OP строка - операнд. П_р_и_м_е_ч_а_н_и_е. Первые символы RES и OP – знаковые. НАЧАЛО Если expr содержит недопустимые символы, то возвратить NULL. ЗАКОНЧИТЬ. Выделить память под RES и OP (сколько???) Инициализировать RES нулями (символами или числами???). Пока не достигнут конец строки expr Поместить в OP очередной операнд СО ЗНАКОМ; (??см. выше??) Поместить в RES АЛГЕБРАИЧЕСКУЮ сумму RES и OP. (как вычислять???) КОНЕЦ НАПРАВЛЕНИЯ ДЕТАЛИЗАЦИИ АЛГОРИТМА. Обсудим вопрос «Как вычислять?» Вариант 1. «Как на арифметике в начальной школе» Сложение: Записать в RES более длинное слагаемое, а в OP – более короткое. Установить «ручку» на самые правые цифры RES и OP. Пока «ручка» не сместилась левее самой левой цифры OP сложить текущие цифры RES и OP если сумма < 10, то поместить её значение в текущий разряд RES иначе прибавить 1 к соседнему слева разряду RES значение (сумма - 10) поместить в текущий разряд RES Вычитание: Запомнить знак большего по модулю слагаемого Записать в RES большее по модулю слагаемое БЕЗ ЗНАКА Записать в OP – меньшее по модулю слагаемое БЕЗ ЗНАКА. Пока «ручка» не сместилась левее самой левой цифры OP Если текущая цифра RES меньше текущей цифры OP, то уменьшить соседний слева разряд RES на 1 увеличить текущий разряд RES на 10. Поместить в текущий разряд RES разность тек. разрядов RES и OP. Присвоить RES сохранённый знак. 6 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Вариант 2. «Как в компьютере целочисленное суммирование» __Идея__: представлять отрицательные числа в «дополнительном коде». n-разрядное целое число (с учётом знака) изображается последовательностью, из n+1 символов. Самый левый (первый) символ – знак числа, остальные n символов – цифры. Пусть number - массив, хранящий изображение n-разрядного числа. ДОГОВОРИМСЯ заполнять его левую позицию НУЛЁМ, если число положительное, или ДЕВЯТКОЙ, если число отрицательное. В остальных позициях записываются цифры. Например, число 123 разместится в массиве четырёх элементов: (0, 1, 2, 3); число -123 можно представить так: (9, 1, 2, 3) (“прямой” код), а можно так: (9, 8, 7, 7) (“дополнительный” код). Если отрицательное число представлено в прямом коде, то операция сложения его с положительным числом реализуется выше описанным алгоритмом вычитания. А если в дополнительном – то выше описанным алгоритмом сложения. ДОГОВОРИМСЯ представлять отрицательные числа в дополнительном коде. Тогда для выполнения операций сложения и вычитания можно использовать один и тот же алгоритм. При суммировании двух отрицательных чисел, представленных в дополнительном коде, в знаковом разряде должна оставаться цифра 9 Обсудим вопрос сколько? памяти выделять под изображения результата и операнда. С операндами всё ясно. Столько байтов, сколько символов в изображении, включая знак. Результат может быть на один разряд длиннее длиннейшего из операндов. Т.Е. Под результат суммирования следует выделять n+2 байта, где n – число ЦИФР в изображении более длинного из операндов. Из двух байтов сверх того один (самый левый) под знак, а другой (второй слева) под возможный дополнительный разряд результата. Наконец, вопрос символами или числами заполнять массивы – операнды? Ответ очевиден. Конечно, ЧИСЛАМИ. Т.е., каждый элемент массива должен быть целым числом из набора 0, 1, 2,…,9. Первый элемент массива интерпретируется как знак, остальные – разряды операнда. АЛГОРИТМ СЛОЖЕНИЯ (Второй уровень детализации) Входные данные : expr строка - арифметическое выражение. Выходные данные : RES строка - значение выражения. Рабочие переменные : OP строка –операнд. НАЧАЛО 1. Если expr содержит недопустимые символы, то возвратить NULL. ЗАКОНЧИТЬ. 2. Выделить первый операнд и поместить его в RES. (Указатель в expr на первом знаке операции!) 3. Пока не достигнут конец expr 3.1. Выделить очередной операнд и поместить его в OP. 3.2. Получить сумму RES + OP и поместить её в RES. 4. Возвратить RES. КОНЕЦ 7 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Выделение операндов очевидно. Интерес представляет алгоритм пункта 3.2. /* АЛГОРИТМ СУММИРОВАНИЯ ДВУХ СЛАГАЕМЫХ, ЗАДАННЫХ СТРОКАМИ ЦИФР, ВОЗМОЖНО С ВЕДУЩИМИ ЗНАКАМИ ‘+’ ИЛИ ‘-‘. Входные данные: opf, ops – строки-операнды. Выходные данные: res – строка-результат суммирования. Рабочие переменные: regf, regs – массивы – регистры сумматора. lenr – длина регистра. lenf, lens – длины opf и ops. НАЧАЛО 1. 2. 3. 4. 5. 6. 7. 8. КОНЕЦ Вычислить значения lenf и lens. Положить lenr = max(lenf, lens) + 2. Создать массив regf[lenr] и заполнить его разрядами opf. Создать массив regs[lenr] и заполнить его разрядами ops. Поразрядно просуммировать regf и regs, размещая результат в regf. Преобразовать содержимое regf в строку и поместить её в res. Освободить память, занятую под regf и regs. Возвратить res. Действия Действия Действие Действие */ 1, 2 – ясно 3, 4 – требуется функция создания регистра. 5 – ясно. 6 - требуется спецификация. #include #include #include #define isop(C) ((C=='+'||C=='-')?1:0) char *creareg(int len, char *op) {//Создаёт регистр длины len, и заполняет его представлением операнда op. char *reg; if((reg = (char*)malloc(len*sizeof(char)))==NULL) return NULL; char sign=(isop(*op))?*op:'+'; int numop=(isop(*op))?strlen(++op):strlen(op); while(*++op); op--; // Число цифр в op. // Указатель в последнюю позицию op. int i=len-1, j=0; if(sign=='+') for( ; i>=0; i--)// Заполнение reg прямым кодом op. reg[i]=(j=0; i--) 8 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» reg[i]=(j9; reg[i]-=10, i--, reg[i]+=1); } return reg; } char *summer(char *opf, char *ops) { // Возвращает в виде строки сумму чисел, заданных строками opf, ops. // В случае нехватки памяти для размещения результата возвращает NULL. char *regf, *regs, *res; int lenr, lenf, lens; lenf = strlen(opf); lens = strlen(ops); /* // Сохранить длины // операндов. lenr = ((lenf>lens)?lenf:lens)+2; Длина "разрядной сетки" на два байта больше длины более длинного из операндов. "Переполнение" в результате операции невозможно. */ regf = creareg(lenr, opf); regs = creareg(lenr, ops); int i; for(i=lenr-1; i>=0; i--) { char s=regf[i]+regs[i]; if(s>9) { regf[i]=s-10; regf[i-1]+=1; } else regf[i]=s; } /* // Заполнить // регистры. // Суммировать регистры. // Если сумма цифр больше девяти, то // в текущий разряд последнюю цифру, // а предыдущий увеличить на 1. СПЕЦИФИКАЦИЯ ДЕЙСТВИЯ 6 Сформировать строку-результат. ПОЛОЖИТЕЛЬНЫЙ РЕЗУЛЬТАТ ВОЗВРАЩАЕТСЯ БЕЗ ЗНАКА. 6.1. Если в знаковом разряде регистра девятка, то получить прямой код отрицательного числа. 6.2. Подсчитать n - число ведущих нулей в regf (знаковый разряд игнорировать!). (Число значащих цифр в коде результата есть lenr-1-n.) 6.3. Если n==lenr-2 если *regf==0, возвратить строку "0", иначе возвратить строку "-1". 6.4. Если *regf==0, выделить под res lenr-n байт, иначе lenr-n+1. (Длина результирующей строки с учётом '\0'). 6.5. Если *regf==9, положить в res[0] '-'. 6.6. Заполнить res кодами цифр из regf. */ 9 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» if(*regf==9) // 1. Если в знаковом разряде регистра девятка, то { // получить прямой код отрицательного числа. for(i=lenr-1; i>0; i--) regf[i]=9-regf[i]; for(i=lenr-1, regf[i]+=1; regf[i]>9&&i>0; regf[i]-=10, i--, regf[i]+=1); } /* 2. Подсчитать n - число ведущих нулей в regf (знаковый разряд игнорировать!). (Число значащих цифр в коде результата есть lenr-1-n.)*/ int n; for(n=1; regf[n+1]==0&&n