Пример решения и комментарии

Задание. По введенному натуральному числу n < 30000 найти значение выражения 2ⁿ.

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

Второй возможный подход к решению данной задачи – это перевод двоичного числа, состоящего из одной единицы и n нулей (а именно так в двоичной системе выглядит 2ⁿ), в десятичную систему счисления методом деления в двоичной системе на 10 = 1010₂. Но деление в двоичной системе придется организовывать самостоятельно (аналогично алгоритму деления “длинного” числа на “короткое”).

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

Приведем такое решение задачи: умножение производится, пока это возможно, на 2¹⁷ (произведение 2¹⁷ на максимальную цифру 10000-й системы счисления – 9999, еще меньше, чем максимальное число, представимое в целом типе). Затем результат домножается на оставшееся 2^k, где k< 17.

Решение на языке Turbo-Pascal:

Var s alоng

L, n, i, k: integer;

Begin

readln (n); {вводим значение степени}

s [1]: =1; {результат для нулевой степени }

L: =1; {длина результата}

while n> 16 do

{умножаем на 1 shl 17=2^17}

begin

mult (s, L, 1 shl 17);

n: = n-17

end;

if n > 0 then {умножаем на оставшуюся степень}

mult (s, L, 1 shl n);

assign (output, ‘ output.txt’); }

rewrite (s[L]); {старший разряд просто печатаем}

for i: = L-1 downto l do

begin

k: = 1000;

while s [i]< k do {недостающие цифры заменим 0}

begin

write (0);

k: = k div 10

end;

write (s [ i ]);

end;

Close (Output)

End.

Решение на языке С:

voidmain ()

{ALONG s;

long L, n, i, k;

FILE *f;

scanf (“%D”, & n);

s [ l ] = l; /*результат для нулевой степени*/

L = l; /*длина результата*/

while (n> 16) /* умножаем на 1< < 17 = 2^17 */

{ Mult (s, & L, (long) l < < 17);

n- = 17;

}

if (n> 0) /* умножаем на оставшуюся степень */

Mult (s, & L, (long) l < < n);

f = fopen (“output.txt”, “wt”);

fprintf (f, “%d”, s[L]);

for (i=L-l; i> =l; i--)

{ k=1000;

while (s [i]< k) /*недостающие цифры заменим 0*/

{ fprintf (f, “%c”, ‘0’);

k/=10;

}

fprintf (f, “%d”, s[i]);

}

fclose (f);

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какой объем памяти в байтах будет занимать текст данного вопроса?

2. В графическом режиме на экране дисплея пиксель можно отображать одним из 1024 цветов. Сколько бит требуется для описания цвета каждого пикселя, если разрешение экрана составляет 800*600 пикселей?

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

4. Объясните, как дополнительный код позволяет заменить операцию вычитания операцией сложения.

5. Объясните, что и когда “плавает” в форме представления чисел с плавающей запятой?

6. Перечислите ошибки, возникающие при работе с вещественными числами в конечном числе разрядов.

7. От чего зависят границы диапазона чисел, представимых в том или ином целом типе?

8. Какие ошибки возникают при сложении чисел в ограниченном числе разрядов? Как можно их избежать?

9. Может ли результат умножения двух положительных чисел, представимых в знаковом типе данных, оказаться отрицательным?

10. Назовите области применения битовых операций.

11. Каковы преимущества компьютерного представления чисел с плавающей запятой по сравнению с фиксированной?

12. Почему современные языки программирования поддерживают одновременно несколько вещественных типов данных?

13. Для чего применяется сдвиг при записи порядка нормализованного числа и что такое машинный нуль?

14. Перечислите и объясните все ошибки, которые могут возникнуть при арифметических операциях с нормализованными числами в ограниченном числе разрядов?

15. Как определить, достаточно ли для точного решения задачи стандартных компьютерных типов данных, или вычисления придется организовывать самому, с помощью алгоритмов “длинной” арифметики?

16. Назовите преимущества и недостатки различных способов представления ”длинных“ чисел.

УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ

Основная литература

1. Аляев Ю.А., Кушев В.О., Лебедев В.В. Прикладное программирование: Учеб. метод. пособие для самостоятельной работы: В 2ч. Ч.1: Алгоритмизация и программирование. – Пермь: Высш.шк., 2007.– 235 с.

2. Баула В.Г., Васюкова Н.Д., Тюляева В.В., Уманец П.В. Основы программирования и алгоритмические языки. – М.: Энергоатомиздат, 2007.– 400 с.

3. Гусева А.И. Учитесь программировать: Pascal 7.0: Задачи методы их решения. – М.: Диалог-МИФИ, 2007. – 256 с.

4. Епанешников А., Епанешников В. Программирование в среде Turbo-Pascal 7.0. – М.: Диалог-МИФИ, 2009. – 288 с.

5. Иванов А.Г. Язык программирования Си: Предварительное описание. // Прикл. информатика. – 2008. – Вып. 1. – С. 68 – 113.

6. Керниган Б., Ритчи Д., Фьюэр А. Язык программирования Си: Задачи по языку Си: Пер. с англ. – М.: Финансы и статистика, 2007. – 279с.

7. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 2009.– 216 с.

8. Хопкрофт Д., Ахо А., Ульман Д. Структуры данных и алгоритмы. – М.: Вильямс, 2009. – 384с.

9. Вирт Н. Алгоритмы и структуры данных. – СПб: Невский диалект, 2011. – 272с.

Дополнительная литература

1. Мейер Б., Бодуэн К. Методы программирования: В 2 т. Пер./ с

фр.Ю.А. Первина; Под ред. А.П. Ершова. – М: Мир, 2002.– 336 с.: ил.

2. Нортон П., Уилтон Р. IBM PC и PS/2: Руководство по

программированию: Пер. с англ. – М: Радио и связь, 1994. – 336 с.: ил.

3. Проценко В.С., Чаленко П.И., Сорока Р.А. Техника программирования: Учеб. пособие. – Киев: Выща шк., 2000. – 183 с.: ил.

4. Касаткин Н.В. Информация. Алгоритмы. ЭВМ. – М.: Просвещение, 1991.– 225 с.

5. Фомин С.В. Системы счисления. – М.: Наука, 2007.– 247 с.

6. Фаронов В.В. Турбо-Паскаль: Практика программирования. – М.: Учеб. инж. центр “ МВТУ-ФЕСТО-ДИДАКТИК”, 2003. – 256 с.

7. Хенкок Л., Кригер М. Введение в программирование на языке Си: Пер.с англ. – М.: Радио и связь, 2006. – 192с.

Задания и методические указанияк выполнению

курсовой работы по дисциплине

«Языки и системы программирования»

Подписано в печать _________. Формат 60´ 84/16. Бумага для множ. аппаратов.

Печать плоская. Усл. печ. л. ___. Уч.-изд. л.____. Тираж ____ экз. Заказ № ____.

ФГАОУ ВПО «Российский государственный профессионально-педагогический университет». Екатеринбург, ул. Машиностроителей, 11.

Ризограф ФГАОУ ВПО РГППУ. Екатеринбург, ул. Машиностроителей, 11.