Анализ алгоритмов решения математических задач (Работа с числами разных форматов) презентация

Соответствие между геометрическими фигурами
алгоритмов и конструкциями языка
программирования. Реализация на Паскале. Название. Изображение
Начало алгоритма/
Конец алгоритма
Название
алгоритма
Следование
X:=abc;
S
S
Это любое действие , изменяющее значение
входных данных
S – Это оператор

Реализация на Паскале. Название. Изображение .
if P then S1 else S2; Развилка (полная)
( Направления только два!)
if P then S; Развилка( неполная)
<условие>
S1
S2
Условие определяет
направление движения
по алгоритму
S
<условие>
true
true
False
False

Реализация на Паскале Название Изображение .
Цикл «Пока»:
Цикл « До»
P
S
true
While P do S – Исполняется одно действие
While P do
Begin
S1; Операторы работают в цикле
S2 ; любое число раз
…………………..
End; // Замечание об операторных
скобках
Repeat
S; Любое число операторов
Until P; в этом цикле
S
P
False
True
Циклы
Составной оператор

Реализация на Паскале. Название. Изображение
Цикл с параметром
For i:=1 to n do S;
Шаг действий равен +1
For i:=n downto 1 do s;
Шаг действий равен -1
Этот оператор является
дополнением оператора While
при известном количестве
повторений цикла.
i=1 до n
{ Шаг 1}
S
Цикл
Выход
из цикла
Вход
В цикл
Войти в цикл можно только через его начало

Реализация на Паскале. Название Изображение
Case k of
k1:S1; k2:S2;
…….
kN: SN;
Else
SX;
End;
Вход
K
S1
S2
SN
SX
k1
k2
kN
Не найдено
Значение K
Это расширение выбора направления
решения при множестве значений выбора
….
Структура «Выбор»

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

Оценка времени работы алгоритмов
Для перемножения двух β - битовых чисел обычным методом потребуется количество битовых операций ~ θ (β2)
Размер входных данных определяется не количеством данных,
а количеством битов для их записи.
Задача разработчика : создать такой алгоритм,
который бы выполнял арифметические операции за
наименьшее время.
Наиболее значимые алгоритмы: Поиск простых и
составных чисел, поиск общих делителей и наибольших
общих делителей, разложение числа на множители,
кодирование и декодирование чисел, генерация случайных
чисел.
Для обработки целых чисел надо всегда помнить о
представлении целого числа в позиционной системе счисления:
где ai – цифры системы счисления
n –количество цифр в записи числа

Решение_задачи_о сумме_цифр.doc
Сумма
младших
цифр
целого числа
Возможная декомпозиция
алгоритма
Подготовка
цикла

Вычисление рядов
Для вычисления рядов основным методом является
математическая индукция:
Сумма всех к от 1 до n равна
Мы показали, что формула оценки суммы верна как
для n слагаемых, так и для (n+1) слагаемого
Метод индукции справедлив не только для вычисления значений сумм с заданной точностью, но и для оценки возможных границ результатов вычислений рядов.
S=1/2*n*(n+1)+(n+1)=(n*(n+1)+2*(n+1))/2=(n+1)*(n+2)/2