Program Java untuk mencari punca kubus nombor menggunakan algoritma carian binari

Akar kubus ialah nilai integer yang, apabila didarab dengan sendirinya tiga kali berturut-turut, menghasilkan nilai asal. Dalam artikel ini, kami akan menulis program Java yang menggunakan carian binari untuk mencari punca kubus nombor. Mencari punca kubus nombor ialah aplikasi algoritma carian binari. Dalam artikel ini, kami akan membincangkan secara terperinci cara menggunakan carian binari untuk mengira punca kubus.

Contoh input-output

Example-1: 
Input: 64 
Output: 4 

Sebagai contoh, punca kubus bagi 64 ialah 4, dan keluarannya ialah 4.

Example-2: 
Input: 216
Output: 6  

Sebagai contoh, punca kubus bagi 216 ialah 6, dan keluarannya ialah 6.

Carian binari

Carian binari ialah algoritma yang digunakan untuk mencari elemen (iaitu kekunci dalam tatasusunan yang diisih). Algoritma binari berfungsi seperti berikut

• Andaikan tatasusunan ialah "arr". Isih tatasusunan dalam tertib menaik atau menurun.

• Mulakan rendah = 0 dan tinggi = n-1 (n = bilangan elemen), dan kira pertengahan sebagai tengah = rendah + (tinggi-rendah)/2. Jika kunci arr[tengah] == kemudian mengembalikan tengah, indeks tengah tatasusunan.

• Jika nilai kunci kurang daripada elemen arr[tengah], tetapkan indeks tinggi kepada indeks tengah -1; jika nilai kunci lebih besar daripada elemen tengah, tetapkan indeks rendah kepada indeks tengah +1

• Teruskan carian binari sehingga anda menemui elemen yang anda ingin cari.

• Jika rendah lebih besar daripada tinggi, kembalikan palsu secara langsung kerana nilai kunci tidak wujud dalam tatasusunan 'arr'.

Contoh mencari kunci menggunakan carian binari

Soalan

Memandangkan tatasusunan integer yang diisih arr = [1, 3, 5, 7, 9, 11], gunakan carian binari untuk mencari indeks elemen, iaitu kunci = 7.

Penyelesaian

• Mulakan rendah = 0 dan tinggi = 5 (indeks terakhir tatasusunan).

• Lelaran pertama gelung while memberikan indeks pertengahan pertengahan = rendah+ (tinggi-rendah)/2

• Median = 0+(5-0)/2 = 2.

Nilai

• arr[pertengahan] ialah 5, iaitu kurang daripada nilai kunci 7. Oleh itu, kami mengemas kini rendah= pertengahan+1 = 3.

• Lelaran kedua gelung while memberikan kita indeks pertengahan pertengahan = 4 dengan menggunakan rendah+ (tinggi-rendah)/2.

Nilai

• arr[pertengahan] ialah 9, iaitu lebih besar daripada nilai kunci 7. Oleh itu, kami mengemas kini tinggi = 3 (pertengahan - 1).

• Lelaran ketiga gelung while memberi kita indeks tengah pertengahan = 3.

• arr[pertengahan] ialah 7, sama dengan nilai kunci. Oleh itu, kami mengembalikan indeks tengah, iaitu 3.

• Jadi, dalam tatasusunan yang diberikan, indeks kunci ialah 7 dan kami mendapati indeks 3 menggunakan algoritma carian binari.

Algoritma untuk mencari punca kubus menggunakan carian binari

Langkah 1 - Pertimbangkan nombor 'n' dan mulakan rendah=0 dan kanan=n (nombor yang diberikan).

Langkah 2 - Cari median nilai rendah dan tinggi menggunakan pertengahan = rendah + (tinggi-rendah)/2.

Langkah 3 − Cari nilai pertengahan * pertengahan * pertengahan, jika pertengahan * pertengahan * pertengahan == n, kembalikan nilai pertengahan.

Langkah 4 - Jika nilai tengah kurang daripada n, maka rendah=pertengahan+1, jika tidak tinggi=pertengahan 1

Langkah 5 - Ulang langkah 2 hingga 4 sehingga anda menemui nilainya.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Dalam contoh ini, kami menggunakan algoritma carian binari untuk mencari punca kubus sesuatu nilai. Kami mencipta kelas tersuai 'BinarySearchCbrt' dan melaksanakan kod carian binari untuk mencari punca kubus nombor dalam fungsi 'cuberoot'. Sekarang, cipta objek kelas tersuai dan mulakan pembolehubah integer yang dipanggil 'nombor' dan panggil fungsi 'cuberoot' menggunakan objek kelas, dengan itu memaparkan output yang dikehendaki.

//Java Program to find Cube root of a number using Binary Search
import java.util.*;
class BinarySearchCbrt {
   public  int cuberoot(int number) {
      int low = 0;
      int high = number;
      while (low <= high) {
         int mid = (low + high) / 2;
         int cube = mid * mid*mid;
         if (cube == number) {
            return mid;
         } else if (cube < number) {
            low = mid + 1;
         } else {
            high = mid - 1;
         }
      }
      return 0;
   }
}
public class Main {
   public static void main(String[] args) {
      int n = 64;
      BinarySearchCbrt Obj  = new  BinarySearchCbrt();
      int result= Obj.cuberoot(n);
      System.out.println("Cube root of " + n + " = " + result);
   }
}

Output

Cube root of 64 = 4 

Kerumitan masa: O(NlogN) Ruang tambahan: O(1)

Jadi, dalam artikel ini kita telah membincangkan cara mencari punca kubus nombor menggunakan algoritma carian binari dalam Java.

Atas ialah kandungan terperinci Program Java untuk mencari punca kubus nombor menggunakan algoritma carian binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!