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

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

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

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

Почему же? Это же классическое округление.
19 апр 21, 13:24    [22310914]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dima T
Member

Откуда:
Сообщений: 15795
ИМХО плавающая точка тут не самый лучший вариант. Целое не может быть более 52-х бит (размер мантиссы в double), больше приведет к ошибкам.

Тут можно обойтись целыми, применить бинарный поиск. Для 64-битного числа результат будет нечетное в диапазоне 1...232-1, т.е. максимум за 31 шаг найдется корень если он есть. Возможно это будет даже быстрее чем std::sqrt()

Сообщение было отредактировано: 19 апр 21, 13:23
19 апр 21, 13:31    [22310920]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

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

petrav
Почему же? Это же классическое округление.

Потому что именно для данной функции оно даст неверный результат.

Posted via ActualForum NNTP Server 1.5

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

Откуда:
Сообщений: 5297
Dimitry Sibiryakov
Ну да, в этом случае код можно было бы сократить до "return false".
Немного изменил иходный пример кода. Исходную функцию переименовал в isSquare_01, вторую назвал isSquare_02, в ней добавил сложение с 0.5F, чтобы сравнить результаты их выполнения. Сошлось на всем диапазоне двухбайтных целых беззнаковых чисел. Для 4-байтных (uint32_t) не дождался результата. И шаблонизацию убрал, чтобы впечатлительных не смущало.
#include <iostream>
#include <limits>

using numberType = unsigned;

void findNumbers(numberType From, numberType To) {
    auto isSquare_01 = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };

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

    for (auto i = From; i <= To; ++i) {
        if (isSquare_01(i) != isSquare_02(i)) {
            std::cout << i << std::endl;
        }
    }
}

int main() {
    findNumbers(1, /*std::numeric_limits<numberType>::max()*/std::numeric_limits<uint16_t>::max());
    return 0;
}


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

Откуда:
Сообщений: 5297
Для четырехбайтных надо брать не максимальное значение, а чуть меньше, чтобы не перескочить через ноль в цикле. Но на моей машине это все равно долго.
19 апр 21, 13:55    [22310950]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
petrav
Member

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

petrav
Почему же? Это же классическое округление.

Потому что именно для данной функции оно даст неверный результат.

Ты имхо чего-то не досмотрел. Ну или пруф в студию. Одно верное входное число для которого будет неверный результат.
19 апр 21, 14:13    [22310969]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dimitry Sibiryakov
Member

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

AmKad
Для 4-байтных (uint32_t) не дождался результата.

Это из-за корня. Он медленный.

petrav
Ты имхо чего-то не досмотрел.

Да, я недосмотрел, что умножение в return идёт в целых.

Posted via ActualForum NNTP Server 1.5

19 апр 21, 14:31    [22310987]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Dima T
Member

Откуда:
Сообщений: 15795
Проверка на целых
bool is_square(uint64_t n) {
	uint64_t l = 1, r = 0xFFFFFFFF;
	while (l < r) {
		uint64_t m = l + (r - l) / 2;
		uint64_t m2 = m*m;

		if (m2 == n)
			return true;

		if (m2 > n)
			r = m;
		else
			l = m+1;
	}
	return l*l == n;
}
19 апр 21, 14:36    [22310991]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
booby
Member

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

...
Это из-за корня. Он медленный.
...

Корень - единственная из функций, вычисление которой было стандартизировано в самой исходной версии IEEE
Поэтому он и быстрый - используются алгоритмы, обладающие не меньше, чем квадратичной сходимостью,
с общей зависимостью скорости вычисления результата от входного значения, не хуже log(N),
и самый гарантированно точный - точность представимого результата в 0.5ulp

Так что медленно не потому, что корень медленный, а потому, что его используют в квадрат лишнее количество раз,
вместо того, чтобы просто оценить только края, что и требуется в именно этой задаче.
19 апр 21, 14:50    [22311012]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
Dima T
Проверка на целых
bool is_square(uint64_t n) {
	uint64_t l = 1, r = 0xFFFFFFFF;
	while (l < r) {
		uint64_t m = l + (r - l) / 2;
		uint64_t m2 = m*m;

		if (m2 == n)
			return true;

		if (m2 > n)
			r = m;
		else
			l = m+1;
	}
	return l*l == n;
}

В качестве начального приближения здесь выбирают половину разрядной сетки от максимального значения
аргумента.

Можно перевести аргумент в double (если экспонента позволяет) и использовать уже
расчитанный вещественный корень как первое приближение и потом быстро конвертнуть обратно
в arbitrary и уже сделать парочку контрольных выстрелов до достижения точности.

Точности снизу или сверху кому как удобно.
19 апр 21, 19:54    [22311228]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 11020
Открываем "Алгоритмические трюки" Генри Уоррена-младшего:
Глава 11. Некоторые элементарные функции
11.1. Целочисленный квадратный корень.
20 апр 21, 06:31    [22311300]     Ответить | Цитировать Сообщить модератору
 Re: Счастливые числа  [new]
mayton
Member

Откуда: loopback
Сообщений: 51389
Из наших экспериментов 15 года с простыми числами. Это и была копи-паста из Генри Уоррена.

uint64_t isqrt64(uint64_t x) {	
	uint64_t x1;
	uint64_t s, g0, g1;
	if (x <= 1) return x;
	s = 1;
	x1 = x - 1;
      if (x1 > 0x100000000 - 1)     { s+=16; x1>>=32;}
	if (x1 > 0x10000     - 1)     { s+=8;  x1>>=16;}
	if (x1 > 0x100       - 1)     { s+=4;  x1>>=8; }
	if (x1 > 0x10        - 1)     { s+=2;  x1>>=4; }
	if (x1 > 3)                   { s+=1; }
	g0 = 1<<s;
	g1 = (g0 + (x >> s)) >> 1;
	while(g1 < g0) {
		g0 = g1;
		g1 = (g0 + (x/g0)) >> 1;
	}
	return g0;
}
20 апр 21, 10:54    [22311370]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / C++ Ответить