Модераторы: 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   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

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


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

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

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

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


 




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


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

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