Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 03.01.2011, 17:08   #1
Pecho
Пользователь
 
Регистрация: 23.11.2010
Сообщений: 37
По умолчанию Delphi 7. ро-метод Полларда (факторизация числа)

Доброго времени суток!
Необходимо написать ро-алгоритм Полларда. Взял Кнута с его "Искусство программирования", реализовал. Но программа в итоге оказалась нерабочей.

Прошу помочь найти ошибку...и извиняйте, что пользовался label, я не аццкий прогер

Код:
program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

label
   Metka1,Metka2;

var
   x,xl,k,l,a,g,n:integer; //a-это xl-x, rez-это временная переменная для нахождения НОД, n-это число, g-значение НОД

function Proverka(x: integer): boolean;//Функция проверки числа на простоту
   var i: integer;
   begin
      Proverka:=false;
      if x<2 then exit;
      // Проверяем на чётность (отсев)
      if not odd(x) then exit; //Если функция Odd не смогла вернуть истину, что данное число нечетно, то выйти
      i:=3;
      // Как таковая проверка
      while i <= sqrt(x) do
      begin
         if x mod i = 0 then exit;
         inc(i,2); //Увеличиваешаг цикла на 2
      end;
      Proverka:=true;
   end;

function Gsd(a,b:integer):integer;//Функция определения НОД. И так всё понятно
   var temp:integer;
   begin
      while (b>0) do
         begin
            temp:= a mod b;
            a:=b;
            b:=temp;
         end;
      Gsd:=a;
   end;

begin
  { TODO -oUser -cConsole Main : Insert code here }
   //1.Начальная установка
   x:=5;
   xl:=2;
   k:=1;
   l:=1;
   Write('Vvedi chislo: ');
   Readln(n);
   
Metka2:
   //2. Проверка на простоту. Если число простое - то вывести на экран и завершить алгоритм
   if (Proverka(n)=true) then
   begin
      Write('1 * ',n);
readln;
      exit;
   end;

Metka1:
   //3 шаг
   a:=xl-x;
   g:=Gsd(a,n);
   if (g=1) then //3.1 Если g=1, то идти к шагу 4
   begin

      //4. Меняем значения
      k:=k-1;
      if k=0 then
      begin
         xl:=x;
         l:=2*l;
         k:=l;
      end;
      x:=(x*x+1) mod n;
   //Затем возвращаемся возврящаемся к 3-ему шагу
      goto Metka1;
   end
   else Write(g,' '); //3.1 Иначе выводим найденный множитель

   //3.2 Если g=n, то прекратить выполнение алгоритма
   if (g=n) then exit
   //3.2 Иначе меняем значения и возвращаемся ко 2-му шагу
   else
   begin
      n:=trunc(n/g);
      x:=x mod n;
      xl:=xl mod n;
      goto Metka2;
   end;

readln
end.
Pecho вне форума Ответить с цитированием
Старый 03.01.2011, 20:29   #2
Pecho
Пользователь
 
Регистрация: 23.11.2010
Сообщений: 37
По умолчанию

Открыл заново код, и дошло.
Строчку
Код:
a:=xl-x;
нужно заменить на
Код:
a:=abs(xl-x);
Pecho вне форума Ответить с цитированием
Старый 03.01.2011, 20:29   #3
Pecho
Пользователь
 
Регистрация: 23.11.2010
Сообщений: 37
По умолчанию

Тему можно закрывать
Pecho вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
метод Лагранжа в Delphi asyagolub Помощь студентам 1 16.06.2011 17:07
ро-метод Полларда fort-_-minor Общие вопросы C/C++ 6 13.08.2010 18:23
как соединить метод гаусса и вычисление числа обусловленности матрицы? Lelechka1984 Помощь студентам 0 18.01.2010 21:28