Форум » Обработка целых чисел » №2574 (24.25) (проблема с алгоритмом) » Ответить

№2574 (24.25) (проблема с алгоритмом)

beep: Здравствуйте! В задаче нужно найти такие числа из отрезка, у которых ровно 5 различных делителей. Вместо перебора в ответах предложен следующий алгоритм: [pre2]from math import sqrt start, end = 11275, 16328 qStart = int(sqrt(start)) qEnd = int(sqrt(end))+1 for q in range( qStart, qEnd+1 ): n = q*q a = [q] # массив для хранения делителей for d in range(1, q): if n % d == 0: a = a + [d, n//d] if len(a) > 5: break if len(a) == 5: print( *sorted(a) )[/pre2] Проблема в том, что если при извлечении корня из левой границы после округления получится квадрат простого числа, но при этом сама левая граница не является квадратом числа, то алгоритм сработает неправильно. Например, если передвинуть левую границу к start = 11**4 + 1 (14642), то алгоритм выдаст такой же ответ "1 11 121 1331 14641", хотя числа 14641 нет в диапазоне. Также алгоритм можно ускорить: идея алгоритма заключается в том, чтобы перебирать не каждое число из диапазона, а только те числа, из которых можно извлечь квадрат, и дальше ищется количество множителей до корня из числа (которое в свою очередь само является корнем из числа из диапазона). Ускорение заключается в том, что нам не нужно искать эти множители, поскольку получившееся число q должно быть само квадратом простого числа. Тогда нужно всего лишь проверить, извлекается ли корень из q и является ли полученный корень простым числом. Во-первых, вложенный цикл будет работать не для каждого q, а только для тех, из которых извлекается корень. Во-вторых, вложенный цикл будет проходиться каждый раз не до корня из числа из диапазона, а до корня четвертой степени из этого числа. В-третьих, при проверке на простоту не нужно перебирать каждое число, а только нечетные (+ отдельная проверка на четность), когда при поиске всех корней цикл идет с шагом 1.

Ответов - 15

zachto: В простом решении данной задачи важно знать формулу нахождения количества различных делителей числа. a=p1^s1·p2^s2·…·pn^sn, где a - само число, pi - простой множитель числа, si - степень простого множителя. Исходя из этого, количество равно произведению всех степеней простых множителей + 1, т. е. S = (s1+1)*(s2+1)*...*(sn+1). В этой задаче 5 делителей требуется. 5, в свою очередь, простое число => требуемые числа будут простыми числами в четвертой степени. Такое число в данной задаче всего одно. from math import ceil a = 11275 b = 16328 start = int(ceil(a ** 0.25)) end = int(b ** 0.25) print(start, end) print(start ** 2, start ** 3) "Решение", естественно, привел для частного случая.

beep: zachto это все понятно. Прочитайте еще раз вдумчиво если передвинуть левую границу к start = 11**4 + 1 (14642), то алгоритм выдаст такой же ответ "1 11 121 1331 14641", хотя числа 14641 нет в диапазоне В Вашем алгоритме такая же проблема. Стоит сместить границу (a = 14642), и он выдает неверный ответ "144 1728". Вы не не проверяете округления и это заканчивается закономерно.

zachto: Вы хотите с помощью одного тривиального алгоритма решить все задачи подобного плана? Могу лишь пожелать удачи. Если в моем алгоритме a - 14642, то start = 12, а end = 11 => чисел вообще нет. В ЕГЭ нужно не только программировать, но и думать немного, смотреть на входные данные задачи.


beep: Вы хотите с помощью одного тривиального алгоритма решить все задачи подобного плана? zachto, а это так сложно? Правда? Могу лишь пожелать удачи. Могу лишь пожелать удачи с частными решениями. У меня для Вас есть куда лучше вариант "print(121, 1331)" - как Вам? Что будете делать, если после извлечения корня четвертой степени из a и округления, в a окажется не простое число? Опять рассказывать про частные решения "половина в голове, половина в коде"? Если в моем алгоритме a - 14642, то start = 12, а end = 11 => чисел вообще нет. Если Ваш алгоритм запустить, то он скажет обратное. Попробуйте сами. [pre2]a = 14642 b = 16328 start = int(ceil(a ** 0.25)) end = int(b ** 0.25) print(start, end) print(start ** 2, start ** 3)[/pre2] В ЕГЭ нужно не только программировать, но и думать немного, смотреть на входные данные задачи. Мир не заканчивается ЕГЭ, во-первых. Во-вторых, вот именно, что думать нужно. Вы как пришли к выводу, что в диапазоне единственное число существует?

zachto: Вы как пришли к выводу, что в диапазоне единственное число существует? Чисел существует не более чем start - end + 1. Что будете делать, если после извлечения корня четвертой степени из a и округления, в a окажется не простое число? Вижу простое число => ok. Вижу составное число => программно ищу ближайшее простое, большее a. Если Ваш алгоритм запустить, то он скажет обратное. Попробуйте сами. Перед отправкой я всегда проверяю код, start = 12, end = 11. У меня для Вас есть куда лучше вариант "print(121, 1331)" - как Вам? Отлично, на ЕГЭ по информатике никто не смотрит ни на код, ни на какое-либо решение. Может быть вам в молитве пришел ответ, nobody cares. а это так сложно? Правда? Нужно уметь комбинировать решения, на мой взгляд, естественно.

beep: Чисел существует не более чем start - end + 1. Нет же, это опять ошибка. Вы тут себя поправляете с моей помощью: Вижу простое число => ok. Вижу составное число => программно ищу ближайшее простое, большее a. Отлично, что Вам Ваш глаз скажет на счет числа 6117 - простое или составное? Перед отправкой я всегда проверяю код, start = 12, end = 11. Потрясающее решение, где все в ручном режиме. Отлично, на ЕГЭ по информатике никто не смотрит ни на код, ни на какое-либо решение. Может быть вам в молитве пришел ответ, nobody cares. Вы егэ сдаете и учитесь программировать для чего? Чтобы навыки развить или грамоту на стенку повесить? Нужно уметь комбинировать решения, на мой взгляд, естественно. Нужно уметь решать задачи в общем виде, особенно, когда это не сложно, не знаю, где учат обратному. Вы и по математике-физике на половине решения в формулы числа подставляете? Написать общее решение намного проще и быстрее, чем что-то там проверять глазами. Если в диапазоне окажется не 1, а 3 числа, что делать будете? Опять костыли придумывать? Выводить в консоль каждое число и работать вручную?

zachto: Нет же, это опять ошибка. Вы тут себя поправляете с моей помощью: Надеюсь, вы знаете что значит "не более чем". Отлично, что Вам Ваш глаз скажет на счет числа 6117 - простое или составное? Сумма цифр кратна 3 => число составное. Вы и по математике-физике на половине решения в формулы числа подставляете? Удивительно, что это пишите Вы. Человек, который хочет "уметь решать задачи в общем виде" и просто подставлять значения в программу. Написать общее решение намного проще и быстрее, чем что-то там проверять глазами. Если в диапазоне окажется не 1, а 3 числа, что делать будете? Опять костыли придумывать? Выводить в консоль каждое число и работать вручную? А что быстрее на экзамене? Вспомнить какое-то там общее решение или сразу написать "костыль"? Нужно уметь решать задачи в общем виде, особенно, когда это не сложно, не знаю, где учат обратному. Нужно лишь понять условие задачи. Общие решения оставьте на олимпиады по проге, физику и математику.

beep: Надеюсь, вы знаете что значит "не более чем". Принято. Удивительно, что это пишите Вы. Человек, который хочет "уметь решать задачи в общем виде" и просто подставлять значения в программу. Удивительно, что это пишет человек, который с разметкой справится не может. Смысл был не в этом же. 8341 простое число? Как там Ваш глаз? А что быстрее на экзамене? Вспомнить какое-то там общее решение или сразу написать "костыль"? Я же написал, что быстрее и проще. Может Вы и заучиваете какие-то там решения, но я их в состоянии писать не вспоминая. Как раз куда проще решить задачу в общем виде, чем заботиться обо всех исключениях и писать "костыли". Нужно лишь понять условие задачи. Общие решения оставьте на олимпиады по проге, физику и математику. Еще раз, Ваш алгоритм работает из-за везения. Вы получаете диапазон [a, b] - как вы с ходу скажете, сколько там есть чисел, из которых можно извлечь корень четвертой степени? Как вы определите на глаз простое число или нет? Каждый раз сидеть с консолью и рассматривать каждый шаг? Это не решение, а мазохизм.

zachto: Удивительно, что это пишет человек, который с разметкой справится не может. Зря тему переводите. чем заботиться обо всех исключениях и писать "костыли" Непонятно о каких исключениях нужно заботиться и какие костыли нужно писать. Печально, что вы не научились мыслить аналитически за все годы в школе. Я же написал, что быстрее и проще. Что проще? Знать, что квадрат двух равен четырем, или писать лишнюю строку кода? Вы получаете диапазон [a, b] Я получаю конкретный отрезок, а не [a, b]. Получу один отрезок - решу одним способом, получу другой - другим. Еще раз, Ваш алгоритм работает из-за везения. У меня, у автора алгоритма, конечно же, везение, хороший отрезок, специально подобранные числа и т.п. Дайте другие входные данные - изменим алгоритм и решим по-другому.

beep: Зря тему переводите. Нет же, это Вы решили извернуться с кратностью на три. Если Вы такой щепетильный, то почему пропусти вопрос про 8341? Я надеюсь, Вы же с первого раза поняли, что я хотел сказать, и решили ускользнуть, перейдя на личности, а теперь обижаетесь. Непонятно о каких исключениях нужно заботиться и какие костыли нужно писать. Я могу повторить, я уже заметил, что у вас проблемы: 1) Ваш алгоритм работает в ручном режиме, нужно постоянно что-то смотреть и додумывать 2) он не универсальный, что будете делать, если в диапазоне больше 1 числа? 3) как проверять полученные числа на простоту? По-сути, это даже не алгоритм, а подгонка "решения" под результат. Смени чуть-чуть диапазон и снова придется половину решать в голове. Вы просто вручную исследуете диапазон и надеетесь на легкий ответ. Печально, что вы не научились мыслить аналитически за все годы в школе. И это говорит человек, для которого общие решения затруднительны. Что проще? Знать, что квадрат двух равен четырем, или писать лишнюю строку кода? Я уже написал несколько раз, что проще. Зачем Вы мне из раза в раз задаете один и тот же вопрос, надеясь услышать оправдывающий Вас ответ? Вместо того, чтобы делать половину действий вручную и просматривать консоль, проще написать пару лишних строк кода, которые вовсе не лишние, потому что если исключений будет чуть больше, Вы сами запутаетесь в своем решении и половину ЕГЭ просидите, ковыряя консоль. У меня, у автора алгоритма, конечно же, везение, хороший отрезок, специально подобранные числа и т.п. Не приписывайте себя к автору. У автора есть недочет, случай, который он не учел. Это сразу понятно. У Вас же это какое-то полуручное недоразумение, а не алгоритм. Дайте другие входные данные - изменим алгоритм и решим по-другому. Ага, очередной велосипед с квадратными колесами на ручном управлении. Ваш уровень решений я понял, спасибо. Мне с Вами обсуждать нечего.

Поляков: beep пишет: Проблема в том, что если при извлечении корня из левой границы после округления получится квадрат простого числа, но при этом сама левая граница не является квадратом числа, то алгоритм сработает неправильно. Спасибо, решение поправил. Также алгоритм можно ускорить: идея алгоритма заключается в том, чтобы перебирать не каждое число из диапазона, а только те числа, из которых можно извлечь квадрат, и дальше ищется количество множителей до корня из числа (которое в свою очередь само является корнем из числа из диапазона). Да, можно. Но нет особой необходимости. Это не критично при заданных данных, но усложнит программу и повысит вероятность ошибки.

beep: Поляков, Спасибо, решение поправил. Вам спасибо за Вашу работу. Можете, пожалуйста, посмотреть соседнюю тему? В материалах для подготовки этот алгоритм тоже рассматривается, как общий, и там тоже есть недочет, который не заметен из-за того, что диапазон удачный попался. Алгоритм будет неправильно срабатывать на любое простое число в 4й степени (алгоритм будет считать, что у такого числа 4 корня, хотя их на самом деле 5) - http://egekp.unoforum.pro/?1-22-0-00000157-000-0-0-1641482077 Да, можно. Но нет особой необходимости. Это просто до кучи уже, раз тема создана. Вдруг кому-нибудь пригодится.

beep: Поляков, в решении для задачи 25.91 (№2595) тот же алгоритм и та же проблема, левая граница не проверяется на вхождение, если взять число чуть большее квадрата простого числа, то алгоритм снова учтет число, которого нет в диапазоне.

Поляков: beep пишет: в решении для задачи 25.91 (№2595) тот же алгоритм и та же проблема Там есть проверка диапазона.

beep: Поляков, моя невнимательность (проще один раз проверить, чем каждый раз в цикле), извините.



полная версия страницы