Отобразить минимальное положительное число, которое невозможно представить в виде суммы элементов массива

@Арен · Регистрация: 27.05.2014

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

Отобразить то минимальное положительное число, которое невозможно представить в виде суммы элементов массива. Количество действий O(n^2).

Кто может помочь с задачей? Заранее спасибо.

IGPIGP · 12.01.2016, 00:31

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

ты в магазине расплачиваешся минимум 2мя купюрами?

Сумма денег и сумма элементов у меня в голове не меняются местами, поэтому рассчитываюсь правильно. Но сумма элементов это значение не одного элемента, а сумма минимум двух.

@nefton · 12.01.2016, 00:34

не вижу никаких проблем просуммировать вообще 0 элементов

IGPIGP · 12.01.2016, 00:39

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

не вижу никаких проблем просуммировать вообще 0 элементов

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

@nefton · 12.01.2016, 00:56

Очередной раз убеждаюсь что патриотизм это хорошо... но факты...
факты говорят о том что на западе (по крайней мере англоязычная) наука намного впереди
http://stackoverflow.com/quest... from-a-set

Байт · 12.01.2016, 01:09

Однако, задача оказалась не столь и сложна.
Массив будем считать отсортированным - O(nlogn)

C++
1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
 
main()
{ int i, k, a[7] = { 1,1,3,6, 12, 17, 20 };
 for(i=k=0; i<7; i++) {
   if (k+1 < a[i]) break;
   k += a[i];
 }
 printf("k=%d\n", k+1);
}

Добавлено через 46 секунд

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

не вижу никаких проблем просуммировать вообще 0 элементов

Я - тоже!

Добавлено через 3 минуты
nefton, Ваша ссылочка:
http://stackoverflow.com/quest... from-a-set

C++
1
2
3
4
5
6
7
8
9
10
11
12
static int Calculate(int[] S)
{
    int max = 0;
    for (int i = 0; i < S.Length; i++)
    {
        if (S[i] <= max + 1)
            max = max + S[i];
        else
            return max + 1;
    }
    return max + 1;
}

Вот, блин! Опять Америку открыл!

@nefton · 12.01.2016, 01:14

Байт, оказывается можно ещё быстрее
http://stackoverflow.com/quest... from-array

IGPIGP · 12.01.2016, 01:15

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

патриотизм это хорошо

угу... но если заглянуть в системный блок, по неволе становишься космополитом. По крайней мере в IT.

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

намного впереди

Опять приблизительно. Подмножество множества <set> может состоять из одного элемента. Подмножество математического множества тоже. Там правда ещё круче, так как этот элемент может быть пустым множеством.
Но сумма элементов массива - вещь простая и домашняя как утюг. В ней минимум 2 элемента должно быть. Положительных причём. Это значит что меньше 2-х такая сумма быть не может и значит число 1 это необходимое и как раз достаточное для ответа число.
2 слагаемых. На меньшее я не согласный! И не просите, дажа.

Байт · 12.01.2016, 01:19

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

Не бывает. Может быть сумма числа и... числа. Даже если это ноль. Я нигде не видел суммы представленной одним слагаемым. То есть в самых общих формулировках:
это просто эмоция.

Что вы? Какая эмоция? Самая обычная математика. Ведь пустое множество - тоже множество. И множество из одного элемента - тоже множество. Иначе вся работа Кантора и прочих отцов основателей - псу под хвост.
Ну посмотрите
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
И самое смешное, что эта формула работает и при n=1 и при n=0

Добавлено через 2 минуты

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

оказывается можно ещё быстрее

В алгоритме не разобрался, но вам верю. Без сортировки, да?

@nefton · 12.01.2016, 01:24

а, похоже нет, это тотже алгоритм

Добавлено через 4 минуты
там просто в дебри влазят с оптимизацией для больших чисел

Байт · 12.01.2016, 01:25

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

И не просите, дажа

Ну что ж. Тогда нам придется ввести 2 понятия суммы. Одно - стандартное. Другое назовем "Сумма по IGPIGP". В математике такие вещи встречаются сплошь да рядом.

@nefton · 12.01.2016, 01:29

а, вот вообще тема (особенно если расчитывать на компьютере

)
без сортировок и используя битовые операторы (1 процессорная команда)
Use bitvectors to accomplish this in linear time.

Start with an empty bitvector b. Then for each element k in your array, do this:

b = b | b << k | 2^(k-1)

To be clear, the i'th element is set to 1 to represent the number i, and | k is setting the k-th element to 1.

After you finish processing the array, the index of the first zero in b is your answer (counting from the right, starting at 1).

b=0
process 4: b = b | b<<4 | 1000 = 1000
process 13: b = b | b<<13 | 1000000000000 = 10001000000001000
process 2: b = b | b<<2 | 10 = 1010101000000101010
process 3: b = b | b<<3 | 100 = 1011111101000101111110
process 1: b = b | b<<1 | 1 = 11111111111001111111111
First zero: position 11.

IGPIGP · 12.01.2016, 01:40

Сообщение от Байт

Самая обычная математика. Ведь пустое множество - тоже множество.

которое содержит себя как элемент. Математика и прикладные задачи для меня две вещи несовместные. То есть расходятся в некоторых местах, а значит не сходятся, строго говоря, вообще. Я никогда не понимал абстракции нуля так как это принято. Есть положительные числа, отрицательные числа и ноль. Три знака.

Причём определяются друг из друга. + это >0, - это < 0, а ноль это как раз в точности уже не -, но ещё не +. То есть ровно по 50% того и другого.
Хотите сумму как математический процесс, - не буду спорить. Мне в практике ближе двухместная операция и её результат. И то и другое, - сумма. Денежная сумма тоже сумма. Остальное - математика. Но задача же не математическая? Мы же не станем контейнер <set> подменять понятием множества. А тут массив... Компилятор вон драться лезет если пытаться объявить массив из нуля элементов. А без этого в попытке ваших с компаньоном аналогий, бо-олшущая ~~логическая~~математическая дыра. Впрочем, я обещал не заводиться и, - на тебе. Нет... Сумма нуля элементов массива, это без меня.

@nefton · 12.01.2016, 01:47

Байт, ввязываясь в этот ~~******~~ бесполезный спор, ты отвлекаешь внимание будущих читателей от своего же классного решения. Пускай и в русскоязычном интернете появятся примеры решения реальных задач не захламлённые холиварами.

Байт · 12.01.2016, 12:57

Сообщение от Арен

Здравствуйте. Хотелось бы узнать, это ваше решение всегда корректно работает?

Я вот не понял, зачем ты это послал мне в личку. Это нарушает правило 4.6 и вообще как-то бессмысленно.
Пойми, что это очень грубое нарушение правил хорошего тона, и постарайся так больше никогда не поступать.
Теперь по делу. Что тебе не нравится? Какие сомнения?
И вот еще. Почти ни об одной программе на свете нельзя сказать, что она всегда корректно работает. Всегда найдутся данные, с которыми она не справится. Просто из-за переполнения разрядной сетки компьютера. Или из-за объема данных, такого, что они не поместятся ни на один носитель.

@Арен · 12.01.2016, 13:05 **[ТС]**

Байт, Извиняюсь. Насчет программы, ход действий соответствует задаче О(n^2) ?

Байт · 12.01.2016, 13:09

Сообщение от Арен

ход действий соответствует задаче О(n^2) ?

Даже меньше
Сортировка (не показана в коде) = O(n*log n)
Код - O(n)
O(n*log n) + O(n) = O(n*log n) = o(n²)

@Арен · 12.01.2016, 15:06 **[ТС]**

Хорошо. Спасибо за ответ.

Добавлено через 1 час 55 минут
Байт, Еще один вопрос возник. Вот в вашем примере есть число 1, а это число тоже же нельзя представить в виде суммы элементов массива?

Байт · 12.01.2016, 15:20

Сообщение от Арен

Вот в вашем примере есть число 1, а это число тоже же нельзя представить в виде суммы элементов массива?

Для ответа на этот вопрос ознакомьтесь с дискуссией, развернувшейся в этом топике, по поводу того, что такое сумма. Если вы разделяете взгляды моего оппонента, то к нему и обращайтесь с вопросами такого типа.

@Арен · 12.01.2016, 16:42 **[ТС]**

Байт, Этот вопрос только что прояснил. Сумма одного числа как сумма не рассматривается.

8-BITOV · 12.01.2016, 17:00

Сообщение от Арен

элементы положительные.

Сообщение от Арен

только что прояснил. Сумма одного числа как сумма не рассматривается.

Ответ : 1

Новые блоги и статьи Все статьи Все блоги /
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Арен 16 / 16 / 12 Регистрация: 27.05.2014 Сообщений: 133

	Отобразить минимальное положительное число, которое невозможно представить в виде суммы элементов массива 11.01.2016, 18:48. Показов 6592. Ответов 52 Метки нет (Все метки) Отобразить то минимальное положительное число, которое невозможно представить в виде суммы элементов массива. Количество действий O(n^2). Кто может помочь с задачей? Заранее спасибо. 0

@nefton 45 / 21 / 6 Регистрация: 28.02.2013 Сообщений: 194
	12.01.2016, 00:34
	не вижу никаких проблем просуммировать вообще 0 элементов 0

@nefton 45 / 21 / 6 Регистрация: 28.02.2013 Сообщений: 194
	12.01.2016, 00:56
	Очередной раз убеждаюсь что патриотизм это хорошо... но факты... факты говорят о том что на западе (по крайней мере англоязычная) наука намного впереди http://stackoverflow.com/quest... from-a-set 1

@nefton 45 / 21 / 6 Регистрация: 28.02.2013 Сообщений: 194
	12.01.2016, 01:14
	Байт, оказывается можно ещё быстрее http://stackoverflow.com/quest... from-array 0

@nefton 45 / 21 / 6 Регистрация: 28.02.2013 Сообщений: 194
	12.01.2016, 01:24
	а, похоже нет, это тотже алгоритм Добавлено через 4 минуты там просто в дебри влазят с оптимизацией для больших чисел 0

@nefton 45 / 21 / 6 Регистрация: 28.02.2013 Сообщений: 194
	12.01.2016, 01:29
	а, вот вообще тема (особенно если расчитывать на компьютере ) без сортировок и используя битовые операторы (1 процессорная команда) Use bitvectors to accomplish this in linear time. Start with an empty bitvector b. Then for each element k in your array, do this: b = b \| b << k \| 2^(k-1) To be clear, the i'th element is set to 1 to represent the number i, and \| k is setting the k-th element to 1. After you finish processing the array, the index of the first zero in b is your answer (counting from the right, starting at 1). b=0 process 4: b = b \| b<<4 \| 1000 = 1000 process 13: b = b \| b<<13 \| 1000000000000 = 10001000000001000 process 2: b = b \| b<<2 \| 10 = 1010101000000101010 process 3: b = b \| b<<3 \| 100 = 1011111101000101111110 process 1: b = b \| b<<1 \| 1 = 11111111111001111111111 First zero: position 11. 0

@nefton 45 / 21 / 6 Регистрация: 28.02.2013 Сообщений: 194
	12.01.2016, 01:47
	Байт, ввязываясь в этот ~~******~~ бесполезный спор, ты отвлекаешь внимание будущих читателей от своего же классного решения. Пускай и в русскоязычном интернете появятся примеры решения реальных задач не захламлённые холиварами. 3

@Арен 16 / 16 / 12 Регистрация: 27.05.2014 Сообщений: 133
	12.01.2016, 13:05 [ТС]
	Байт, Извиняюсь. Насчет программы, ход действий соответствует задаче О(n^2) ? 0

@Арен 16 / 16 / 12 Регистрация: 27.05.2014 Сообщений: 133
	12.01.2016, 15:06 [ТС]
	Хорошо. Спасибо за ответ. Добавлено через 1 час 55 минут Байт, Еще один вопрос возник. Вот в вашем примере есть число 1, а это число тоже же нельзя представить в виде суммы элементов массива? 0

@Арен 16 / 16 / 12 Регистрация: 27.05.2014 Сообщений: 133
	12.01.2016, 16:42 [ТС]
	Байт, Этот вопрос только что прояснил. Сумма одного числа как сумма не рассматривается. 0