C ++ рекурсивная помощь - PullRequest
Новая
       36

C ++ рекурсивная помощь

0 голосов
/ 16 марта 2011

У меня проблемы с рекурсией.Может кто-нибудь показать мне, как получить это в форме кода?

с учетом vector <int> со значениями 1,2,3,4,5, ..

Я хочу написать функцию, которая сравниваетвсе значения друг с другом.меня не волнует, что 1 != 2 сейчас эквивалентно 2 != 1.

я настолько плох в рекурсии

и я обещаю, что это не домашняя работа

РЕДАКТИРОВАТЬ что я пытаюсь сделатьсделать, это отсортировать события по расписанию.У меня есть несколько событий, происходящих в один и тот же день, и я хочу выяснить, все перестановки графика

2, вложенные в циклы, не будут работать, так как я сравниваю несколько (> 2) значений 

event 1 @ 0100-0230, or @ 0200-0330
event 2 @ 1200-1500, or @ 0800-1100
event 3 @ 1200-1300, or @ 1300-1400, or @ 1400-1500
.
.
.

для каждого сравнения я хочу выяснить, пересекается ли этот набор событий.я не пытаюсь найти набор событий, которые не пересекаются

я хочу получить вывод типа 

event 1 @ 0100-2300, event 2 @ 0800-1100, event 3 @ 1200-1300 // will be printed out
event 2 @ 0200-0330, event 2 @ 1200-1500, event 3 @ 1200-1300 // will be ignored

Ответы [ 3 ]

2 голосов
/ 16 марта 2011

Полагаю, вы исследуете связь между рекурсией и итерацией. Обычно простая итерация преобразуется в хвостовую рекурсию - вид рекурсии, где рекурсивный вызов - это последнее, что вы делаете, поэтому нет необходимости иметь глубокий стек.

Это немного псевдокод, плюс он не проверен - но он должен работать. 

void compareOne(int compareWith, iterator b, iterator e) {
    if (b == e) return;
    if (compareWith == *b) {
        // do something
    }
    compareOne(compareWith, b+1, e);
}


void compareAll(iterator b, iterator e) {
    if (b == e) return;
    compareOne(*b, b+1, e);
    compareAll(b+1, e);
}
1 голос
/ 16 марта 2011

Бьюсь об заклад, это домашнее задание ... но я не понимаю, зачем вам рекурсия: 

for(int i = 0; i<v.size(); ++i)
{
   for(int j = i+1; j < v.size(); ++j)
   {
      compare v[i] and v[j]
   }
}
0 голосов
/ 16 марта 2011

Зачем тебе рекурсия? Простая итерация будет делать: 

using namespace std;
vector<int> v;
...
for (int i = 0; i < v.size() - 1; i++)
    for (int j = i + 1; j < v.size(); j++)
        if (v[i] == v[j])
            cout << "Oops" << endl;

Или вы можете использовать итераторы: 

vector::const_iterator beforelast = v.end(); --beforelast;
for (vector::const_iterator i = v.begin(); i != beforelast; ++i)
    for (vector::const_iterator j = i + 1; j != v.end(); ++j)
        if (*i == *j)
            cout << "Oops" << endl;

Один может попытаться решить проблему с помощью рекурсии: 

bool f(vector<int>& v, int lastidx)
{
    int lastval = v[lastidx];
    for (int i = 0; i < lastidx; i++)
        if (v[i] == lastval)
            return false;
    return f(v, lastidx - 1);
}

Однако, по моему мнению, нерекурсивное решение лучше.

...