Teka-teki dengan kurungan (Tahap 3, Kuliah 4)

Terdapat tugas sedemikian, saya percaya, yang menyebabkan pelbagai emosi di kalangan ramai kadet JavaRush. Pada bulan September, apabila saya memulakan kursus, tugasan telah dirumuskan seperti berikut: Dalam ungkapan 1+2*3+4*5+6*7+8*9+10, letakkan dua pasang kurungan supaya nilai ungkapan menjadi sama dengan 537 Sekarang, setelah kembali kepada penyelesaian, saya mendapati bahawa kata-kata telah diubah, adalah perlu untuk meletakkan dua pasang kurungan dalam ungkapan 2*3+4*5+6*7 supaya nilainya menjadi sama dengan 382. keadaan baru, sudah tentu, adalah lebih mudah daripada yang sebelumnya, kerana bilangan pilihan yang mungkin telah berkurangan kira-kira satu susunan magnitud. Tetapi baki 85 adalah cukup untuk menghabiskan satu atau dua jam pada carian manual. Jelas sekali, tugas itu tidak berkaitan secara langsung dengan pengaturcaraan Java. Itulah sebabnya saya tidak menyelesaikannya. Masalah sedemikian tidak mempunyai sebarang penyelesaian analitikal berdasarkan penaakulan atau sifat nombor, hanya kekerasan, iaitu carian tumpul semua pilihan yang mungkin. Sebaliknya, tidak kurang jelasnya bahawa dengan bantuan pengaturcaraan masalah jenis ini diselesaikan. Sebab tu saya balik. Saya baru terbiasa dengan IDE, dan masalah kursus pada tahap 8 membingungkan saya dan saya tidak keberatan menghabiskan satu atau dua petang untuk menyelesaikannya. Di bawah ialah cara anda boleh menyelesaikan masalah ini menggunakan Java. Saya menggunakan keadaan lama sebagai asas untuk contoh. Pertama sekali, kita memerlukan cara untuk mengira nilai ungkapan yang ditulis sebagai rentetan. Kami tidak dapat mencari kaedah sedemikian dalam perpustakaan Java standard. Saya google ini: http://www.cyberforum.ru/java-j2se/thread283139.html agak sesuai untuk tujuan kami. Algoritma ini berdasarkan tatatanda Poland terbalik dan berfungsi untuk rentetan sah yang mengandungi empat operasi aritmetik dan kurungan. Buat projek baharu dengan kelas PPN di dalamnya, salin dan tampal kod daripada pautan ke dalam fail. Masalahnya boleh diselesaikan dalam kaedah main() kelas PPN. Tetapi ia tidak perlu. Ideologi Java didasarkan pada membahagikan masalah kepada subtugas kecil, yang setiap satunya dilaksanakan dalam kelas dan kaedahnya sendiri. Pendekatan yang baik adalah untuk menyelesaikan masalah dalam kelas lain, disimpan dalam fail berasingan. Oleh itu, buat kelas lain di mana anda akan menulis algoritma untuk menghitung kurungan. Untuk mengira nilai rentetan, anda perlu memanggil kaedah eval() kelas PPN: Contohnya, seperti ini

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

atau lebih

int result = PPN.eval(s2);

Mari kita lihat dengan teliti pada baris 1+2*3+4*5+6*7+8*9+10 dan tanya diri kita sendiri berapa banyak cara kita boleh meletakkan tanda kurung pembuka? Ia boleh diletakkan dalam sepuluh cara. Jika anda menomborkan aksara rentetan bermula dari sifar, maka kurungan pembukaan boleh diletakkan pada kedudukan {0,2,4,6,8,10,12,14,16,18}. Meletakkan kurungan, sebagai contoh, pada kedudukan keenam bermakna anda perlu mengambil semua aksara dari sifar hingga lima inklusif, kemudian letakkan kurungan, kemudian ambil semua aksara dari keenam hingga penghujung baris: Begitu juga, kurungan penutup boleh diletakkan pada kedudukan {1,3,5,7,9,11,13,15,17,20}. Dua nombor terakhir merosakkan keseluruhan raspberi, semua kedudukan lain berbeza antara satu sama lain dengan dua, dan 17 dan 20 dengan tiga. Oleh itu, tidak mungkin untuk hanya mengisytiharkan pembolehubah yang mengandungi nombor kedudukan kurungan penutup dan meningkatkan nilainya sebanyak dua pada setiap langkah seterusnya. Kami akan menyimpan nilai kedudukan dalam tatasusunan:

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

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

Dan kami akan meningkatkan pembolehubah indeks sebanyak satu pada setiap lelaran gelung yang bertanggungjawab untuk menghitung pilihan. Secara keseluruhan, dua kurungan pembukaan dan dua kurungan penutup diperlukan, masing-masing, empat pembolehubah indeks diperlukan:

int indLeft1, indLeft2, indRight1, indRight2;

Tanda kurung dalam ungkapan boleh diletakkan dalam dua cara:

(  )  (  )
(  (  )   )

Untuk setiap kaedah anda perlu menulis algoritma anda sendiri; pertimbangkan algoritma untuk kaedah pertama menyusun kurungan. Penghitungan sebenar pilihan diwakili oleh gelung bersarang:

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++)

Pada permulaan program, kami memulakan pembolehubah rentetan dengan rentetan asal tanpa kurungan:

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

Dalam badan gelung dalam kita membentuk garisan dengan kurungan:

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

Beri perhatian kepada keanehan kaedah substring() kelas String. Subrentetan dipilih, bilangan aksara pertama yang sama dengan parameter pertama, dan nombor yang terakhir adalah sama dengan parameter kedua tolak satu . lihat https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , malah terdapat contoh yang diberikan untuk mengurangkan salah faham. Selepas membentuk rentetan dengan kurungan, kami mengira nilai dan membandingkannya dengan yang diperlukan:

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

Blok untuk susunan kurungan bersarang ditulis dengan cara yang sama. Satu-satunya perkara yang saya ingin menarik perhatian ialah apabila kurungan bersarang, kurungan pembukaan atau penutup boleh berada dalam kedudukan yang sama, contohnya.

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

atau

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

Sebenarnya, itu sahaja. Selepas pelancaran, atur cara yang ditulis dengan betul menghasilkan satu jawapan: 1+2*(3+4*(5+6*7)+8*9)+10