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

Задание 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. Последнее из таких чисел соответствует всему исходному множеству. Теперь можно подсчитать и количество различных подмножеств данного множества. Оно равно 2n–1 (или с учетом пустого множества 2n).

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

Задание 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

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

Числа	10-тичные	8-битные	Беззнаковые	Знаковые
А	59	00111011	59	59
В	106	01101010	106	106
А + В	165	10100101	165	-91
А – В	-47	11010001	209	-47

Задание 23

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

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

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

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

Задание 24

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

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

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

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

Задание 25

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