Программирование на Фортране

Размещено на http://www.allbest.ru/

Программирование на Фортране

1. Нахождение синуса через разложение в ряд

Понятие ряда. Разложение в ряд.

Рядом называется выражение вида

a₁ + a₂ + a₃ +…, (1)

в котором a₁, a₂, a₃,…, a_n,… (члены ряда) суть определенные числа, закон построения которых известен.

Иногда ряд (1) записывают в форме

(2)

Самой важной стороной дела при образовании выражения вида (1) является то многоточие, которое поставлено в конце этого выражения. Оно показывает, что множество чисел a_k, участвующих в определении ряда (1), обязательно бесконечно. Таким образом, с чисто формальной точки зрения, ряды - это суммы, содержащие бесконечное число слагаемых.

Первый вопрос, возникающий при рассмотрении подобных выражений, заключается в том, имеют ли они какое-либо числовое значение. Оказывается, что приписать разумным образом такое значение удается далеко не всем, а лишь так называемым сходящимся рядам (в более высоких частях теории оказывается возможным и некоторым расходящимся рядам придавать числовое значение).

Пусть дан ряд (1). Образуем последовательность чисел S₁, S₂, S₃,…, полагая

S_n = a₁ + a₂ +… + a_n (n = 1, 2, 3,…).

Эти числа называются частичными суммами ряда (1).

Если существует конечный предел

(3)

то говорят, что ряд (1) сходится, а предел (3) называется его суммой. Если же предела (3) не существует или он бесконечен, то ряд (1) называется расходящимся.

Таким образом, сумма ряда - это (конечный) предел последовательности его частичных сумм.

Если ряд (1) имеет сумму S, то пишут

S = a₁ + a₂ + a₃ +…,

 

Если же ряд расходится, то ему не приписывают никакого числового значения (в более высоких частях теории оказывается возможным и некоторым расходящимся рядам придавать числовое значение).

Ряд Темйлора - разложение функции в бесконечную сумму степенных функций.

Ряд назван в честь английского математика Брука Тейлора, хотя ряд Тейлора был известен задолго до публикаций Тейлора - его использовали ещё в XVII веке Грегори, а также Ньютон.

Ряды Тейлора применяются при аппроксимации функции многочленами. В частности, линеаризация уравнений происходит путём разложения в ряд Тейлора и отсечения всех членов выше первого порядка.

Определение

Пусть функция f(x) бесконечно дифференцируема в некоторой окрестности точки a. Формальный ряд



называется рядом Тейлора функции f в точке a.

Связанные определения

· В случае, если a = 0, этот ряд также называется рядом Макломрена.

Свойства

· Если f есть аналитическая функция, то её ряд Тейлора в любой точке a области определения f сходится к f в некоторой окрестности a.

· Существуют бесконечно дифференцируемые функции, ряд Тейлора которых сходится, но при этом отличается от функции в любой окрестности a. Например, Коши предложил такой пример:

Формула Тейлора

Формула Тейлора используется при доказательстве большого числа теорем в дифференциальном исчислении. Говоря нестрого, формула Тейлора показывает поведение функции в окрестности некоторой точки.

Теорема:

· Пусть функция f(x) имеет n + 1 производную в некоторой окрестности точки a, U (a, е) · Пусть · Пусть p - произвольное положительное число, тогда: точка при x < a или при x > a:

Это формула Тейлора с остаточным членом в общей форме (форма Шлёмильха - Роша).

Различные формы остаточного члена

В форме Лагранжа:

В форме Коши:

Ослабим предположения:

· Пусть функция f(x) имеет n ? 1 производную в некоторой окрестности точки a

· И n производную в самой точке a, тогда:

 - остаточный член в асимптотической форме (в форме Пеано, в локальной форме)

Ряды Маклорена некоторых функций

для всех

Квадратный корень:

для всех

для всех | x | < 1

Конечный геометрический ряд:

для всех

Тригонометрические функции:

для всех

Гиперболические функции:

для всех

для всех

для всех

Алгоритм программы

Шаг1 Для решения поставленной задачи используем формулу Тайлера:

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

2. Текст программы

PROGRAM razlozhenie

IMPLICIT NONE

REAL (8): e, f, m, snx, n, x, snx_old

INTEGER (8): i, z, l

PRINT *, ' Vvedite zna4enie ugla v radianah'

READ *, x

WRITE (*,*)'To4nost ravna 1E-06'

e = 0.000000

snx = 0

DO i = 0, 500

f = 1

DO z=1, 2*i+1

f = f * z

END DO

l = (-1)**i

m = x**(2*i+1)

n = (l*m) / f

snx_old = snx

snx = snx + n

WRITE (*,*) (n)

IF ((ABS (snx_old - snx)).LT.) GO TO 1

CYCLE

END DO

1 WRITE (*,*) 'sinus ugla x =', snx

END PROGRAM

3. Сравнение взаимно простых чисел

Понятие о простых и взаимно простых числах

Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1. Примеры: 14 и 25 взаимно просты, а 15 и 25 не взаимно просты (у них имеется общий делитель 5).

Наглядное представление: если на плоскости построить «лес», установив на точки с целыми координатами «деревья» нулевой толщины, то из начала координат видны только деревья, координаты которых взаимно просты.

Связанные определения

• Если в наборе чисел любые два взаимно просты, то такие числа называются попарно взаимно простыми. Для двух чисел понятия «взаимно простые» и «попарно взаимно простые» совпадают.

Примеры

• 8, 15 - не простые, но взаимно простые.

• 6, 8, 9 - взаимно простые числа, но не попарно взаимно просты.

• 8, 15, 49 - попарно взаимно простые.

Свойства

• Числа a и b взаимно просты тогда и только тогда, когда их наибольший общий делитель равен единице, или, иными словами, если существуют целые x и y такие, что (см. соотношение Безу).

• Любые два простых числа взаимно просты.

• Если a - делитель bc, и a взаимно просто с b, то a - делитель c.

• Если числа a1,…, an - попарно взаимно простые числа, то НОК (a1,…, an) = |a1·…·an|.

Обобщения

Понятия простого числа и взаимно простых чисел естественно обобщаются на произвольные коммутативные кольца, например, на кольцо многочленов или гауссовы целые числа. Обобщением понятия простого числа является «неприводимый элемент». Два элемента кольца называются взаимно простыми, если они не имеют никаких общих делителей, кроме делителей единицы. При этом аналог основной теоремы арифметики выполняется не во всех, а только в факториальных кольцах.

Нахождение НОД

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Пример: для чисел 70 и 105 наибольший общий делитель равен 35.

Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.

Способы вычисления

Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.

Кроме того, значение НОД (m, n) можно легко вычислить, если известно каноническое разложение чисел m, n на простые множители:

где - различные простые числа, а и - неотрицательные целые числа (они могут быть нулями, если соответствующее простое отсутствует в разложении). Тогда НОД (m, n) и НОК (m, n) выражаются формулами:

Если чисел более двух: , их НОД находится по следующему алгоритму:

d2 = (a1, a2)

d3 = (d2, a3)

………

dn = (dn ? 1, an) - это и есть искомый НОД.

Для решения моей задачи я воспользовалась методом Евклида, который сводится к следующему.

Алгоритм Евклида для целых чисел

Пусть a и b - целые числа, не равные одновременно нулю, и последовательность чисел

определена тем, что каждое rk - это остаток от деления предыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть

a = bq0 + r1

b = r1q1 + r2

r1 = r2q2 + r3

rk ? 2 = rk ? 1qk ? 1 + rk

rn ? 1 = rnqn

Тогда НОД (a, b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности.

Существование таких r1, r2,…, то есть возможность деления с остатком m на n для любого целого m и целого , доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений:

• Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).

Проще сформулировать алгоритм Евклида так: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.

Пример

Для иллюстрации, алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала, от 1071 отнимем кратное значение 462, пока не получим знаменатель меньше чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147

1071 = 2 Ч 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим знаменатель меньше чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21.

462 = 3 Ч 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим знаменатель меньше чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка.

147 = 7 Ч 21 + 0.

Так как последний остаток равен нулю, алгоритм заканчивается и gcd (1071, 462)=21.

Алгоритм программы

Шаг 1. Для нахождения 2х взаимно простых чисел воспользуемся 1 свойством простых чисел, а именно: числа a и b взаимно просты тогда и только тогда, когда их наибольший общий делитель (НОД) равен единице.

Шаг 2. Для решения поставленной задачи мы воспользуемся более простой формулировкой алгоритма Евклида, состоящей в следующем: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД. Найдем НОД для пары заданных чисел.

Шаг 3. Сравниванием полученные значения НОД между собой. Если они равны между собой и при этом равны 1, заданные числа взаимно простые.

Шаг4. Если числа являются взаимно простыми, то сравниваем их между собой.

Текст программы

PROGRAM MAIN

REAL a, b, c, d

WRITE(*,*) 'Vvedite 1oe 4islo'

READ (*,*) a

WRITE (*,*) 'Vvedite 2oe 4islo'

READ (*,*) b

c = a

d = b

DO WHILE (b.NE.a)

IF (b.GT.a) b = b - a

IF (b.LT.a) a = a - b

END DO

IF ((a.NE.b).OR. (a.NE.1).OR. (b.NE.1)) THEN

WRITE (*,*) 'Eto ne vzaimnoprostie 4isla'

ELSE

IF ((a.EQ.b).AND. (a.EQ.1)) THEN

WRITE (*,*) 'Eto vzaimnoprostie 4isla'

IF (c.LT.d) WRITE (*,*) '1oe 4islo menshe chem 2oe'

IF (c.GT.d) WRITE (*,*) '1oe 4islo bolshe chem 2oe'

END IF

END IF

END

4. Нахождение простых цифр-близнецов до 1000000

Понятие о простых числах и цифрах - близнецах

Простое число - это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Все остальные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.

Разложение натуральных чисел в произведение простых

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа - элементарные «строительные блоки» натуральных чисел.

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

Алгоритмы поиска и распознавания простых чисел

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина.

Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера - Рабина) и используются для нужд криптографии. Только в 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала - Каяла - Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.

Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).

Бесконечность множества простых чисел

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор.

Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма всех чисел, обратных к простым, расходится.

Известная теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое р(n), растёт как n / ln(n).

Наибольшее известное простое

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа^[1]. Один из рекордов поставил в своё время Эйлер, найдя простое число 2³¹ ? 1 = 2147483647.

Наибольшим известным простым числом по состоянию на февраль 2011 года является 2^43112609 ? 1. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M_43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка - Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел из более чем 100000000 и 1000000000 десятичных цифр EFF назначила денежные призы соответственно в 150000 и 250000 долларов США.

Некоторые свойства

· Если p_i - простое, p_{i + 1} следующее за ним простое число, p_{i + 2} следующее за p_{i + 1} простое число, то для всех простых чисел справедливо 3p_{i + 1} ? p_i > p_{i + 2} (постулат Шкулева).

· Если p - простое, и p делит ab, то p делит a или b. Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется в доказательстве основной теоремы арифметики.

· Кольцо вычетов является полем тогда и только тогда, когда n - простое.

· Характеристика каждого поля - это ноль или простое число.

· Если p - простое, а a - натуральное, то a^p ? a делится на p (малая теорема Ферма).

· Если G - конечная группа с pⁿ элементов, то G содержит элемент порядка p.

· Если G - конечная группа, и pⁿ - максимальная степень p, которая делит | G |, то G имеет подгруппу порядка pⁿ, называемую силовской подгруппой, более того, количество силовских подгрупп равно pk + 1 для некоторого целого k (теоремы Силова).

· Натуральное p > 1 является простым тогда и только тогда, когда (p ? 1)! + 1 делится на p (теорема Вильсона).

· Если n > 1 - натуральное, то существует простое p, такое, что n < p < 2n (постулат Бертрана).

· Ряд чисел, обратных к простым, расходится. Более того, при

разложение ряд программа фортран

· Любая арифметическая прогрессия вида a, a + q, a + 2q, a + 3q,…, где a, q > 1 - целые взаимно-простые числа, содержит бесконечно много простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).

· Всякое простое число, большее 3, представимо в виде 6k + 1 или 6k ? 1, где k - некоторое натуральное число. Отсюда, если разность между последовательными простыми числами одинакова, то она кратна 6.

· Если p > 3 - простое, то p² ? 1 кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3).^[3]

· Теорема Грина-Тао (англ.). Существуют сколь угодно длинные арифметические прогрессии, состоящие из простых чисел.^[4]

· Никакое простое число не может иметь вид n^k ? 1, где n>2, k>1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, бомльшим 2. Из этого следует также, что если простое число имеет вид 2^k ? 1, то k - простое (см. числа Мерсенна).

· Никакое простое число не может иметь вид n^{2k + 1} + 1, где n>1, k>0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, бомльшим 1.

Простые числа-близнецы - пары простых чисел, отличающихся на 2.

Общая информация

Все пары простых-близнецов, кроме (3, 5), имеют вид .

По модулю 30 все пары близнецов, кроме первых двух, имеют вид (11, 13), (17, 19) или (29, 1).

Первые простые числа-близнецы:

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139), (149, 151), (179, 181), (191, 193), (197, 199), (227, 229), (239, 241), (269, 271), (281, 283), (311, 313), (347, 349), (419, 421), (431, 433), (461, 463), (521, 523), (569, 571), (599, 601), (617, 619), (641, 643), (659, 661), (809, 811), (821, 823), (827, 829), (857, 859), (881, 883)

На данный момент, наибольшими известными простыми-близнецами являются числа .

Предполагается, что таких пар бесконечно много, но это не доказано. По гипотезе Харди-Литтлвуда, количество р₂(x) пар простых-близнецов, не превосходящих x, асимптотически приближается к

где C₂ - константа простых-близнецов:

Теорема Бруна

Вигго Брун в 1919 доказал, что и ряд обратных величин сходится

Это означает, что если простых близнецов и бесконечно много, то они все же расположены в натуральном ряду довольно редко.

Значение называется константой Бруна для простых-близнецов.

Впоследствии была доказана сходимость аналогичного ряда для обобщенных простых близнецов.

Самые большие известные простые близнецы

· (100355 цифр)

· (58711 цифр)

· (51780 цифр)

· (51780 цифр)

· (51779 цифр).

Алгоритм программы

Шаг 1. Для нахождения простых чисел воспользуемся свойством простых чисел, согласно которому число a является простым только в том случае, если делится только на себя и на 1.

Шаг 2. Для нахождения цифр - близнецов из простых чисел воспользуемся определением, что простые числа-близнецы - пары простых чисел, отличающихся на 2. Для этого будем проверять разность между двумя последующими числами. Если разность равна двум, значит, цифры являются цифрами-близнецами.

Текст программы

PROGRAM main

IMPLICIT NONE

INTEGER (8), PARAMETER: n = 1000000

INTEGER: i, j

INTEGER (8): z

LOGICAL flag

OPEN (3, FILE='massiv.txt')

OPEN (4, FILE='massiv2.txt')

z = 0

DO i=2, n

flag =.false.

DO j = 2, i-1

IF (MOD (i, j).EQ.0) flag=.TRUE.

END DO

IF (.NOT.flag) THEN

WRITE (3,*) i

WRITE (*,*) i

z = z+1

END IF

CYCLE

END DO

WRITE (*,*) 'vsego prostuh 4isel ', z

WRITE (*,*) ' cifru - bliznecu:'

WRITE (4,*) z, z

CLOSE (3)

CLOSE (4)

CALL daf

END

SUBROUTINE daf

INTEGER, DIMENSION(:), ALLOCATABLE: Ar

INTEGER: k, l, z

OPEN (3, FILE='massiv.txt')

OPEN (4, FILE='massiv2.txt')

READ (4,*) z, k

ALLOCATE (Ar(k))

DO k = 1, z

READ (3,*) l

Ar(k) = l

END DO

DO k = 1, z-1

IF (Ar (k+1) - Ar(k).EQ.2) THEN

PRINT *, Ar(k), Ar (k+1)

WRITE (4,*) Ar(k), Ar (k+1)

END IF

END DO

END SUBROUTINE

Список литературы

1. Немнюгин М.А., Стесик О.Л. Н50 Современный Фортран. Самоучитель. - СПб.: БХВ-Петербург, 2004. - 496 с.

2. Д. Тейнсли Linux и Unix: программирование в shell. Руководство разработчика: Пер. с англ. - К.: Издательская группа BHV, 2001. - 464 с.

3. О.В. Бартеньев - Современный Фортран

4. Очков В.Ф., Пухначев Ю.В. - 128 советов начинающему программисту - М.: Энергоатомиздат, 1991 - 256 с.

Размещено на Allbest.ru