Курсовой работы

Задание 1

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

1) исходное число А делится на Р нацело в десятичной системе и

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

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

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

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

Задание 2

Способ перевода целого числа из десятичной системы счисления в
Р-ичную, основанный на выделении максимальной степени числа Р в исходном десятичном числе, заключается в определении левой цифры в
Р-ичной записи числа а_n путем такой степени числа Р, для которой выполняется неравенство: Рⁿ£ а< Рⁿ⁺¹, то а_n будет равно целой части от деления а на Р_n. Остатком же от такого деления является число а, состоящее из цифр: а_n-1, …, а₁, а₀. Если оно равно 0, то и все его цифры равны 0, на этом вычисления заканчиваются. В противном случае необходимо определить максимальную степень k числа Р, для которой справедливо: Р^k£ а_n-1Р^n-1+ … +а₁Р+а₀< Р^k+1£ Рⁿ.Тогда 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)-й степени относительно Р. Например, для шестизначного числа а=а₅а₄а₃а₂а₁а₀ оно имеет вид: а=а₀Р⁵+а₁Р⁴+а₂Р³+а₃Р²+а₄Р+а₅.

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

Задание 13

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

Задание 14

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

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

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

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

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

Задание 15

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

Задание 16

Решение этого задания должно быть основано на следующем факте: если из положительного двоичного числа m вычесть единицу, то содержимое младших разрядов этого числа (до разряда с младшей единицей включительно) меняется на противоположное (цифра 0 заменяется на 1, а 1 – на 0), а старшие разряды остаются без изменения. Если, например, m=10011000, то r=m–1=110010111.

Теперь битовая операция r and m приведет к удалению младшей единицы из исходного числа. Например, если r and m=10010000, то для подсчета числа единиц в двоичном представлении натурального числа указанную процедуру надо выполнять до тех пор, пока очередная операция and не приведет к нулевому значению, а количество повторений этой процедуры и есть искомый результат.

Задание 17

Любое подмножество можно охарактеризовать, указав для каждого элемента исходного множества, принадлежит оно данному подмножеству или нет. Сделать это можно, поставив соответственно к каждому элементу 0 (элемент не принадлежит подмножеству) или 1 (элемент подмножеству принадлежит). Тогда каждому подмножеству соответствует n-значное число в двоичной системе счисления (строго говоря, такие числа могут начинаться с произвольного количества нулей, которые значащими цифрами не считаются). Отсюда следует, что полный перебор всех подмножеств данного множества соответствует перебору всех чисел в двоичной системе счисления от 0…01 до 1…1. Последнее из таких чисел соответствует всему исходному множеству. Теперь можно подсчитать и количество различных подмножеств данного множества. Оно равно 2ⁿ–1 (или с учетом пустого множества 2ⁿ).

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

Задание 18

Решение этой задачи основано на следующем свойстве побитовой логической операции “исключающее или“ – XOR (^ в С):

B xor B º 0,

А xоr В xоr В º А и

В xоr А xоr В º А

(докажите это, используя таблицу всех возможных значений логических переменных А и В). Эти же тождества справедливы и в случае, когда операция является битовой (^ в С), а А и В – числами.

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

Теперь легко составить программу, которая будет верно работать, в том числе и для случая, когда в исходном файле находится всего одно число (оно же тогда и является результатом).

Данная программа является также примером организации ввода из файла чисел в случае, когда заранее неизвестно их количество. Применение в языке Turbo-Pascal логической функции SeekEof вместо Eof позволяет игнорировать пробелы и символы перевода строки в конце файла после ввода последнего числа. В языке С такую ситуацию требуется обрабатывать самостоятельно.

Задание 19

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

Алгоритм компьютерного сложения (вычитания) двух вещественных чисел:

1) порядки чисел выравниваются по большему из них;

2) выполняется операция сложения (вычитания) над мантиссами с округлением по значению n+1-й значащей цифры результата;

3) мантисса результата должна быть нормализована.

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

1) потеря значащих цифр мантиссы у меньшего из чисел при выравнивании порядков:

2) потеря крайней справа значащей цифры результата при сложении или вычитании мантисс;

3) выход за границу допустимого диапазона значений того или иного

вещественного типа при нормализации результата (выполнение программы прерывается с сообщением об ошибке: “Арифметическое переполнение”).

Задание 20

Один из возможных вариантов решения этой задачи заключается в прямом вычислении значения произведения этих чисел и определении количества хвостовых нулей в нем. Программа фактически будет состоять лишь из процедуры умножения “длинного” Р-ичного числа на “короткое”.

Если количества двоичных разрядов в стандартных типах данных для представления числа недостаточно, то такое число называется “длинным”.

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

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

Задание 21

Очевидно, что различных остатков при делении на n не может быть больше, чем n (их значения лежат в интервале от n до n–1). Если даже все первые n остатков при делении m на n различны, то (n+1)-й остаток обязательно совпадет с одним из уже полученных ранее, т.е. он находится в периодической части. Поэтому для нахождения длины периода L следует запомнить (n+1)-й остаток и генерировать остатки дальше, пока не будет получен совпадающий с ним. Количество сгенерированных при этом чисел и составит длину периода.

Если известна длина периода L, непериодическую часть можно найти следующим образом. Сначала получают L-й остаток. Если он совпадает с m, то непериодическая часть нулевая, в противном случае – сравнивают первый и (L+1)-й остаток, второй и (L+2)-й и т.д., пока не найдется совпадающая пара. Количество сравнений до совпадения и является длиной непериодической части. Получаемые при этом в результате деления цифры можно выдавать на печать. Следующие же за непериодической частью L цифр результата деления составят период. Если дробь является конечной, то в качестве периода будет напечатано число 0.

Задание 22

Числа А и В не должны превосходить 127 и подбираются таким образом, чтобы сумма чисел была больше, чем 127, а их разность была отрицательна, например: А = 59, В = 106.Так, для приведенного примера результаты оформляются в виде таблицы (табл.3).

Таблица 3

Таблица ответов

Задание 23

Для умножения двух длинных чисел существует несколько различных алгоритмов. Один из них заключается в умножении каждой цифры первого множителя на каждую цифру второго и размещении каждого из таких произведений в соответствующем разряде результата. Если в каком-то разряде результата оказывается число большее, чем максимальная цифра соответствующей системы счисления (9 в десятичной системе), то производится перенос в старший разряд. Такой алгоритм соответствует умножению двух чисел столбиком.

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

Применение в языке Turbo-Pascal логической функции SeekEoln вместо Eoln позволяет игнорировать пробелы в конце строки при вводе “длинного” числа. В языке С такую ситуацию требуется отслеживать самостоятельно.

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

Задание 24

Входные данные удобнее представлять в файле, так как делитель у нас является числом “коротким”, а остаток от деления всегда меньше делителя, то для его получения массив не нужен.

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

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

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

Задание 25

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

То же замечание касается и возведения тройки в целую степень. Заметим, что при 1 < k £ 100 log₂k принимает значения от 1 до 6. Следовательно, сто обыкновенных дробей, которые требуется сложить, имеют всего 6 различных знаменателей: 3, 3², 3³, … 3⁶, причем наименьшим общим знаменателем этих дробей является 3⁶ (это число “короткое”). Поэтому несложно привести все 100 дробей к общему знаменателю и, используя лишь целочисленную арифметику, получить значение числителя и знаменателя результирующей дроби. Для перехода от обыкновенной дроби к десятичной можно воспользоваться алгоритмом деления “короткого” числа на “короткое” и определить точное значение искомой суммы.