アルゴリズム講座

この講座の目標はアルゴリズムを学び、実際に生かせるようになることである。なので、最初はいくつかの基本的なソートの実装について学ぶ。その後は実際に問題を解き考え方を学びたい。このアルゴリズム講座は去年初めて開かれ、今年で二回目であるため手探りの部分が多く見苦しい点については容赦していただきたい。

第一回アルゴリズム講座

内容

・アルゴリズムとは

絶対に必要な知識

・条件分岐(if,else)
・ループ文
・配列
・動的配列(vector)

追加で覚えておきたい知識

上述の条件分岐、ループ、配列もしくはvectorはアルゴリズムに対して絶対に必要な知識である。これができれば、実際なんとかなる。が、後々のために追加で覚えていたほうが良い知識を紹介すると、
・文字列処理
・連想配列
などがある。
・計算量
・問題
・今回のまとめと次回の話

アルゴリズムとは

アルゴリズムは、wikipediaによると

アルゴリズム（英: Algorithm）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法（さんぽう）と訳されることもある。

と書いてある。簡単に言うと「与えられた入力から必要な出力を得るために定められた明確な手順」であり、これをコンピューターに指示するためのものがプログラムである。なので、一口にアルゴリズムと言っても多くの種類がある。アルゴリズムの中で最も有名なのは、バブルソートやクイックソートなどのソートだろう。だが、それ以外にもたくさんあり、遺伝的アルゴリアズムや機械学習、探索アルゴリズムなどもある。第一回ではアルゴリズムを学ぶ前に、必要な知識の復習・学習をする。

条件分岐(if,else)

前期のC言語講座でやった条件分岐は非常に重要なので復習しよう。最も重要な文と言っても過言ではないだろう。

int func(int hoge)
{
    if(hoge%2 == 0)
    {
        return 1;
    }
    return 0;
}

ループ文(for)

同じ処理を繰り返し行うための文である。どのプログラミング言語でも頻出であり、重要である。

#include<stdio.h>
int Repeat(int i)
{
    for(int j = 0;j<i;j++)
    {
        printf("%d\n",j);
    }
    return 0;
}

配列

複数のデータを管理する際によく用いる。上述のfor文ととても相性が良いため、よく組み合わせられて使われる。

#include<stdio.h>
int hoge[9] = {2,3,5,7,11,13,17,19,23,29}
for(int i = 0;i<9;i++)
{
    printf("%d\n",hoge[i])
}

動的配列(Vector)

上述の配列の上位互換。宣言時に要素数を宣言しなくてもよく、要素の数は後から増やしたり減らしたりできる。使う際は<vector>ヘッダーを#includeしなくてはならない。

#include<vector>
std::vector<int> hoge;//int型の変数を格納するhogeという変数名のvectorを宣言した。
hoge.push_back(1);//hogeに後ろから要素が１のものを追加する。
hoge.resize(6);//要素数を6に設定。
int hoge_size = hoge.size();//hogeのサイズをint型の変数に代入。
int foo = hoge[2];//hoge[2]の値を代入している。
hoge.clear();//要素を全削除する。

上のサンプルのように様々なことが手軽にできる。vectorの全要素を回すには以下のどれかのように書けば良い。以下の例はすべて要素の出力をしている。

イテレータを使ったもの(C++11)

#include<vector>
#include<iostrem>

int func(std::vector<int> hoge)
{
    for(auto i = hoge.begin();i != hoge.end();i++)
    {
        std::cout << *i << std::endl;
    }
    return 0;
}

イテレーターを使ったもの(C++03)

#include<vector>
#include<iostrem>

int func(std::vector<int> hoge)
{
    for(std::vector<int>::iterator i = hoge.begin();i != hoge.end();i++)
    {
        std::cout << *i << std::endl;
    }
    return 0;
}

要素数を使ったもの

#include<vector>
#include<iostrem>

int func(std::vector<int> hoge)
{
    for(int i = 0;i < hoge.size();i++)
    {
        std::cout << hoge[i] << std::endl;
    }
    return 0;
}

3つ目のものは今まで慣れ親しんだ配列の全要素を回すものとさほど変わらないので違和感なく使えるはずである。だが、上の2つのように書けると、後々学ぶかもしれない連想配列でも役立つので上の書き方にも慣れておいたほうが良い。

上述の条件分岐、ループ、配列もしくはvectorはアルゴリズムに対して絶対に必要な知識である。これができれば、実際なんとかなる。が、後々のために追加で覚えていたほうが良い知識を紹介すると、

文字列処理　
連想配列　
ソート

などがある。

文字列処理

C言語で文字列処理をするのはとても苦労する。そこでC++で導入された文字列を簡単に扱えるstring型について少し紹介する。string型を使う際は必ず<string>をインクルードしなくてはならない。

#include<iostream>
#include<string>

int main()
{
    std::string hoge = "千葉大学";//初期化
    std::string foo = "電子計算機研究会";//初期化
    std::string bar = hoge + foo;//+演算子による文字列の結合

    std::cout << bar << std::endl;//「千葉大学電子計算機研究会」と出力される。
    std::cout << bar[0] << std::endl;//「千」が出力される。
    std::cout << bar.length() << std::endl;//文字列の長さを出力

    std::string piyo = bar.substr(2,5);//"大学電子計"

    return 0;
}

C言語で文字列を扱おうとするとポインタがついて回るが、C++でstring型を使って文字列を扱うとポインタから開放される。上記以外にもC言語の文字列(char型の配列)に変換する事もできる。

連想配列

C++で言うところのmapである。詳しくは自分で調べるなり、C++講座の講師に聞くと良いだろう。私自身はmapに対して詳しくないため、ここでは説明しない。

計算量

単に計算量といっても次の2つがあります。
・実行時間を予測する時間計算量
・メモリ使用量を予測する空間計算量
ここでは上の時間計算量について話します。次のソースコードを見てください。

void calc()
{
    A();
    for(int i = 0;i<N;i++)
    {
        B();
        for(int j = 0;j<M;j++)
        {
            C();
        }
    }
}

このようなcalc関数が与えられた時関数A，B，Cはそれぞれ何回呼び出されるだろうか。 Aは1回、BはN回、CはNM回呼ばれるのがわかると思う。ここでA,B,Cが一瞬で終わる関数だった場合calc関数の計算量を予測するにはどの関数に着目すればいいか？
関数Cの実行回数を数えればcalc関数の計算結果がだいたい分かるという予測が立つだろう。このように、一番実行される部分を探して、その大体の計算時間を調べる」というのが計算量の考え方である。
さて、上のような例では計算時間は O(nm) と表記する。Oはオーダーと呼ばれ、計算時間がnmに比例するという意味である。これのとらえ方は最悪でもnm回の計算しかしないという程度に捉えれば良い。詳しいのを知りたい場合は「ランダウの記号」で検索するのを勧める。ランダウの記法を使う場合は定数の項や変数が十分に大きくなった場合無視できる項を除いて構わない。例えば、O(4n^2+3n+5)はO(n^2)と書いて構わない。どれくらいの勢いで計算時間が増えていくのかを知りたいのでこうしたこうは無視できるためである。

問題

N本のジュースが入っている瓶があります。i番目の瓶の容量をcapacities[i]、i番目の瓶に入っているジュースの量をbottles[i]とします。さて、ここでM回の操作をします。j回目の操作とは、ボトルfromID[j]からtoID[j]にジュースを注ぐことを意味します。ただし、ボトルdromID[j]が空になったり、ボトルtoID[j]が満杯になったときは、どちらか早い方の条件で注ぐのをやめます。 i番目の要素がすべての操作を終えた時のi番目のボトルの中のジュースの量となるN個の要素を持つ整数型の配列を返す関数を作ってください。例1：・capasities = {20，20}
・bottles = {5,8}
・fromID = {0}
・toID = {1}
・return :{0,13}
例2：・capasities = {10，10}
・bottles = {5,8}
・fromID = {0}
・toID = {1}
・return :{3,10}
例3：・capasities = {30，20，10}
・bottles = {10,5,5}
・fromID = {0,1,2}
・toID = {1,2,0}
・return :{10,10,0}
例4：・capasities = {14，35，86，58，25，62}
・bottles = {6,34,27,38,9,60}
・fromID = {1,2,4,5,3,3,1,0}
・toID = {0,1,2,4,2,5,3,1}
・return :{0,14,6535,25,35}
例5：・capasities = {70000,800000,900000,1000000}
・bottles = {478478,478478,478478,478478}
・fromID = {2,3,2,0,1}
・toID ={0,1,1,3,2}
・return :{0,156956,900000,856956}

答え

#include<vector>
std::vector<int> func(std::vector<int> bottles,std::vector<int> capacities,std::vector<int> fromID,std::vector<int> toID)
{
    for(int i = 0;i<bottle.size();i++)
    {
        int f = fromID[i];
        int t = toID[i];
        int space = capacities[t] - bottles[t];

        if( space >= bottles[f])
        {
            int vol = bottles[f];
            bottles[t] += vol;
            bottles[f] = 0;
        }
        else
        {
            int vol = space;
            bottles[t] += bol;
            bottles[f] -= vol;
        }
    }
    return bottles;
}

今回のまとめと次回の話

今回はアルゴリズムの話というよりも今まで学んできたことを中心に話した。次回はソートの話をする予定である。具体的には、バブルソートとクイックソートの実装をする。