Zenn
👋

アルゴリズムをコードにする練習0：2値交換

2020/11/18に公開
初心者
アルゴリズム
tech

はじめに

先日、プログラムの基本を繰り返し学習して、制御文もしっかり理解したけれど、コードが長くなるとまるで分からない…という話を聞いて、問題点としては

  • コードのトレースが出来ない
    ということなんですが、なんで出来ないのかな？　ってなったときに、
  • ロジックが読めてない
    というのがあるなあと思いました。

もちろん他にも理由はあるだろうけれど、プログラミング入門の教材ではアルゴリズムをやらないものがほとんどなので、実践的な長文コードを見たときの理解の取っ掛かりをどこにするかって考えたときに、自分の中にアルゴリズムの引き出しを作っておくとだいぶ違うんじゃないのかなと。

ということでそのアルゴリズムをコードにする練習を書いてみようと思います。
そして、アルゴリズムをコードにするにはまず最初に押さえておかないといけない前提があるので、それをまずまとめます。

使える言語色々使って書いていきます。その時々で書く言語は変えると思います。わからない言語のコードは読み飛ばして説明だけ見てください。基本文法はわかってるということでお願いします。
今回はPython,C,C++,C#,VB,JavaScript,Javaで書きました。

変数というもの

変数に型があるかどうかとかはさておき、変数は機械語やアセンブリ言語以外ならどんなプログラミング言語にも存在するものですね。
基本文法を理解している人には今更ですが、あらためて確認すると、特定のデータを一時的に名前を付けて保存しておくことで、再利用出来るようにするのが変数です。
ここでポイントは、

  • 変数には1つの値しか代入できない
  • すでに値が入っている変数に別の値を代入すると、元の値から新しい値に上書きされて、元の値は消える
  • 変数に入っていないものは再利用できない

ということです。

2つの変数の値を交換する

アルゴリズム、という程ではないですが、変数の特徴を理解するのに必要な考え方が、2つの変数の値を交換する（2値交換）の手順です。
よく、変数はデータの入れ物、ということで箱に例えられますが、ここに問題があります。
「2つの箱の中身を入れ替えましょう」と言われたら、

  • 片方の箱の中身を外に出して
  • 空になった箱にもう一方の箱の中身を移して
  • 外に出ている中身を反対の箱に入れる

ということが現実世界では出来ますが、プログラムの世界では「変数の外にある値の再利用」は出来ません。再利用するためには値は変数の中に入っていないといけないのです。
なので、プログラムではこの「外」の代わりにもう一つ変数を用意します。
この変数、一時的に値を入れておくということで、一時的（Temporary）を意味するtempやtmpといった名前をつけられることが多いです。
2つの変数をa,bとして、外をtempとすると、2つの変数を交換するというアルゴリズムは

  1. tempにaを代入する
  2. aにbを代入する
  3. bにtempを代入する

という流れになります。
代入が　=　で右辺のものを左辺に代入することを表す言語で書くと、

temp = a;
a = b;
b = temp;

になりますね。

2値交換をモジュール化する

モジュール化とは、コードのまとまりを分離して、再利用できるように部品化することです。
C言語やC++,JavaScriptやPythonでは関数、JavaやC#ではメソッド、VB.Netではファンクションやサブルーチンと呼ばれるものになります。
部品化することで、長いコードを分割することが出来、コードの可読性や保守性が上がります。
もし、この2値交換をモジュールに分けるとすると、

  1. 2つの値を受け取る
  2. 2つの値を交換する
  3. （2つの値を返す）

ということになります。3の手順は、言語によっては出来ないものがあるので（）をつけました。
これを、いろんな言語で見ていきましょう。知らない言語は、説明だけ軽く読んでください。

Pythonの関数（戻り値が2つ）

Pythonではこれは簡単ですね。

def swap(a,b):
    temp = a
    a = b
    b = temp
    return a,b
    
a = 10
b = 20
a, b = swap(a, b)
print('a:',a,'b:',b)

ここで注意したいのが変数のスコープです。
変数は、それぞれのブロックの中が有効範囲です。違うブロックのものは違う範囲です。
なので、上記のコードでは、swap関数の中のa,bと外のa,bは違うものになります。ということは、

def swap(a,b):　　　　　//　ここから
    temp = a
    a = b
    b = temp　　　　　　//　ここまでのa,bと
    
a = 10　　　　　　　　　 //　ここから
b = 20
swap(a, b)　　　
print('a:',a,'b:',b)　　//　ここまでのa,bは別物

こうだと、最後に表示されるのは

a: 10 b: 20

です。

Pythonではこんなふうに、戻り値を複数返すことが出来ますが、そうではない言語の場合はどうすればよいでしょう。

C言語の関数（ポインタ渡し）

C言語だと、ポインタ渡しという作業を使います。

#include <stdio.h>
void swap(int *, int *);

int main(void)
{
    int a = 10;
    int b = 20;
    swap(&a, &b);
    printf("a:%d b:%d", a, b);
    return 0;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

関数を呼び出すところで、&を変数名の前に書くことで、その変数の格納されているメモリのアドレスを関数に渡すことが出来ます。
関数では、変数の定義の前に* をつけることで、その変数はアドレスを格納する、ポインタ変数になります。
ポインタ変数は、値を利用するときに* をつけることで、そのポインタのアドレスに格納されている値を利用できます。
これで、スコープが違っても、おなじ変数の値をやり取りできます。

C++の関数（参照渡し）

C++だと、参照渡しが使えるので、もっと簡単です。

#include <iostream>
void swap(int &, int &);

int main(void)
{
    int a = 10;
    int b = 20;
    swap(a, b);
    std::cout << "a:" << a << " b:" << b << std::endl;
    return 0;
}

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

関数の引数の前に&をつけることで、渡された変数の参照（アドレス）が受け取れるんですね。参照で受け取った変数は、そのまま利用することが出来ます。これで、main関数のa,bとswap関数のa,bが同じメモリを参照していることになります。

C#のメソッド（参照渡し）

C#も参照渡しができます。

using System;

namespace ConsoleApp1
{
    class Test
    {
        static void Main(string[] args)
        {
            int a = 10;
            int b = 20;
            swap(ref a, ref b);
            Console.WriteLine("a:" + a + " b:" + b);
        }

        static void swap(ref int a, ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
    }
}

関数を呼び出すときに引数の前にrefをつけ、呼び出される関数も引数の前にrefをつけると参照渡しです。

VBのサブルーチン（参照渡し）

VBもやはり参照渡しが使えます。

Imports System

Module Test
    Sub Main(args As String())
        Dim a = 10
        Dim b = 20
        swap(a, b)
        Console.WriteLine("a:" & a & " b:" & b)
    End Sub

    Sub swap(ByRef a As Integer, ByRef b As Integer)
        Dim temp = a
        a = b
        b = temp
    End Sub
End Module

関数の定義のところでByRefをつけると、その引数を参照で受け取ることが出来ます。

JavaScriptの関数（配列利用）

残念ながら、JavaScriptでは、戻り値を複数返すことも、引数を参照渡しすることも出来ないので、渡し方か戻し方をちょっとひねる必要があります。色々な解決法がありますが、今回は配列をやり取りしてみます。

function swap(array){
    const temp = array[0];
    array[0] = array[1];
    array[1] = temp;
}

<html>
  <head>
    <script type="text/javascript" src="test.js"></script>
    <script type="text/javascript">
      function check(){
        array = [10, 20];
        swap(array);
        alert("a:"+array[0] + " b:" + array[1]);
      }
    </script>    
  </head>  
  <body>
    <input type="button" value='button' onclick='return check()' />
  </body>
</html>

配列は、「値の一部を書き換えることが出来る型」です。そして、配列名だけを記述すると、それは「値全体への参照」を表します。それを引数に渡すことで、関数と中と外で同じ値を参照することが出来ます。

Javaのメソッド（配列利用）

JavaもJavaScriptと同じく、複数の戻り値も参照渡しも出来ないので、これも配列を使ったやり取りにします。

class Test{
    public static void main(String[] args) {
        int array[] = {10,20};
        swap(array);
        System.out.println("a:" + array[0] + " b:" + array[1]);
    }

    static void swap(int[] array) {
        int temp = array[0];
        array[0] = array[1];
        array[1] = temp;
    }
}

動きはJavaScriptと同じですね。

まとめ

アルゴリズムをコードにするには、変数の取り扱いの基本をまずしっかり押さえておく必要があるので、今回はそこをまずまとめました。
サンプルのコードは、https://github.com/riko111/IntroductionToAlgorithm/tree/main/algo0
にアップしています。
何か疑問や指摘があればコメントいただければ幸いです。

Discussion