Числа
<<  Алгебраические выражения Числовые ряды  >>
Тема 5. Числовые функции
Тема 5. Числовые функции
5.1. Работа с целыми числами
5.1. Работа с целыми числами
При работе с целыми числами достаточно распространенной операцией
При работе с целыми числами достаточно распространенной операцией
Определение остатка от деления может потребоваться в таких задачах,
Определение остатка от деления может потребоваться в таких задачах,
Отметим, что в языке Haskell имеется еще одна функция для нахождения
Отметим, что в языке Haskell имеется еще одна функция для нахождения
При таком определении остаток любого целого числа, найденный при
При таком определении остаток любого целого числа, найденный при
Получение списка простых чисел
Получение списка простых чисел
Получение списка простых чисел
Получение списка простых чисел
Получение списка простых чисел
Получение списка простых чисел
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Определение дня недели
Стратегии разработки программ
Стратегии разработки программ
Стратегии разработки программ
Стратегии разработки программ
5.2. Численные вычисления
5.2. Численные вычисления
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Численное дифференцирование
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Вычисление квадратного корня
Нули функции
Нули функции
Нули функции
Нули функции
Нули функции
Нули функции
Нули функции
Нули функции
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция
Обратная функция

Презентация: «Тема 5. Числовые функции». Автор: . Файл: «Тема 5. Числовые функции.ppt». Размер zip-архива: 230 КБ.

Тема 5. Числовые функции

содержание презентации «Тема 5. Числовые функции.ppt»
СлайдТекст
1 Тема 5. Числовые функции

Тема 5. Числовые функции

1

2 5.1. Работа с целыми числами

5.1. Работа с целыми числами

2

3 При работе с целыми числами достаточно распространенной операцией

При работе с целыми числами достаточно распространенной операцией

является нахождение остатка (remainder) от деления нацело одного числа на другое. Так при делении нацело числа 10 на число 3 остаток равен 1. В преамбуле определена функция rem, предназначенная для нахождения остатка: ---> 345 ‘rem‘ 12 9

3

4 Определение остатка от деления может потребоваться в таких задачах,

Определение остатка от деления может потребоваться в таких задачах,

как вычисление различных временных характеристик: например, если сейчас 9 часов, то через 33 часа текущее время будет равно (9+35) ‘rem‘ 24 = 20 часов; определение имени дня недели: закодируем дни (0 воскресенье, 1 понедельник, ..., 6 суббота), если сегодня среда (день с номером 3), то через 30 дней будет пятница (33 ‘rem‘ 7 = 5); выяснение возможности разделить нацело одно число на другое: число будет делиться на число п, если остаток от деления этого числа на n равен нулю; определение количества цифр в десятичной записи числа: последняя цифра числа х находится по формуле х ‘rem‘ 10, следующая цифра равна (х/10) ‘rem‘ 10, третья (х/100) ‘rem‘ 10 и так далее.

4

5 Отметим, что в языке Haskell имеется еще одна функция для нахождения

Отметим, что в языке Haskell имеется еще одна функция для нахождения

остатка числа – это функция mod. Результаты функций rem и mod совпадают при нахождении остатков от положительных чисел, но различаются для отрицательных чисел. Функция mod для любого числа (как положительного, так и отрицательного) находит остаток в соответствии со следующим математическим определением остатка: Для любого целого числа m и положительного целого n существуют и при том единственные q и r, такие что m = q ? n + r, где остаток r удовлетворяет условию 0<r<п. Другими словами, (m ‘div‘ n)*n + m ‘mod‘ n тождественно равно m.

5

6 При таком определении остаток любого целого числа, найденный при

При таком определении остаток любого целого числа, найденный при

помощи функции mod есть число неотрицательное, в отличии от функции rem, которая оперирует положительными числами, а лишь затем учитывает знак. ---> 34 ‘rem‘ 10 4 ---> 34 ‘mod‘ 10 4 ---> (-34) ‘rem‘ 10 -4 ---> (-34) ‘mod‘ 10 6 Рассмотрим еще две задачи, связанные с обработкой целых чисел. В обеих задачах используется функция rem.

6

7 Получение списка простых чисел

Получение списка простых чисел

Говорят, что целое число m делится на целое n, если остаток от деления m на n равен нулю. Функция divisible проверяет делится ли одно число на другое: divisible :: Int -> Int -> Bool divisible m n = m ‘rem‘ n == 0

7

8 Получение списка простых чисел

Получение списка простых чисел

Делителями числа называют такие целые числа, на которые исходное число делится без остатка. Функция denominators определяет список всех делителей заданного числа: denominators :: Int -> [Int] denominators x = filter (divisible x) [1..x] Заметим, что здесь функция divisible частично параметризована переменной х; функция filter «отфильтровывает» из списка целых чисел от 1 до х только те, которые являются делителями числа х.

8

9 Получение списка простых чисел

Получение списка простых чисел

Целое число называется простым, если оно имеет ровно два делителя: единицу и само себя. Функция prime проверяет, действительно ли в списке делителей находятся только эти два числа: prime :: Int -> Bool prime x = denominators x == [1, x] И наконец, функция primes находит все простые числа, не превышающие данное: primes :: Int -> [Int] primes x = filter prime [1..x] И хотя этот способ вычисления списка простых чисел, не превышающих данное, не является наиболее эффективным, он имеет неоспоримое преимущество – все функции в нем являются простым переложением математических определений на язык Haskell.

9

10 Определение дня недели

Определение дня недели

Каким днем недели будет последний день текущего года? А в какой день недели вы родились? Для ответа на подобные вопросы определим функцию day, которая по заданному дню месяца, месяцу и году будет выдавать день недели, на который он приходится. ---> day 31 12 2002 "Tuesday"

10

11 Определение дня недели

Определение дня недели

Если уже известен номер дня недели, то, основываясь на предложенной выше схеме кодирования, функцию day легко написать: day d m y = weekday (daynumber d m y) weekday 0 = "Sunday" -- Воскресенье weekday 1 = "Monday" -- Понедельник weekday 2 = "Tuesday" -- Вторник weekday 3 = "Wednesday" -- Среда weekday 4 = "Thursday" -- Четверг weekday 5 = "Friday" -- Пятница weekday 6 = "Saturday" -- Суббота Функция weekday использует семь шаблонов для определения наименования дня недели (результатом является строка, заключенная в кавычки).

11

12 Определение дня недели

Определение дня недели

Функция daynumber: определяет число дней, прошедших с последнего воскресенья, и добавляет к нему: число целых лет, умноженное на 365; поправку на число прошедших високосных годов; число дней во всех уже полностью прошедших в текущем году месяцев; число дней, прошедших с начала месяца; pатем находится остаток от деления на 7 полученного (огромного) числа – это и будет номер дня недели.

12

13 Определение дня недели

Определение дня недели

В нашем (григорианском) календаре, введенном папой Григорием в 1752 году, действуют следующие правила определения високосных годов (длина которых 366 дней): если номер года делится на 4, то год является високосным (например, 1972); но: если номер года делится на 100, то год не високосный (например, 1900); но: если номер года делится на 400, то год является високосным (например, 2000).

13

14 Определение дня недели

Определение дня недели

Теперь, зная, что 1 января 0 года было воскресеньем, легко полностью определить функцию daynumber: daynumber d m y = ((y-l)*365 + (y-1) ‘div‘ 4 - (y-1) ‘div‘ 100 + (y-1) ‘div‘ 400 + sum (take (m-1) (months y)) + d ) ‘rem‘ 7 Вызов take n xs возвращает первые n элементов списка xs. Эта функция может быть определена, например, так (данное определение немного отличается от приведенного в преамбуле): take 0 xs = [] take (n+1) (x:xs) = x : take n xs

14

15 Определение дня недели

Определение дня недели

Функция months возвращает число дней в каждом из месяцев заданного года: months y=[31,feb,31,30,31,30,31,31,30,31,30,31] where feb | leap y =29 | otherwise = 28 Функция leap используется в охранном выражении предыдущей функции: leap y = divisible y 4 && (not (divisible y 100)) || divisible y 400 Ее же можно определить и по-другому: leap y | divisible y 100 = divisible y 400 |otherwise = divisible y 4

15

16 Определение дня недели

Определение дня недели

Для того чтобы сделать полностью корректным определение функции day, добавим охранное выражение, не позволяющее применить эту функцию к периоду до введения григорианского календаря: day d m y | y > 1752 = weekday (daynumber d m y) Теперь вызов этой функции с последним параметром, меньшим чем 1752, приведет к сообщению об ошибке. ---> day 16 9 2002 "Monday" ---> day 16 9 120 " Program error: Номер года меньше 1752

16

17 Стратегии разработки программ

Стратегии разработки программ

При проектировании программ для этих двух примеров использовались две различные стратегии разработки. Во втором примере сначала определена функция day в терминах функций weekday и daynumber; при разработке функции daynumber использована функция months, которая в свою очередь использовала функцию leap. Такая стратегия носит название «сверху вниз»: начинается разработка с наиболее важных вещей и, затем, по мере надобности, определяются дополнительные функции.

17

18 Стратегии разработки программ

Стратегии разработки программ

В первом же примере применена стратегия «снизу вверх»: сначала была написана функция divisible, с ее помощью определили функцию denominators, затем функцию prime и, наконец, primes. Применение той или иной стратегии никак не сказывается на окончательном результате: ведь интерпретатор ничего не знает о том, в каком порядке разрабатывались функции. Тем не менее, при разработке программ следует обращать внимание на то, какой из стилей используется.

18

19 5.2. Численные вычисления

5.2. Численные вычисления

19

20 Численное дифференцирование

Численное дифференцирование

При вычислениях, в которых участвуют числа типа Float, точное нахождение результата в большинстве случаев невозможно. Результат вычисления округляется с точностью до нескольких десятичных цифр после запятой. ---> 10.0/6.0 1.66667 При вычислении некоторых математических функций, таких как sqrt, результат также округляется. Поэтому и при разработке своих собственных функций, оперирующих числами типа Float, полученный результат также будет являться апроксимацией «реального» значения.

20

21 Численное дифференцирование

Численное дифференцирование

Примером этого может служить вычисление производной той или иной математической функции. Математическое определение производной f’ от функции f таково: Точное значение предела не может быть вычислено на компьютере. Однако, приближенное значение может получено с использованием достаточно малых значений h.

21

22 Численное дифференцирование

Численное дифференцирование

Операция дифференцирования есть функция высшего порядка: функция берется в качестве аргумента и функция является результатом вычисления. Определение может быть таким: diff :: (Float->Float) -> (Float->Float) diff f = f' where f' x = (f (x+h) - f x) / h h =0.001 С целью получения карринговой формы функции можно убрать вторую пару скобок в объявлении типа, так как -> ассоциативна справа. diff :: (Float->Float) -> Float -> Float

22

23 Численное дифференцирование

Численное дифференцирование

Теперь функцию diff можно считать функцией от двух параметров: (1) функции, производную которой следует вычислить, и (2) точки, в которой значение производной должно быть подсчитано. С этой точки зрения определение теперь выглядит так: diff f = (f (x + h) - f x) / h where h = 0.001 Эти два определения абсолютно эквивалентны. Вторая версия программы предпочтительнее, так как она проще и яснее (в ней отсутствует необходимость ввода дополнительной функции f'. С другой стороны, первое определение подчеркивает, что diff может быть рассмотрена, как преобразование функции.

23

24 Численное дифференцирование

Численное дифференцирование

Функцию diff очень удобно использовать после частичной параметризации, как в следующем определении: derivative_of_sine_square = diff (square . sin) Величина h в обоих определениях diff задается в предложении where. Тем не менее, легко переделать программу таким образом, чтобы ее можно было бы в будущем легко изменять. Наиболее гибкий путь – это задать h в качестве параметра diff: flexDiff h f x = (f (x+h) - f x) / h Задав h в качестве первого аргумента функции flexDiff, можно использовать и ее в частично параметризованной форме, чтобы получить различные версии diff: roughDiff = flexDiff 0.01 fineDiff = flexDiff 0.0001 superDiff = flexDiff 0.000001

24

25 Вычисление квадратного корня

Вычисление квадратного корня

В прелюдии определена функция sqrt для вычисления квадратного корня из числа. В этом разделе будет рассмотрен процесс разработки определения функции sqrt, в котором не будет использоваться стандартная функция, предназначенная для этих целей. Этот пример позволит продемонстрировать технику работы с числами типа Float. В следующих разделах будет рассмотрен процесс вычисления обратной функции, что позволит дать другую реализацию функции вычисления квадратного корня.

25

26 Вычисление квадратного корня

Вычисление квадратного корня

Для квадратного корня из числа х имеет место следующее утверждение: если y есть хорошее приближение для , то является еще лучшим приближением.

26

27 Вычисление квадратного корня

Вычисление квадратного корня

Это свойство может быть использовано для вычисления корня из числа х: возьмем 1 в качестве первого приближения и будем подправлять приближение до тех пор, пока результат нас не устроит. Величина y является хорошим приближением , если y2 не очень отличается от х. Для величины приближения y0, y1 и т.д. таковы: y0 =1 y1 = 0.5 * (y0 + 3/y0) = 2 y2 = 0.5* (y1 + 3/y1) = 1.75 y3 = 0.5 * (y2 + 3/y2) = 1.732142857 y4 = 0.5 * (y3 + 3/y3) = 1.732050810 y5 = 0.5 * (y4 + 3/y4) = 1.732050807 Квадрат последней аппроксимации только на 10-18 отличается от трех.

27

28 Вычисление квадратного корня

Вычисление квадратного корня

Для процесса «подправки» начального значения удобно использовать введенную ранее функцию until: root х = until goodEnough improve 1.0 where improve y = 0.5*(y + x/y) goodEnough y = y*y ~= x Оператор ~= (приблизительно равно), может быть определен следующим образом: infix 5 ~= a ~= b = a-b<h && b-a<h where h = 0.000001 В этом определении функция высшего порядка until оперирует функциями improve (улучшать) и goodEnough (достаточно хорошо), используя начальное значение 1.0.

28

29 Вычисление квадратного корня

Вычисление квадратного корня

Хотя в записи функции root сразу за improve располагается 1.0, функция improve не применяется непосредственно к числу 1.0; вместо этого оба эти объекта передаются функции until. С точки зрения процесса карринга, это эквивалентно следующей расстановке скобок (((until goodEnough) improve) 1.0). Только заглянув в определении функции until можно увидеть, как improve применяется к 1.0.

29

30 Нули функции

Нули функции

Другой вычислительной проблемой, которая может быть решена с помощью итерации, является нахождение нулей функции. Рассмотрим функцию f, корень x0 которой требуется найти. Возьмем b в качестве первого приближения для нуля функции. Тогда касательная, проведенная к функции f в точке b пересекает ось х в точке, являющейся лучшим приближением нуля, чем b (см. рисунок). Приближение методом Ньютона

30

31 Нули функции

Нули функции

Точка пересечения касательной с осью х находится на расстоянии d от первого приближения b. Величина d может быть вычислена следующим образом. Тангенс угла наклона касательной к функции f в точке b равен f'(b). С другой стороны, это значение равно f(b)/d, поэтому d=f(b)/f'(b).

31

32 Нули функции

Нули функции

Данное замечание позволяет нам сделать следующий вывод: если b есть первое приближение нуля функции f, то b–f(b)/f'(b) есть лучшее приближение. Этот метод известен, как «метод Ньютона». Этот метод не всегда работает для функций с локальными экстремумами: вы можете «ходить вокруг» нужного корня и никогда в него не попасть.

32

33 Нули функции

Нули функции

Для получения функции, вычисляющей нули этим методом также можно использовать функцию until. В качестве параметра будем использовать приближение (improve), задаваемое приведенной выше формулой (для чего воспользуемся ранее определенной функцией diff). Условием окончания итераций будет служить достаточно малое отклонение функции от нулевого значения. zero f = until goodEnough improve 1.0 where improve b = b - f b / diff f b goodEnough b = f b ~= 0.0 Мы выбрали 1.0 в качестве первого приближения, но с таким же успехом, это могло быть и число 17.93. Вообще, это может быть любая точка из области определения функции f.

33

34 Обратная функция

Обратная функция

Ноль функции f, где f(x)=x2–а, равен . С учетом этого замечания мы можем вычислить как ноль функции f . Применив функцию zero, root можно определить так: root a = zero f where f x = x*x - a Кубический корень можно вычислить так: cubic a = zero f where f x = x*x*x - a Аналогично, любая функция, обратная к заданной, может быть вычислена с использованием этой функции в определении функции f, например, arcsin a = zero f where f x = sin x - a arccos a = zero f where f x = cos x - a

34

35 Обратная функция

Обратная функция

Наличие общности в определениях этих функций является сигналом для определения функции высшего порядка, которая обобщает эти случаи (по аналогии с определением функции foldr, которая появилась как обобщение sum, product и and). В данном случае функция inverse является функцией высшего порядка, имеющей дополнительный параметр – функцию g, инверсию которой требуется вычислить: inverse g a = zero f where f x = g x - a

35

36 Обратная функция

Обратная функция

Если вы случайно заметили некую закономерность, то следует попытаться определить функцию высшего порядка так, чтобы другие функции стали просто частными случаями ее применения. При этом все частные случаи следует определить через полученную функцию, которая будет частично параметризована различными параметрами: arcsin = inverse sin arccos = inverse cos ln = inverse exp

36

37 Обратная функция

Обратная функция

Функцию inverse можно рассматривать как функцию с двумя параметрами (функция и Float) и Float в качестве результата, или как функцию с одним параметром (функция) и функцией как результатом. Это следует из эквивалентности следующих объявлений типа функции inverse: inverse :: (Float->Float)->Float->Float и inverse :: (Float->Float)->Float->Float (вспомним о правой ассоциативности ->).

37

38 Обратная функция

Обратная функция

Функция нахождения корня, использующая метод Ньютона, может быть получена подобным путем. Рассмотрим определение функции root: root a = zero f where f x = x*x - a Заменив вызов функции zero f его определением, получим: root a = until goodEnough improve 1.0 where improve b = b - f b / diff f b goodEnough b = f b ~= 0.0 f x = x*x - a

38

39 Обратная функция

Обратная функция

В данном случае нет необходимости определять dif f численно: производная f есть функция (2*), поэтому формула в функции improve b может быть упрощена: Это и есть формула, использованная нами еще на слайде 26.

39

«Тема 5. Числовые функции»
http://900igr.net/prezentacija/algebra/tema-5.-chislovye-funktsii-138699.html
cсылка на страницу
Урок

Алгебра

35 тем
Слайды
900igr.net > Презентации по алгебре > Числа > Тема 5. Числовые функции