-1

Добрый вечер! Как можно решить данную задачу: требуется написать консольное приложение на языке с#, пользователь вводит размер массива, далее массив заполняется случайными числами от 0 до 100 (именно до 100, не до 101), заполненный массив выводится на экран, после этого пользователя просят ввести еще одно рандомное целочисленное число, после этого программа должна попытаться составить введенное число из элементов массива складывая их друг с другом или самих на себя (только сложение), например, массив получился таким: 1 2 3 4 5 6 7, пользователь ввел число 125 - ответ: такое число получить не удалось, а если введено было число: 12 - ответом должно быть: такое число возможно получить и в идеале перечислить из каких элементов массива оно получается? Очень долго думал на как это реализовать... Буду очень признателен! PS: если это облегчит задачу, то можно обойтись фиксированным размер массива - 20.

7
  • 6
    Добрый день. На нашем сайте не делают задания за других, поэтому ответ на ваш вопрос "как решить" прост: начните писать сами. Когда столкнётесь с конкретным вопросом -- задавайте конкретный вопрос. Также поиском по сайту можно найти много готовых фрагментов вашей задачи. Либо пойти на сайты фрилансеров -- там за вас решат эту задачу и можно будет вообще не думать.
    – A K
    23 ноя 2017 в 12:08
  • В целом программу я уже написал, осталось последняя деталь - как проверить возможность "собрать указанное число из элементов массива".
    – Kasper
    23 ноя 2017 в 12:12
  • 1
    Найдите в массиве единичку и сложите ее с собой нужное количество раз 23 ноя 2017 в 12:35
  • 1
    Если у вас есть программа в целом -- можете привести её код в вопросе и указать непонятное место. Ещё лучше, если выделите из своего кода минимально необходимый пример.
    – A K
    23 ноя 2017 в 12:42
  • 1
    В целом программу я уже написал, осталось последняя деталь то есть осталось по сути решить задачу :)
    – tym32167
    23 ноя 2017 в 13:13

2 ответа 2

0

Алгоритм решения должен опираться на перебор всех елементов которые меньше или равны искомому. Здесь можно попробовать решить при помощи рекурсии. Следующий код не проверял на работоспособность, здесь чисто декларативное описание:

List<int> GetSumm(int[] array, int sum)
{
     Array.Sort(array);
     var stack = new Stack<int>();
     if (FindSumR(array, stack, sum));
         return stack.ToList();
     // не фартануло
     return null;
}

bool FindSumRec(int[] array, Stack<int> stack, int sum)
{
     var indx = Array.FindIndex(array, item => item > sum) - 1; // индекс элемента который меньше или равен искомому
     if (indx < 0) return false;
     var diff = sum - array[indx];
     // если уже меньше то двигаться вперёд смысла нет.
     if (diff < 0) return false;
     // если равен нулю то мы нашли комбинацию.
     if (diff == 0) 
     {
           stack.Push(array[indx]);
           return true;
     }
     // перебираем все оставшиеся варианты
     stack.Pop(array[indx]);
     while (!FindSumRec(array, stack, sum - array[indx])) 
     {
          indx--;
          // так и не нашли подходящей комбинации
          if (indx < 0) return false;              
          // перебираем дальше
          stack.Pop()
          stack.Push(array[indx]);
     }

     return true;
}
0

Для решения данной задачи, как оказалось, необходимо прибегнуть к двоичной системе счисления. С помощью цикла представленного ниже, компьютер пройдет по всем возможным комбинациям из представленного массива array с размером size. terms - это вспомогательный массив для хранения чисел, из которых было получено значение number.

for (int i = 0, s = 0; i < (1 << size); i++)
        {
            for (int j = 0, k = 0; j < size; j++)
                if ((i & (1 << j)) != 0)
                {
                    sum += array[j];
                    mas[k++] = array[j];
                    if (sum == number && s < 1){
                        foreach (int w in mas)
                            if (w != 0)
                                terms[x++] = w;
                        Console.WriteLine();
                        print = true;
                        s++;
                    }
                }

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.