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

@Woody-krsk · Регистрация: 20.12.2010

Author24 — интернет-сервис помощи студентам

Всем привет! Собственно есть задача с которой я не могу совладать. Загвоздка не в программировании, а в том чтоб придумать алгоритм, чтобы решал эту задачу. Может кто подскажет, я уже всю голову сломал.
Задача на первый взгляд элементарная, но это только на первый взгляд.
Задача: есть некоторая разнородная многопроцессорная система, которая состоит из 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
и т.д.

Подскажите, может я не могу догнать до какого-то очевидного и простого решения?

valeriikozlov · 21.04.2012, 07:37

вариант:

C++

#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 · 21.04.2012, 10:56 **[ТС]**

Ух, блин, чот тут с рекурсией, нельзя ли некоторые места раскоментить, а то я некоторые моменты и не знаю?..
Вот тут где границы и цикла и что делает 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 · 21.04.2012, 12:05

Сообщение от 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 · 22.04.2012, 04:54 **[ТС]**

Все равно куча вопросов, но пока попробую разобраться сам, никогда с рекурсией раньше не работал.
Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно?

valeriikozlov · 22.04.2012, 06:24

Сообщение от Woody-krsk

Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно?

да, все правильно

@Woody-krsk 1 / 1 / 0 Регистрация: 20.12.2010 Сообщений: 62
		1
	Задача перебора элементов 21.04.2012, 05:35. Показов 3701. Ответов 5 Метки нет (Все метки) Всем привет! Собственно есть задача с которой я не могу совладать. Загвоздка не в программировании, а в том чтоб придумать алгоритм, чтобы решал эту задачу. Может кто подскажет, я уже всю голову сломал. Задача на первый взгляд элементарная, но это только на первый взгляд. Задача: есть некоторая разнородная многопроцессорная система, которая состоит из 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 и т.д. Подскажите, может я не могу догнать до какого-то очевидного и простого решения? 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]; } Ну и идею бы на словах еще. 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	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);// вызываем рек.функцию для значения со следующим индексом } } 1

@Woody-krsk 1 / 1 / 0 Регистрация: 20.12.2010 Сообщений: 62
	22.04.2012, 04:54 [ТС]	5
	Все равно куча вопросов, но пока попробую разобраться сам, никогда с рекурсией раньше не работал. Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно? 0

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	22.04.2012, 06:24	6
	Сообщение от Woody-krsk Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно? да, все правильно 0