задачи с перебором условий или без?

[knyazoleg]

помогите решить две задачи:
1.Задано целое положительное число >=1. Вывести на экран все его полож. делители
2.Задана последовательность чисел 1,1+1/2,1+1/2+1/3, ... Найти первый её элемент, который больше числа а, ввод. с клавиатуры.

[Poma][a]

И где здрасте?
Тут не онлайн решатель задач, а живые люди от которых возможно зависит Ваше дальнейшее образование.
Где наработки?
№1
В чем сложность? Берем и решаем в лоб, от 1 до n, if n mod i = o then WriteLn (i);

Если Вы более менее математик, то берем и решает по теореме (название не помню), всё так же, но проверяем до (корня из числа n) - 1 (не забудь Trunc при присваивании), и так же выводим только и i, и n div i; после for не забываем развилочку с проверкой на делимость корня. И профит
№ 2 а тут вообще без премудростей, вообщем или с наработками или с денюжкой во фриланс.

[TinMan]

Сообщение от Poma][a

И где здрасте?

хехе, и где же ты видел, штоб князья здоровкались? ))

берем и решает по теореме (название не помню), всё так же, но проверяем до (корня из числа n) - 1 (не забудь Trunc при присваивании), и так же выводим только и i, и n div i; после for не забываем развилочку с проверкой на делимость корня.

Что за теорема? вспоминай название давай - один человек на свете знал, да и тот забыл!.. ))

Зачем вычитать 1? я бы лучше прибавил, если уж ты используешь Trunc.. ))

И что за развилка? делимость корня на что?..

[Poma][a]

Что за теорема? вспоминай название давай - один человек на свете знал, да и тот забыл!.. ))

щас подумаем

Зачем вычитать 1? я бы лучше прибавил, если уж ты используешь Trunc.. ))

Я решал до квадратного корня -1, потом развилочка.

sq := Trunc (Sqrt(n));

for i := 1 to sq-1 do
           if n mod i = 0 then
                    WriteLn (n, ' ', n mod i);

if n mod sq = 0 then
           if sq*sq = n then
                    WriteLn (sq)
           else
                    WriteLn (sq, ' ', n mod sq)

Писал не проверяя. Уж простите...
UPD Забыл про пробельчики
Неа, не помню я название теоремы, завтра у преподавателя спрошу. (может вообще не теорема)...

[TinMan]

Сообщение от Poma][a

Я решал до квадратного корня -1, потом развилочка.

Ром, но зачем? Почему ты вынес то, что должно было быть последним оборотом цикла, ЗА пределы цикла и выполнил отдельно? Промотивируй.

Теперь по поводу Trunc.. Квадратный корень - функция действительного типа, считается на компьютере с некоторой точностью. Что это значит? Что результат вычисления, например, Sqrt(4) может быть равен 2, а может 1.999999999999. При этом, второе число ДОЛЖНО считаться ПРАВИЛЬНЫМ. Почему? Потому что, если точность вычислений равна d, то два числа, отличающиеся меньше, чем на d, ДОЛЖНЫ считаться РАВНЫМИ. Это - смысл концепции ТОЧНОСТЬ ВЫЧИСЛЕНИЙ. Без понимания этого разговоры про точность - пустой звук.

Далее. Если в некоторый момент ты получаешь, например, Sqrt(100000000) равным не 10000, как ожидается, а 9999.9999999 (и этот результат, повторюсь, ПРАВИЛЬНЫЙ), то что произойдет? Trunc тупо отбросит дробную часть, и конечный результат будет меньше нужного аж на 1!! И вот тогда you're in trouble..

Чтоб этого не случилось, рекомендую сделать одно из двух:

1. либо делать цикл не до scrt(n)-1, и даже не до sqrt(n), а до sqrt(n)+1. При этом ты, возможно (и даже скорее всего), сделаешь лишнюю работу, но зато не пропустишь верный результат.

2. либо вместо Trunc делать тривиальный Round. Он преобразует число к ближайшему целому. Да, ты снова будешь делать лишнюю работу, но меньше, чем в предыдущем случае (примерно вдвое).

Есть еще и третий способ, на самом деле, и он лучше (ээ.. эффективнее) этих двух, но он некоторым боком завязан на точность вычислений, что мне не импонирует, хотя это проблема разрешимая. Допустим, ты используешь тип real, точность которого 10^-12 (примерно). Далее, твой целый тип достигает только (условно) 10000, а корень из него не более всего лишь 100. Значит, ошибка при вычислении корня будет порядка 10^-10. Для уверенности продвинем ее до 10^-9. И теперь мы ведем цикл до Trunc(Sqrt(n)+10^-9). Что мы получим? да, мы по-прежнему будем делать ИНОГДА лишнюю работу, но НАМНОГО реже, чем в первом случае или даже во втором. Причем, если мы не уверены, какая реальная точность вычислений, мы можем загрубить эту добавку - сделать ее 10^-8, or 10^-7, or even 10^-5 at last!.. There still will be NO MISTAKE in our calculations - just little bit of extra job done.

Я понятно выразился? )

[Poma][a]

Так : давайте по порядку.
1)

Ром, но зачем? Почему ты вынес то, что должно было быть последним оборотом цикла, ЗА пределы цикла и выполнил отдельно? Промотивируй.

если не выносить, то при вводе, например 4, программа выдаст :

1 4 
2 2

только ради этого и существует развилка.

2) Про Trunc. Разговор пока отложим. Я пойду почитаю про

концепцию ТОЧНОСТИ ВЫЧИСЛЕНИЙ

3) Возможно на данный момент лучше использовать Round (до тех пор пока я не знаю точность вычислении)

[TinMan]

Сообщение от Poma][a

если не выносить, то при вводе, например 4, программа выдаст :

1 4 
2 2

только ради этого и существует развилка.

Ром, не понял, что ты имеешь в виду. Говори, пожалуйста, яснее. Какая именно программа выдаст такое? и что значат эти числа? Если ты имеешь в виду тот фрагмент, что ты написал выше, то он явно отработает не так..

Однако... упс!! )))
По мере разбирательства с тобой, заметил ошибку у себя.. Я как-то молчаливо согласился с тобой, что перебор надо делать до корня из n - а это же неправильно! Перебор для отыскания ВСЕХ делителей нужно, конечно же, делать до n пополам..

var
  n,i: integer;

begin
  readln(n);
  for i:=1 to n div 2 do
    if n mod i=0 then write(i:5);
  readln
end.

И тогда, ессно (поскольку нет действительных чисел), не надо ни транков, ни раундов. И концепция точности вычислений тоже не нужна.. Вот так! ))

Да - так какая там теорема-то? не вспомнил? ))

[DiemonStar]

Касательно точности вычислений - зачем в for упираться рогами если это решается по-другому:

Readln(n);
i := 1;
While sqr(i) <= n do
  begin
    {ну и всё остальное делаем}
    i := i + 1;
  end;

это на случай, вдруг появится такая необходимость )

[Poma][a]

программа без развилки, до sqrt(n) при аргументе 4, выдаст

1 4
2 2

программа с развилкой, до sqrt(n)-1 при аргументе 4, выдаст

1 4
2

Только ради этого и была развилка.

Теперь возьмем аргумент 100, если в цикле n div 2, то работаем да 50, если sqrt(n)-1 то до 10.

Вот нашел подтверждение
http://www.programmersforum.ru/showp...9&postcount=20
Сама тема : http://www.programmersforum.ru/showthread.php?t=119883

Касательно точности вычислений - зачем в for упираться рогами если это решается по-другому:

Это эквивалентно циклу for. + экономит 2 строки.

Был я у учителя, узнал, что на самом деле теоремы никакой нет, Sqrt получен путем размышлений и только.
Про Trunc, он полностью подтвердил слова TinMan'a. (кстати во избежание всяких иллюзий, сомнений в словах TinMan'a в жизни не было)

приведу пример для делителей 20, ответы :

1 20
2 10
4 5
____________________
5 4
10 2
20 1

Вот. Мы проверяем до черты (т.к. дальше нет смысла (все делители уже на экране)). Путем логических раздумий и вычисление, приходим к Sqrt.
Тоесть где должна находиться "черта", примерно на квадратном корне.


Маленький итог на данном этапе :
1) Trunc однозначно убрать
2) Получить максимальное(по возможности) быстродействие. (но пока без замены на 3 пункт решения предложенного TinMan'ом)
3) И наверное отбросить развилочку (я в своё время сдавал преподавателю, так как он просил => с развилкой)

[TinMan]

LOL )))
Ромаха, я твой должник ). Сейчас попробую прибавить репу..
Сегодня проснулся и в тот же момент понял, как прозрел )). Понял, во что я не врубался так долго.. Ты же выдаешь ДВА числа! я понимаю, что это ОЧЕНЬ просто и тривиально, но вот - барьер какой-то был.. (( мож, грипп мешал, зараза - сегодня первый день без температуры.. Кароч, не буду многословным - Ром, ты прав во всем, все мои слова беру обратно, они сказаны не на тот предмет.

Единственное, что можно добавить - все же хотелось бы видеть результат упорядоченным (хотя этого нет в условии задачи, согласен). Думаю, проще всего одно число (меньшее) выводить, а вторые (большие) - накапливать (например, в списке). Затем накопленные вывести в обратном порядке. Тогда не потребуется собственно упорядочивания.

Ромаха, еще раз спасибо за науку! )