Определить номер треугольного числа (последовательность A000217)

@KaPJIcOn · Регистрация: 21.01.2016

Студворк — интернет-сервис помощи студентам

Напишите на языке C / C++ программу, определяющую номер треугольного числа (последовательность A000217 в «Энциклопедии целочисленных последовательностей»).

Вход: одно целое (возможно, со знаком «плюс» и символом «перевод строки» \n) число в диапазоне от 1 до 9'223'372'036'854'775'807.

Выход: порядковый номер поданного на вход числа в последовательности треугольных чисел или 0 (ноль), если такого числа в последовательности нет. Символ 0 (ноль) должен выдаваться и во всех случаях подачи на вход некорректных (отрицательных и лежащих вне допустимого диапазона положительных числовых, а также символьных / строковых) данных.

Sample Input:
10
Sample Output:
4

последовательность A000217 : https://oeis.org/A000217

@ilyalesnoi · 31.08.2016, 08:21

_Ivana, я сейчас не в плане придерательств, а наоборот вдохновившись Вашим решением пытаюсь своё изменит на подобии Вашего, но не особо подсмативая, и вспомнил почему я выбрал long double и 128 бит.

Например, если число будет вот таким 9223372036854775806 - то в коде если мы используем unsigned long long тип в переменной t = c*(c+1)/2 - то получается здесь будет переполнение на с*с и далее результат вычислений будет не верен.

Правильно же?

Тогда, здесь

C++
1
v<1 || v>n ? 0 : b==a+1 ? (t==v ? a : t+b==v ? b : 0) : t>v ? f(v,a,c) : f(v,c,b)

если случилось переполнение уже будет некоторый неточный результат?

Правильно? или я могу не видеть некоторую "магию" (не исключаю что в умелых руках и переполнение можно учитывать и высчитывать из него корректный результат)

Добавлено через 58 секунд
конечно интересно, давайте. Судя по всему у Вас хорошая математическая подготовка, а такие решения, основанные на математике - всегда интересно узнавать.

@_Ivana · 31.08.2016, 08:27

Сообщение от ilyalesnoi

Например, если число будет вот таким 9223372036854775806 - то в коде если мы используем unsigned long long тип в переменной t = c*(c+1)/2 - то получается здесь будет переполнение на с*с и далее результат вычислений будет не верен.
Правильно же?

Неправильно

Посмотрите границы, с которыми я вызываю свою функцию - и все поймете. А в процессе рекурсии они только сужаются! Я бы мог а и b вообще unsigned int сделать - просто поленился лишние буквы писать

Поэтому в ull все отлично влезает - можете проверить

Сообщение от ilyalesnoi

конечно интересно, давайте.

Хорошо, но, возможно, сегодня вечером - сейчас у меня пол девятого утра - надо поспать часика 3 перед работой (на которой, кстати, я буду - о боже (С) - промышленно программировать

(С))

@ilyalesnoi · 31.08.2016, 12:09

ну вот там как раз и есть магия) я вставил cout и в первой итерации будет переполнение но оно не не будет учтено, а потом из-за "магии" (границ) получается что из-за сужения потом вычисления числа становится возможным или типа того

вот например: вводим 9069927036051871146
./a.out2
9069927036051871146
2305843008139952128 //вывод t - в первый раз - переполнение
5188146769120198656
7061644213837889536
8106479327253626880
8655918481725718528
8937393458402820096
9079819796601634816
9008465890013872128
9044107658935664640
9061954931675627520
9070885165115375616
9066419498639687680
9068652194438578176
9069768645417238528
9070326896676372480
9070047768899321856
9069908206621409280
9069977987626147840
9069943097090224128
9069925651847428096
9069934374466728960
9069930013156554240
9069927832501860096
9069926742174611328
9069927287338227520
9069927014756417376
9069927151047321936
9069927082901869528
9069927048829143420
9069927031792780390
9069927040310961903
9069927036051871146 // к концу из-за сужений - переполнения нет
9069927036051871146
4259090756

в итоге все работает правильно (ну я долго перебирал возможные почти максимальные числа) мой код тоже работает кстати, просто у меня без магии (и дробями в целочисленной задачи) а у Вас с магией и промежуточными переполнениями- но в итоге все верно - это супер, я и говорю что не исключал что в опытных руках и переполнение можно высчитывать как правильный ход вычислений)

Добавлено через 3 часа 13 минут
хех, не прошло и 21 минуты (ну я правда другим занимался, а ща вернулся к этой темке): я и не заметил что с*с это ж влазит (unsigned int -> ull) - так что это не переполнение )

в общем буду ожидать вашего улучшенного решение, предыдущее мне очень понравилось.

@_Ivana · 31.08.2016, 15:07

Обещанное решение, по просьбам ранимых телезрителей сделано в цикле, без рекурсии - прошу ~~любить и жаловать~~ смотреть и пробовать

. Количество итераций при малых входных аргументах такое же, как и в предыдущем варианте, при больших аргументах количество итераций существенно меньше (у исходного варианта количество итераций всегда одно и то же для любых аргументов). Но здесь чуть посложнее математика, деление опять же, может и съест преимущество - надо миллисекунды замерять. Но если ловить мизерные отличия, тогда и первый вариант надо оптимизировать максимально - сделать циклом вместо рекурсии и попробовать уменьшить тип пары переменных до unsigned int.

C++
1
2
3
4
5
6
7
8
9
10
typedef unsigned long long ull;
ull n = 9223372036854775807;
 
ull g(ull v, ull b) {
    if (v<1 || v>n) return 0;
    ull a;
    do {a = b; b = a - (a*a+a-2*v)/(2*a+1);} while (b<a);
    return b*(b+1)/2 == v ? b : b*(b-1)/2 == v ? b-1 : 0;
}
int main() {ull v; cin>>v; cout<<g(v, numeric_limits<unsigned int>::max());}

@avgoor · 31.08.2016, 18:52

Не по теме:

Сообщение от _Ivana

Но здесь чуть посложнее математика

Ну, так, и написали бы: "берем и решаем уравнение методом касательных". А то тут регулярно всплывают задачи "решить уравение методом...". Студенты их делают, а потом не знают где применить.:)

@VD · 31.08.2016, 19:16

Задача с курса от mail.ru

я её решил)

@_Ivana · 31.08.2016, 20:50

Не по теме:

Сообщение от avgoor

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

Так я про Ньютона на прошлой странице и говорил не скрывая :)

Сообщение от VD

Задача с курса от mail.ru

Понятно откуда халявщики тогда

@avgoor · 31.08.2016, 22:55

Не по теме:

Сообщение от _Ivana

Так я про Ньютона на прошлой странице и говорил не скрывая

Наискосок читал, не заметил.

@ilyalesnoi · 05.09.2016, 20:37

_Ivana,

Обещанное решение, по просьбам ранимых телезрителей сделано в цикле, без рекурсии - прошу

спасибо, красивое решение)

@Vorthys · 19.04.2017, 15:43

Сообщение от _Ivana

Посмотрите границы, с которыми я вызываю свою функцию - и все поймете

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

Вернее, понятно, почему верх ограничен максимумом от uint, но почему мы стартуем с этого значения всегда?

У нас же номер для всех треугольных чисел, кроме 1 и 3, заведомо меньше 1/2 от этого треугольного числа. То есть вот делить исходное число на 2 можно сходу, уже сразу сужая границы поиска. В чем смысл постоянного старта алгоритма с самого правого края допустимых значений? Проверял на куче разных произвольных значений, заменяя правую границу на v/2 + 1 (+1 нужен на случай ввода 1 или 3), всё отлично работает. Чего я не понимаю?

@_Ivana · 19.04.2017, 17:00

Сообщение от Vorthys

Чего я не понимаю?

Если не ошибаюсь - того, что "деленное на 2 исходное число" при данном диапазоне входных данных вылезет за границу uint, и соответственно при возведении в квадрат вылезет за ull - и все поломается

Но методом прямого расчета было выяснено, что для максимального входного треугольного числа его номер не превышает uint

Отсюда и стартовый диапазон. Другими словами, чтобы остаться в рамках убогих целочисленных типов С++ без привлечения библиотек длинной арифметики.

@Vorthys · 19.04.2017, 22:11

Сообщение от _Ivana

"деленное на 2 исходное число" при данном диапазоне входных данных вылезет за границу uint, и соответственно при возведении в квадрат вылезет за ull

Да, именно этот момент я и не учел, спасибо. Причем, стоило вам написать, и сразу же убедительно нашлось значение, на котором код с моей модификацией давал переполнение и неправильный ответ. ) Хотя было бы интересно сравнить по скорости и такие варианты. Подскажите, такому мышлению где-то учат, или оно только с опытом приходит? Или вообще врожденное? ))

@_Ivana · 19.04.2017, 23:14

Vorthys, будете интересоваться, прикладывать усилия, решать задачи разного уровня - и все придет.

Новые блоги и статьи Все статьи Все блоги /
сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .	Сукцессия 20. Война автоботов. Делаем ставки. Лёд против "пш-пш!". anaschu 11.07.2026 Битва ИИ в ризосфере: Как мы скрестили жесткие ОДУ, закон Фика и «подземный шантаж» Уважаемые коллеги! Хочу поделиться уникальным опытом ведения междисциплинарной компьютерной разработки. Прямо. . .	Сукцессия 19. Какие выводы я сделал из модели? Часть 2.Внутримикоризный стехиометрический буфер и хроно-дискретные зоны экспансии anaschu 11.07.2026 Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования	Сукцессия 18. Какие выводы я сделал из войны грибов с деревьями? Часть 1- рассказ и немного про термины anaschu 11.07.2026 Био-Инженерный Ликбез: Архитектура Модели Ризосферы Математический аппарат моделирования Система ОДУ описывает динамику изменения массы различных компонентов системы во времени. Ключевой. . .
Просветление в 5 секунд kumehtar 10.07.2026 Андрей Веретенников выдал фразу недавно: "Вам не обязательно кем-то себя считать"	Эксперимент с картинкой-обложкой на CodinGame Adler 10.07.2026 Решил на днях провести эксперимент. У меня есть аккаунт на CodinGame, ТОП-3 по РФ среди 2200 участников (в разделе соревнования по программированию ИИ-ботов). Там есть обложка, куда можно влепить. . .	GitDOS: Когда я решил скрестить MS-DOS, GitHub и Claude MaGz GoLd 08.07.2026 Привет, Киберфорум! Хочу поделиться своим проектом, который, надеюсь, вас заинтересует. GitDOS — это веб-приложение, которое позволяет запускать DOS в браузере с тремя крутыми фичами: диски живут в. . .	Учебный мини "цифровой двойник" = (Сервер = Java + Flask_питон )+(3D = Гугловскаая 4T nvideo + google colab) +( WMS = Odoo на Docker) anaschu 07.07.2026 Увидел в требованиях к вакансии создателя имитационных моделей связку (REst + Api + WMS + Anylogic + питон + 3D Nvideo), и решил посмотреть, что это такое. Из этого всего я работал более менее. . .

@KaPJIcOn 0 / 0 / 0 Регистрация: 21.01.2016 Сообщений: 36

	Определить номер треугольного числа (последовательность A000217) 24.07.2016, 11:48. Показов 11056. Ответов 32 Метки нет (Все метки) Напишите на языке C / C++ программу, определяющую номер треугольного числа (последовательность A000217 в «Энциклопедии целочисленных последовательностей»). Вход: одно целое (возможно, со знаком «плюс» и символом «перевод строки» \n) число в диапазоне от 1 до 9'223'372'036'854'775'807. Выход: порядковый номер поданного на вход числа в последовательности треугольных чисел или 0 (ноль), если такого числа в последовательности нет. Символ 0 (ноль) должен выдаваться и во всех случаях подачи на вход некорректных (отрицательных и лежащих вне допустимого диапазона положительных числовых, а также символьных / строковых) данных. Sample Input: 10 Sample Output: 4 последовательность A000217 : https://oeis.org/A000217 0

@ilyalesnoi 3 / 2 / 1 Регистрация: 30.08.2016 Сообщений: 12
	31.08.2016, 12:09
	ну вот там как раз и есть магия) я вставил cout и в первой итерации будет переполнение но оно не не будет учтено, а потом из-за "магии" (границ) получается что из-за сужения потом вычисления числа становится возможным или типа того вот например: вводим 9069927036051871146 ./a.out2 9069927036051871146 2305843008139952128 //вывод t - в первый раз - переполнение 5188146769120198656 7061644213837889536 8106479327253626880 8655918481725718528 8937393458402820096 9079819796601634816 9008465890013872128 9044107658935664640 9061954931675627520 9070885165115375616 9066419498639687680 9068652194438578176 9069768645417238528 9070326896676372480 9070047768899321856 9069908206621409280 9069977987626147840 9069943097090224128 9069925651847428096 9069934374466728960 9069930013156554240 9069927832501860096 9069926742174611328 9069927287338227520 9069927014756417376 9069927151047321936 9069927082901869528 9069927048829143420 9069927031792780390 9069927040310961903 9069927036051871146 // к концу из-за сужений - переполнения нет 9069927036051871146 4259090756 в итоге все работает правильно (ну я долго перебирал возможные почти максимальные числа) мой код тоже работает кстати, просто у меня без магии (и дробями в целочисленной задачи) а у Вас с магией и промежуточными переполнениями- но в итоге все верно - это супер, я и говорю что не исключал что в опытных руках и переполнение можно высчитывать как правильный ход вычислений) Добавлено через 3 часа 13 минут хех, не прошло и 21 минуты (ну я правда другим занимался, а ща вернулся к этой темке): я и не заметил что с*с это ж влазит (unsigned int -> ull) - так что это не переполнение ) в общем буду ожидать вашего улучшенного решение, предыдущее мне очень понравилось. 0

@VD 24 / 13 / 3 Регистрация: 02.08.2012 Сообщений: 160
	31.08.2016, 19:16
	Задача с курса от mail.ru я её решил) 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	19.04.2017, 23:14
	Vorthys, будете интересоваться, прикладывать усилия, решать задачи разного уровня - и все придет. 0