Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [Pascal] Поиск пифагоровых чисел


Автор: Tauros 12.10.2006, 18:00
Нужно сделать задание на паскале:
" Спроектировать алгоритм по нисходящей схеме с использованием базовых управляющих структур для задачи:
Найти все пифагоровы числа на заданном интервале [n,m]. Пифагоровы числа удовлетворяют условию a*a+b*b=c*c "

Автор: Sartorius 12.10.2006, 18:08
Цитата

Спроектировать алгоритм по нисходящей схеме с использованием базовых управляющих структур для задачи:


 страшно звучит smile 

Перебирай просто все троики из интервала.... 

Автор: Kuvaldis 13.10.2006, 12:12
Sartorius, 
Цитата

Перебирай просто все троики из интервала....

Это не рационально.

оптимизированный вариант
Для начала немного математики
пусть нас интересует интервал [n, m] и числа a, b, с на нем
Причем в поиске a <= b (ищем тройки с точностью до слагаемых)
Очевидно, что минимально возможным значением для с в этой ситуации будет sqrt(n^2 + n^2) = n * sqrt(2)
так как с^2 = a^2 + b^2.
Минимальное a = миниальное b = n
Поэтому переменную c для прокрутки в цикле  инициализируем так
Код

c := integer( Trunc(n * sqrt(2)) ) + 1;


ТАк как решили искать с точностью до слагаемых, то a <= b.
Значит, a^2 <= b^2
Значит, 2 * a^2 <= c^2
Значит, a <= с /sqrt(2) 

Код

var
    m, n    : integer;
    a, b, c : integer;   // искомые числа
    k       : integer;     // место, на котором заканчиваем поиск a 
    b2      : integer;
    count   : integer;
begin
    writeln('Input lower border n');
    readln(n);
    writeln('Input higer border m');
    readln(m);
    
    c := integer( Trunc(n * sqrt(2)) ) + 1;
    count := 0;
    while (c <= m) do
    begin
        k := integer (Trunc(c / sqrt(2)) );
        for a := n to k do
        begin
            b2 := c * c - a * a;
            b := integer (Trunc(sqrt(b2)) );
            if (b * b = b2) then
            begin
                count := count + 1;
                writeln('"', count, '" ', a : 3, b : 3, c : 3);
            end;
        end;
        c := c + 1;
    end;
    if (count = 0) then
       writeln('Not found');
    readln;
End.

Автор: Sartorius 13.10.2006, 12:36
Kuvaldis,  простой перебор имеет трудоемкость |n-m|**3 ... Твой алгоритм дает немного меньше 1/4*|n-m|**3 ИМХО не очень большой выигрыш... Хотя если интервал достаточно большой, а машина медленная , то и такое может пригодиться...

Автор: MBo 13.10.2006, 12:45
все тройки a,b,c генерируются, например, методом древних греков:

u^2-v^2,  2uv, u^2+v^2
u>v 
(лучше взаимно простые числа брать для получения базовых троек (типа 3,4,5), а производные тройки (9,12,15) получать умножением)

Автор: Kuvaldis 13.10.2006, 12:46
Sartorius, 
А есть ли кардинально лучший и эффективный алгоритм?

To MBo:
одновременно сообщения отправили. smile 

Автор: Sartorius 13.10.2006, 12:54
 
Kuvaldis,  да вот в том что предложил  MBo что то есть... тока нада задать границы для u и v прально... и построить таблицу простых чисел в этом интервале

Автор: MBo 13.10.2006, 12:57
Sartorius, 
>и построить таблицу простых чисел в этом интервале 
не простых, а взаимно простых (разной четности, не делящихся одновременно на 3 и т.д.)

Автор: Tauros 14.10.2006, 14:29
Kuvaldis, 
спасибо за программу, но если вводить отрицательные значения то выдает "Error 207 Invalid floating point operation"
, курсор после строки 
Код

  b2 := c * c - a * a;

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

Автор: Kuvaldis 14.10.2006, 15:09
Tauros, 
Цитата

также вроде ошибка появляется если ввести значение верхней границы больше 150 или около того

Проблема из-за того, что я по умолчанию для вывода цифр каждой тройки отвел 3 позиции. После 150 они сливаются. Лечится элементарно
Код

writeln('"', count, '" ', a : 6, b : 6, c : 6);


А про отрицательные числа никто не говорил. Лан, сейчас посмотрю

Надеюсь, ты не собираешься вводить границы разных знаков: нижняя - отрицательная, верхняя - положительная??? smile 

Автор: Tauros 14.10.2006, 15:14
Kuvaldis, 
нет, так не получается, все равно та же ошибка, кстати я проверил, нормально считает до 181 включительно т.е. рассчитывает максимум 291 троек, а ошибка потом... 

Цитата(Kuvaldis @  14.10.2006,  15:09 Найти цитируемый пост)
Надеюсь, ты не собираешься вводить границы разных знаков: нижняя - отрицательная, верхняя - положительная??? 

ну так я пробовал вводить... но даже если вводить обе границы отрицательными все равно ошибка!!! Программа находит 3 тройки среди которых есть ПОЛОЖИТЕЛЬНЫЕ и 0 b, хотя интервал отрицательный, а потом ошибка

Автор: Kuvaldis 14.10.2006, 15:25
Скорректированный вариант
Код

var    
    m, n    : integer;    
    a, b, c : integer;   // искомые числа    
    k       : integer;     // место, на котором заканчиваем поиск a    
    b2      : integer;    
    count   : integer; 
   sign    : integer;   

begin    
    writeln('Input lower border n');    
    readln(n);    
    writeln('Input higer border m');    
    readln(m);
    sign := 1;
   // если границы отрицательные (-5 -3) ->  (3, 5)
    if (m * n > 0) and (m < 0) then    // вместо чисел их модули и меняем их местами
    begin
        a := -m;
        m := -n;
        n := a;
        sign := -1;
    end;    
     
    c := integer( Trunc(n * sqrt(2)) ) + 1;    
    count := 0;    
    while (c <= m) do    
    begin    
        k := integer (Trunc(c / sqrt(2)) );    
        for a := n to k do    
        begin    
            b2 := c * c - a * a;    
            b := integer (Trunc(sqrt(b2)) );    
            if (b * b = b2) then    
            begin    
                count := count + 1;    
                writeln('"', count, '" ', a * sign : 6, b * sign: 6, c * sign: 6); 
            end;    
        end;    
        c := c + 1;    
    end;    
    if (count = 0) then    
       writeln('Not found');    
    readln;    
End.


Цитата

т.е. рассчитывает максимум 110 троек, а ошибка потом... 


Какая ошибка? Как получил? 

Автор: Tauros 14.10.2006, 15:32
теперь работают отрицательные интервалы, но  в ответе все равно числа положительные... ясное дело что там квадрат и разницы никакой... но все же.... 
ошибка при верхнем интервале большем 181 та же самая - 207
p.s. а почему не работает интервал от отрицательного до положительного???

Автор: Kuvaldis 14.10.2006, 15:35
Tauros, 
Цитата

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

Это маленькая опечатка. Можешь исправить сам.
Цитата

p.s. а почему не работает интервал от отрицательного до положительного???

Это сделать чуть-чуть сложнее. Я ж у тебя и спросил: это надо или нет?

Автор: Tauros 14.10.2006, 15:37
Цитата(Kuvaldis @  14.10.2006,  15:35 Найти цитируемый пост)
Это маленькая опечатка. Можешь исправить сам.

угу... может и могу, но не знаю где  smile 

Цитата(Kuvaldis @  14.10.2006,  15:35 Найти цитируемый пост)
Это сделать чуть-чуть сложнее. Я ж у тебя и спросил: это надо или нет? 

и намного это будет сложнее??? если тебе не трудно и не влом, то напиши
но мне кажется что и такая программа прокатит

Автор: Kuvaldis 14.10.2006, 15:38
Со знаком поправил, см. предыдущий пост

Автор: Tauros 14.10.2006, 15:47
после значения верхней границы 181 выдает ошибку 207 (ту же самую)

Автор: Kuvaldis 14.10.2006, 15:50
Tauros, 
Понял!!!smile 
Ты ж пишешь в паскале (я тестил в консольке Delphi). А какое максимально допустимое значение для типа integer в паскале?? Правильно: 32767 (2 байтовое знаковое число). Поэтому так и работает. Чтобы исправить, замени все переменные типа integer на longint 

Автор: Tauros 14.10.2006, 16:00
Kuvaldis, 
действительно помогло!!!!!!  smile 
а что насчет разных знаков интервала???? очень много менять придется?

Автор: Kuvaldis 14.10.2006, 16:15
Tauros, 
ну, ты душу всю вынешь. smile  Вот
Добавилась процедура, которая проверяет все возможные комбинации из 3 чисел (их 8) на попадание в заданный интервал. Если попадает, то выводим

P.S. int на longint сам замени. Мне лень.

Код

program Project2;
var
    m0, n0  : integer;
    m, n    : integer;
    a, b, c : integer;   
    k       : integer;   
    b2      : integer;
    count   : integer;
//*****************************************************************************
procedure OutputAnswer(var count : integer; a, b, c, n0, m0 : integer);
var
  i, j, k : integer;
begin   
   for i := 1 to 2 do
   begin
       for j := 1 to 2 do
       begin
           for k := 1 to 2 do
           begin
                if ((c >= n0) and (c <= m0)) and ((b >= n0) and (b <= m0)) and
                   ((a >= n0) and (a <= m0))  then
                begin
                    count := count + 1;
                    writeln('"', count, '" ', a  : 6, b : 6, c : 6);  
                end;
                c := -c;
           end;
           b := -b;
       end;
       a := -a;
   end;
end;   
//*****************************************************************************
begin
    writeln('Input lower border n');
    readln(n0);
    writeln('Input higer border m');
    readln(m0);
    
    if (m0 * n0 > 0) and (m0 < 0) then    // exchange
    begin
        n := -m0;
        m := -n0;
    end
    else if (m0 * n0 < 0) then
    begin
        n := 0;
        if abs(n0) > abs(m0) then
          m := abs(n0)
        else
          m := abs(m0);
    end
    else
    begin
        n := n0;
        m := m0;
    end;

    c := integer( Trunc(n * sqrt(2)) ) + 1;
    count := 0;
    while (c <= m) do
    begin
        k := integer (Trunc(c / sqrt(2)) );
        for a := n to k do
        begin
            b2 := c * c - a * a;
            b := integer (Trunc(sqrt(b2)) );
            if (b * b = b2) then
            begin
                OutputAnswer(count, a, b, c, n0, m0);            
            end;
        end;
        c := c + 1;
    end;
    if (count = 0) then
       writeln('Not found');
    readln;
End.

Автор: Tauros 14.10.2006, 16:18
Kuvaldis, 
дааа ))) мягко говоря потруднее стало ))))  Спасибо большое за помощь!!! )))

p.s. ты в код еще какую то программу засунул!!! ))))

Автор: Kuvaldis 14.10.2006, 16:27
Tauros, 
1.Надеюсь, теперь ты удовлетворен?
2. 
Цитата

p.s. ты в код еще какую то программу засунул!!! ))))

Основная программа осталась без изменений почти. Мы корректируем отрезок из положительных (!) чисел для поиска. Если одно число < 0, а другое > 0, то ищем все варианты на отрезке 0 .. max(m0, n0).

Ищем неотрицательные тройки. Потом вызываем процедуру, которая перебирает все возможные варианты троек (когда а, b, c +/-) и проверяет попадают ли эти числа в заданный интервал. Если да, то вывод

Автор: Tauros 16.10.2006, 16:00
Kuvaldis, 
Цитата(Sartorius @  12.10.2006,  18:08 Найти цитируемый пост)
Перебирай просто все троики из интервала.... 


Цитата(Kuvaldis @  13.10.2006,  12:12 Найти цитируемый пост)
Это не рационально.


может и не рационально, но преподша сказала , про тот вариант что я показал (твой), цитирую: "Зачем так сложно?... Что это? я это не понимаю.... давай, я этого не видела, переделай..." и еще оказалось что пофиг на то положительные числа или отрицательные

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)