Функция, возвращающая в виде строки произведение двух целых чисел, заданных строками

1 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Часть 2 Мультипликативные операции НАПОМИНАНИЕ На прошлой лекции мы поставили перед собой задачу: написать программу, которую назвали «Неограниченный калькулятор». Программа должна обеспечивать ввод арифметического выражения и возвращать значение этого выражения. Операндами выражения являются рациональные числа, т.е. пары {числитель, знаменатель}. Возвращаемое значение – также рациональное число. Программа не должна накладывать на значения операндов никаких ограничений, связанных с размером разрядной сетки технической платформы. Мы выяснили, что для программной реализации арифметики рациональных чисел необходимо написать функции, реализующие операции арифметики целых чисел, по крайней мере, операции сложения, вычитания и умножения. Мы приняли решение представлять «неограниченное» целое число массивом чисел из диапазона 0  9, изображающим «строковую запись» числа в десятичной системе счисления. Мы приняли решение представлять отрицательное целое число в десятичном дополнительном коде, аналогичном бинарному, используемому в компьютерной арифметике. Это открывает возможность использования единого алгоритма для реализации обеих аддитивных операций целочисленной арифметики. Наконец, мы написали код функции, реализующей знакомый нам с детства алгоритм сложения «в столбик, как на бумаге». На сегодня ЗАДАЧА Написать функцию, возвращающую в виде строки произведение двух целых чисел, заданных строками. char *multiplier(char *opf, char *ops) Ограничений на размеры операндов нет. ИДЕЯ Пусть opf и ops – целые числа и пусть 10^(m-1) < opf < 10^m; 10^(n-1) < ops < 10^n. Очевидно res = opf*ops < 10^(m+n). 2 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Часть 2 Мультипликативные операции Создадим регистры regf, regs длин lenf = m и lens = n соответственно, и поместим в них цифры операндов. (Сохраним знак результата!!!) Создадим регистр regp, в котором будет накапливаться произведение. Его длина lenp = m + n. Сложим в regp реультат перемножения “в столбик” содержимого regf и regs. Преобразуем regp в строку цифр (с ведущим знаком, если произведение отрицательно). АЛГОРИТМ Входные данные: opf, ops – строки цифр, возможно с ведущим знаком ‘+’ или ‘-’. Выходные данные: res – строка цифр, возможно, с ведущим знаком ‘-’. Рабочие переменные: lenf, lens – число цифр в строках opf и ops соответственно; regf, regs – массивы-регистры длин lens, lenr соответственно; regp – массив-регистр длины lens+lenr; sign – знак произведения; ptf, pts, ptp - оперативные указатели в regf, regs и regp. НАЧАЛО 1. Если знаки opf и ops совпадают, положить в sign ‘+’, иначе ‘-’. 2. Подсчитать числа цифр в операндах lenf и lens. 3. Создать и загрузить регистры regf и regs. 4. Создать регистр regp длины lenf+lens и заполнить его нулями. 5. Установить указатели pts и ptp в концы regs и regp. 6. Пока указатель pts внутри массива regs 6.1. Умножить содержимое regf на текущую цифру regs; 6.2. Сложить результат с текущим состоянием regp (с учётом сдвига!); 6.3. Нормализовать*) значения разрядов regp. 6.3. Уменьшить значения указателей pts и ptp на единицу. 7. Преобразовать содержимое regp в строку res. 8. Возвратить res. КОНЕЦ *) После выполнения операций 6.1 и 6.2 разряды регистра regp могут содержать двузначные числа. Нормализация – приведение значения каждого разряда регистра к однозначному числу с переносом “лишних” десятков в старший разряд. 3 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Часть 2 Мультипликативные операции РЕАЛИЗАЦИЯ Особенности 1. В качестве регистров сомножителей используются блоки памяти, занятые строками opf и ops. Т.о., указатели regf и regs указывают на ПЕРВЫЕ ЦИФРЫ строк opf и ops соответственно. 2. Строка-результат формируется в блоке памяти, выделенном под регистр regp. #define isop(C) ((C=='+'||C=='-')?1:0) /* Макрос преобразует операнд OP в регистр сомножителя. R - указатель регистра. Устанавливается на первую цифру сомножителя. L - число цифр операнда OP.*/ #define creg(R, OP, L) {R=(isop(*OP))?(OP+1):OP;\ L=strlen(R);\ int i;\ for(i=0; i=0; i--) { int j; for(j=lenf-1; j>=0; j--) //6.1. умножить содержимое regf на текущую цифру regs { *ptp+=regf[j]*regs[i]; //6.2. сложить результат с текущим состоянием ptp; *(ptp-1)+=*ptp/10; *ptp=*ptp%10; //6.3. Нормализовать значения разрядов ptp. ptp--; } ptp+=lenf-1; // 6.4. Сдвинуть указатель ptp влево. } /* 7. Преобразовать регистр regp в строку. В регистре не более двух ведущих нулей! Если regp[1]=0, то уменьшить lenr на 1, положить regp[1]=regp[0] увеличить regp на единицу. Если regp[0]=0, то положить res=++regp иначе положить res=regp увеличить regp на единицу Преобразовать разряды regp в цифры. */ if(!regp[1]) { lenr--; regp[1]=regp[0]; regp++; } if(!regp[0]) res=++regp; else { res=regp; regp++; } for(i=0; i1”, “0”}. 3. Если |num| < |denom| возвратить {“0”, <знак>num}. 4. Определить длины регистров. 5. Создать и загрузить regden (см. умножалку). 6. Создать регистр regrem и загрузить в него первые lenden цифр из num. 7. Если regrem < regden (Макрос REGCMP), то добавить в regrem ещё одну цифру из num (Макрос ADDFIG). 8. Создать регистр regint, regwrk (инициализировать нулями). 9. Пока есть цифры в num 9.1. Подобрать и поместить в текущую позицию регистра regint цифру fig, удовлетворяющую условию regden*fig <= regrem < regden*(fig+1) (Макрос SEARCHFIG). 9.2. Поместить в regrem значение regrem - regden*fig. 9.3. Добавить в regrem очередную цифру num (ADDFIG). 9.4. Пока regrem < regden и есть цифры в num 9.4.1. Добавить в regrem очередную цифру num (ADDFIG). 9.4.2. Добавить 0 в текущую позицию regint. 10. Преобразовать regint в строку с учётом знака и поместить указатель в res[0]. 11. Преобразовать regrem в строку с учётом знака и поместить указатель в res[1]. 12. Возвратить res. КОНЕЦ 9 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Часть 2 Мультипликативные операции КОД АЛГОРИТМА ДЕЛЕНИЯ «В СТОЛБИК» #include #include #include #define isop(C) ((C=='+'||C=='-')?1:0) #define strabs(str) (*str=='+'||*str=='-')?str++:str int opcmp(char *op1, char *op2) // Возвращает 1 при op1 > op2, // 0 при op1==op2, // -1 при op1 < op2. { int len1=strlen(op1), len2=strlen(op2); if(len1>len2) return 1; if(len1*op2) return 1; if(*op1<*op2) return -1; op1++; op2++; } return 0; } char **divider(char *num, char *denom) { char *regden, // регистр делителя, *regrem, // регистр остатка, *ptrr, // рабочий указатель в regrem *regint, // регистр целой части, *ptri, // рабочий указатель в regint, *regwrk, // рабочий регистр, *ptrw, // рабочий указатель в regwrk, sign; // знак результата деления. int lennum, lenden, lenrem, lenint, lenwrk; // // // // // число длина длина длина длина цифр делимого, regden (число цифр делителя), regrem, regint, regwrk, char **res=malloc(2*sizeof(char*)); /* // Результат деления 1. Если знаки num и denom совпадают, то sign = 0, иначе sign = 1.*/ sign = (((isop(*num))?*num:'+')==((isop(*denom))?*denom:'+'))?0:1;// Знак результата. 10 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Часть 2 Мультипликативные операции /* Получить "абсолютные значения" операндов*/ strabs(num); strabs(denom); /* 2. Если |num| == |denom| возвратить {“<знак>1”, “0”}.*/ if(!opcmp(num, denom)) { if(sign) { res[0]=(char*)calloc(3, sizeof(char)); res[0][0]='-'; res[0][1]='1'; } else { res[0]=(char*)calloc(2, sizeof(char)); res[0][0]='1'; } res[1]=(char*)calloc(2, sizeof(char)); res[1][0]='0'; return res; } /* 3. Если |num| < |denom| возвратить {“0”, <знак>num}.*/ lennum = strlen(num); if(opcmp(num, denom)<0) { res[0]=(char*)calloc(2, sizeof(char)); res[0][0]='0'; if(sign) { res[1]=(char*)calloc(lennum+2, sizeof(char)); res[1][0]='-'; strcpy(res[1]+1, num); } else { res[1]=(char*)calloc(lennum+1, sizeof(char)); strcpy(res[1], num); } return res; } /* 3. Определить длины регистров.*/ lenden = strlen(denom); lenrem = lenden+1; lenint = lennum-lenden+1; lenwrk = lenrem; /* 4. Создать и загрузить regden.*/ regden=(char*)calloc(lenden, sizeof(char)); 11 ПРОЕКТ «КАЛЬКУЛЯТОР РАЦИОНАЛЬНЫХ ЧИСЕЛ» Часть 2 Мультипликативные операции int i; for(i=0; i