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

Задача перебора элементов - C++

Восстановить пароль Регистрация
 
Woody-krsk
1 / 1 / 0
Регистрация: 20.12.2010
Сообщений: 62
21.04.2012, 05:35     Задача перебора элементов #1
Всем привет! Собственно есть задача с которой я не могу совладать. Загвоздка не в программировании, а в том чтоб придумать алгоритм, чтобы решал эту задачу. Может кто подскажет, я уже всю голову сломал.
Задача на первый взгляд элементарная, но это только на первый взгляд.
Задача: есть некоторая разнородная многопроцессорная система, которая состоит из N типов процессоров и mi процессоров каждого типа, i=0,...,N. Система описывается сменой состояний a, например при N=3, a(0,0,0) - нет ни одного запроса к шине, а(1,0,0) - есть один запрос от процессоров первого типа, а(1,1,0) - есть по 1 запросу к шине от процессоров первого и второго типа. Есть формула для оценки вероятности нахождения системы в каждом состоянии, в этой формуле необходимо перебрать все возможные варианты состояний. Собственно как организовать этот перебор я и не могу придумать. Можно организовать N вложенных друг в друга циклов, но мне нужно, что число N задавалось пользователем и все считалось.
Пример перебора: N = 3, m1 = 2, m2 = 3, m3 = 1.
Состояния системы
000
100
200
010
110
210
020
120
220
030
130
230
001
101
201
011
111
211
и т.д.

Подскажите, может я не могу догнать до какого-то очевидного и простого решения?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2012, 05:35     Задача перебора элементов
Посмотрите здесь:

Алгоритм перебора C++
C++ Ускорение алгоритма перебора
C++ Программа метод перебора
Объяснить алгоритм просто перебора C++
Оптимизация полного перебора C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.04.2012, 07:37     Задача перебора элементов #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
#include <iostream>
using namespace std;
#define N_max 10
int mas[N_max], mas1[N_max], N;
void rec(int a)
{
    int i;
    if(a==N)
    {
        for(i=0; i<N; i++)
            cout<<mas1[i]<<" ";
        cout<<endl;
        return;
    }
    for(i=0; i<=mas[a]; i++)
    {
        mas1[a]=i;
        rec(a+1);
    }
}
int main()
{
    int i;
    cout<<"N= "; cin>>N;
    for(i=0; i<N; i++)
    {
        cout<<"m"<<i+1<<"= "; cin>>mas[i];
    }
    rec(0);
    return 0; 
}
Woody-krsk
1 / 1 / 0
Регистрация: 20.12.2010
Сообщений: 62
21.04.2012, 10:56  [ТС]     Задача перебора элементов #3
Ух, блин, чот тут с рекурсией, нельзя ли некоторые места раскоментить, а то я некоторые моменты и не знаю?..
Вот тут где границы и цикла и что делает return?
Цитата Сообщение от valeriikozlov Посмотреть сообщение
for(i=0; i<N; i++)
cout<<mas1[i]<<" ";
cout<<endl;
return;
А вот тут как вы сделали, что оно в консольке начинали все с новой строчки без endl'ов?
Цитата Сообщение от valeriikozlov Посмотреть сообщение
cout<<"N= "; cin>>N;
for(i=0; i<N; i++)
{
cout<<"m"<<i+1<<"= "; cin>>mas[i];
}
Ну и идею бы на словах еще.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.04.2012, 12:05     Задача перебора элементов #4
Цитата Сообщение от Woody-krsk Посмотреть сообщение
Ну и идею бы на словах еще.
лучше с этого и начать.
Идея: перебор всех вариантов с помощью рекурсии.
Эта часть:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
cout<<"N= "; cin>>N;
for(i=0; i<N; i++)
{
cout<<"m"<<i+1<<"= "; cin>>mas[i];
}
в консольке ничего не выводит с новой строчки, а просто идет заполнение значениями mi массива mas[].
Далее следует вызов: rec(0); - начинаем работать с первым элементом вариантов состояний.

см комментарии:
Цитата Сообщение от valeriikozlov Посмотреть сообщение
void rec(int a)
{
int i;
if(a==N)// если количество элементов равно N
{
for(i=0; i<N; i++)// то выводим на экран очередной вариант, записанный в mas1[]
cout<<mas1[i]<<" ";
cout<<endl;// переводим на новую строку
return;// и возвращаемся из функции rec()
}
for(i=0; i<=mas[a]; i++)// эта точка будет достижима когда a<N. Для очередного элемента с индексом a, перебираем возможные варианты от 0 до m[a]
{
mas1[a]=i;// и записываем эти значения в mas1[a]
rec(a+1);// вызываем рек.функцию для значения со следующим индексом
}
}
Woody-krsk
1 / 1 / 0
Регистрация: 20.12.2010
Сообщений: 62
22.04.2012, 04:54  [ТС]     Задача перебора элементов #5
Все равно куча вопросов, но пока попробую разобраться сам, никогда с рекурсией раньше не работал.
Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 06:24     Задача перебора элементов #6
Цитата Сообщение от Woody-krsk Посмотреть сообщение
Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно?
да, все правильно
Yandex
Объявления
22.04.2012, 06:24     Задача перебора элементов
Ответ Создать тему
Опции темы

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