再帰関数とは 2分探索を再帰関数を使った方法で取り組む前に、再帰のおさらいをしておく。再帰関数とは、自分自身を呼び出す関数のことで、下記の条件をもつ関数のこと。 再帰関数の中で自分自身を呼び出す 終了条件を書く 終了条件に向かうように自分自身を…

問題 基本的な検索アルゴリズムの2分探索問題にチャレンジする。2分探索は、ソート済のリストに対して、検索範囲を狭めながら探索を行っていくアルゴリズム。2分探索は再帰で実装する方法もあるので、それはまた今度。 実装 アルゴリズムとしては、リストの…

問題 リストの中から見つけたい要素と一致する要素のインデックスを返す問題。線形探索の問題。「ランダムに並んでいるリスト」から探索を行う唯一の方法。 実装1 解説は不要なのかもしれませんが、線形探索を行えばよいので、インデックスをインクリメント…

問題 奇数のインデックスでは-を、偶数のインデックスでは/を交互に出力するという問題。余剰の練習問題。 実装1 これまでも使っている余剰を使って組み立てる。この実装では、繰り返す回数分、if文の判定が行われるので効率が良くない。 def print_line(n: …

問題 本日はFind the Rotation Count in Rotated Sorted arrayの問題にチャレンジする。昇順ソートされたリストがあり、k回時計回りに回転させた配列が与えられたときの回転数kの値を見つける問題。言葉では分かりづらいけど、言っていることは下記のとおり…

問題 今回はMaximum sum of 'i*arr[i]' among all rotations of a given arrayの問題。与えられたリストをローテーションしながら、リストの要素のインデックスをかけ合わせて、最大値を見つけるという問題。 Input: arr[] = {8, 3, 1, 2} Output: 29 つまり…

問題 リストとある値が与えられたとき、リストの中に、合計がある値に一致するペアを見つけるというGiven an array 'A' and a number x, check for pair in 'A' with sum as xの問題。下記の例では-3+1=-2となるので、(-3, 1)というペアを返さればOK。 input…

問題 リストとある値が与えられたとき、リストの中に、合計がある値に一致するペアを見つけるというGiven an array 'A' and a number x, check for pair in 'A' with sum as xの問題。下記の例では-3+1=-2となるので、(-3, 1)というペアを返さればOK。 input…

問題 Program for array rotationにあるリストのローテーション問題。指定されたdの数分、左にローテーションさせていく問題。このページの最後にある最大公約数を使ったローテーション方法の内容を勉強。 d = 3 input: 1,2,3,4,5,6,7,8,9 ↓ output: 4,5,6,7…

問題 正の整数のリストが渡されたときに、そのリストの総和を計算し、その計算過程を出力させるというもの。 input: [1,2,3,4,5] output: 1+2+3+4+5=15 実装 まずは総和を計算するコードを書いてみる。 numbers = [1,2,3,4,5] sum = 0 for i in range(len(nu…

問題 配列が与えられたら、配列の要素を1つ時計回り、反時計回りに回転させる。反時計に回す場合は、for文、while文、indexErrorを条件に使い、リストのメソッドは使わない。簡単な問題かもしれないが、何事も練習あるのみ・・・。 input: [1,2,3,4,5] ↓ out…

問題 今回もリストのローテーションを勉強する。問題はgeeksforgeeksのBlock swap algorithm for array rotationにあるローテーション問題。アルゴリズムの中身は下記のような内容を実装できれば良い。 1. A = arr [0..d-1]およびB = arr [d..n-1]を初期化し…

問題 今回はReversal algorithm for array rotationにあるリストの並びをローテーションないしスワップさせて、リストのブロック要素を反転する方法を勉強する。具体的には下記のようなリストがあったときに、dで指定した数値分リストを分割し、その分割した…

問題 今回はProgram for array rotationにあるリストの並びをローテーションする方法を勉強する。具体的には下記のようなリストがあったときに、dで指定した数値分、リストを左にローテーションすることが目的。 d=2 pre: [1, 2, 3, 4, 5, 6, 7] ↓ post:[3, …

turtle turtleであそびます。 turtleで四角形 turtleで四角形を書くには、直線を書いて、曲がってを4回繰り返せば四角形になる。 import turtle turtle.shape('turtle') def square(): for i in range(4): turtle.forward(100) turtle.right(90) square() tu…

range for文やwhile文を使って、何らかの問題を解く際に、インデックスをうまく動かす必要がある。そうすることで配列の値をうまく動かせるので、インデックスとは仲良くないといけない。とりあえず簡単にrangeの使い方をまとめておく。以降、ここではlen_ar…