Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > расстоновки скобок в, например, строке

Автор: gosn1ck 18.4.2009, 14:45

Добрый день, есть задачка в учебнике Шень А. "Программирование: теоремы и задачи" и звучит она так: "Перечислить все расстановки скобок в произведении 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

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

Автор: math64 18.4.2009, 16:12

В 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());
}

Автор: gosn1ck 19.4.2009, 19:45

спасибо =)