こんにちは、カブロビテス。 一連の記事には、チェリャビンスク物理および数学ライセウムNo. 31のコンピューターサイエンスレッスンでグレード8に与えられたタスクの議論が含まれています。 ちょっとした歴史...私たちのライセウムは、ロシアで最も強力な教育機関の1つであり、卒業生の競争力ランキングで5位になり、モスクワとサンクトペテルブルクの学校に負けました。 生徒は定期的に国内および国際レベルで大会に勝ちます。
この記事は理論に欠けており、問題を解決する方法のみが含まれています。 ビン検索の詳細については、ここで説明します。
それでは、タスクに移りましょう。 これらのタスクには、回答のビン検索を含むバイナリ検索の使用が含まれます。 ご存じのように、ビン検索は、オブジェクトのセット内の特定の属性によってオブジェクトを検索するためのアルゴリズムです。 昇順/降順でソートされたリストに適用します。 「レーズンのないアルゴリズム」を適用することを目的とするタスクは2つだけです 。
左右のバイナリ検索
このタスクでは、最初に1行目と2行目の長さを考慮してから、リストの次の各行に書き込む必要があります。 2番目のリストの各要素を取得し、左右の境界を探した後。 数値がリストにない場合、左右のビン検索の左境界線と右境界線の合計値が等しいことに気付くかもしれません。
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)
近似バイナリ検索
ここにひねりを加えたこのパズルがあります！ ここでは、検索のリストにない番号でも実行されるように検索を変換する必要があります。 ここでも「境界リスト」の中央を探し、中央の数字と比較される要素、それより小さい場合は、中央のインデックス+ 1（つまり、境界リストに過去の中央を含めない）を左の境界線（インデックス）に書き込みます。それ以外の場合、中央のインデックスは右の境界に書き込まれます。 左境界線が右境界線よりも小さい間、これをすべて行います。 左右を見つけた後、数字がリストになく、左への距離が右への距離以下である場合を考えます。 したがって、[left-1]、そうでなければ[left]を推定します。
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])
平方根と平方
タダム！ 回答によるバイナリ検索のタスク。 まず、数学ライブラリから、平方根を計算するsqrt関数を接続します。その後、条件で指定された制限に基づいて、左境界に0、右境界に1e10、つまり100億を定義します。 次に、通常のビン検索のように、中間を探して、後で比較します。 しかし、興味深いのは何ですか？ ここで、中央は方程式のxです。 これを考慮して、方程式の値を決定し、それを実際の答え（つまり、C）と比較します。 さて、境界の差が100億以下になるまで境界を移動します。これが測定の精度です。 その後、100万を乗算し、四捨五入して、同じ100万の整数と実際の除算に変換します。
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)
非常に簡単な挑戦
このタスクの分析は既に行われているため、コードのみを添付します。
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)