Найти наименьшее целое положительное число, которое нельзя представить в виде суммы нескольких элементов массива - C# (187769)
Формулировка задачи:
Блин, даже и не ожидала, что кто-то ответит на мою предыдущую задачу, а оказалось, что ответили чуть ли не в ту же минуту. Класс! Класс! Класс! Теперь просто так от меня не отделаетесь...хе,хе,хе....
А теперь другая задачка, в которой я без помощи вооообще никак(((
1) Дан неубывающий массив положительных целых чисел a[1]≤a[2]≤…≤a[n]. Найти наименьшее целое положительное число, которое нельзя представить в виде суммы нескольких элементов этого массива (элемент массива должен быть использован один раз).
и вот кусочек к первой задаче(нашла в нете), пишут, это якобы задачка по московской олимпиаде по программированию...
Решение. Пусть известно, что числа, представимые в виде
суммы элементов a[1],...,a[k], заполняют отрезок от 1 до некото-
рого N. Если a[k+1] > N+1, то N+1 и будет минимальным числом, не
представимым в виде суммы элементов массива a[1]..a[n]. Если же
a[k+1] <= N+1, то числа, представимые в виде суммы элементов
a[1]..a[k+1], заполняют отрезок от 1 до N+a[k+1].
k := 0; N := 0;
{инвариант: числа, представимые в виде суммы элементов массива
a[1]..a[k], заполняют отрезок 1..N}
while (k <> n) and (a[k+1] <= N+1) do begin
| N := N + a[k+1];
| k := k + 1;
end;
{(k = n) или (a[k+1] > N+1); в обоих случаях ответ N+1}
writeln (N+1);
надеюсь и жду...плиз
Решение задачи: «Найти наименьшее целое положительное число, которое нельзя представить в виде суммы нескольких элементов массива»
textual
Листинг программы
static int Calculate(int[] a) { int max = 0; for (int i = 0; i < a.Length && a[i] <= max + 1; i++) max += a[i]; return max + 1; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д