括弧付きパズル (レベル 3、レクチャー 4)

多くの JavaRush 候補生の間でさまざまな感情を引き起こしたそのようなタスクがあったと思います。9 月にコースを開始したとき、タスクは次のように定式化されました。 式 1+2*3+4*5+6*7+8*9+10 に、2 組のかっこを配置して、式は 537 と等しくなります さて、ソリューションに戻って、表現が変更されていることを発見しました。値が 382 になるように、式 2*3+4*5+6*7 に 2 組のかっこを置く必要があります。もちろん、新しい状態は以前のものよりも単純です。可能なオプションの数は約 1 桁減少しました。しかし、残りの 85 件は手動検索に 1 ～ 2 時間を費やすのに十分です。明らかに、このタスクは Java プログラミングに直接関係しません。だからこそ解決しなかったのです。このような問題には、推論や数値の特性に基づいた分析的な解決策はなく、強引な方法、つまりすべての可能な選択肢を単純に探索する方法しかありません。一方で、この種の問題が解決されるのはプログラミングの助けであることも同様に明白です。だからこそ戻ってきたのです。ちょうど IDE に慣れてきたところですが、レベル 8 までのコースの問題には度肝を抜かれ、問題を解くのに 1 ～ 2 晩費やすことも気にしませんでした。Java を使用してこの問題を解決する方法を以下に示します。例の基礎として古い条件を使用しました。まず、文字列として記述された式の値を計算する方法が必要です。標準 Java ライブラリにはそのようなメソッドは見つかりませんでした。これをグーグルで調べました：http://www.cyberforum.ru/java-j2se/thread283139.htmlは私たちの目的に非常に適しています。このアルゴリズムは逆ポーランド記法に基づいており、四則演算と括弧を含む有効な文字列に対して機能します。PPN クラスを含む新しいプロジェクトを作成し、リンクからコードをコピーしてファイルに貼り付けます。この問題は、PPN クラスの main() メソッドで解決できます。しかし、それは必要ありません。Java のイデオロギーは、問題を小さなサブタスクに分割し、それぞれが独自のクラスとメソッドで実装されることに基づいています。良いアプローチは、別のファイルに保存された別のクラスで問題を解決することです。したがって、括弧を列挙するためのアルゴリズムを記述する別のクラスを作成します。文字列の値を計算するには、PPN クラスの eval() メソッドを呼び出す必要があります。たとえば、次のようになります。

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

とか、ぐらい

int result = PPN.eval(s2);

1+2*3+4*5+6*7+8*9+10 という行をよく見て、開き括弧を入れる方法は何通りあるか自問してみましょう。10通りの配置が可能です。文字列の文字にゼロから始まる番号を付ける場合、左括弧は位置 {0,2,4,6,8,10,12,14,16,18} に配置できます。たとえば 6 番目の位置に括弧を置くということは、0 から 5 までのすべての文字を取得し、次に括弧を入れてから、6 番目から行末までのすべての文字を取得する必要があることを意味します。 同様に、閉じ括弧は {1,3,5,7,9,11,13,15,17,20} の位置に配置できます。最後の 2 つの数字はラズベリー全体を台無しにし、他のすべての位置は互いに 2 ずつ異なり、17 と 20 は 3 ずつ異なります。したがって、閉じ括弧の位置番号を含む変数を単純に宣言し、次のステップごとにその値を 2 ずつ増やすことはできません。位置の値を配列に保存します。

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

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

そして、オプションを列挙するループの反復ごとにインデックス変数を 1 つずつ増やします。合計で、開き括弧が 2 つと閉じ括弧が 2 つ必要になり、インデックス変数が 4 つ必要になります。

int indLeft1, indLeft2, indRight1, indRight2;

式の中のかっこは、次の 2 つの方法で配置できます。

(  )  (  )
(  (  )   )

メソッドごとに独自のアルゴリズムを作成する必要があります。括弧を配置する最初のメソッドのアルゴリズムを検討してください。オプションの実際の列挙は、ネストされた 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++)

プログラムの最初に、括弧のない元の文字列を使用して文字列変数を初期化します。

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

内側のループの本体では、括弧で囲まれた行を形成します。

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

String クラスの substring() メソッドの特殊性に注意してください。部分文字列が選択されます。その最初の文字の番号は最初のパラメータに等しく、最後の文字の番号は 2 番目のパラメータから 1 を引いたものに等しくなります。https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int)を参照してください。誤解を減らすために例も示されています。括弧で文字列を形成した後、値を計算し、必要な値と比較します。

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

括弧の入れ子配置のブロックも同様の方法で記述されます。唯一注意したいのは、括弧がネストされている場合、開始括弧または終了括弧が同じ位置にある可能性があるということです。

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

または

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

実はそれだけです。起動後、正しく書かれたプログラムは 1+2*(3+4*(5+6*7)+8*9)+10 という 1 つの答えを生成します。