ЛАБОРАТОРНАЯ РАБОТА № 3

Целочисленная арифметика

1. Введение в постановку задачи

1.1. Позиционные системы счисления

При записи числа в позиционной системе счисления вклад каждой цифры в числовую величину определяется самой цифрой и весом позиции, которую она занимает. Для системы счисления с основанием p вес позиции с номером i (i=0÷n-1, n – количество цифр в числе) определяется как pⁱ.

Чтобы перевести число a_n-1…a₀ из системы счисления с основанием p в систему счисления с основанием q, можно воспользоваться любым из двух алгоритмов: алгоритмом «умножения», вычисляющим многочлен a_n-1 p ^n-1+a₁ p+…+a₀, или алгоритмом «деления», вычисляющим последовательные остатки от деления на q исходного числа и целых частей частного от деления на q. Следующий пример является иллюстрацией к алгоритмам «деления» и «умножения» при «переводе» числа из десятичной в десятичную систему счисления.

N=85462=10*8546+2

8546=10*854+6

854=10*85+4

85=10*8+5

8=10*0+8

Полученные остатки и являются последовательными цифрами числа, записанного в позиционной системе.

N=85462=10*8546+2=10(10*854+6)+2=10(10(10*85+4)+6)+2=10(10(10(10*8+5)+4)+6)+2.

После преобразований получим:

N=85462=8*10⁴+5*10³+4*10²+6*10¹+2*10⁰.

Выбор одного из двух алгоритмов определяется тем, в какой системе счисления будут выполняться вычисления. В алгоритме «умножения» действия выполняются в системе счисления с основанием q, в алгоритме «деления» – в системе счисления с основанием p.

Принцип представления числа в любой позиционной системе счисления остается общим, при этом цифры-знаки в системе с основанием p – это арабские цифры от 0 до p-1 и, при необходимости, – буквы латинского алфавита.

1.2. Рекомендации по организации работы со строками

Строка в С-программе может быть представлена одномерным массивом символов (например: char string1[100]) или указателем на данные символьного типа (например: char *string2). Во втором случае компилятор отводит память только для размещения переменной-указателя, но не для размещения собственно символьных данных, которые в этом варианте организации строки должны быть размещены в динамической памяти. Для выделения динамической памяти можно воспользоваться, например, оператором new (string2= new char[100]) или malloc (string2=(char *)malloc(100)). В любом случае, для обращения к одному символу строки, имеющему тип char, используется оператор [] (например: string1[10] или string2[i+1]). Для работы со строками имеется набор функций (заголовочный файл – string.h), из которых при выполнении данной лабораторной работы могут понадобиться:

char * strcpy(char *s1, char *s2) – копирование строки s2 в строку s1;

char * strcat(char *s1, char *s2) – сцепление (конкатенация) двух строк;

int strlen(char *s) – определение длины строки.

В лабораторной работе необходимо выполнить перевод числа из одной системы счисления (начальной) в другую (конечную) согласно варианту, используя в качестве промежуточной системы счисления внутреннее представление числа в памяти компьютера (двоичная система). На вход подается цепочка символов (строка), содержащая только цифры начальной системы счисления, на выходе формируются два результата: число в промежуточной системе в формате long и число в конечной системе счисления также в виде цепочки символов. Перевод из внутреннего представления в конечную систему осуществляется путем деления на основание конечной системы счисления. Все циклические операции должны быть организованы рационально. Содержательные части программы оформляются функциями (см. ОБЩИЕ ТРЕБОВАНИЯ...). Необходимо предусмотреть контроль ошибок ввода, когда цифры в строке ввода не являются цифрами-знаками начальной системы счисления.

2. Задание на лабораторную работу

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