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

Перебор всех возможных способов размещения n различных предметов по m различным ящикам - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 40, средняя оценка - 4.73
Decoy
0 / 0 / 0
Регистрация: 18.03.2009
Сообщений: 3
18.03.2009, 11:24     Перебор всех возможных способов размещения n различных предметов по m различным ящикам #1
Ребят, я на этом форуме не очень давно и хочу попросить помощи, Задача такого рода:
написать программу перебора всех возможных способов размещения n различных предметов по m различным ящикам, не более чем по одному в ящик, m и n вводятся с пользователем. Задумки были но учебный сервак упал вместе со всем что на нем было, поэтому буду писать только на локальной машине. Заранее благодарен...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2009, 11:24     Перебор всех возможных способов размещения n различных предметов по m различным ящикам
Посмотрите здесь:

Реализовать перебор всех возможных IP-адресов (С++) C++
Перебор всех возможных подмножеств множества целых чисел C++
В массиве хранится сведения о стоимости 12 различных предметов. определить общую стоимость всех предметов? C++
перебор и вывод всех возможных сочетаний C++
Перебор возможных вариантов разреза трубы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Humanitis
 Аватар для Humanitis
170 / 162 / 5
Регистрация: 12.01.2009
Сообщений: 430
18.03.2009, 13:33     Перебор всех возможных способов размещения n различных предметов по m различным ящикам #2
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
#include <iostream>
 
 
void placement(int citems,int iter,int const cboxes,char* output)
{
    if(!citems)
    {
        for(int i=0;i<cboxes-iter;i++)
            output[i]='0';
        std::cout<<(output-iter)<<'\n';
        return;
    }
    *output='1';
    placement(citems-1,iter+1,cboxes,output+1);
    if(citems<cboxes-iter)
    {
        *output='0';
        placement(citems,iter+1,cboxes,output+1);
    }
}
 
int main()
{
    int n,m;
    std::cout<<"input count of items:";
    std::cin>>n;
    std::cout<<"\ninput count of boxes:";
    std::cin>>m;
    if(n>m)std::cout<<"No solutions";
    else if(n==m)for(int i=0;i<m;i++)std::cout<<'1';
    else
    {
        char* output=new char[m+1];
        output[m]=0;
        placement(n,0,m,output);
    }
    std::cout<<'\n';
    system("pause");
    return 0;
}
Decoy
0 / 0 / 0
Регистрация: 18.03.2009
Сообщений: 3
24.03.2009, 08:34  [ТС]     Перебор всех возможных способов размещения n различных предметов по m различным ящикам #3
Огромное спасибо!
Decoy
0 / 0 / 0
Регистрация: 18.03.2009
Сообщений: 3
05.04.2009, 11:48  [ТС]     Перебор всех возможных способов размещения n различных предметов по m различным ящикам #4
Черт, получилось немного не то, что нужно n различных предметов, т.е. к примеру n=5, т.е. предметы 1,2,3,4,5, что-то я не понимаю как это дело реализовать...
Humanitis
 Аватар для Humanitis
170 / 162 / 5
Регистрация: 12.01.2009
Сообщений: 430
05.04.2009, 14:01     Перебор всех возможных способов размещения n различных предметов по m различным ящикам #5
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
#include <iostream>
 
void placement(int citems,int iter,int const cboxes,char* output)
{
    if(iter==citems)
        std::cout<<output<<'\n';
    else
        for(int i=0;i<cboxes;i++)
        {
            if(output[i]!='0')
                continue;
            output[i]=49+iter;
            placement(citems,iter+1,cboxes,output);
            output[i]='0';
        }
}
 
int main()
{
    int n,m;
    std::cout<<"input count of items:";
    std::cin>>n;
    std::cout<<"\ninput count of boxes:";
    std::cin>>m;
    if(n>m)std::cout<<"No solutions";
    else
    {
        char* output=new char[m+1];
        for(int i=0;i<m;i++)
            output[i]='0';
        output[m]=0;
        placement(n,0,m,output);
    }
    std::cout<<'\n';
    system("pause");
    return 0;
}
David Sylva
 Аватар для David Sylva
1280 / 942 / 51
Регистрация: 17.05.2012
Сообщений: 2,686
13.07.2012, 22:20     Перебор всех возможных способов размещения n различных предметов по m различным ящикам #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
#include <iostream> 
#include <algorithm>
using namespace std; 
int main() 
{   
    setlocale(0, "rus");
    int n, m;  
    int i; 
    int* array;       
 
    cout << "Введите n предметов  "; 
    cin >> n; 
    cout << "Введите m ящиков "; 
    cin >> m; 
 
    if( n > m)   
        cout << "Нет решения " << endl; 
    else 
    { 
       array = new int[m+1]; 
       for ( i = 0; i < m; i++) 
       {   
           if(i >= n)        
               array[i] = 0; 
           else 
               array[i] = i+1;  
       } 
 
       sort(array,array+m); 
 
       do 
       {   
          for ( i = 0; i < m; i++) 
               cout << array[i] << " ";  
           cout << endl; 
 
       } while(next_permutation(array, array+m)); 
    }
 
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.01.2014, 15:53     Перебор всех возможных способов размещения n различных предметов по m различным ящикам
Еще ссылки по теме:

Организовать перебор всех возможных сочетаний C++
Вычислить количество способов группировки K предметов из N при больших N C++
C++ Составить программу, которая, по данным N и K, вычисляет количество способов группировки K предметов из N

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

Или воспользуйтесь поиском по форуму:
games over
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 9
03.01.2014, 15:53     Перебор всех возможных способов размещения n различных предметов по m различным ящикам #7
помогите пожалуйста
Ввести число. Используя рекурсивную функцию, получить все возможные перестановки цифр этого числа.
Yandex
Объявления
03.01.2014, 15:53     Перебор всех возможных способов размещения n различных предметов по m различным ящикам
Ответ Создать тему
Опции темы

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