Tugas pembekalan. Beanpoisk_1

Halo, orang Khabrovit terkasih. Serangkaian artikel berisi diskusi tentang tugas-tugas yang diberikan di kelas 8 pada pelajaran ilmu komputer di Chelyabinsk Fisika dan Matematika Lyceum No. 31. Sedikit sejarah ... Lyceum kami adalah salah satu lembaga pendidikan terkuat di Rusia, yang menempati peringkat ke-5 dalam peringkat pada daya saing lulusan, kalah dari sekolah-sekolah di Moskow dan St. Petersburg. Murid secara teratur memenangkan kompetisi di tingkat nasional dan internasional.
Artikel ini tidak memiliki teori, hanya berisi metode untuk memecahkan masalah. Rincian tentang pencarian bin dijelaskan di sini.
Jadi, mari kita beralih ke tugas. Tugas-tugas ini melibatkan penggunaan pencarian biner, termasuk pencarian bin untuk jawaban. Seperti yang kita ketahui, pencarian bin adalah algoritma untuk mencari objek dengan atribut yang diberikan dalam satu set objek. Kami mendaftar untuk daftar yang diurutkan dalam urutan naik / turun. Hanya 4 tugas, 2 di antaranya ditujukan untuk menerapkan "algoritma tanpa kismis . "

Pencarian biner kiri dan kanan

Dalam tugas ini, Anda harus terlebih dahulu mempertimbangkan panjang baris pertama dan kedua, kemudian menulis setiap baris berikutnya dalam daftar. Setelah kita mengambil setiap elemen dari daftar kedua dan mencari perbatasan kanan dan kiri untuk itu. Anda mungkin memperhatikan bahwa jika jumlahnya tidak ada dalam daftar, nilai total perbatasan kiri dan perbatasan kanan dalam pencarian biner kiri dan kanan sama.

n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = -1 right = len(a) # ,     while right - left > 1: middle = (right + left) // 2 if a[middle] < x: left = middle else: right = middle left_1 = -1 right_1 = len(a) # ,     while right_1 - left_1 > 1: middle = (right_1 + left_1) // 2 if a[middle] <= x: left_1 = middle else: right_1 = middle if left == left_1 and right == right_1: print(0) #     ,     continue if right == left_1: print(right + 1, right + 1) else: print(right + 1, left_1 + 1) 

Perkiraan pencarian biner

Ini adalah teka-teki dengan twist! Di sini perlu untuk mengubah pencarian sehingga dilakukan bahkan untuk angka yang tidak ada dalam daftar untuk pencarian. Di sini kita juga mencari tengah dalam "daftar batas", maka elemen yang di tengah dibandingkan dengan angka, jika kurang dari itu, kita menulis indeks tengah + 1 (yaitu, tidak termasuk tengah masa lalu dalam daftar batas) ke perbatasan kiri (yang merupakan indeks), jika tidak, di perbatasan kanan kita menulis indeks tengah. Kami melakukan semua ini sementara perbatasan kiri lebih kecil dari kanan. Setelah menemukan kiri dan kanan, kami mempertimbangkan kasus ketika jumlahnya tidak ada dalam daftar dan jarak ke kiri kurang dari atau sama dengan yang di kanan. Oleh karena itu, kami menyimpulkan [kiri - 1], jika tidak, [kiri].

 n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) for x in b: left = 0 right = n - 1 while left < right: middle = (left + right) // 2 if a[middle] < x: left = middle + 1 else: right = middle if left > 0 and a[left] != x and abs(a[left - 1] - x) <= abs(a[left] - x): print(a[left - 1]) else: print(a[left]) 

Akar kuadrat dan kuadrat persegi

Tadam! Tugas pencarian biner dengan jawaban. Untuk mulai dengan, dari perpustakaan matematika kita menghubungkan fungsi sqrt, yang menghitung akar kuadrat, setelah itu kita mendefinisikan 0 untuk perbatasan kiri, dan 1e10 untuk perbatasan kanan, yaitu, 10 miliar, berdasarkan pembatasan yang ditentukan dalam kondisi. Selanjutnya, seperti dalam pencarian bin yang khas, kami mencari tengah, kemudian kami membandingkan. Tapi apa yang menarik? Di sini tengah adalah x dalam persamaan. Mengingat hal ini, kami menentukan nilai persamaan dan membandingkannya dengan jawaban nyata (mis., C). Baiklah, kita memindahkan batas, sampai perbedaan batas kurang dari atau sama dengan 10 miliar, ini adalah akurasi pengukuran. Kemudian kita mengalikan satu juta, membulatkan, menerjemahkan ke dalam divisi int dan nyata dengan jutaan yang sama.

 from math import sqrt c = float(input()) left = 0 right = 1e10#1 c 10-  while right - left > 10e-10:#10   1 middle = (left + right) / 2 if middle * middle + sqrt(middle) >= c: right = middle else: left = middle #  10e6, ,   int,   10e6 print(int(round(left*10e6))/10e6) 

Tantangan yang Sangat Mudah

Sudah ada analisis untuk tugas ini, jadi saya hanya akan melampirkan kode.

 n, x, y = map(int, input().split()) min1 = min(x, y) if n == 1: print(min1) else: left = 0 right = n * (x + y - min1 + 1) while right - left > 1: middle = (right + left) // 2 if n - 1 <= middle // x + middle // y: right = middle else: left = middle print(min1 + left + 1) 

Untuk mengkonsolidasikan materi, Anda dapat memecahkan masalah dari sini.