|
Счастливые числа
|
|||
---|---|---|---|
#18+
Счастливые числа - числа сума цифр числа является квадратом какого-то целого числа.Нужно посчитать, сколько счастливых чисел является на отрезке от А до В (включая А и В). Пример входных и выходных данных Введение: 1 15 Вывод: 5 Комментарий. Счастливыми на отрезке [1, 15] является числа 1, 4, 9, 10, 13. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.04.2021, 18:18 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
OmikamiНужно посчитать Удачи! https://www.sql.ru/forum/940953/posobie-dlya-studentov-i-shkolnikov Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
15.04.2021, 18:34 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Omikami, Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38.
output Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 16:40 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
AmKad, Продемонстрировал знание С++17. ТС не сможет такую лабу защитить, а принимающий доцент не сможет понять что там написано. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 19:26 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petrav ТС не сможет такую лабу защитить, а принимающий доцент не сможет понять что там написано. petrav Продемонстрировал знание С++17. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 19:32 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
AmKad, Хорошо. Ты уверен что в рамках такого кода: Код: plaintext 1. 2. 3. 4.
И в рамках пространства unsigned не существует квадратного числа, такого что твоя лямбда вернёт false? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 19:43 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petrav, Нет, не уверен. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 19:47 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petrav, Видите, как интересно. Теперь Вы принимающий доцент, а я студент. Подумаю, может быть есть другое решение. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 19:51 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
AmKad petrav, Видите, как интересно. Теперь Вы принимающий доцент, а я студент. Подумаю, может быть есть другое решение. Ну я не доцент. Просто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы. Давайте думать. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 19:57 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petrav, Нашел тут утверждение, что "любой квадрат это сумма последовательных нечетных чисел". Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9.
Похоже автор не врал. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 20:08 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
AmKad petrav, Нет, не уверен. Я не смог найти таких чисел. Но это не отрицает факта, что там где плавающая точка, то там бывают чудеса. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 21:19 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petravПросто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы. Во-первых, они предсказуемые. Во-вторых, в области без дробной части в пределах точности их нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 22:09 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov petravПросто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы. Что, простите? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.04.2021, 22:22 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petravЧто, простите? Два в квадрате всегда ровно четыре. Три в квадрате всегда ровно девять. И так далее. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
17.04.2021, 00:24 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov petravЧто, простите? Два в квадрате всегда ровно четыре. Три в квадрате всегда ровно девять. И так далее. Понятно, с целыми числами обычно проблем не возникает. Но тот кто реально работал с вычислительной математикой, тот сомневается во всём. И это правильно. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.04.2021, 01:44 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Задача задана в целочисленной арифметике. Каким образом в тему топика зашли числа с плавающей точкой? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.04.2021, 14:27 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
mayton, я уже часто с удовольствием заглядываю в топик С++, здесь часто теряется грань в С++ и вычислительных алгоритмах... ... |
|||
:
Нравится:
Не нравится:
|
|||
18.04.2021, 22:18 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Поднимем ставки. Сумма разрядов в Stepanoff-style. С хвостовым хвостиком. Код: plaintext 1. 2. 3.
... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 00:01 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
mayton Задача задана в целочисленной арифметике. Каким образом в тему топика зашли числа с плавающей точкой? В целых числах, кроме того, что квадрат всегда равен сумме нечетных чисел, можно использовать знание о том, что 1+ 2+...+(n–1)+n+(n–1)+...+2+1=n^2 = S(n) Тогда S(n+1) = S(n) + n + (n+1)= S(n) + 2n +1 mayton ...Stepanoff-style.... Степанов, в последние годы перед пенсией, занимался уже только тем, что учил программистов продвинутого уровня программировать. В его стиле было бы взять исходную реализацию, с нелинейной зависимостью времени работы от размера задачи, сорта показанной AmKad и, для начала сделать реализацию с линейным временем, на основе или суммирования нечетных чисел или вышеприведенного соотношения, продемонстрировав, что лямбды и функции - это здорово, но еще здоровее бывают процедуры, возвращающие полезный побочный результат. А затем уже перейти к заданию для старших курсов - а можно ли достичь логарифмической зависимости времени работы от размера задачи? На этом этом этапе эксплуатируется знание о том, что полных квадратов между A и B столько, сколько целых чисел между их корнями. Решать ее можно и в действительных числах, с использованием таких оговорок, которые показывают, что ты понимаешь, что делаешь. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 10:52 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
По поводу этого кода. Код: plaintext 1. 2. 3. 4.
мне он не нравится по следующим причинам. Шаблонизация в данном случае сообщает нам, что тип данных нам не важен. Но для данной конкретной задачи нам - очень важно оперировать округлением квадратного корня "с избытком" или "с недостатком". И возможно здесь вместо auto нужно подставлять генерик целочисленного типа чтобы акцентировать внимание на этом а не полагаться абстракции которые неочевидны к явному указанию типа в самой задаче. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 11:09 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
mayton, правда и то, что в своих лекциях/выступлениях/текстах работы с действительными числами Степанов избегал всеми доступными ему способами, отвечая на вопросы вида, "а что если в действительных числах..." длинно, мутно и страшно вращая глазами... Операции с действительными числами не только не коммутативны, с этим так или иначе придется иметь дело, но и не ассоциативны. А вот с этим, все, или почти все обобщенное программирование идет лесом автоматически. А поскольку сверхзадача была обучить не просто программированию, но обобщенному, то на действительные числа приходилось страшно вращать глазами. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 11:14 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
mayton Шаблонизация в данном случае сообщает нам, что тип данных нам не важен. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 11:48 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
mayton По поводу этого кода. Код: plaintext 1. 2. 3. 4.
мне он не нравится по следующим причинам. Шаблонизация в данном случае сообщает нам, что тип данных нам не важен. Но для данной конкретной задачи нам - очень важно оперировать округлением квадратного корня "с избытком" или "с недостатком". В этом коде нет округления. Там есть отбрасывание дробной части. Поэтому для меня не очевидно почему оно всегда должно работать. Это стрёмный, имхо, код. Вот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 12:08 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petravВот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело. Ну да, в этом случае код можно было бы сократить до "return false". Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 13:07 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petrav mayton По поводу этого кода. Код: plaintext 1. 2. 3. 4.
мне он не нравится по следующим причинам. Шаблонизация в данном случае сообщает нам, что тип данных нам не важен. Но для данной конкретной задачи нам - очень важно оперировать округлением квадратного корня "с избытком" или "с недостатком". В этом коде нет округления. Там есть отбрасывание дробной части. Поэтому для меня не очевидно почему оно всегда должно работать. Это стрёмный, имхо, код. Вот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело. Вещественные числа обладают таким странным "гистерезисом", что сложение с небольшим другим вещественным может не оказать влияние на результат. Тоесть если-б я был Степанов - я-бы щас дико вращал глазами и скрипел зубами. Короче обсуждать надо любую попытку микса целочисленных расчетов с вещественными. Хотя... как оптимизацию .. да я ее поддерживаю. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 13:24 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov petravВот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело. Ну да, в этом случае код можно было бы сократить до "return false". Почему же? Это же классическое округление. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 13:24 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
ИМХО плавающая точка тут не самый лучший вариант. Целое не может быть более 52-х бит (размер мантиссы в double), больше приведет к ошибкам. Тут можно обойтись целыми, применить бинарный поиск. Для 64-битного числа результат будет нечетное в диапазоне 1...2 32 -1, т.е. максимум за 31 шаг найдется корень если он есть. Возможно это будет даже быстрее чем std::sqrt() ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 13:31 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
petravПочему же? Это же классическое округление. Потому что именно для данной функции оно даст неверный результат. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 13:35 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov Ну да, в этом случае код можно было бы сократить до "return false". Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27.
... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 13:39 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Для четырехбайтных надо брать не максимальное значение, а чуть меньше, чтобы не перескочить через ноль в цикле. Но на моей машине это все равно долго. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 13:55 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov petravПочему же? Это же классическое округление. Потому что именно для данной функции оно даст неверный результат. Ты имхо чего-то не досмотрел. Ну или пруф в студию. Одно верное входное число для которого будет неверный результат. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 14:13 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
AmKadДля 4-байтных (uint32_t) не дождался результата. Это из-за корня. Он медленный. petravТы имхо чего-то не досмотрел. Да, я недосмотрел, что умножение в return идёт в целых. Posted via ActualForum NNTP Server 1.5 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 14:31 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Проверка на целых Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 14:36 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Dimitry Sibiryakov ... Это из-за корня. Он медленный. ... Корень - единственная из функций, вычисление которой было стандартизировано в самой исходной версии IEEE Поэтому он и быстрый - используются алгоритмы, обладающие не меньше, чем квадратичной сходимостью, с общей зависимостью скорости вычисления результата от входного значения, не хуже log(N), и самый гарантированно точный - точность представимого результата в 0.5ulp Так что медленно не потому, что корень медленный, а потому, что его используют в квадрат лишнее количество раз, вместо того, чтобы просто оценить только края, что и требуется в именно этой задаче. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 14:50 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Dima T Проверка на целых Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
В качестве начального приближения здесь выбирают половину разрядной сетки от максимального значения аргумента. Можно перевести аргумент в double (если экспонента позволяет) и использовать уже расчитанный вещественный корень как первое приближение и потом быстро конвертнуть обратно в arbitrary и уже сделать парочку контрольных выстрелов до достижения точности. Точности снизу или сверху кому как удобно. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.04.2021, 19:54 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Открываем "Алгоритмические трюки" Генри Уоррена-младшего: Глава 11. Некоторые элементарные функции 11.1. Целочисленный квадратный корень. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.04.2021, 06:31 |
|
Счастливые числа
|
|||
---|---|---|---|
#18+
Из наших экспериментов 15 года с простыми числами. Это и была копи-паста из Генри Уоррена. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.
... |
|||
:
Нравится:
Не нравится:
|
|||
20.04.2021, 10:54 |
|
|
start [/forum/search_topic.php?author=igorhh&author_mode=last_topics&do_search=1]: |
0ms |
get settings: |
9ms |
get forum list: |
13ms |
get settings: |
10ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
134ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
63ms |
get tp. blocked users: |
1ms |
others: | 612ms |
total: | 878ms |
0 / 0 |