Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.58/50: Рейтинг темы: голосов - 50, средняя оценка - 4.58
Genn55
378 / 225 / 108
Регистрация: 26.12.2012
Сообщений: 744
1

Показать все возможные комбинации чисел составляющих сумму заданного числа

15.02.2014, 16:41. Просмотров 9144. Ответов 18
Метки нет (Все метки)

Доброго всем времени суток!Помогите пожалуйста с решением такой задачи.Дана последовательность вещественных чисел.Пользователь вводит число.Программа должна показать все возможные комбинации чисел составляющих сумму заданного числа из этой последовательности.Если таких комбинаций нет выдать сообщение.Количество чисел для комбинации задает пользователь.Результат вывести в виде таблицы.
Пример последовательность 1,2,3,4,5,6.Пользователь задает число 6. Комбинация из 2х чисел
1 + 5 = 6
2 + 4 = 6
3 + 3 = 6
из 3х чисел
1 + 2 + 3 = 6
2 + 2 + 2 = 6
1 + 1 + 4 = 6
Вот мой вариант решения " в лоб" т.е перебор всей последовательности вложенными циклами.
Я изучаю с++ самостоятельно и консультироваться негде.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <iomanip>
#include <windows.h>
 
//Прототипы функций подбора.Пока используются 2 остальные аналогичны
void Podbor2(double *,const int,const double);//комбинация из 2х чисел
void Podbor3(double *,const int,const double);//комбинация из 3х чисел
//void Podbor4(double *,const int,const double);
//void Podbor5(double *,const int,const double);
//void Podbor6(double *,const int,const double);
void Shapka1(const int);//Печать заголовка
bool PrintRez(const double,const double);//Печать результатов.
bool PrintRez(const double,const double,const double);//Печать результатов.
//Считает сумму
double Summ (double a,double b,double c = 0,double d = 0,double k = 0)
{
 return a + b + c + d + k;
}
 
using namespace std;
 
int main()
{
 SetConsoleCP(1251);
 SetConsoleOutputCP(1251);
 int num_prop;
 double num;
 void (*Pf[2])(double *,const int,const double)={Podbor2,Podbor3};//Массив указателей
 const int size = 6;
 double  Arr[size] = {1,2,3,4,5,6};//Для упрощения заполнил целыми числами
 
    cout << " Введите число  \n";
    cin >>num;
    cout << " Введите количество чисел для подбора 2 или 3   \n";
    cin >>num_prop;
 
    Shapka1(num_prop);
    (*Pf[num_prop-2])(Arr,size,num);//Обращяемся по индексу (идексация с 0,комбинция из1 числа не нужна
 
 return 0;
 }
void  Podbor2(double *mass,const int leng,const double m)
{
 bool rez = false;
 
    for (int i = 0; i < leng; i++)
    {
         for (int j = i; j < leng; j ++)
         {
           if (Summ(mass[i],mass[j]) == m)
               rez = PrintRez (mass[i],mass[j]);
         }
    }
    if (!(rez))
       cout << " Поиск завершен результатов нет! \n";
}
void  Podbor3(double *mass,const int leng,const double m)
{
 bool rez = false;
     for (int i = 0; i < leng; i++)
    {
         for (int j = i; j < leng; j ++)
         {
            for (int k = j; k < leng; k ++)
             {
                if (Summ(mass[i],mass[j],mass[k]) == m)
                    rez = PrintRez (mass[i],mass[j],mass[k]);
             }
         }
    }
    if (!(rez))
       cout << " Поиск завершен результатов нет! \n";
}
bool PrintRez(const double a,const double b)
{
 bool rezult = false;
     cout << setw(15)<<setprecision(3) << a << setw(15) << b
     << setw(15)<<setprecision(4) << Summ(a,b)<<setw(15) <<"\n";
   return  rezult = true;
}
bool PrintRez(const double a,const double b,const double c)
{
    bool rezult = false;
 cout << setw(15)<<setprecision(3) <<a<< setw(15) << b<< setw(15)
     <<c<< setw(15)<<setprecision(4) << Summ(a,b,c)<<setw(15) <<"\n";
     return  rezult = true;
}
void Shapka1(const int n)
{
    cout << "\t\t\t Комбинация из " << n << "  чисел \n";
 if (n == 2)
    {
    cout << setw (15)<<"Число1"<<setw (15)<<"Число2"<<setw (15)<<"Сумма \n\n";
    }
 if ( n == 3)
    {
     cout << setw (15)<<"Число1"<<setw (15)<<"Число2"<<setw (15)<<setw (15)<<"Число3"
          << setw (15)<<"Сумма \n\n";
    }
}
Дошел до 6 циклов,но мне кажется,что это не лучшее решение такой задачи.Этот код работает и выдает верный результат.Может кто предложит более рациональное решение?За ранее всем спасибо.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.02.2014, 16:41
Ответы с готовыми решениями:

Найти все возможные комбинации пятизначного числа.
Есть задача: во-первых, найти кол-во возможных комбинаций пятизначного...

Получить все возможные комбинации
Дана строка, например: АРТО Необходимо получить все возможные комбинации из...

Вывести все возможные комбинации цифр заданного числа
Введено число. Вывести все возможные комбинации цифр данного числа. Просьба...

Все возможные комбинации чисел
Есть числа 1,2,3,7,8,9. Как вывести их все возможные комбинации, если...

Все возможные комбинации 5 чисел
В общем задача такая: Нужно, чтобы программа выдавала все возможные комбнации...

18
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
16.02.2014, 13:06 2
Непереборное решение трудно придумать, поэтому попробуйте рекурсивную реализацию данной задачи.
Она упростит код.
0
Genn55
378 / 225 / 108
Регистрация: 26.12.2012
Сообщений: 744
16.02.2014, 13:16  [ТС] 3
Код может и упростит,а какова глубина рекурсии может быть,если последовательность больше,это для примера 6.Циклы работают побыстрее.
0
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
16.02.2014, 13:39 4
Вообще, мне кажется, что кроме перебора, тут вряд ли будет хорошее решение. А глубина, естественно, равна размеру исходного массива. То есть сложность - соответствующая степень двойки
1
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
17.02.2014, 12:46 5
Есть ограничение по вводимому числу? А то введет пользователь, например, 1000 и получайте длиннющий список из всех возможных комбинаций.

Тут либо рекурсия, либо более хитрый цикл с автоматическим изменением количества цифр. В обоих случаях последовательность разбивается на голову (основание, которое понемногу изменяем) и хвост, который каждый раз пытаемся дополнить до нужной суммы.
Начинать можно либо с минимума, либо с максимума
Пусть начнем с максимума для цикла - сначала найдем набор повторений максимального числа, чтобы их сумма была не меньше чем нужная сумма, если больше, то менее чем на одно максимальное число
В цикле
- если сумма совпадает - выводим
- смотрим на последнее число:
-- Если сумма больше чем нужно - заменить на число, меньшее на один шаг, если же число минимальное - то удалить, если число к тому же и последнее(единственное оставшееся) - выйти из цикла.
-- Если сумма меньше чем нужно - добавить в конец еще одно такое же число.

Как-то так.

Добавлено через 14 минут
Алгоритм обязательно бесконечно зациклится, думаю над решением.

Добавлено через 5 минут
Скорее всего
-- Если сумма больше чем нужно - заменить на число, меньшее на один шаг, если же число минимальное - то удалить, если число к тому же и последнее(единственное оставшееся) - выйти из цикла.
Заменить на
-- Если сумма больше чем нужно - заменить на число, меньшее на один шаг, если же число минимальное - удалить все минимумы в конце, а последний не минимум - уменьшить на один шаг, если же при удалении мы удалили все числа что были - выйти из цикла.
0
Genn55
378 / 225 / 108
Регистрация: 26.12.2012
Сообщений: 744
17.02.2014, 17:57  [ТС] 6
Нет ограничений по вводу нет.Но число из скольки чисел составлять комбинации выбирает пользователь.В данном коде это из 2х чисел или из3х.А нужно до10.Меня смущает 10 вложенных циклов.Я так полагаю,что работать они будут очень долго.Список конечно может быть и длинным,главное чтобы результат показывался 1 раз.Т.е. не было 2 + 3 = 5 или 3 + 2 = 5,а что нибудь одно 2 + 3 = 5 или 3 + 2 = 5.
достигается это уменьшением количества чисел при каждом следующем проходе по массиву
C++
1
2
3
 for (int i = 0; i < leng; i++)
    {
         for (int j = i; j < leng; j ++)
Вы меня подтолкнули на мысль.Если я начну проходы с максимального (т.е инвертирую последовательность)
и при первой проверке сумма окажется меньше введенного числа то выходим из цикла,дальше можно не продолжать.Если равна выводим этот единственный результат.Если больше продолжаем проверку пока следующие 2 максимума не станут меньше.Будут уменьшаться выходим из цикла.Наверное как то так.Верно?
0
wingblack
280 / 254 / 45
Регистрация: 09.04.2013
Сообщений: 953
18.02.2014, 14:26 7
Тебе не нужно делать 10 вложенных циклов for, тебе нужно сделать один цикл while с одним бегающим индексом

P.S. Если, конечно, не найдется что-то более элегантное чем слегка оптимизированный перебор.
0
ZzSan9zZ
0 / 0 / 1
Регистрация: 27.11.2013
Сообщений: 27
19.02.2014, 21:52 8
Вот моё решение, с помощью простой рекурсии.
В данном случае в выборку попадают повторения.
Я хочу удалить их следующем образом - как только мы находим верную комбинацию, сразу сортируем ее по возрастанию, и проверяем не попадалась ли нам данная комбинация ранее.
На сколько правилен мой код, и мой вариант избавления от повторений.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication1
{
    class Program
    {
        public static void Summ(int[] MasOfSum, int QuantOfSum, int Summa,int[]AllSum, int NumbOfSum, int NumbInMas)
        {
            AllSum[NumbOfSum] = MasOfSum[NumbInMas];
            if (NumbOfSum == QuantOfSum-1) 
            {
                int prov=0;
                for (int i = 0; i < QuantOfSum; i++)
                {
                    prov += AllSum[i];
                }
                if (prov == Summa)
                {
                    for (int i = 0; i < QuantOfSum-1; i++)
                    {
                        Console.Write(AllSum[i] + " + ");
                    }
                    Console.Write(AllSum[QuantOfSum-1] + " = " + Summa);
                    Console.WriteLine();
                }
            }
            if (NumbOfSum < QuantOfSum-1)
            {
                Summ(MasOfSum, QuantOfSum, Summa,AllSum, NumbOfSum + 1, 0);
            }
            if(NumbInMas<(MasOfSum.Length-1))
            {
                
                Summ(MasOfSum, QuantOfSum, Summa,AllSum, NumbOfSum, NumbInMas+1);
            }
        }
        static void Main(string[] args)
        {
            int summ,leng,first,quant;
            Console.WriteLine("Введите число, которое необходимо получить");
            summ = Convert.ToInt16(Console.ReadLine());
            Console.WriteLine("Введите первое значене ряда");
            first= Convert.ToInt16(Console.ReadLine());
            Console.WriteLine("Введите количество элементов ряда");
            leng= Convert.ToInt16(Console.ReadLine());
            Console.WriteLine("Введите число слагаемых, с помощью которых необходимо получить ваше число");
            quant = Convert.ToInt16(Console.ReadLine());
            int[] summands = new int[leng];
            for (int i = 0; i < leng; i++)
            {
                summands[i] += first;
                first++;
            }
            int[] allsumm = new int[quant];
            Summ(summands, quant, summ, allsumm, 0, 0);
            Console.ReadKey();
        }
    }
}
0
VladislavTepes
78 / 78 / 14
Регистрация: 27.06.2012
Сообщений: 555
Записей в блоге: 1
20.02.2014, 04:52 9
Бинарный перебор.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
 
int main()
{
    int comb_amount, bin[5] {0}, last_nil, ones_amount = 0, comb_len, sum, correct_sum;
    int numbers[] {1, 2, 3, 4, 5};
    comb_amount=1<<5;
    std::cout<<"Введите необохдимую сумму:";
    std::cin>>correct_sum;
    std::cout<<"Введите количество чисел для комбинации:";
    std::cin>>comb_len;
    for (int i=0; i<comb_amount-1; i++)
    {
        ones_amount = 0;
        sum = 0;
 
        for(int j=0; j<5; j++)
        {
            if (bin[j] == 0)
            {
                last_nil=j;
            }
        }
        for (int z=last_nil; z<5; z++)
        {
            bin[z]=0;
        }
        bin[last_nil]=1;
        for (int a=0; a<5; a++)
        {
            if (bin[a] == 1) ++ones_amount;
        }
        if (ones_amount == comb_len)
        {
            for (int x=0; x<5; x++)
            {
                if (bin[x] == 1) sum+=numbers[x];
            }
            if (sum == correct_sum)
            {
                for (int k=0; k<5; k++)
                {
                    if (bin[k] == 1) std::cout<<numbers[k]<<" ";
                }
                std::cout<<std::endl;
            }
 
 
        }
 
    }
    return 0;
}
0
Миниатюры
Показать все возможные комбинации чисел составляющих сумму заданного числа  
VladislavTepes
78 / 78 / 14
Регистрация: 27.06.2012
Сообщений: 555
Записей в блоге: 1
20.02.2014, 05:29 10
Бинарным перебором очень неплохо решаются подобные комбинаторные задачи - задача об укладке рюкзака, например.
0
Genn55
378 / 225 / 108
Регистрация: 26.12.2012
Сообщений: 744
21.02.2014, 00:33  [ТС] 11
VladislavTepes Спасибо большое!Но,возможно я не верно разобрался в вашем коде,он работает не корректно.Втом виде как он есть он у меня не скомпелировался.Пришлось подправить под свой Code::Blocks 10-05.Теряются комбинации.Подправленный код.Возможно я допустил ошибки.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
 
int main()
{
    int n = 10;
    int comb_amount,bin[10]={0},last_nil, ones_amount = 0, comb_len, sum, correct_sum;
    int numbers[n];
   for (int i =0; i<n; i++)
         numbers[i]= i+1;
    //int numbers[]= {1, 2, 3, 4, 5,6,7,8,9,10};
    comb_amount=1<<n;
    std::cout<<"Введите необохдимую сумму:";
    std::cin>>correct_sum;
    std::cout<<"Введите количество чисел для комбинации:";
    std::cin>>comb_len;
    for (int i=0; i<comb_amount-1; i++)
    {
        ones_amount = 0;
        sum = 0;
 
        for(int j=0; j<n; j++)
        {
            if (bin[j] == 0)
            {
                last_nil=j;
            }
        }
        for (int z=last_nil; z<n; z++)
        {
            bin[z]=0;
        }
        bin[last_nil]=1;
        for (int a=0; a<n; a++)
        {
            if (bin[a] == 1) ++ones_amount;
        }
        if (ones_amount == comb_len)
        {
            for (int x=0; x<n; x++)
            {
                if (bin[x] == 1) sum+=numbers[x];
            }
            if (sum == correct_sum)
            {
                for (int k=0; k<n; k++)
                {
                    if (bin[k] == 1) std::cout<<numbers[k]<<" ";
                }
                std::cout<<std::endl;
            }
        }
    }
    return 0;
}
Пожалуйста,если можно поясните работу кода или раскомментируйте,чтобы легче было понять.Я начинающий и еще очень много не понимаю.Спасибо.

Добавлено через 3 часа 20 минут
ZzSan9zZ спасибо вам большое,но я C# не знаю вообще и поэтому ничего не могу сказать по вашему коду.
0
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
21.02.2014, 11:40 12
Лучший ответ Сообщение было отмечено Genn55 как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
 
vector< int > seq; // исходная последовательность
vector< int > sub; // вектор слагаемых
 
void read_seq()
{
    // плохой способ ввода последовательности, но всего 1 строчка :)
    copy( istream_iterator< int >( cin ), istream_iterator< int >(), back_inserter( seq ) );
}
 
void show_sub()
{
    copy( sub.begin(), sub.end(), ostream_iterator< int >( cout, " " ) );
    cout << endl;
}
 
void fun( int x, int c, size_t i = 0 )
{
    if ( c < 0 || x < 0 ) return;
    else if ( !x && c ) return;
    else if ( x && !c ) return;
    else if ( !x && !c ) show_sub();
    else
        for ( ; i < seq.size(); ++i )
        {
            sub.push_back( seq[ i ] );
            fun( x - seq[ i ], c - 1, i );
            sub.pop_back();
        }
}
 
int main()
{
    int x, c;
 
    cout << "Введите число: ";
    cin >> x;
    cout << "Введите количество чисел для подбора: ";
    cin >> c;
    cout << "Введите последовательность (ctrl-Z закончить ввод): ";
    read_seq();
    fun( x, c );
 
    return 0;
}
глубина рекурсии равна числу, которое раскладываем на слагаемые
кстати, вводимая последовательность не должна содержать повторяющихся элементов
1
Genn55
378 / 225 / 108
Регистрация: 26.12.2012
Сообщений: 744
21.02.2014, 11:59  [ТС] 13
пасибо огромное!Все работает.Правда я с векторами вплотную не работал,только знаком с ними,но разберусь.Спасибо.
0
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
21.02.2014, 12:45 14
когда писал прогу, думал что это очевидно, что числа в последовательности и само раскладываемое число должны быть строго больше нуля, иначе рекурсия может уйти в бесконечность. но теперь думаю, что надо про это сказать. вот и сказал.

от этого ограничения можно избавиться, если брать каждое число из последовательности ровно 1 раз. тогда глубина рекурсии станет равна длине исходной последовательности.

вектора нужны, чтобы легче менять размер массива (push_back и pop_back), можно легко обойтись и без них, но тогда надо вводить доп. переменную для хранения размера массива sub, а это немного усложнит алгоритм.
0
Genn55
378 / 225 / 108
Регистрация: 26.12.2012
Сообщений: 744
21.02.2014, 16:30  [ТС] 15
Спасибо.Мне можно было бы об этом и не говорить,но читаю сообщения на форуме не я один.В полной программе последовательности и все остальное вычисляется не по одному разу.Вот меня и смутили вложенные циклы уж слишком они тормозили работу программы,хотя считают точно.Буду пробовать дальше,пока все нормально.Через массивы уже переделывать не буду,хотя и не так уж сложно.Надо же когда то и STL осваивать вот и начну.Спасибо.

Добавлено через 40 минут
К стати следует заметить,что size_t определен в <cstddef> у вас этого хедера нет.Стандарт не гарантирует, что без использования cstddef(stddef.h) вы сможете получить объявление данного типа.Это значит,что у кого то код не скампеллируется.
0
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
21.02.2014, 19:23 16
Цитата Сообщение от Genn55 Посмотреть сообщение
Стандарт не гарантирует, что без использования cstddef(stddef.h) вы сможете получить объявление данного типа.
подумайте число логически: метод size() класса vector возвращает значение типа size_t, а использование класса vector не требует подключать ничего, кроме хедера <vector>. какой следует вывод?
0
Somebody
2807 / 1618 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
21.02.2014, 20:04 17
Цитата Сообщение от ya_noob Посмотреть сообщение
метод size() класса vector возвращает значение типа size_t
Вообще-то vector<>::size_type.
0
ya_noob
_
315 / 149 / 27
Регистрация: 08.10.2011
Сообщений: 432
21.02.2014, 20:18 18
Цитата Сообщение от Somebody Посмотреть сообщение
Вообще-то vector<>::size_type.
ну это же псевдоним size_t.
вот как в gcc он определен:
C++
1
typedef size_t                   size_type;
реальный тип то size_t
0
Genn55
378 / 225 / 108
Регистрация: 26.12.2012
Сообщений: 744
21.02.2014, 21:30  [ТС] 19
Как начинающий я спорить не буду (уж лучше прислушаюсь к советам более опытных).В cstring size_t тоже используется.Но при работе с этим типом данных я руководствовался этим:
http://www.viva64.com/ru/t/0044/
Возможно я и не прав мне пока трудно об этом судить.
0
21.02.2014, 21:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.02.2014, 21:30

Получить все возможные комбинации чисел
Доброго дня! Подскажите, как реализовать макрос? есть такие числа: &quot;1&quot; - 46...

Вывести все возможные комбинации чисел
Здравствуйте, помогите с задачкой пожалуйста. от 1-го до n нужно вывести все...

Получить все возможные комбинации чисел
есть числа подскажите, пожалуйста, как при помощи средств delphi можно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
19
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru