|
Модераторы: bsa |
|
altairaimenov |
|
|||
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 3.3.2015 Репутация: нет Всего: нет |
Добрый день! Нам даётся число n. Необходимо ставить поочередно "+" и "-" между цифрами от 1 до n и вывести результат примера
Ограничение : 0.5 секунды n - 10^15 Пример: 12 Ответ: 5 Поясняю: +1 -2 +3 -4 +5 -6 +7 -8 +9 -1+0 -1+1 -1+2 = 5 P.s. Язык - C++ Это сообщение отредактировал(а) altairaimenov - 5.3.2015, 20:11 |
|||
|
||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Ну а что у вас не получается то? мы тут все такие помогаем, а то я смотрю вы обрадовались что за вас все вчера решили
|
|||
|
||||
altairaimenov |
|
|||
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 3.3.2015 Репутация: нет Всего: нет |
Дело в том что N = 10^15. Тривиальный алгоритм я могу написать,но он до 10^7.Я просто искал форумы где я могу просить помощи в нерешенных мной задач.Занимаюсь я не ради кого-то,а ради себя. Думаю понятно Это сообщение отредактировал(а) altairaimenov - 5.3.2015, 20:12 |
|||
|
||||
sQu1rr |
|
|||
Опытный Профиль Группа: Участник Сообщений: 597 Регистрация: 11.11.2008 Где: london Репутация: 3 Всего: 13 |
Здесь есть раздел - алгоритмы, там помогают именно с ними. Но не надо уже дублировать. Есть какиенибудь идеи - как решить? |
|||
|
||||
konshyn |
|
|||
Опытный Профиль Группа: Участник Сообщений: 295 Регистрация: 19.9.2013 Репутация: нет Всего: нет |
Обыная задачка на последовательности:
суммы: 1..9 = 5 10..99 = 45 100..999 = 450 1000..9999 = 4500. Так как на нужно записывать цифры по порядку, то: числа с нечетным набором цифр имеют положительные суммы, с четным - отрицательные, т.е., например, нам нужно найти сумму от 1 до 99 999, то будет такая последовательность: +5 -45 + 450 - 4500 + 45000 = 40910. Тут понятно, что сложить 5 чисел намного быстрее, чем пускать 5 циклов, чтобы посчитать от 1 до 100 000, или как Вы там считаете. Я думаю, что дальше сами справитесь с анализом цифр. -------------------- «Потому что ценность акта действия в этой стране возрастает в несколько раз». |
|||
|
||||
feodorv |
|
|||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
Как-то я не уверен, что здесь будет знакопеременный ряд. В обоснование приведу такое соображение. Рассмотрим знакоинвертированный ряд (для удобства):
Тогда в подпоследовательности 0..9 будет четное число членов, и 1 от числа 10 пойдет со знаком +. В подпоследовательности 10..99 опять-таки будет четное число членов, и 1 от числа 100 пойдет со знаком +. В подпоследовательности 100..999 опять-таки будет четное число членов, и 1 от числа 1000 пойдет со знаком +. И так далее. Для чисел с нечетным числом цифр всё вообще элементарно. -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
|||
|
||||
konshyn |
|
|||
Опытный Профиль Группа: Участник Сообщений: 295 Регистрация: 19.9.2013 Репутация: нет Всего: нет |
1) Прежде, чем написать, я проверил:) 2) Знакоинвертированный ряд здесь не может быть примером, т.к. автор написал, как выглядит последовательность. Да:) -------------------- «Потому что ценность акта действия в этой стране возрастает в несколько раз». |
|||
|
||||
feodorv |
|
|||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
Вот это одобряю! Ну тогда частичные суммы имеют иной вид:
А общая сумма такая: 5 - (45 - 450 + 4500 - 45000) Почему? Трудно в конце знак поменять?))) Такой ряд удобен, потому что для него частичные суммы 0..9 = -5 10..99 = 45 100..999 = -450 1000..9999 = 4500 10000..99999 = -45000 тупо складываются, а итоговая сумма выглядит проще: -(-5+45-450+4500-45000). Если что, то я тоже проверял))) -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
|||
|
||||
konshyn |
|
|||
Опытный Профиль Группа: Участник Сообщений: 295 Регистрация: 19.9.2013 Репутация: нет Всего: нет |
Вы правы, более удобное решение за Вами:) -------------------- «Потому что ценность акта действия в этой стране возрастает в несколько раз». |
|||
|
||||
feodorv |
|
||||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
konshyn, да там удобства кот наплакал, но все же)))
Благодаря тому, что сумма ряда
равна нулю, для чисел с четным числом цифр возможно рассчитать частичную сумму от 100..0 до abc..z (а это то, что не доставало))) путем редуцирования начального числа делением на 100 (что подразумевает индукцию). С учетом некоторых хитростей программа для вычисления частичных сумм произвольных четноцифровых (черт, как это одним словом сказать?) чисел приобрела вид:
Если это всё ещё интересно Альтаиру, то расскажу, как она получилась. Это сообщение отредактировал(а) feodorv - 11.3.2015, 04:08 -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
||||
|
|||||
konshyn |
|
|||
Опытный Профиль Группа: Участник Сообщений: 295 Регистрация: 19.9.2013 Репутация: нет Всего: нет |
feodorv, мне интересно. Напишите, пожалуйста
-------------------- «Потому что ценность акта действия в этой стране возрастает в несколько раз». |
|||
|
||||
altairaimenov |
|
|||
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 3.3.2015 Репутация: нет Всего: нет |
||||
|
||||
feodorv |
|
||||||||||||||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
Да, давайте сейчас, а то потом всё забудется...
Несколько предварительных замечаний.
-------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
||||||||||||||
|
|||||||||||||||
feodorv |
|
||||||||||||||||||||||||||||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
Если представить четноцифровое число N в виде 100*A+B, то так и хочется написать
А теперь эту формулу будем суммировать от 10^(n-1) до N. Возьмем для примера число 8765 (для него A=87, B=65). Понятно, что
То есть неполную частичную сумму мы разбили на две суммы - основную (в которой участвуют пачки по 100 штук чисел:
и остаточную (с неполной сотней чисел). С учетом вышеприведенной формулы основная сумма приобретает вид:
Удивительно, но в сумме SUM(A:10..86) T(A) мы неожиданно узнаем S(10..86) (то есть неполную частичную сумму для числа, которое в 100 меньше изначального, и ещё на единицу, это важно). А вторая сумма оказывается равной 0! То есть суммирование сотнями приводит нас к редукции задачи Здесь мы, пожалуй впервые сталкиваемся с рядом
полная сумма которого равна 0))) В дальнейшем нам придётся иметь дело с неполной суммой этого ряда, поэтому давайте на нём остановимся поподробнее. Обозначим через R(X) (где X - натуральное число, меньшее 100) следующую сумму
Мы уже убедились, что R(99) равно 0. Для числа X, представленного в виде 10*a+b (здесь a и b - цифры двухциферного числа X), аналитически можно найти значение
Что легко проверить программным путем. Но, проще, всё же, определить массив R[100] и заполнить его в начале программы, что и делает функция rFill(). Тем не менее, у нас есть ещё остаточная сумма, давайте её найдём:
В общем случае, если представить четноцифровое число N в виде 100*A+B, то получается так:
Вот так))) Тем не менее, эта редукционная формула имеет один изъян, а именно значение A-1. Дело в том, что если A представляет собой степень десятки (например, 1000), то A-1 становиться нечетноцифровым числом (для нашего примера - 999), что нарушает редукцию, так как мы хотим, чтобы все числа для S() были бы четноцифровые. Программно этот случай можно обойти (так как основная сумма в этом случае просто равна 0), но, честно говоря, выглядит это не очень красиво. Хотелось бы избавиться от -1 для A, и это возможно, если в основную сумму впихнуть 100 следующих чисел, а потом вычесть то лишнее, что мы этим добавили:
С суммой по сотням проблем нет, а вот с остатком придётся разобраться:
-------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||
feodorv |
|
||||||
Эксперт Профиль Группа: Комодератор Сообщений: 2214 Регистрация: 30.7.2011 Репутация: 12 Всего: 45 |
Ясно, что в конце концов мы доредуцируемся до двухциферных чисел. Иными словами, в конце редукции мы должны вычислить сумму S(10..K), где К - двухциферное число, состоящее из первых двух цифр числа N. Казалось бы, эту сумму и так легко найти простым циклом, но понятно, что ряд S(10..K) - это кусок R(K), в котором отброшены первые 10 членов:
Поэтому
То есть имея массив R[], мы легко можем вычислить последнюю сумму S(10..K). Объединим все полученное в одну функцию, которая индуктивно будет вызывать сама себя:
Как-то так, как сумел, так и объяснил, прошу прощения за графоманство -------------------- Напильник, велосипед, грабли и костыли - основные инструменты программиста... |
||||||
|
|||||||
Правила форума "C/C++: Для новичков" | |
|
Запрещается! 1. Публиковать ссылки на вскрытые компоненты 2. Обсуждать взлом компонентов и делиться вскрытыми компонентами
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa. |
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | C/C++: Для новичков | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |