Можно ли перед каждым из чисел от 1 до N расставить знаки «+» или «–» так, чтобы сумма получившихся чисел была равна 0?

@RezoStyleOMG · Регистрация: 30.10.2019

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

Легенда гласит, что Карл Фридрих Гаусс, учась в школе, смог быстро посчитать сумму целых чисел от 1 до 100, заметив, что 1 + 100 = 2 + 99 = … = 50 + 51. Теперь решите
задачу посложнее: можно ли перед каждым из чисел от 1 до N расставить знаки «+» или «–» так, чтобы сумма получившихся чисел была равна 0? Например, для N = 3 сумма –1 –2 +3
будет равна 0, а для N = 2 этого сделать нельзя. Программа получает на вход целое неотрицательное число N, не превосходящее 10в(5)степени. Программа должна вывести последовательность из N символов «+» или «–», соответствующих знакам, которые нужно расставить перед числами от 1 до N так, чтобы сумма получившихся чисел была равна 0. Если задача имеет несколько решений, нужно вывести один (лобой) ответ. Если задача не имеет решения для данного N, нужно вывести одно слово «IMPOSSIBLE».

Пример:Ввод:
3
2
Вывод:
--+
IMPOSSIBLE
Примечание:
Правильным ответом будет также «++-»

Нужно решить на С#

@Diamante · 16.11.2019, 01:03

мысли?наработки? или очередной "сами ниместние, ничиго нипанимать, памагити"?

@RezoStyleOMG · 16.11.2019, 07:07 **[ТС]**

Вроде того

@Элд Хасп · 17.11.2019, 09:16

RezoStyleOMG, вы где учитесь?
В школе в пятом классе?
Ещё не проходили арифметическую прогрессию?

Сумма чисел от 1 до N равна N*(N+1)/2
Если сумма нечётная, то не имеет решения.
Если четная, то сумируются первые элементы, до тех пор пока их сумма не станет равна или больше половины общей суммы.
Если равна - вывод решения.
Если больше, то исключается элемент равный разнице и вывод решения.

Добавлено через 12 минут
Решение в общем виде:

Общая Summa = N*(N+1)/2
Если Summa % 2 != 0, то нет решения
Искомая сумма части ряда Summa2 = Summa / 2
Количество элементов: int count = 0; for(int i = 1; (count+=i) < Summa2; i++);
Элемент который не входит в искомую последовательность равен Summa2-count
Вывести все найденные элементы с одним знаком, а иные с другим.

@alexus5 · 17.11.2019, 12:38

RezoStyleOMG, при первом рассмотрении задачи закономерность не очевидна. Проведем наблюдение за поведением требуемой последовательности для некоторого количества натуральных чисел, подчеркиванием будут ограничены структурные элементы.
1. {1} Imp.
2. {1,2} Imp.
3. {1,2,3} -_-_+ четная сумма, есть возможность для разделения
4. {1,2,3,4} -+_+- прибавили четное к четному, сумма осталась четной
5. {1,2,3,4,5} Imp. - прибавили нечетное число, сумма стала нечетной
6. {1,2,3,4,5,6} Imp. - прибавили четное к нечетному, сумма осталась нечетной
7. {1,2,3,4,5,6,7} -+-_-+-_+ - прибавили нечетное к нечетному, сумма стала четной.
8. {1,2,3,4,5,6,7,8} -+-+_+-+- четное + четное = четное
9. {1,2,3,4,5,6,7,8,9} Imp. четное + нечетное = нечетное
Как видно, исход зависит от значения остатка от деления на 4.
если mod == 1 или 2 - сумма нечетная - нет решения.
Для остальных случаев есть решение, ниже один из возможных алгоритмов:
В качестве основы выступит базовая последовательность чередующихся знаков длиной, равной половине исходного числа, дополненной затем ее зеркальным отображением.
если mod == 3, то нужно добавить еще плюс.

C#

        public static string GetSigns(uint n)
        {
            // получаем остаток целочисленного деления на 4
            uint mod = n % 4;
            // проверяем на равенство 1 или 2
            if (mod == 1 || mod == 2) return "IMPOSSIBLE";
            // формирование базовой последовательности
            var baseSeq = 
                Enumerable.Range(0, (int)n / 2) // целочисленная половина числа
                .Select(x => x % 2 == 0 ? '-' : '+'); // чередование минусов и плюсов
            // дополнение обратным вариантом
            baseSeq = baseSeq.Concat(baseSeq.Reverse());
            // добавляем плюс
            if (mod == 3) baseSeq = baseSeq.Append('+');
            // подождать немного
            //System.Threading.Thread.Sleep(500);
            // возвратить требуемую строку
            return string.Concat(baseSeq);
        }

проверка:

Кликните здесь для просмотра всего текста

C#

        public static void Main(string[] args)
        {
            Console.BufferHeight = 10000;
            var date1 = DateTime.Now;
            for(int i = 1;i<25;i++)
            {
                var testStr = GetSigns((uint)i);
                var test = GetSum(testStr);
                Console.WriteLine($"{i} - {testStr} {test == 0}");
            }
            Console.WriteLine($"{(DateTime.Now - date1).TotalMilliseconds} ms ");
            Console.ReadKey();
        }
        public static int GetSum(string signs)
        {
            if (signs[0] == 'I') return 0;
            int sum = 0, n = 1;
            foreach(var sign in signs)
            {
                sum += sign == '+' ? n : -n;
                n++;
            }
            return sum;
        }

@RezoStyleOMG 0 / 0 / 0 Регистрация: 30.10.2019 Сообщений: 3
		1
	Можно ли перед каждым из чисел от 1 до N расставить знаки «+» или «–» так, чтобы сумма получившихся чисел была равна 0? 15.11.2019, 18:42. Показов 4428. Ответов 4 Метки нет (Все метки) Легенда гласит, что Карл Фридрих Гаусс, учась в школе, смог быстро посчитать сумму целых чисел от 1 до 100, заметив, что 1 + 100 = 2 + 99 = … = 50 + 51. Теперь решите задачу посложнее: можно ли перед каждым из чисел от 1 до N расставить знаки «+» или «–» так, чтобы сумма получившихся чисел была равна 0? Например, для N = 3 сумма –1 –2 +3 будет равна 0, а для N = 2 этого сделать нельзя. Программа получает на вход целое неотрицательное число N, не превосходящее 10в(5)степени. Программа должна вывести последовательность из N символов «+» или «–», соответствующих знакам, которые нужно расставить перед числами от 1 до N так, чтобы сумма получившихся чисел была равна 0. Если задача имеет несколько решений, нужно вывести один (лобой) ответ. Если задача не имеет решения для данного N, нужно вывести одно слово «IMPOSSIBLE». Пример:Ввод: 3 2 Вывод: --+ IMPOSSIBLE Примечание: Правильным ответом будет также «++-» Нужно решить на С# 0

@Diamante 3564 / 2505 / 1174 Регистрация: 14.08.2016 Сообщений: 8,214
	16.11.2019, 01:03	2
	мысли?наработки? или очередной "сами ниместние, ничиго нипанимать, памагити"? 1

@RezoStyleOMG 0 / 0 / 0 Регистрация: 30.10.2019 Сообщений: 3
	16.11.2019, 07:07 [ТС]	3
	Вроде того 0

@Элд Хасп Модератор 15826 / 10977 / 2849 Регистрация: 21.04.2018 Сообщений: 32,221 Записей в блоге: 2
	17.11.2019, 09:16	4
	RezoStyleOMG, вы где учитесь? В школе в пятом классе? Ещё не проходили арифметическую прогрессию? Сумма чисел от 1 до N равна N(N+1)/2 Если сумма нечётная, то не имеет решения. Если четная, то сумируются первые элементы, до тех пор пока их сумма не станет равна или больше половины общей суммы. Если равна - вывод решения. Если больше, то исключается элемент равный разнице и вывод решения. Добавлено через 12 минут* Решение в общем виде: Общая Summa = N*(N+1)/2 Если Summa % 2 != 0, то нет решения Искомая сумма части ряда Summa2 = Summa / 2 Количество элементов: int count = 0; for(int i = 1; (count+=i) < Summa2; i++); Элемент который не входит в искомую последовательность равен Summa2-count Вывести все найденные элементы с одним знаком, а иные с другим. 0

	17.11.2019, 12:38