powered by simpleCommunicator - 2.0.52     © 2025 Programmizd 02
Форумы / C++ [игнор отключен] [закрыт для гостей] / Счастливые числа
37 сообщений из 37, показаны все 2 страниц
Счастливые числа
    #40062836
Omikami
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Счастливые числа - числа сума цифр числа является квадратом какого-то целого числа.Нужно посчитать, сколько счастливых чисел является на отрезке от А до В (включая А и В).

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

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

Комментарий. Счастливыми на отрезке [1, 15] является числа 1, 4, 9, 10, 13.
...
Рейтинг: 0 / 0
Счастливые числа
    #40062843
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
OmikamiНужно посчитать

Удачи!
https://www.sql.ru/forum/940953/posobie-dlya-studentov-i-shkolnikov
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Счастливые числа
    #40063112
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
#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
Код: 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.
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

...
Рейтинг: 0 / 0
Счастливые числа
    #40063166
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AmKad,

Продемонстрировал знание С++17. ТС не сможет такую лабу защитить, а принимающий доцент не сможет понять что там написано.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063167
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav
ТС не сможет такую лабу защитить, а принимающий доцент не сможет понять что там написано.
Ага. Я и не ставил себе целью получение зачета этим студентом. Увидел задачку - пальчики размять захотелось.

petrav

Продемонстрировал знание С++17.
Мне казалось, я за рамки 11-го стандарта не выходил.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063171
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AmKad,

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

Код: plaintext
1.
2.
3.
4.
    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };


И в рамках пространства unsigned не существует квадратного числа, такого что твоя лямбда вернёт false?
...
Рейтинг: 0 / 0
Счастливые числа
    #40063172
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav,

Нет, не уверен.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063173
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav,

Видите, как интересно. Теперь Вы принимающий доцент, а я студент. Подумаю, может быть есть другое решение.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063175
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AmKad
petrav,

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

Ну я не доцент. Просто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы. Давайте думать.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063178
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav,

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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
    auto isSquare = [](numberType Value) {
        numberType i = 1;
        numberType n = 0;
        while (n < Value) {
            n += i;
            i += 2;
        };
        return (n == Value);
    };


Похоже автор не врал.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063189
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AmKad
petrav,

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

Я не смог найти таких чисел. Но это не отрицает факта, что там где плавающая точка, то там бывают чудеса.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063207
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petravПросто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы.

Во-первых, они предсказуемые. Во-вторых, в области без дробной части в пределах точности их нет.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063210
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
petravПросто там где фигурируют плавающие точки, я знаю, там непредсказуемые проблемы.
Во-вторых, в области без дробной части в пределах точности их нет.
Что, простите?
...
Рейтинг: 0 / 0
Счастливые числа
    #40063231
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petravЧто, простите?

Два в квадрате всегда ровно четыре. Три в квадрате всегда ровно девять. И так далее.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Счастливые числа
    #40063240
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov

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

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

Понятно, с целыми числами обычно проблем не возникает. Но тот кто реально работал с
вычислительной математикой, тот сомневается во всём. И это правильно.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063582
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задача задана в целочисленной арифметике. Каким образом в тему топика зашли числа с плавающей точкой?
...
Рейтинг: 0 / 0
Счастливые числа
    #40063651
Фотография Alex_Ustinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

я уже часто с удовольствием заглядываю в топик С++, здесь часто теряется грань в С++ и вычислительных алгоритмах...
...
Рейтинг: 0 / 0
Счастливые числа
    #40063666
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Поднимем ставки.

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

Код: plaintext
1.
2.
3.
numberType sumDigits(numberType Value, numberType Sum = 0) {
    return Value > 0 ? sumDigits(Value / 10, Sum + Value % 10) : Sum;
};
...
Рейтинг: 0 / 0
Счастливые числа
    #40063734
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 столько, сколько целых чисел между их корнями.
Решать ее можно и в действительных числах, с использованием таких оговорок, которые показывают, что ты понимаешь, что делаешь.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063743
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По поводу этого кода.

Код: plaintext
1.
2.
3.
4.
    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };



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

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

И возможно здесь вместо auto нужно подставлять генерик целочисленного
типа чтобы акцентировать внимание на этом а не полагаться абстракции которые
неочевидны к явному указанию типа в самой задаче.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063747
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,



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

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

А вот с этим, все, или почти все обобщенное программирование идет лесом автоматически.
А поскольку сверхзадача была обучить не просто программированию, но обобщенному,
то на действительные числа приходилось страшно вращать глазами.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063766
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Шаблонизация в данном случае сообщает нам, что тип данных нам не важен.
Не путайте шаблонизацию (обобщенное программирование) и объявление алиаса для целочисленного типа.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063778
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
По поводу этого кода.

Код: plaintext
1.
2.
3.
4.
    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };



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

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

В этом коде нет округления. Там есть отбрасывание дробной части. Поэтому для
меня не очевидно почему оно всегда должно работать. Это стрёмный, имхо, код.
Вот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063812
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petravВот если бы написали так: `std::sqrt(Value)+0.5`. Другое дело.

Ну да, в этом случае код можно было бы сократить до "return false".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Счастливые числа
    #40063821
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petrav
mayton
По поводу этого кода.

Код: plaintext
1.
2.
3.
4.
    auto isSquare = [](numberType Value) {
        const auto Sqrt = static_cast<decltype(Value)>(std::sqrt(Value));
        return Sqrt * Sqrt == Value;
    };



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

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

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

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

Хотя... как оптимизацию .. да я ее поддерживаю.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063822
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov

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

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

Почему же? Это же классическое округление.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063827
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ИМХО плавающая точка тут не самый лучший вариант. Целое не может быть более 52-х бит (размер мантиссы в double), больше приведет к ошибкам.

Тут можно обойтись целыми, применить бинарный поиск. Для 64-битного числа результат будет нечетное в диапазоне 1...2 32 -1, т.е. максимум за 31 шаг найдется корень если он есть. Возможно это будет даже быстрее чем std::sqrt()
...
Рейтинг: 0 / 0
Счастливые числа
    #40063831
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
petravПочему же? Это же классическое округление.

Потому что именно для данной функции оно даст неверный результат.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Счастливые числа
    #40063835
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov
Ну да, в этом случае код можно было бы сократить до "return false".
Немного изменил иходный пример кода. Исходную функцию переименовал в isSquare_01, вторую назвал isSquare_02, в ней добавил сложение с 0.5F, чтобы сравнить результаты их выполнения. Сошлось на всем диапазоне двухбайтных целых беззнаковых чисел. Для 4-байтных (uint32_t) не дождался результата. И шаблонизацию убрал, чтобы впечатлительных не смущало.
Код: 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.
#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;
}
...
Рейтинг: 0 / 0
Счастливые числа
    #40063849
Фотография AmKad
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Для четырехбайтных надо брать не максимальное значение, а чуть меньше, чтобы не перескочить через ноль в цикле. Но на моей машине это все равно долго.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063862
petrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov

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

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

Ты имхо чего-то не досмотрел. Ну или пруф в студию. Одно верное входное число для которого будет неверный результат.
...
Рейтинг: 0 / 0
Счастливые числа
    #40063873
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
AmKadДля 4-байтных (uint32_t) не дождался результата.

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

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

Да, я недосмотрел, что умножение в return идёт в целых.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Счастливые числа
    #40063876
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Проверка на целых
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
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;
}
...
Рейтинг: 0 / 0
Счастливые числа
    #40063889
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov

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

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

Так что медленно не потому, что корень медленный, а потому, что его используют в квадрат лишнее количество раз,
вместо того, чтобы просто оценить только края, что и требуется в именно этой задаче.
...
Рейтинг: 0 / 0
Счастливые числа
    #40064002
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Проверка на целых
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
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 и уже сделать парочку контрольных выстрелов до достижения точности.

Точности снизу или сверху кому как удобно.
...
Рейтинг: 0 / 0
Счастливые числа
    #40064054
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Открываем "Алгоритмические трюки" Генри Уоррена-младшего:
Глава 11. Некоторые элементарные функции
11.1. Целочисленный квадратный корень.
...
Рейтинг: 0 / 0
Счастливые числа
    #40064102
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Из наших экспериментов 15 года с простыми числами. Это и была копи-паста из Генри Уоррена.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
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;
}
...
Рейтинг: 0 / 0
37 сообщений из 37, показаны все 2 страниц
Форумы / C++ [игнор отключен] [закрыт для гостей] / Счастливые числа
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]