помогите отчисляют - ProgZ.ru - Форумы по программированию

IPB

Здравствуйте, гость ( Вход | Регистрация )
платный хостинг Ipipe.ru

[X]
Помощник
Загрузка. Пожалуйста, подождите...

Новости
 Статьи
 FAQ

ProgZ.ru - Форумы по программированию > Языки программирования > Pascal
помогите отчисляют
Опции V
flug | 14.7.2006, 13:53 Сообщение #1
Группа: Пользователи Сообщений: 1 Регистрация: 14.7.2006 | ПОМОГИТЕ!!! ОТЧИСЛЯЮТ. дано четное n>2 проверить для этого числа гипотезу гольдбаха, которая заключается в том, что каждое четное n>2 представляется в виде суммы двух простых чисел, определить процедуры позволяющуюю распозновать простые числа, Братья и сестры заранее спасибо
Fuud | 14.7.2006, 16:01 Сообщение #2
Отличный человек Группа: Пользователи Сообщений: 3 387 Регистрация: 3.9.2004 Из: SPb | без проблем. Но за деньги (асю и мыло смотри в профиле). что тебе нужно: 1)написать функцию, определяющую простое перед нами число или нет. 2)перебрать все числа от 1 до n-1, ища пару простых. что конкретно не получается? --------------------
DeepFinder
11.8.2006, 0:10
Сообщение #3

Группа: Пользователи
Сообщений: 147
Регистрация: 14.6.2004
Я здеся не хочу ни кого критиковать, но хочу показать что скрывается за невинными призывами о помощи. И что должен знать студент дабы не вылететь. Или что должен знать и проделать кто-то, что бы спасти студента (мы предполагаем что это был всё-таки бедный студент, а не лодырь [image] )

Цитата
ПОМОГИТЕ!!! ОТЧИСЛЯЮТ. дано четное n>2 проверить для этого числа гипотезу гольдбаха, которая заключается в том, что каждое четное n>2 представляется в виде суммы двух простых чисел, определить процедуры позволяющуюю распозновать простые числа, Братья и сестры заранее спасибо

Тов. Fuud правильно среагировал
Цитата
без проблем. Но за деньги

И уточнил задачу:
Код
1)написать функцию, определяющую простое перед нами число или нет.
2)перебрать все числа от 1 до n-1, ища пару простых.

Дальнейший ход событий мы к сожалению не увидели.

Я большой приверженец Паскаля, как императивного языка, но всё больше становлюсь приверженцем функциональных и логических языков типа Scheme (диалект Lisp), Prolog. Процедуры переводить на Паскаль не стал - лень. Яжели кому оччень надо могу попробовать.

Код
[b]Знания необходимые для решения проблемы:[/b] (взяты из книги по языку Scheme)

Можно использовать два метода проверки числа n на простоту, один с порядком роста sqrt(n), и другой, "вероятностный", алгоритм с порядком роста log (n).

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

Код
(define (smallest-divisor n) (find-divisor n 2))

(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))

(define (divides? a b) (= (remainder b a) 0))

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

Код
(define (prime? n) (= n (smallest-divisor n)))

Тест на завершение основан на том, что если число n не простое, у него должен быть делитель, меньше или равный sqrt(n). Если d - делитель n, то n/d тоже. Но d и n/d не могут оба быть больше sqrt(n). Это означает, что алгоритм может проверять делители только от 1 до sqrt(n). Следовательно, число шагов, которые требуются, чтобы определить, что n простое, будет иметь порядок роста sqrt(n).

Тест на простоту с порядком роста (log n) основан на утверждении из теории чисел, известном как Малая теорема Ферма.

Код
Малая теорема Ферма:
Если n - простое число, а a - произвольное целое число меньше, чем n, то a, возведенное в n-ю степень, равно a по модулю n.

(Говорят, что два числа равны по модулю n (congruent modulo n), если они дают одинаковый остаток при делении на n. Остаток от деления числа a на n называется также остатком a по модулю n (remainder of a modulo n) или просто a по модулю n.)

Если n не является простым, то, вообще говоря, большинство чисел a < n не будут удовлетворять этому условию. Это приводит к следующему алгоритму проверки на простоту:

имея число n, случайным образом выбрать число a < n и вычислить остаток от a^n по модулю n. Если этот остаток не равен a, то n определенно не является простым. Если он равен a, то мы имеем хорошие шансы, что n простое. Тогда нужно взять еще одно случайное a и проверить
его тем же способом. Если и оно удовлетворяет уравнению, мы можем быть еще более уверены, что n простое. Испытывая все большее количество a, мы можем увеличивать нашу уверенность в результате. Этот алгоритм называется тестом Ферма.

Для реализации теста Ферма нам нужна процедура, которая вычисляет степень числа по модулю другого числа:

Код
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
(else (remainder (* base (expmod base (- exp 1) m)) m)) ))

Эта процедура использует последовательное возведение в квадрат, так что число шагов логарифмически растет с увеличением степени.

---
Шаги редукции для случаев, когда степень больше 1, основаны на том, что для любых целых чисел x, y и m мы можем найти остаток от деления произведения x и y на m путем отдельного вычисления остатков x по модулю m, y по модулю m, перемножения их, и взятия остатка по модулю m от результата. Например, в случае, когда e четно, мы можем вычислить остаток b^(e/2) по модулю m, возвести его в квадрат и взять остаток по модулю m. Такой метод полезен потому, что с его помощью мы можем производить вычисления, не используя чисел, намного больших, чем m.

Тест Ферма производится путем случайного выбора числа a между 1 и n-1 включительно и проверки, равен ли a остаток по модулю n от n-ой степени a.

Код
(define (fermat-test n)
(define (try-it a) (= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))

Следующая процедура прогоняет тест заданное число раз, как указано ее параметром. Ее значение истинно, если тест всегда проходит, и ложно в противном случае.

Код
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))

Вероятностные методы

Тест Ферма отличается по своему характеру от большинства известных алгоритмов, где вычисляется результат, истинность которого гарантирована. Здесь полученный результат верен лишь с какой-то вероятностью. Более точно, если n не проходит тест Ферма, мы можем точно сказать, что оно не простое. Но то, что n проходит тест, хотя и является очень сильным показателем, все же не гарантирует, что n простое. Нам хотелось бы сказать, что для любого числа n, если мы проведем тест достаточное количество раз и n каждый раз его пройдет, то вероятность ошибки в нашем тесте на простоту может быть сделана настолько малой, насколько мы того пожелаем.

К сожалению, это утверждение неверно. Существуют числа, которые "обманывают" тест Ферма: числа, которые не являются простыми и тем не менее обладают свойством, что для всех целых чисел a < n a^n равно a по модулю n. Такие числа очень редки, так что на практике тест Ферма вполне надежен.

---
Числа, "обманывающие" тест Ферма, называются числами Кармайкла (Carmichael numbers), и про них почти ничего неизвестно, кроме того, что они очень редки. Существует 255 чисел Кармайкла, меньших 100 000 000. Несколько первых - 561, 1105, 1729, 2465, 2821 и 6601. При проверке на простоту больших чисел, выбранных случайным образом, шанс наткнуться на число, "обманывающее" тест Ферма, меньше, чем шанс, что космическое излучение заставит компьютер сделать ошибку при вычислении <правильного> алгоритма. То, что по первой из этих причин алгоритм считается неадекватным, а по второй нет, показывает разницу между математикой и техникой.
Существуют варианты теста Ферма, которые обмануть невозможно. В таких тестах, подобно методу Ферма, проверка числа n на простоту ведется путем выбора случайного числа a < n и проверки некоторого условия, зависящего от n и a.
------
Один из вариантов теста Ферма, который невозможно обмануть, называется тест Миллера-Рабина (Miller-Rabin test) (Miller 1976; Rabin 1980). Он основан на альтернативной формулировке Малой теоремы Ферма, которая состоит в том, что если n - простое число, а a - произвольное положительное целое число, меньшее n, то a в n.1-ой степени равняется 1 по модулю n. Проверяя простоту числа n методом Миллера-Рабина, мы берем случайное число a < n и возводим его в (n. 1)-ю степень по модулю n с помощью процедуры expmod. Однако когда в процедуре expmod мы проводим возведение в квадрат, мы проверяем, не нашли ли мы <нетривиальный квадратный корень из 1 по модулю n>, то есть число, не равное 1 или n . 1, квадрат которого по модулю n равен 1. Можно доказать, что если такой нетривиальный квадратный корень из 1 существует, то n не простое число. Можно, кроме того, доказать, что если n - нечетное число, не являющееся простым, то по крайней мере для половины чисел a < n вычисление a^(n-1) с помощью такой процедуры обнаружит нетривиальный квадратный корень из 1 по модулю n (вот почему тест Миллера-Рабина невозможно обмануть). Модифицируйте процедуру expmod так, чтобы она сигнализировала обнаружение нетривиального квадратного корня из 1, и используйте ее для реализации теста Миллера-Рабина с помощью процедуры, аналогичной fermat-test. Проверьте свою процедуру на нескольких известных Вам простых и составных числах. Подсказка: удобный способ заставить expmod подавать особый сигнал - заставить ее возвращать 0.

С другой стороны, в отличие от теста Ферма, можно доказать, что для любого n условие не выполняется для большинства чисел a < n, если n не простое. Таким образом, если n проходит тест для какого-то случайного a, шансы, что n простое, уже больше половины. Если n проходит тест для двух случайных a, шансы, что n простое, больше, чем 3 из 4. Проводя тест с большим количеством случайных чисел, мы можем сделать вероятность ошибки сколь угодно малой.
Существование тестов, для которых можно доказать, что вероятность ошибки можно сделать сколь угодно малой, вызвало большой интерес к алгоритмам такого типа. Их стали называть вероятностными алгоритмами (probabilistic alorithms). В этой области ведутся активные исследования, и вероятностные алгоритмы удалось с успехом применить во многих областях.
---
Одно из наиболее впечатляющих применений вероятностные алгоритмы получили в области криптографии. Хотя в настоящее время вычислительных ресурсов недостаточно, чтобы разложить на множители произвольное число из 200 цифр, с помощью теста Ферма проверить, является ли оно простым, можно за несколько секунд. Этот факт служит основой предложенного в Rivest, Shamir, and Adleman 1977 метода построения шифров, которые "невозможно" взломать. Полученный алгоритм RSA (RSA algorithm)стал широко используемым методом повышения секретности электронных средств связи. В результате этого и других связанных событий исследование простых чисел, которое раньше считалось образцом "чистой" математики, изучаемым исключительно ради самого себя, теперь получило важные практические приложения в таких областях, как криптография, электронная передача денежных сумм и хранение информации.

Вот так-то. И таких милых просьб в разных ветках хватает на весь форум

--------------------
Best regards ...
DeepFinder ...
2006 A.D.

Fuud | 12.8.2006, 18:32 Сообщение #4
Отличный человек Группа: Пользователи Сообщений: 3 387 Регистрация: 3.9.2004 Из: SPb | Спасибо. Очень интересно. ps Побольше бы таких ответов! --------------------
DeepFinder | 13.8.2006, 10:49 Сообщение #5
Группа: Пользователи Сообщений: 147 Регистрация: 14.6.2004 | Цитата Спасибо. Очень интересно. Усегда рад. ps Побольше бы таких ответов! Так это надо дабы тема Ынтересная попалась, а то всё простые банальности. -------------------- Best regards ... DeepFinder ... 2006 A.D.
« Предыдущая тема · Pascal · Следующая тема »

Режим отображения: Стандартный · Переключить на: Линейный · Переключить на: Древовидный

Подписка на тему · Сообщить другу · Версия для печати · Подписка на этот форум

ProgZ.ru - Форумы по программированию > Языки программирования > Pascal

Текстовая версия Сейчас: 30.1.2007, 21:03