Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Pascal] Поиск пифагоровых чисел, а заданном интервале 
:(
    Опции темы
Tauros
Дата 12.10.2006, 18:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

Репутация: нет
Всего: нет
Нужно сделать задание на паскале:
" Спроектировать алгоритм по нисходящей схеме с использованием базовых управляющих структур для задачи:
Найти все пифагоровы числа на заданном интервале [n,m]. Пифагоровы числа удовлетворяют условию a*a+b*b=c*c "
PM MAIL   Вверх
Sartorius
Дата 12.10.2006, 18:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
Цитата

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


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

Перебирай просто все троики из интервала.... 
PM MAIL ICQ   Вверх
Kuvaldis
Дата 13.10.2006, 12:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
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.



Это сообщение отредактировал(а) Kuvaldis - 13.10.2006, 12:31


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Sartorius
Дата 13.10.2006, 12:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
Kuvaldis,  простой перебор имеет трудоемкость |n-m|**3 ... Твой алгоритм дает немного меньше 1/4*|n-m|**3 ИМХО не очень большой выигрыш... Хотя если интервал достаточно большой, а машина медленная , то и такое может пригодиться...
PM MAIL ICQ   Вверх
MBo
Дата 13.10.2006, 12:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 7
Всего: 18
все тройки a,b,c генерируются, например, методом древних греков:

u^2-v^2,  2uv, u^2+v^2
u>v 
(лучше взаимно простые числа брать для получения базовых троек (типа 3,4,5), а производные тройки (9,12,15) получать умножением)
PM MAIL   Вверх
Kuvaldis
Дата 13.10.2006, 12:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Sartorius, 
А есть ли кардинально лучший и эффективный алгоритм?

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

Это сообщение отредактировал(а) Kuvaldis - 13.10.2006, 12:54


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Sartorius
Дата 13.10.2006, 12:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: 8
Всего: 37
 
Kuvaldis,  да вот в том что предложил  MBo что то есть... тока нада задать границы для u и v прально... и построить таблицу простых чисел в этом интервале
PM MAIL ICQ   Вверх
MBo
Дата 13.10.2006, 12:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 7
Всего: 18
Sartorius, 
>и построить таблицу простых чисел в этом интервале 
не простых, а взаимно простых (разной четности, не делящихся одновременно на 3 и т.д.)
PM MAIL   Вверх
Tauros
Дата 14.10.2006, 14:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

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

  b2 := c * c - a * a;

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

Это сообщение отредактировал(а) Tauros - 14.10.2006, 14:57
PM MAIL   Вверх
Kuvaldis
Дата 14.10.2006, 15:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Tauros, 
Цитата

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

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

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


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

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

Это сообщение отредактировал(а) Kuvaldis - 14.10.2006, 15:20


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Tauros
Дата 14.10.2006, 15:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

Репутация: нет
Всего: нет
Kuvaldis, 
нет, так не получается, все равно та же ошибка, кстати я проверил, нормально считает до 181 включительно т.е. рассчитывает максимум 291 троек, а ошибка потом... 

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

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

Это сообщение отредактировал(а) Tauros - 14.10.2006, 15:26
PM MAIL   Вверх
Kuvaldis
Дата 14.10.2006, 15:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Скорректированный вариант
Код

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 троек, а ошибка потом... 


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

Это сообщение отредактировал(а) Kuvaldis - 14.10.2006, 15:37


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Tauros
Дата 14.10.2006, 15:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

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

Это сообщение отредактировал(а) Tauros - 14.10.2006, 15:35
PM MAIL   Вверх
Kuvaldis
Дата 14.10.2006, 15:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Tauros, 
Цитата

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

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

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

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


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Tauros
Дата 14.10.2006, 15:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

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

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

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

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

Это сообщение отредактировал(а) Tauros - 14.10.2006, 15:39
PM MAIL   Вверх
Kuvaldis
Дата 14.10.2006, 15:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Со знаком поправил, см. предыдущий пост


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Tauros
Дата 14.10.2006, 15:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

Репутация: нет
Всего: нет
после значения верхней границы 181 выдает ошибку 207 (ту же самую)
PM MAIL   Вверх
Kuvaldis
Дата 14.10.2006, 15:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

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

Это сообщение отредактировал(а) Kuvaldis - 14.10.2006, 15:50


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Tauros
Дата 14.10.2006, 16:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

Репутация: нет
Всего: нет
Kuvaldis, 
действительно помогло!!!!!!  smile 
а что насчет разных знаков интервала???? очень много менять придется?
PM MAIL   Вверх
Kuvaldis
Дата 14.10.2006, 16:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
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.


Это сообщение отредактировал(а) Kuvaldis - 14.10.2006, 16:21


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Tauros
Дата 14.10.2006, 16:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

Репутация: нет
Всего: нет
Kuvaldis, 
дааа ))) мягко говоря потруднее стало ))))  Спасибо большое за помощь!!! )))

p.s. ты в код еще какую то программу засунул!!! ))))
PM MAIL   Вверх
Kuvaldis
Дата 14.10.2006, 16:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


механик-вредитель
***


Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: 32
Всего: 61
Tauros, 
1.Надеюсь, теперь ты удовлетворен?
2. 
Цитата

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

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

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


--------------------
Помни - когда ты спишь, враг не дремлет
Спи чаще и дольше, изматывай врага бессоницей
PM MAIL ICQ   Вверх
Tauros
Дата 16.10.2006, 16:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 24.9.2006

Репутация: нет
Всего: нет
Kuvaldis, 
Цитата(Sartorius @  12.10.2006,  18:08 Найти цитируемый пост)
Перебирай просто все троики из интервала.... 


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


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

Это сообщение отредактировал(а) Tauros - 16.10.2006, 16:12
PM MAIL   Вверх
Страницы: (2) [Все] 1 2 
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0682 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.