Задания и методические указания к выполнению курсовой работы по дисциплине «Языки и системы программирования» (стр. 2 )

3) справа налево последовательно;

4) справа налево все положительные и все отрицательные, затем вычитание.

20. Дана последовательность из не более чем 1000 неотрицательных целых чисел, каждое из которых удовлетворяет ограничению 0<m<231. Числа записаны в позиционной системе счисления с основанием Р. Необходимо определить количество последних идущих подряд нулей в произведении этих чисел, записанном в той же системе счисления.

21. Даны взаимно простые натуральные числа m и n ( m < n ). Найти периодическую и непериодическую части десятичной дроби., равной m/n.

22. Даны десятичные числа А и В. Найти их сумму и разность в 8-разряд-

ном беззнаковом и знаковом представлении. Ответ записать в таблицу.

23. Реализовать алгоритм умножения “длинного” числа на “длинное” с помощью алгоритма умножения двух чисел столбиком.

24. Реализовать алгоритм целочисленного деления с остатком “длинного” числа на “короткое”.

25.  Вычислить с максимальной точностью значение суммы k элементов,

вычисляемых следующим выражением: (k/3n), где n=logk2 , а k изменяется от 1 до 100.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ

КУРСОВОЙ РАБОТЫ

Задание 1

Алгоритм перевода целого числа из десятичной системы счисления в Р-ичную.

1)  исходное число А делится на Р нацело в десятичной системе и записывается в качестве нового значения десятичного числа А целой части результата от деления.

2)  остаток от деления заменяется на соответствующую цифру в Р-ичной системе счисления, которая приписывается слева к полученным ранее цифрам в Р-ичной записи числа А (первая полученная цифра соответствует младшему разряду и ее просто записывают);

3)  пп.1и 2 выполняются до тех пор, пока число А не станет равным 0.

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

Задание 2

Способ перевода целого числа из десятичной системы счисления в Р-ичную, основанный на выделении максимальной степени числа Р в исходном десятичном числе, заключается в определении левой цифры в Р-ичной записи числа аn путем такой степени числа Р, для которой выполняется неравенство: Рn£а<Рn+1, то аn будет равно целой части от деления а на Рn. Остатком же от такого деления является число а, состоящее из цифр: аn-1, …,а1, а0. Если оно равно 0, то и все его цифры равны 0, на этом вычисления заканчиваются. В противном случае необходимо определить максимальную степень k числа Р, для которой справедливо: Рk£аn-1Рn-1+ … +а1Р+а0<Рk+1£Рn. Тогда n–1–k следующих за аn цифр будут равны нулю, а аk получают в результате деления нацело а на Рk и, пока остаток от деления не окажется равен нулю, продолжают описанные действия.

Преимущество этого метода состоит в естественном порядке записи получившихся Р-ичных цифр (слева направо), что важно при программировании: очередная полученная цифра сразу же может выводиться на печать.

Задание 3

Алгоритм перевода целых чисел из Р-ичной системы счисления в десятичную:

1) каждая цифра числа в Р-ичной системе счисления переводится в число в десятичной системе;

2) полученные числа нумеруются справа налево, начиная с нуля (номера соответствуют степеням Р);

3)  десятичное число, соответствующее каждой Р-ичной цифре,

умножается на Рk, где k – номер этого числа, и результаты складываются, причем все эти арифметические действия проводятся в десятичной системе.

Задание 4

В решении сначала производится перевод в десятичную систему целой части, а затем дробной. Для того чтобы не накапливалась погрешность вычислений при переводе дробной части в десятичную систему, сначала получают обыкновенную дробь в виде целочисленных числителя и знаменателя, а затем делят числитель на знаменатель, получая в результате требуемые 8 цифр после запятой.

Алгоритм перевода конечной Р-ичной дроби в десятичную:

1) целая часть переводится в десятичную систему отдельно;

2) каждая цифра дробной части числа в Р-ичной системе счисления переводится в число в десятичной системе;

3) полученные в результате преобразования дробной части числа нумеруются слева направо, начиная с единицы;

4) десятичное число, соответствующее каждой Р-ичной цифре, умножается на Р-k, где k – номер этого числа и результаты складываются, причем все эти арифметические действия проводятся в десятичной системе.

Задание 5

Алгоритм перевода правильной конечной десятичной дроби в Р-ичную систему счисления:

1) исходное число умножается на Р (основание новой системы счисления), целая часть полученного произведения является первой цифрой после запятой в искомом числе (целая часть может быть как равна нулю, так и быть больше девяти, но она всегда меньше чем Р, это позволяет записать ее в виде ровно одной цифры Р-ичной системы счисления);

2) дробная часть произведения снова умножается на Р, целая часть полученного числа заменяется на цифру в Р-ичной системе, которая приписывается справа к результату;

3) п.2 выполняется до тех пор, пока дробная часть произведения не станет равной нулю или не выделится период (дробная часть окажется равной уже получавшейся ранее дробной части произведения).

Задание 6

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

1) если при умножении периода дроби на некоторое число количество цифр в произведении равно количеству цифр в периоде исходного числа, то период результата равен полученному произведению. В этом случае переходим к п.6, в противном – к п.2;

2) “лишними” цифрами считаются n – k первых слева цифр результата, где n – количество цифр в результате, k – количество цифр в периоде исходной дроби;

число, образованное “лишними” цифрами, складывается с числом, образованным правыми k цифрами промежуточного результата;

3) если количество цифр, получившихся в результате сложения, больше, чем k, то процесс следует повторить с п.2;

4) если количество цифр результата сложения стало равным количеству цифр периода исходной дроби, то период произведения равен последнему результату суммирования;

5) непериодическая (целая – для чисто периодических дробей) часть результата равна сумме чисел, образованных из “лишних” цифр каждого этапа.

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

Второй способ перевода состоит в том, что любую периодическую дробь можно представить в виде обыкновенной, затем целочисленные числитель и знаменатель перевести в Р-ичную систему, и уже в ней вновь преобразовать обыкновенную дробь в Р-ичную, организовав деление столбиком.

Задание 7

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

перевода обыкновенной дроби в десятичную приведен в методических указаниях к заданию 4.Значение Р-ичной дроби вводится в следующем формате: 0,хх(хх), где вместо произвольного количества символов х должны стоять цифры Р-ичной системы, не превосходящие 9 (значение же Р может быть и больше 10), непериодическая часть может отсутствовать. Для решения описанной задачи в программе сначала ищутся числитель x и знаменатель z обыкновенной дроби для непериодической части, затем числитель y и знаменатель q для периода. Окончательный же результат равен x/y=y/zq.

Задания 8 – 12

Для n-значных чисел мы получаем полиномиальное уравнение (n–1)-й степени относительно Р. Например, для шестизначного числа а=а5а4а3а2а1а0 оно имеет вид: а=а0Р5+а1Р4+а2Р3+а3Р2+а4Р+а5.

Если возникшее уравнение имеет натуральные корни (корень), отличные от 1, то они будут основаниями искомых систем счисления. Все такие корни полинома являются числителями свободного члена полинома (в нашем случае это а5–а). Таким образом, для решения полиномиального уравнения в натуральных числах следует найти все делители положительного числа а–а5, и проверить путем подстановки, являются ли они корнями уравнения.

Задание 13

Несмотря на то что все цифры чисел А и В по условию не превосходят 9, основания их систем счисления x и y могут быть как угодно большими. Это делает процесс простого перебора всех пар оснований систем счисления не только неэффективным, но и невозможным. Поэтому перебор следует организовать лишь по одному из оснований, например x. И для каждого x, определив значение а получившегося числа Аx в десятичной системе счисления, решить, как и в задании 11, полиномиальное уравнение относительно y. Коэффициентами полинома в данном случае будут являться цифры числа В, а свободный член равен (b0–а).

Задание 14

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

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

Таблица 1 Таблица 2

Таблица умножения Таблица умножения

в двоичной системе счисления в троичной системе счисления

Х	0	1		Х	0	1	2
0	0	0		0	0	0	0
1	0	1		1	0	1	2
				2	0	2	11

Задание 15

При решении следует учитывать тот факт, что любое натуральное число хранится в компьютере в своем двоичном представлении. Поэтому достаточно узнать и напечатать значения всех его разрядов слева направо, опуская незначащие левые нули. Считается, что все разряды в представлении двоичного числа n пронумерованы справа налево, начиная с нуля. Тогда значение i-го разряда равно 0, если (1 shl i) and n=0, так как 1 shl i представляет из себя число, в двоичном представлении которого присутствует всего одна единица в i-м разряде справа. Если в этом разряде у числа n единицы нет, то результат указанной битовой операции окажется нулевым.