Определить номер треугольного числа (последовательность 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, будете интересоваться, прикладывать усилия, решать задачи разного уровня - и все придет.

Новые блоги и статьи Все статьи Все блоги /
ИИ и человечность kumehtar 21.07.2026 Забавно, что общаясь с ИИ, я замечаю, насколько он высказывается умно, и насколько верит в людей. Он умеет прощать. Он знает как отвечать не обесценивая опыт других людей, даже если сам не верит. Он. . .	Нейтральные знания ..., ... чистая наука. Пока что-то проходит модерацию на Хабре, стоит развить мысль ... Hrethgir 20.07.2026 К таким радикальным взглядам я конечно в той публикации не приходил, но чтобы скоротать вечер, решил углубиться немного. 1. Почему показания термометра заряжены целью? Цель заложена в самом. . .	Установка нескольких штампов электронной подписи в строго определенных местах файла docx ВладимирСамохин 19.07.2026 (В!) Работа с Электронной подписью - это неотъемлемая часть современного документооборота. Но что делать, если нужно поставить несколько штампов электронной подписи в строго определенных местах. . .	сукцессия 35. Научная статья о проделанной работе anaschu 19.07.2026 Написал в формате латекс и пдф
Вангую, что это не пройдёт модерацию, и на неделе я запущу свой сервер. Hrethgir 19.07.2026 Эта публикация сейчас в песочнице и ждёт приглашения. https:/ / habr. com/ ru/ sandbox/ 295048/ По ссылке 403. Не очень информативно такую ссылку постить. Запись от Usaga размещена Сегодня в 06:46 . . .	сукцессия 33. открытые вопросы от клауде anaschu 19.07.2026 "Что накопилось за эту часть А — тринадцать правок, из которых шесть пришли из ваших вопросов и каждая оказалась реальной ошибкой, а не калибровкой: односторонний симбиоз, отсутствующий листопад,. . .	32 сукцессия anaschu 19.07.2026 сукцессия 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не «подкручивает» сходимость —. . .	сукцессия 31: модель микоризы - это модель ещё нескольких явлений, социальных и экономических anaschu 18.07.2026 Теория «Всего»: апдейт v1. 1. 2 — 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не. . .

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

	Определить номер треугольного числа (последовательность A000217) 24.07.2016, 11:48. Показов 11067. Ответов 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