Puzzle z nawiasami (Poziom 3, Wykład 4)

Myślę, że jest takie zadanie, które wywołało różne emocje wśród wielu kadetów JavaRush. We wrześniu, kiedy zaczynałem kurs, zadanie było sformułowane następująco: W wyrażeniu 1+2*3+4*5+6*7+8*9+10 umieść dwie pary nawiasów tak, aby wartość wyrażenie staje się równe 537 Teraz, wracając do rozwiązania, odkryłem, że zmieniono sformułowanie, należy w wyrażeniu 2*3+4*5+6*7 umieścić dwie pary nawiasów, aby wartość wynosiła 382. nowy warunek jest oczywiście prostszy niż poprzedni, ponieważ liczba możliwych opcji zmniejszyła się o około rząd wielkości. Ale pozostałych 85 wystarczy, aby spędzić godzinę lub dwie na ręcznym wyszukiwaniu. Oczywiście zadanie nie jest bezpośrednio związane z programowaniem w Javie. Dlatego tego nie rozwiązałem. Takie problemy nie mają żadnych rozwiązań analitycznych opartych na rozumowaniu czy własnościach liczb, a jedynie brutalna siła, czyli tępe przeszukanie wszystkich możliwych opcji. Z drugiej strony nie mniej oczywiste jest, że to właśnie za pomocą programowania rozwiązuje się problemy tego typu. Dlatego wróciłem. Po prostu przyzwyczaiłem się do IDE, a problemy kursu na poziomie 8 powaliły mnie na łopatki i nie miałem nic przeciwko spędzeniu wieczoru lub dwóch na ich rozwiązywaniu. Poniżej przedstawiono sposób rozwiązania tego problemu za pomocą języka Java. Jako podstawę przykładu użyłem starego warunku. Przede wszystkim potrzebujemy sposobu obliczenia wartości wyrażenia zapisanego w postaci ciągu znaków. Nie znaleźliśmy takiej metody w standardowych bibliotekach Java. Wygooglowałem to: http://www.cyberforum.ru/java-j2se/thread283139.html jest całkiem odpowiedni do naszych celów. Algorytm opiera się na odwrotnej notacji polskiej i działa dla prawidłowych ciągów znaków zawierających cztery operacje arytmetyczne i nawiasy. Utwórz nowy projekt z klasą PPN, skopiuj i wklej kod z linku do pliku. Problem można rozwiązać za pomocą metody main() klasy PPN. Ale to nie jest konieczne. Ideologia Java opiera się na podziale problemu na małe podzadania, z których każde jest realizowane we własnej klasie i metodzie. Dobrym rozwiązaniem byłoby rozwiązanie problemu w innej klasie, zapisanego w osobnym pliku. Dlatego utwórz kolejną klasę, w której napiszesz algorytm wyliczania nawiasów. Aby obliczyć wartość ciągu, należy wywołać metodę eval() klasy PPN: Na przykład tak

System.out.println(PPN.eval(“2*3+4”));

lub tak

int result = PPN.eval(s2);

Przyjrzyjmy się bliżej linii 1+2*3+4*5+6*7+8*9+10 i zadajmy sobie pytanie, na ile sposobów możemy umieścić nawias otwierający? Można go ułożyć na dziesięć sposobów. Jeżeli numerujemy znaki ciągu zaczynając od zera, to nawias otwierający można umieścić w pozycjach {0,2,4,6,8,10,12,14,16,18}. Umieszczenie nawiasu np. na szóstej pozycji oznacza, że ​​należy wziąć wszystkie znaki od zera do pięciu włącznie, następnie umieścić nawias, a następnie wziąć wszystkie znaki od szóstej do końca wiersza: Podobnie nawias zamykający można umieścić w pozycjach {1,3,5,7,9,11,13,15,17,20}. Dwie ostatnie cyfry psują całą malinkę, wszystkie pozostałe pozycje różnią się od siebie o dwa, a 17 i 20 o trzy. Nie będzie więc możliwe proste zadeklarowanie zmiennej zawierającej numer pozycji nawiasu zamykającego i zwiększanie jej wartości o dwa w każdym kolejnym kroku. Wartości pozycji będziemy przechowywać w tablicach:

int[] left = {0,2,4,6,8,10,12,14,16,18};

int[] right = {1,3,5,7,9,11,13,15,17,20};

I będziemy zwiększać zmienną indeksową o jeden przy każdej iteracji pętli odpowiedzialnej za wyliczanie opcji. W sumie potrzebne są odpowiednio dwa nawiasy otwierające i dwa zamykające, wymagane są cztery zmienne indeksujące:

int indLeft1, indLeft2, indRight1, indRight2;

Nawiasy w wyrażeniu można umieścić na dwa sposoby:

(  )  (  )
(  (  )   )

Dla każdej metody należy napisać własny algorytm; rozważ algorytm dla pierwszej metody rozmieszczania nawiasów. Rzeczywiste wyliczenie opcji jest reprezentowane przez zagnieżdżone pętle for:

for (int indLeft1=0;indLeft1<10;indLeft1++)
   for(int indRight1=indLeft1+1;indRight1<10;indRight1++)
      for (int indLeft2=indRight1+1;indLeft2<10;indLeft2++)
         for (int indRight2=indLeft2+1;indRight2<10;indRight2++)

Na początku programu inicjujemy zmienną łańcuchową oryginalnym ciągiem znaków bez nawiasów:

String s = "1+2*3+4*5+6*7+8*9+10";

W treści wewnętrznej pętli tworzymy linię z nawiasami:

String s2 = s.substring(0, left[indLeft1]) + "(" +
		 s.substring(left[indLeft1], right[indRight1]) + ")" +
		 s.substring(right[indRight1],left[indLeft2]) + "(" +
		 s.substring(left[indLeft2], right[indRight2]) + ")" +
		 s.substring(right[indRight2], s.length());

Zwróć uwagę na specyfikę metody substring() klasy String. Wybierany jest podciąg, którego numer pierwszego znaku jest równy pierwszemu parametrowi, a numer ostatniego jest równy drugiemu parametrowi minus jeden . zobacz https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , podano nawet przykłady mające na celu ograniczenie nieporozumień. Po utworzeniu ciągu znaków w nawiasach obliczamy wartość i porównujemy ją z wymaganą:

int result = PPN.eval(s2);
if (result == 537)
          System.out.println(s2);

Blok zagnieżdżonego układu nawiasów jest napisany w podobny sposób. Jedyne na co chcę zwrócić uwagę to to, że przy zagnieżdżeniu nawiasów nawias otwierający lub zamykający może znajdować się w tej samej pozycji, np.

1+((2*3+4*5+6)*7+8*9+10)

Lub

(1+2*(3+4*5+6*7+8))*9+10

Właściwie to wszystko. Po uruchomieniu poprawnie napisany program generuje pojedynczą odpowiedź: 1+2*(3+4*(5+6*7)+8*9)+10