То же замечание касается и возведения тройки в целую степень. Заметим, что при 1 < k £ 100 log2k принимает значения от 1 до 6. Следовательно, сто обыкновенных дробей, которые требуется сложить, имеют всего 6 различных знаменателей: 3, 32, 33, … 36,причем наименьшим общим знаменателем этих дробей является 36 (это число “короткое”). Поэтому несложно привести все 100 дробей к общему знаменателю и, используя лишь целочисленную арифметику, получить значение числителя и знаменателя результирующей дроби. Для перехода от обыкновенной дроби к десятичной можно воспользоваться алгоритмом деления “короткого” числа на “короткое” и определить точное значение искомой суммы.
ПРИМЕР РЕШЕНИЯ И КОММЕНТАРИИ
Задание. По введенному натуральному числу n < 30000 найти значение выражения 2n.
Известно, что существует эффективный по количеству выполняемых действий умножения алгоритм возведения произвольного числа в натуральную степень. Однако при его реализации для больших значений степени n придется выполнять операцию умножения “длинного” числа на “длинное”, которая требует порядка L2 умножений, где L – количество цифр в каждом из “длинных” множителей.
Второй возможный подход к решению данной задачи – это перевод двоичного числа, состоящего из одной единицы и n нулей (а именно так в двоичной системе выглядит 2n), в десятичную систему счисления методом деления в двоичной системе на 10 = 10102. Но деление в двоичной системе придется организовывать самостоятельно (аналогично алгоритму деления “длинного” числа на “короткое”).
Наиболее простым с точки зрения понимания и отладки программы является алгоритм простого последовательного умножения на некоторую степень двойки, являющуюся “коротким” числом.
Приведем такое решение задачи: умножение производится, пока это возможно, на 217 (произведение 217 на максимальную цифру 10000-й системы счисления – 9999, еще меньше, чем максимальное число, представимое в целом типе). Затем результат домножается на оставшееся 2k, где 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. Бумага для множ. аппаратов.
Печать плоская. Усл. печ. л. ___. Уч.-изд. л.____. Тираж ____ экз. Заказ № ____.
ФГАОУ ВПО «Российский государственный профессионально-педагогический университет». Екатеринбург, .
Ризограф ФГАОУ ВПО РГППУ. Екатеринбург, .
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
