Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Счастливые числа  [new]
Omikami
Member

Откуда:
Сообщений: 1
Счастливые числа - числа сума цифр числа является квадратом какого-то целого числа.Нужно посчитать, сколько счастливых чисел является на отрезке от А до В (включая А и В).

Пример входных и выходных данных

Введение: 1 15
Вывод: 5

Комментарий. Счастливыми на отрезке [1, 15] является числа 1, 4, 9, 10, 13.
15 апр 21, 18:18    [22309486]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 53394

Omikami
Нужно посчитать

Удачи!
https://www.sql.ru/forum/940953/posobie-dlya-studentov-i-shkolnikov

Posted via ActualForum NNTP Server 1.5

15 апр 21, 18:34    [22309501]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
Omikami,

#include <iostream>
#include <deque>

using numberType = unsigned;

template<typename T>
void findNumbers(numberType From, numberType To, T Inserter) {
    auto sumDigits = [](numberType Value) {
        numberType Sum = 0;
        while (Value) {
            Sum += Value % 10;
            Value /= 10;
        }
        return Sum;
    };

    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };

    for (auto i = From; i <= To; ++i) {
        if (isSquare(sumDigits(i))) {
            Inserter = i;
        }
    }
}

int main() {
    std::deque<numberType> d;
    findNumbers(1, 200, std::back_inserter(d));

    for (const auto& v : d) {
        std::cout << v << std::endl;
    }

    return 0;
}
+ output
1
4
9
10
13
18
22
27
31
36
40
45
54
63
72
79
81
88
90
97
100
103
108
112
117
121
126
130
135
144
153
162
169
171
178
180
187
196
16 апр 21, 16:40    [22309929]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
AmKad,

Продемонстрировал знание С++17. ТС не сможет такую лабу защитить, а принимающий доцент не сможет понять что там написано.
16 апр 21, 19:26    [22309999]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
petrav
ТС не сможет такую лабу защитить, а принимающий доцент не сможет понять что там написано.
Ага. Я и не ставил себе целью получение зачета этим студентом. Увидел задачку - пальчики размять захотелось.

petrav

Продемонстрировал знание С++17.
Мне казалось, я за рамки 11-го стандарта не выходил.
16 апр 21, 19:32    [22310000]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
AmKad,

Хорошо. Ты уверен что в рамках такого кода:

    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };

И в рамках пространства unsigned не существует квадратного числа, такого что твоя лямбда вернёт false?
16 апр 21, 19:43    [22310004]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
petrav,

Нет, не уверен.
16 апр 21, 19:47    [22310005]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
petrav,

Видите, как интересно. Теперь Вы принимающий доцент, а я студент. Подумаю, может быть есть другое решение.
16 апр 21, 19:51    [22310007]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
AmKad
petrav,

Видите, как интересно. Теперь Вы принимающий доцент, а я студент. Подумаю, может быть есть другое решение.

Ну я не доцент. Просто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы. Давайте думать.
16 апр 21, 19:57    [22310009]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
petrav,

Нашел тут утверждение, что "любой квадрат это сумма последовательных нечетных чисел".

    auto isSquare = [](numberType Value) {
        numberType i = 1;
        numberType n = 0;
        while (n < Value) {
            n += i;
            i += 2;
        };
        return (n == Value);
    };

Похоже автор не врал.

Сообщение было отредактировано: 16 апр 21, 20:02
16 апр 21, 20:08    [22310012]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
AmKad
petrav,

Нет, не уверен.

Я не смог найти таких чисел. Но это не отрицает факта, что там где плавающая точка, то там бывают чудеса.
16 апр 21, 21:19    [22310030]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 53394
petrav
Просто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы.

Во-первых, они предсказуемые. Во-вторых, в области без дробной части в пределах точности их нет.

Сообщение было отредактировано: 16 апр 21, 22:01
16 апр 21, 22:09    [22310049]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
Dimitry Sibiryakov
petrav
Просто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы.
Во-вторых, в области без дробной части в пределах точности их нет.

Что, простите?
16 апр 21, 22:22    [22310055]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 53394

petrav
Что, простите?

Два в квадрате всегда ровно четыре. Три в квадрате всегда ровно девять. И так далее.

Posted via ActualForum NNTP Server 1.5

17 апр 21, 00:24    [22310078]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
Dimitry Sibiryakov

petrav
Что, простите?

Два в квадрате всегда ровно четыре. Три в квадрате всегда ровно девять. И так далее.

Понятно, с целыми числами обычно проблем не возникает. Но тот кто реально работал с
вычислительной математикой, тот сомневается во всём. И это правильно.
17 апр 21, 01:44    [22310087]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
Задача задана в целочисленной арифметике. Каким образом в тему топика зашли числа с плавающей точкой?
18 апр 21, 14:27    [22310555]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Alex_Ustinov
Member

Откуда: Nickel
Сообщений: 3797
mayton,

я уже часто с удовольствием заглядываю в топик С++, здесь часто теряется грань в С++ и вычислительных алгоритмах...
18 апр 21, 22:18    [22310663]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
Поднимем ставки.

Сумма разрядов в Stepanoff-style. С хвостовым хвостиком.

numberType sumDigits(numberType Value, numberType Sum = 0) {
    return Value > 0 ? sumDigits(Value / 10, Sum + Value % 10) : Sum;
};


Сообщение было отредактировано: 18 апр 21, 23:53
19 апр 21, 00:01    [22310689]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
booby
Member

Откуда:
Сообщений: 2534
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 апр 21, 10:45
19 апр 21, 10:52    [22310798]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
По поводу этого кода.

    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };


мне он не нравится по следующим причинам.

Шаблонизация в данном случае сообщает нам, что тип данных нам не важен.
Но для данной конкретной задачи нам - очень важно оперировать округлением
квадратного корня "с избытком" или "с недостатком".

И возможно здесь вместо auto нужно подставлять генерик целочисленного
типа чтобы акцентировать внимание на этом а не полагаться абстракции которые
неочевидны к явному указанию типа в самой задаче.
19 апр 21, 11:09    [22310811]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
booby
Member

Откуда:
Сообщений: 2534
mayton,



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

Операции с действительными числами не только не коммутативны, с этим так или иначе придется иметь дело,
но и не ассоциативны.

А вот с этим, все, или почти все обобщенное программирование идет лесом автоматически.
А поскольку сверхзадача была обучить не просто программированию, но обобщенному,
то на действительные числа приходилось страшно вращать глазами.

Сообщение было отредактировано: 19 апр 21, 11:07
19 апр 21, 11:14    [22310815]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
AmKad
Member

Откуда:
Сообщений: 5297
mayton
Шаблонизация в данном случае сообщает нам, что тип данных нам не важен.
Не путайте шаблонизацию (обобщенное программирование) и объявление алиаса для целочисленного типа.
19 апр 21, 11:48    [22310840]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

Откуда:
Сообщений: 2944
mayton
По поводу этого кода.

    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };


мне он не нравится по следующим причинам.

Шаблонизация в данном случае сообщает нам, что тип данных нам не важен.
Но для данной конкретной задачи нам - очень важно оперировать округлением
квадратного корня "с избытком" или "с недостатком".

В этом коде нет округления. Там есть отбрасывание дробной части. Поэтому для
меня не очевидно почему оно всегда должно работать. Это стрёмный, имхо, код.
Вот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело.
19 апр 21, 12:08    [22310855]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 53394

petrav
Вот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело.

Ну да, в этом случае код можно было бы сократить до "return false".

Posted via ActualForum NNTP Server 1.5

19 апр 21, 13:07    [22310897]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
petrav
mayton
По поводу этого кода.

    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };


мне он не нравится по следующим причинам.

Шаблонизация в данном случае сообщает нам, что тип данных нам не важен.
Но для данной конкретной задачи нам - очень важно оперировать округлением
квадратного корня "с избытком" или "с недостатком".

В этом коде нет округления. Там есть отбрасывание дробной части. Поэтому для
меня не очевидно почему оно всегда должно работать. Это стрёмный, имхо, код.
Вот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело.

Вещественные числа обладают таким странным "гистерезисом", что сложение с небольшим другим вещественным
может не оказать влияние на результат. Тоесть если-б я был Степанов - я-бы щас дико вращал глазами и
скрипел зубами. Короче обсуждать надо любую попытку микса целочисленных расчетов с вещественными.

Хотя... как оптимизацию .. да я ее поддерживаю.
19 апр 21, 13:24    [22310913]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / C++ Ответить