Форум программистов, компьютерный форум CyberForum.ru

Комбинаторика - C++

Восстановить пароль Регистрация
 
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
14.02.2014, 22:55     Комбинаторика #1
Доброго всем времени суток!Помогите пожалуйста с решением такой задачи.Дана последовательность вещественных чисел.Пользователь вводит число.Программа должна показать все возможные комбинации чисел составляющих сумму заданного числа из этой последовательности.Если таких комбинаций нет выдать сообщение.Количество чисел для комбинации задает пользователь.Результат вывести в виде таблицы.
Пример последовательность 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 циклов,но мне кажется,что это не лучшее решение такой задачи.Может кто предложит более рациональное решение?За ранее всем спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.02.2014, 22:55     Комбинаторика
Посмотрите здесь:

комбинаторика C++
Комбинаторика C++
C++ Комбинаторика на С++
комбинаторика в программировании C++
C++ Комбинаторика и переборные алгоритмы
C++ Комбинаторика
C++ Комбинаторика. Сочетания
Покерная комбинаторика C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Amandosov
Знаток
156 / 156 / 65
Регистрация: 18.11.2012
Сообщений: 411
Записей в блоге: 2
14.02.2014, 23:47     Комбинаторика #2
А там точно цифры повторяются из последовательности, типа 3+3 или 1+1+4?
Наверно тогда можно и из 4 чисел составить: 1+1+2+2
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
15.02.2014, 17:32  [ТС]     Комбинаторика #3
Последовательность может быть любой с не повторяющимися числами.Я упростил для примера.Нужно составлять комбинации по выбору пользователя из 2х,3х,4х,5ти,6ти чисел,но может быть и больше отдельно.Результат не должен повторяться т.е 2 + 4 = 6 и 4 + 2 = 6.результат должен быть один или 2 + 4 или 4 + 2.В этом коде упрощено до 3х.Код именно так и работает результат дает верный.

Добавлено через 17 часов 29 минут
Тема еще актуальна.Пожалуйста покритикуйте этот код или подскажите что нужно доработать или переделать.Возможно я вообще не верно решаю эту задачу.Буду благодарен любой подсказке.Спасибо.
Yandex
Объявления
15.02.2014, 17:32     Комбинаторика
Ответ Создать тему
Опции темы

Текущее время: 16:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru