Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Woody-krsk
1 / 1 / 1
Регистрация: 20.12.2010
Сообщений: 62
#1

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

21.04.2012, 05:35. Просмотров 968. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2012, 05:35
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача перебора элементов (C++):

Задача о рюкзаке методом полного перебора. Нужно пояснение по коду
Здравствуйте, нужно пояснение по этому коду. Код не мой, также в нем много...

Исключение элементов из перебора и последовательность двойки
Первый вопрос Как исключить элемент из перебор? Допустим у меня есть массив...

Алгоритм перебора
Всем доброго времени суток! Уважаемые форумчане подскажите алгоритм полного...

Оптимизация полного перебора
Пусть требуется подобрать пин-код длиной 4 символа (может содержать как цифры и...

Программа метод перебора
"Составить программу, находящую максимальное и минимальное значе-ние функции...

Ускорение алгоритма перебора
Здравствуйте! В общем есть такая задачка: Имеются N(1 ≤ N ≤ 18) камней с...

5
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 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; 
}
1
Woody-krsk
1 / 1 / 1
Регистрация: 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
Эксперт С++
4683 / 2509 / 751
Регистрация: 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);// вызываем рек.функцию для значения со следующим индексом
}
}
1
Woody-krsk
1 / 1 / 1
Регистрация: 20.12.2010
Сообщений: 62
22.04.2012, 04:54  [ТС] #5
Все равно куча вопросов, но пока попробую разобраться сам, никогда с рекурсией раньше не работал.
Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно?
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
22.04.2012, 06:24 #6
Цитата Сообщение от Woody-krsk Посмотреть сообщение
Один вопрос главный, return возвращает нас в то место, где функция была вызвана, правильно?
да, все правильно
0
22.04.2012, 06:24
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2012, 06:24
Привет! Вот еще темы с решениями:

Объяснить алгоритм просто перебора
доброго времени суток! мой вопрос, наверное, покажется Вам очень глупым, но...

Изменения перебора и сохранение в файл
Всем добрый день. Есть исходный код перебора символов 0123. Перебирает...

Поиск массива методом последовательного перебора
Поиск массива методом последовательного перебора в С++

Решение нелинейного уравнения методом перебора
Решить уравнение sin(1/x)=0 методом перебора на промежутке x = .


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

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

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