おまんこっちんこうし358

この広告は30日以上更新がないブログに表示されております。
新規記事の投稿を行うことで、非表示にすることが可能です。

二分探索法のアルゴリズムを覚えていなくても
「Arrays.binarySearch」メソッドで二分探索を行い
目的のデータを探索することができます。

public class Demo {
public static void main(String[] args) {

int[] num = { 5, 30, 10, 20, 70, 90 };
Arrays.sort(num); //配列をソート
System.out.println(Arrays.toString(num)); //ソートした配列を出力
int result = Arrays.binarySearch(num, 30);
System.out.println("インデックス：" + result);
}
}

========== 実行結果 ==========

[5, 10, 20, 30, 70, 90]
インデックス：3

==============================

Arrays.binarySearchも二分探索で目的のデータを探索するので
探索前に配列がソートされている必要があります。

† 地球の末路！？ †

目的のデータと配列の中央のデータを比較しながら
目的のデータを探索する探索法が二分探索法です。

二分探索法は、探索前に配列のデータをソートする必要があります。

中央のデータと目的のデータが一致しない場合は
中央のデータを除き、探索範囲を縮小して探索をします。

public class Example4 {
public static void main(String[] args) {

int[] num = { 5, 30, 10, 20, 70, 90 };
Arrays.sort(num);
System.out.println(Arrays.toString(num)); //ソートした配列を出力
System.out.println("インデックス：" + search(num, 30));

}

public static int search(int[] data, int target) {
int result = -1;
int left = 0; //配列のインデックスは0から始まるから左端は0
int right = data.length - 1; //右端はインデックスが要素-1になるから

while(left <= right) {
int middle = (left + right) / 2; //中央のデータを求める
if(data[middle] == target) {
return middle;
}else if(data[middle] < target) {
left = middle + 1;
}else {
right = middle - 1;
}
}
return result;
}

}


===== 実行結果 =====

[5, 10, 20, 30, 70, 90]
インデックス：4

====================


中央のデータと目的のデータが一致した場合は、中央の値をreturn。
目的のデータが大きい場合は「middle + 1」して探索範囲を縮小。
目的のデータが小さい場合は「middle - 1」して探索範囲を縮小。

「0,1,2,3,4,5,6」
中央が「3」だとします。「3」を基準として大小関係を調べて
目的のデータが中央のデータと同じ場合は「return 3」。

目的のデータが大きい場合、0〜3には目的のデータは存在しない。
なので、探索範囲を縮小するために
中央のデータに+1して中央のデータを除いた4〜6を探索します。
この時、新たに「int middle = (left + right) / 2」で
中央のデータが設定されます。

大きい場合だと、4〜6に探索範囲が縮小されると
中央の値は「(4 + 6) / 2」で5になります。

逆に、目的のデータが小さい場合、3〜6には目的のデータは存在しない。
なので、探索範囲を縮小するために
中央のデータに-1して中央のデータを除いた0〜2を探索します。
この時、新たに「int middle = (left + right) / 2」で
中央のデータが設定されます。

小さい場合だと、0〜2に探索範囲が縮小されると
中央の値は「(0 + 2) / 2」で1になります。

最後に、int型となっているので少数点以下は切り捨てられます。
APIで用意されているメソッドを使用した二分探索もあります。
それは、また次回に。

† 地球の末路！？ †

そもそもアルゴリズムって？
アルゴリズムは何らかの問題を有限の時間で解くための手順。
「これと、これをこうやって、こうして」みたいな感じの手順を
コンピュータに与えるプログラムのこと。

線形探索法は、配列の先頭から目的のデータを探索する方法。
不規則に配列されているデータの中から
目的のデータを探し出すのには適しているのですが
データが多くなると探索に時間がかかります。

class Demo{
　public static void main(String[] args) {

　　int[] num = {60, 20, 80, 10, 30, 50, 120, 70, 5};
　　System.out.println("インデックス：" + search(num, 120) );
　}

　　public static int search(int[] data, int target) {
　　　int result = -1;
　　　　for(int i = 0; i < data.length; i++) {
　　　　　if(data[i] == target) {
　　　　　result = i ;
　　　　　}
　　　　}
　　　　return result;
　　}
}

========== 実行結果 ==========

インデックス：6

==============================

targetが見つからない場合は-1を返します。
見つかった場合にはインデックスをreturnします。

† 地球の末路！？ †

配列の中から最大値を求めるアルゴリズムです。
maxメソッドは要素の大小比較するメソッドになります。
このメソッドをmainメソッド側で配列を渡して呼び出しています。

public class Demo {
　public static void main(String[] args) {

　　int[] num = {60, 70, 30, 10, 50, 40, 20};
　　System.out.println(max(num));
　}

　public static int max(int[] data) {
　　int max = data[0];
　　for(int i = 1; i < data.length; i++) {
　　　if(max < data[i]) {
　　　　max = data[i];
　　　}
　　}
　　return max;
　}
}

data[0]に格納されている要素を仮の最大値として変数maxに代入します。
forが1から始まるのは、インデックス0を仮の最大値としているから。
比較しても意味がないということです。

インデックス0の仮の最大値よりインデックス1以降の要素が大きければ
変数maxの値を上書きしてif文とfor文から出てmaxをreturnします。

maxメソッドの引数の変数dataは
渡された配列を受け取るための変数なので変数名は何でもOKです。

それから、もう一つ。

maxメソッドをstaticにしているかというとオブジェクトを生成しなくてもいいから。
staticでない時「max(num)」ではメソッドにアクセスすることはできないので
オブジェクトを生成してアクセスする必要があります。こんな感じで。

public class Demo {
　public static void main(String[] args) {

　　int[] num = {60, 70, 30, 10, 50, 40, 20};
　　Demo demo = new Demo();
System.out.println(demo.max(num));
　}

　public int max(int[] data) {
　　int max = data[0];
　　for(int i = 1; i < data.length; i++) {
　　　if(max < data[i]) {
　　　　max = data[i];
　　　}
　　}
　　return max;
　}
}

† 地球の末路！？ †

Queueは格納した値を、格納した順に取り出します。
両方に穴の開いた筒の左側から1、2・・・5とピンポン玉を順番に入れると
右側から入れた時と同じ順番で1、2・・5と出てきます。Queueはこんな感じです。
難しいことは無しにしてプログラムで書くとこんな感じになります。

add：値を追加
poll：値を取り出して削除
peek：値を参照


class Demo {
　public static void main(String[] args) {

　　String[] s = {"Orange", "Apple", "Kiwi", "Strawberry", "Remon"};
　　Queue q = new LinkedList();

　　for(int i = 0; i < s.length; i++) {
　　　q.add(s[i]);
　　}

　　System.out.println(q.peek());
　　System.out.println(q);

　　System.out.println();
　　System.out.println();

　　System.out.println(q.poll());
　　System.out.println(q);

　}
}


===== 実行結果 =====

Orange
[Orange, Apple, Kiwi, Strawberry, Remon]


Orange
[Apple, Kiwi, Strawberry, Remon]

====================

pollは値を参照するだけなのでQueueの値は削除されていません。
逆に、peekは値を取り出して、取り出した値が削除されています。

タグ：Queue キュー ADD poll peek

† 地球の末路！？ †

配列はインデックスを使って値を取り出したり
変更したりすることができます。

class Demo{
　public static void main(String[] args) {

　　int[] num = {100, 200, 300};

　　//インデックス2の値の取り出し
　　System.out.println(num[2]);

　　//インデックス1の値を変更
　　num[1] = 500;

　　System.out.println();
　　System.out.println();

　　//forで出力
　　for(int i = 0; i < num.length; i++) {
　　　System.out.println(num[i]);
　　}
　　
　　System.out.println();
　　System.out.println();

　　//拡張forで出力
　　for(int j: num) {
　　　System.out.println(j);
　　}
　｝
}

===== 実行結果 =====

300


100
500
300


100
500
300

====================

† 地球の末路！？ †

配列は大きく分けると3つ宣言方法があります。

1つ目は
「int[] num = new int[3];
　num[0] = 100;
　num[1] = 200;
　num[2] = 300;」

2つ目は「int[] num = new int[]{100, 200, 300};」
3つ目は「int[] num = {100, 200, 300};」

実行結果はint型の配列1と同じになります。

† 地球の末路！？ †

配列はインデックス(添え字)は1からではなく0から始まるので注意して下さい。
下記のように要素数を3つ宣言した場合、インデックスは0、1、2となります。

class Demo{
　public static void main(String[] args) {

　　int[] num = new int[3];

　　　num[0] = 100;
　　　num[1] = 200;
　　　num[2] = 300;

　　//forで出力
　　for(int i = 0; i < num.length; i++) {
　　　System.out.println(num[i]);
　　}
　　
　　System.out.println();
　　System.out.println();

　　//拡張forで出力
　　for(int j: num) {
　　　System.out.println(j);
　　}
　｝
}

===== 実行結果 =====

100
200
300


100
200
300

====================


「int[] num = new int[3];
　num[0] = 100;
　num[1] = 200;
　num[2] = 300;」

こんな感じで値を格納するのは結構面倒・・・と
そんな時には、forを使って値をnumに格納することも。

for(int i = 0; i < num.length; i++){
　num[i] = (i + 1) * 100;
}

要素数が3つだけなので「int[] num = {}100, 200, 300;」にした方がもっと楽かな。
でも、キーボードで入力するのが面倒なほど要素数が増えると別だけど・・・

† 地球の末路！？ †

Setは要素を順番に格納しないのでバラバラに取り込んだような順不同になります。
また、要素の重複不可なので重複している要素は取り込まれません。

class Demo{
　public static void main(String[] args) {

　　Set＜String＞ set = new HashSet＜String＞();

　　　set.add("リンゴ");
　　　set.add("オレンジ");
　　　set.add("キウイ");
　　　set.add("リンゴ");

　　　for(String s: set) {
　　　　System.out.println(s);
　　　}
　}
}

========== 実行結果 ==========

リンゴ
キウイ
オレンジ

==============================

要素の重複不可なので最後に格納した「リンゴ」は変数のsetに格納されていません。
forのところをIteratorに換えても出力することもできます。実行結果は同じです。

　Iterator＜String＞ iterator = set.iterator();
　while(iterator.hasNext()) {
　　System.out.println(iterator.next());
　}

† 地球の末路！？ †

Stack(スタック)は後入れ先出しLIFO

スタックは最初に格納されたものが最後に出て最後に格納されたものが最初に出ます。
日本語で書くと「後入れ先出し」、英語で書くと「Last-In First-Out」。
これを一般的に「LIFO」と書いたり、言ったりします。

イメージ的にはメスシリンダーにピンポン玉を入れていくと
ピンポン玉の上に、ピンポン玉が重なっていくので
必然的に、最初に入れたピンポン玉は最後に取り出すことになります。
逆に、最後に入れたピンポン玉も必然的に、最初に取り出すことになります。

スタックに格納する順番と取り出しの順番は逆になります。
それを確認するためのプログラムを難しいことは省いて、簡単に書くとこんな感じ。


class Demo{
　public static void main(String[] args) {

　　//配列を宣言
　　String[] str = {"ミカン","リンゴ","イチゴ"};

　　//空のスタックの作成
　　Stack＜String＞ stack = new Stack＜String＞();

　　/*empty()でスタックが空かどうかを調べてスタックが空なら
　　push()で配列の要素をスタックに格納*/

　　if(stack.empty()){
　　　for(int i = 0; i < str.length; i++) {
　　　　stack.push(str[i]);
　　　}
　　}

　　/*empty()でスタックが空かどうかを調べて空でなかったら
　　pop()で格納されているものを取り出します。*/

　　while(!stack.empty()) {
　　　System.out.println(stack.pop());
　　}
　}
}


===== 実行結果 =====

イチゴ
リンゴ
ミカン

====================

ミカン、リンゴ、イチゴの順番で格納したものが
取り出す時には逆になっているのが分かるかと思います。

† 地球の末路！？ †