二分探索法と類似のアルゴリズム
二分探索法に似た考え方を使って、次の課題を解いてみましょう。
課題４６：同じ長さの紐が k 本欲しい
長さ $x$ の紐が $k$ 本欲しい。手元にあるのは、長さが $L_i$ であるような $n$ 本の紐であるとき、$x$ の最大値を小数点以下２桁までを切り捨てで出力する関数を作ってください。
ただし、$x$ や $L$ は実数とし、
- 1 ≤ $k$ ≤ 104
- 1 ≤ $n$ ≤ 104
- 1 ≤ $L_i$ ≤ 105
とします。
- 例1
n = 3
k = 2
L = [7.47, 6.66, 4.11]
6.66
- 例2
n = 4
k = 5
L = [2.86, 2.69, 2.05, 5.23]
2.05
- 例3
n = 5
k = 9
L = [6.33, 3.18, 6.92, 9.38, 8.96]
3.16
課題提出方法
-
基本的にGoogle Colaboratoryを用いてプログラミングしてください。どうしても Google Colaboratory を用いることができない場合のみ、Jupyter Notebook または Jupyter Lab を用いてください。
-
課題１つごとに、ノートブックを新規作成してください。１つのノートブックで複数の課題を解かないでください。
-
ノートブックを新規作成すると「Untitled.ipynb」のような名前になりますが、それを「学籍番号・氏名・課題番号」のような名前に変更してください。
-
質問・感想・要望などございましたらぜひ書き込んでください。
-
もし課題を解くにあたって参考になったウェブサイトがあれば、それについても触れてください。
-
課題を計算し終わった ipynb ファイルを提出するときは、指定したメールアドレスに Google Drive で共有する形で授業担当者に提出してください。