Найти такой набор целых положительных чисел, чтобы их сумма была равна N - C#

Узнай цену своей работы

Формулировка задачи:

Доброго времени! Весь вечер ломаю голову, на ум ничего не приходит. Задание. Написать программу,которая находит такой набор целых положительных чисел X1...Xn, чтобы их сумма была равна N, а произведение максимально. Программа должна быть выполнена в виде отдельных методов. Вот что у меня написано на данный момент.. Это недоразумение создает рандомный массив, при чем заменяет его элементы до тех пор, пока сумма этих элементов не будет равняться заданному пользователем числу. Так же выводится максимальное из всех произведений. Т.е. программа выполняется скажем 3 раза, число заданное с клавиатуры - 20, а количество элементов, чья сумма даст 20 - 3. Генерируются например такие элементы 1: 5 12 3 (180), 2: 10 8 2 (160), 3: 3 2 15(90), в данном случае максимальное произведение - 180, его я вывожу на экран, но как мне так же вывести элементы, которые дадут именно это произведение? Если кто реализовывал что-то подобное, подскажите пожалуйста..
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace qwer
{
    class Program
    {
        static void Main(string[] args)
        {   
            Random rnd = new Random();
            Console.Write("Введите число: ");
            
            int chislo = int.Parse(Console.ReadLine());
            Console.WriteLine("");
            Console.Write("Введите колличество элементов: ");
 
            long elem = long.Parse(Console.ReadLine());
            Console.WriteLine(" ");
 
            long[] k = new long[elem]; //массив-вектор элементов, сумма которых дает введенное число
 
            long[] qw = new long[5]; //под нужды
           
            string[] ar = new string[5];
            for(int i = 0; i<5; i++)
            
            {   Gener(chislo, elem, k, qw, rnd ); //формирует массив элементов, сумма которых дает введенное пользователем число
                    
                ar[i] = Vivod(k, elem, qw );  //Вывод на экран элементов массива, которые в сумме дают заданное пользователем число
                
               Max(qw,k); //находим максимальное произведение   
 
            }
 
Console.WriteLine("Максимальное произведение: " +qw[2] + " ");  
            Console.ReadKey();
 
        }
        //Метод выводит на экран элементы массива, сумма которых дает число n, так же он выводит произведение этих элементов
        //1-й аргумент - массив, в котором эти элементы хранятся
        //2-й аргумент - колличество элементов массива []k
        //3-й аргумент массив для хранения данных
 
        static string Vivod(long[]k, long elem, long[]qw )
        {  string ssq ="";
            qw[0] = 1;
            qw[3] ++;
            for (long i = 0; i < elem; i++)
            {
                 ssq += (k[i].ToString()+ " ");
                qw[0] *= k[i];
            }           
            Console.Write("Элементы: " +ssq);
            Console.WriteLine(" Произведение: " +qw[0] + " ");         
            return ssq; 
        }
    
        //Метод находит максимальный из 3 элементов qw[0], qw[1], qw[2] массива qw, 
        //и присваивает элементу qw[2] найденное максимальное значение (служит для нахождения максимального произведения)
        //1-й аргумент - массив-вектор qw 
        
        static void Max(long[]qw,long[] k)
        
        { long max =0;      
      max = qw[0];   //находим максимальный элемент из массива qw
         
          qw[1] = qw[0];
          
        for (int i = 0; i < 5; i++)
        {
            if (qw[i] > max)
            {
                max = qw[i];
                
            }
        }
     
        qw[2] = max;
               
        }
        
        //Метод генерирует случайные числа, сумма которых должна равняться числу chislo
 
        //1-й аргумент - число которому должна равняться сумма случайных элементов
        //2-й аргумент - колличество случайных элементов
        //3-й аргумент - массив-вектор, который хранит случайные элементы
        //4-й аргумент - экземпляр класса Random

        static void Gener( int chislo, long elem, long[]k, long[]qw, Random rnd )
        {  int jg =0;
           long sum =0;
            int s = 0;
    
            {  
                
            while (sum != chislo)
                {
                    sum = 0;
                    for (long i = 0; i < elem; i++)
                    {
                        s =rnd.Next(0, chislo);
 
                        k[i] = Convert.ToInt64(s);
 
                        sum += k[i];
    
                    }}sum =0; }

            }

        }
 
}

Решение задачи: «Найти такой набор целых положительных чисел, чтобы их сумма была равна N»

textual
Листинг программы
class Program {
    static void Main(string[] args) {
        /// Тут организуешь ввод числа. Это на твой вкус
        int summ = 2;
        /// Список для хранения найденных слагаемых
        List<int> numbers;
        /// Рекурсивный поиск слагаемых
        numbers = SplitToSummands(summ, new List<int>());
        /// Вычисление произведения. Не для проверки, только для вывода на экран
        int prod = 1;
        foreach (int item in numbers)
            prod *= item;
 
        /// Печать результата
        Console.WriteLine("Число {0} может быть можно разбить на такие слагаемые, произведение которых максимально {1} = {2}", summ,
            string.Join(" * ", numbers.ConvertAll<string>((i) => i.ToString()).ToArray()),
            prod);
 
        Console.Read();
    }
    /// <summary>
    /// Функция разбивки целого числа на слагаемые, так, чтобы их произведение было максимальным
    /// </summary>
    /// <param name="num">Число для разбивки</param>
    /// <param name="list">Список для хранения найденных слагаемых</param>
    /// <returns>Возвращает набор слагаемых заданного числа так, что их произведение максимально</returns>
    static List<int> SplitToSummands(int num, List<int> list) {
        if (num <= 2) {
            /// При таком методе минимальное слагаемое будет или 2(если исходное число нечётное)
            /// или 1 (если исходное число чётное). Это минимальное слагаемое прибавляем к первому
            /// элементу списка (самому большому слагаемому)
            list[0] += num;
        }
        else {
            /// Добавляем в список число на 1 больше половины исходного числа.
            list.Add(num / 2 + 1);
            /// Продолжаем разбивку. Если исходное число чётное, то дальше передаётся число на 1
            /// меньше половины. Если нечётное — остаток целочисленного деления на 2
            SplitToSummands(num / 2 + num % 2 - 1, list);
        }
        return list;
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 3.25 из 5
Похожие ответы