VPF::расстоновки скобок в, например, строке

gosn1ck

Дата 18.4.2009, 14:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 18.4.2009

Репутация: 1
Всего: 1

Добрый день, есть задачка в учебнике Шень А. "Программирование: теоремы и задачи" и звучит она так: "Перечислить все расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий. Например, для n=4 есть 5 расстановок: ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd))."

хотелось бы реализовать на c++, а мыслей нет с чего начать. я не прошу за меня прогу написать. помогите с алгоритмом. не знаю даже как "подойти" к задачe.

megabist

Дата 18.4.2009, 15:30 (ссылка)

(нет голосов)

Загрузка ...

Mart Slaaf

Профиль
Группа: Участник
Сообщений: 455
Регистрация: 3.4.2006
Где: Мск

Репутация: нет
Всего: 31

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

--------------------

Don't panic!

Жди, и Фатум тебя приведёт...

math64

Дата 18.4.2009, 16:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

В C++, возможно, проще составть дерево:

Код


class Product {
private:
   string args; // строка abcd
   int index; // место разделения на левое и правое произведения
   Product* left; //первый аргумент: первоначально a
   Product* right; //второй аргумент: первоначально bcd
   void BuildArguments(); // создать left и right в соответствии с index
public:
   Product(string args);
   ~Product();
   bool Next(); // получить следующий вариант расстановки скобок
   void Print(); // напечатать
};

void main() {
   Product p("abcd");
   do {
      p.Print();
   } while(p.Next());
}

Это сообщение отредактировал(а) math64 - 18.4.2009, 16:13

gosn1ck

Дата 19.4.2009, 19:45 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 18.4.2009

Репутация: 1
Всего: 1

спасибо =)

Это сообщение отредактировал(а) gosn1ck - 19.4.2009, 19:46

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »