Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






    Задание. По введенному натуральному числу 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. Бумага для множ. аппаратов.

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

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

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






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.