Уроки 64 - 65
Длинные числа
(§38. Целочисленные алгоритмы)
Содержание урока
Задачи
Задачи
1. Докажите, что если у числа k нет ни одного делителя в диапазоне от 2 до √k, то оно простое.
Напишите две программы, которые находят все простые числа от 2 до N двумя разными способами:
а) проверкой каждого числа из этого интервала на простоту;
б) используя решето Эратосфена.
Сравните число шагов цикла (время работы) этих программ для разных значений N. Постройте для каждого варианта зависимость количества шагов от N, сделайте выводы о сложности алгоритмов.
3. Докажите, что в приведённой в параграфе программе вычисления 100! не будет переполнения при использовании 32-битных целых переменных.
4. Можно ли в программе вычисления 100! в одной ячейке массива хранить 9 цифр «длинного» числа?
5. Без использования программы определите, сколько нулей стоит в конце числа 100!
6. Соберите всю программу и вычислите 100!. Сколько цифр входит в это число?
7. Оформите вывод «длинного» числа на экран в виде отдельной процедуры. Учтите, что число может быть нулевым.
*8. Придумайте другой способ вывода «длинного» числа, использующий символьные строки.
9. Напишите процедуру для ввода «длинных» чисел из файла.
10. Напишите процедуры для сложения и вычитания длинных чисел.
*11. Напишите процедуры для умножения и деления «длинных» чисел.
*12. Напишите процедуру для извлечения квадратного корня из «длинного» числа.
Следующая страница 
§38. Целочисленные алгоритмы
Cкачать материалы урока
