Задача
Построить все правильные скобочные выражения длины 10, то есть, которые содержат по 5 левых и по 5 правых скобок.
Код на языке С++:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <string> using namespace std; void f(int x, string s){ if(s.size() == 10){cout << s << endl; return;} if(x>0){f(x-1,s+")");} if(10-s.size() > x){f(x+1,s+"(");} } int main() { f(0,""); return 0; } |
Посмотреть программу можно здесь
Код на языке Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void f (int x, String s) { if(s.length() == 10) { System.out.println(s) ; return; } if(x>0) f(x-1,s+")"); if(10-s.length() > x) f(x+1,s+"("); } public static void main (String[] args) { f(0, ""); } } |
Ссылка на программу: http://ideone.com/9MjHSA
Решение:
В переменной [latex]x[/latex] мы будем хранить количество открытых ([latex]»(«[/latex]) скобок. Далее проверяем условие, что если [latex]x>0[/latex], то можем поставить закрывающую ([latex]»)»[/latex]) скобку. Идем дальше, смотрим сколько свободных мест осталось и если мест осталось столько же, сколько открывающих, то все остальные закрывающие.