カテゴリー: アルゴリズムとデータ構造

PHP 挿入ソート Insertion Sort

2021年1月21日2021年1月21日 | by 優 | にコメントを残す

挿入ソート(Wikipedia) 平均計算量 О(n2) 挿入ソートとはコードを実装しよう https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Sort/InsertionSort.php [crayon-600ebecd7ce0396 …

の続きを読む

アルゴリズムとデータ構造

PHP 選択ソート Selection Sort

2021年1月16日2021年1月17日 | by 優 | にコメントを残す

https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Sort/SelectionSort.php 選択ソートって何？ ∂ この動きを理解しておきますループする毎に配列の数を削っていく、この動きの理解が大切 [crayon-600ebecd7d7731 …

の続きを読む

アルゴリズムとデータ構造, PHP

PHP バブルソート

2021年1月4日2021年1月5日 | by 優 | にコメントを残す

バブルソート１ループ毎に隣同士で比較するソートです。実装コード https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Sort/BubbleSort.php 爆速レンタルサーバならConoHa WING サーバはプロに全部お任せ！「仕事」に専念した …

の続きを読む

アルゴリズムとデータ構造, PHP, 数学

PHP ユークリッドの互除法

2021年1月3日2021年1月3日 | by 優 | にコメントを残す

ユークリッドの互除法コード実装 https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Theorem/EuclideanAlgorithm.php

<?php

$flag = false;
$number1 = 465;
$number2 = 360;
main($flag, $number1, $number2);

function main(bool $flag = true, int $number1, int $number2) {
    switch ($flag) {
        // テスト
        case 0:
            testEuclideanAlgorithm();
            break;
        // 実行
        case 1:
            $answer = euclideanAlgorithm($number1, $number2);
            printf("「%d / %d」の最大公約数は%dです", $number1, $number2, $answer);
            break;
    }
}

/**
 * ユークリッドの互除法
 */
function euclideanAlgorithm(int $number1, int $number2)
{
    if ($number1 < $number2) {
        echo '入力値異常エラー。ユークリッドの互除法の前提条件は $number1 >= $number2 です。';
        return null;
    }

    $remainder = $number1 % $number2;
    echo "{$number1} % {$number2} 余り「{$remainder}」\n";
    if ($remainder === 0) {
        return $number2;
    }
    return euclideanAlgorithm($number2, $remainder);
}


/**
 * テストコード
 */
function testEuclideanAlgorithm()
{
    $items = [
        [3355, 2379],
        [1617, 273],
    ];
    foreach ($items as $item) {
        euclideanAlgorithm($item[0], $item[1]);
        $answer = euclideanAlgorithm($item[0], $item[1]);
        printf("「%d / %d」の最大公約数は%dです\n\n", $item[0], $item[1], $answer);
    }

    // 3355 % 2379 余り「976」
    // 2379 % 976 余り「427」
    // 976 % 427 余り「122」
    // 427 % 122 余り「61」
    // 122 % 61 余り「0」
    // 3355 % 2379 余り「976」
    // 2379 % 976 余り「427」
    // 976 % 427 余り「122」
    // 427 % 122 余り「61」
    // 122 % 61 余り「0」
    // 「3355 / 2379」の最大公約数は61です

    // 1617 % 273 余り「252」
    // 273 % 252 余り「21」
    // 252 % 21 余り「0」
    // 1617 % 273 余り「252」
    // 273 % 252 余り「21」
    // 252 % 21 余り「0」
    // 「1617 / 273」の最大公約数は21です
}

<?php

$flag = false;

$number1 = 465;

$number2 = 360;

main($flag, $number1, $number2);

function main(bool $flag = true, int $number1, int $number2) {

switch ($flag) {

// テスト

case 0:

testEuclideanAlgorithm();

break;

// 実行

case 1:

$answer = euclideanAlgorithm($number1, $number2);

printf("「%d / %d」の最大公約数は%dです", $number1, $number2, $answer);

break;

}

/**

* ユークリッドの互除法

function euclideanAlgorithm(int $number1, int $number2)

{

if ($number1 < $number2) {

echo '入力値異常エラー。ユークリッドの互除法の前提条件は $number1 >= $number2 です。';

return null;

}

$remainder = $number1 % $number2;

echo "{$number1} % {$number2} 余り「{$remainder}」\n";

if ($remainder === 0) {

return $number2;

}

return euclideanAlgorithm($number2, $remainder);

}

/**

* テストコード

function testEuclideanAlgorithm()

{

$items = [

[3355, 2379],

[1617, 273],

];

foreach ($items as $item) {

euclideanAlgorithm($item[0], $item[1]);

$answer = euclideanAlgorithm($item[0], $item[1]);

printf("「%d / %d」の最大公約数は%dです\n\n", $item[0], $item[1], $answer);

}

// 3355 % 2379 余り「976」

// 2379 % 976 余り「427」

// 976 % 427 余り「122」

// 427 % 122 余り「61」

// 122 % 61 余り「0」

// 3355 % 2379 余り「976」

// 2379 % 976 余り「427」

// 976 % 427 余り「122」

// 427 % 122 余り「61」

// 122 % 61 余り「0」

// 「3355 / 2379」の最大公約数は61です

// 1617 % 273 余り「252」

// 273 % 252 余り「21」

// 252 % 21 余り「0」

// 1617 % 273 余り「252」

// 273 % 252 余り「21」

// 252 % 21 余り「0」

// 「1617 / 273」の最大公約数は21です

}

爆速レンタルサーバならC …

の続きを読む

アルゴリズムとデータ構造, 数学

PHP フィボナッチ数列

2021年1月1日2021年1月3日 | by 優 | にコメントを残す

フィボナッチ数列外部サイト https://www.studyplus.jp/445 コード実装 https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Sequence/FibonacciSequence.php

<?php

$max = 400;
$flag = false;
main($flag, $max);


function main(bool $flag = true, int $max) {
    switch ($flag) {
        // テスト
        case 0:
            testFibonacciSequence();
            break;
        // 実行
        case 1:
            var_dump(fibonacciSequence($max));
            break;
    }
}

/**
 * フィボナッチ数列生成
 *
 * @param int $max
 * @return array $data
 * // 1, 1, 2, 3, 5, 8, 13, 21 ...
 */
function fibonacciSequence(int $max, array $data = [])
{
    $i = 2;
    while (true) {
        $data[0] = 1;
        $data[1] = 1;
        $temp = (int) ($data[$i -2] + $data[$i -1]);
        // $maxを超えていたら処理終了
        if ($temp > $max) {
            break;
        }
        $data[$i] = $temp;
        $i++;
    }
    return $data;
    // return var_dump($data);
}


/**
 * テストコード
 */
function testFibonacciSequence()
{
    for ($i = 0; $i < 100; $i++) {
        $max = rand(100, 1000);
        $result = fibonacciSequence($max);
        $count = count($result);

        $diceNum = rand(1, 6);
        $n = $count - $diceNum;
        $a = $n -2;
        $b = $n -1;

        if ($result[$n] !== (int) ($result[$a] + $result[$b])) {
            var_dump($result);
            echo '異常な値';
            return;
        }
    }
    print("正常");
}


// array(14) {
//     [0]=>
//     int(1)
//     [1]=>
//     int(1)
//     [2]=>
//     int(2)
//     [3]=>
//     int(3)
//     [4]=>
//     int(5)
//     [5]=>
//     int(8)
//     [6]=>
//     int(13)
//     [7]=>
//     int(21)
//     [8]=>
//     int(34)
//     [9]=>
//     int(55)
//     [10]=>
//     int(89)
//     [11]=>
//     int(144)
//     [12]=>
//     int(233)
//     [13]=>
//     int(377)
//   }

100

101

<?php

$max = 400;

$flag = false;

main($flag, $max);

function main(bool $flag = true, int $max) {

switch ($flag) {

// テスト

case 0:

testFibonacciSequence();

break;

// 実行

case 1:

var_dump(fibonacciSequence($max));

break;

}

/**

* フィボナッチ数列生成

* @param int $max

* @return array $data

* // 1, 1, 2, 3, 5, 8, 13, 21 ...

function fibonacciSequence(int $max, array $data = [])

{

$i = 2;

while (true) {

$data[0] = 1;

$data[1] = 1;

$temp = (int) ($data[$i -2] + $data[$i -1]);

// $maxを超えていたら処理終了

if ($temp > $max) {

break;

}

$data[$i] = $temp;

$i++;

}

return $data;

// return var_dump($data);

}

/**

* テストコード

function testFibonacciSequence()

{

for ($i = 0; $i < 100; $i++) {

$max = rand(100, 1000);

$result = fibonacciSequence($max);

$count = count($result);

$diceNum = rand(1, 6);

$n = $count - $diceNum;

$a = $n -2;

$b = $n -1;

if ($result[$n] !== (int) ($result[$a] + $result[$b])) {

var_dump($result);

echo '異常な値';

return;

}

print("正常");

}

// array(14) {

// [0]=>

// int(1)

// [1]=>

// int(1)

// [2]=>

// int(2)

// [3]=>

// int(3)

// [4]=>

// int(5)

// [5]=>

// int(8)

// [6]=>

// int(13)

// [7]=>

// int(21)

// [8]=>

// int(34)

// [9]=>

// int(55)

// [10]=>

// int(89)

// [11]=>

// int(144)

// [12]=>

// int(233)

// [13]=>

// int(377)

// }

…

の続きを読む

アルゴリズムとデータ構造, PHP

PHP 配列の最大値を求める max() array_search()

2020年1月22日2021年1月22日 | by 優 | にコメントを残す

max()とarray_search()を組み合わせて使うのが良いです🐱

$list = [5, 20 , 8, 45, 100, 0, 6, 11];

$value = max($list);
$max_key = array_search($value, $list);
$max_value = $list[$max_key];
$response = [
  $max_key => $max_value
];

print_r($response);
// array(1) {
//     [4]=>
//     int(100)
//   }

$list = [5, 20 , 8, 45, 100, 0, 6, 11];

$value = max($list);

$max_key = array_search($value, $list);

$max_value = $list[$max_key];

$response = [

$max_key => $max_value

];

print_r($response);

// array(1) {

// [4]=>

// int(100)

// }

実装してみた https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Search/MaxKeyValueSearc …

の続きを読む

アルゴリズムとデータ構造

PHP ボゴソート Bogo Sort

2020年1月18日2021年1月18日 | by 優 | にコメントを残す

https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Sort/BogoSort.php ボゴソート？偶然揃うまでシャッフルし続けるネタソート実装してみたよ

<?php

$list = range(1, 8);
shuffle($list);
print_r(bogoSort($list));
// Array
// (
//     [試行回数] => 7146
//     [data] => Array
//         (
//             [0] => 1
//             [1] => 2
//             [2] => 3
//             [3] => 4
//             [4] => 5
//             [5] => 6
//             [6] => 7
//             [7] => 8
//         )
// )


/**
 * ボゴソート
 *
 * @param array $list
 * @return array
 */
function bogoSort($list): array
{
    shuffle($list);

    $clone_list = $list;
    sort($clone_list);

    $count = 1;
    while (true) {
        shuffle($list);
        if ($clone_list == $list) {
            return $response = [
                '試行回数' => $count,
                'data' => $list
            ];
        }
        $count++;
    }
}

<?php

$list = range(1, 8);

shuffle($list);

print_r(bogoSort($list));

// Array

// (

// [試行回数] => 7146

// [data] => Array

// (

// [0] => 1

// [1] => 2

// [2] => 3

// [3] => 4

// [4] => 5

// [5] => 6

// [6] => 7

// [7] => 8

// )

/**

* ボゴソート

* @param array $list

* @return array

function bogoSort($list): array

{

shuffle($list);

$clone_list = $list;

sort($clone_list);

$count = 1;

while (true) {

shuffle($list);

if ($clone_list == $list) {

return $response = [

'試行回数' => $count,

'data' => $list

];

}

$count++;

}

&nbsp …

の続きを読む

アルゴリズムとデータ構造, PHP

PHP 線形探索(リニアサーチ)

2019年1月5日2021年1月5日 | by 優 | にコメントを残す

線形探索とはループでぐるーっと探索して、ifで見つけるやつ。実装コード https://github.com/yuukanehiro/AlgorithmsDataStructure/blob/main/Search/LinearSearch.php

<?php

printf("テスト結果は「%s」です。", testLinearSearch());

/**
 * 線形探索
 *
 * @param array $data
 * @param int $target
 * @return int
 */
function linearSearch(array $data, int $target): int
{
    foreach ($data as $key => $value) {
        if ($value === $target) {
            return $key;
        }
    }
}

/**
 * テストコード
 */
function testLinearSearch(): string
{
    for ($i = 0; $i < 1000; $i++) {
        $data = range(0, 100);
        shuffle($data);
        $max = count($data);
        $target_key = rand(0, $max-1); // サイコロ
        $key = linearSearch($data, $data[$target_key]);

        if ($data[$key] !== $data[$target_key])
        {
            return '失敗';
        }
    }
    return '成功';
}

<?php

printf("テスト結果は「%s」です。", testLinearSearch());

/**

* 線形探索

* @param array $data

* @param int $target

* @return int

function linearSearch(array $data, int $target): int

{

foreach ($data as $key => $value) {

if ($value === $target) {

return $key;

}

/**

* テストコード

function testLinearSearch(): string

{

for ($i = 0; $i < 1000; $i++) {

$data = range(0, 100);

shuffle($data);

$max = count($data);

$target_key = rand(0, $max-1); // サイコロ

$key = linearSearch($data, $data[$target_key]);

if ($data[$key] !== $data[$target_key])

{

return '失敗';

}

return '成功';

}

&nbsp …

の続きを読む

アルゴリズムとデータ構造, PHP

PHP FizzBuzz

2017年12月4日2021年1月20日 | by 優 | にコメントを残す

どうしてプログラマに・・・プログラムが書けないのか? ちゃんとしたプログラマであれば、これを実行するプログラムを2分とかからずに紙に書き出せるはずだ。怖い事実を聞きたい? コンピュータサイエンス学科卒業生の過半数にはそれができないのだ。自称上級プログラマが答えを書くのに10-15分もかかっているのを見たこともある。 FizzBuzzを解いてみ …

の続きを読む