アルゴリズムとAPG4bについてざっくりまとめてみた

目次

アルゴリズムとは

アルゴリズムとは、問題を解決するための手順です。 コンピュータは、アルゴリズムに従って計算をしています。アルゴリズムが非効率なものであると、どんなに性能が良いコンピュータを使っていても計算量が多くなってしまいます。

より良いアルゴリズムとは

より良いアルゴリズムとは、少ない計算回数で同じ結果を得ることがアルゴリズムです。

C++のキーポイント

• #include <bits/stdc++.h> と using namespace std; は毎回最初に書く
• C++のプログラムはmain関数から始まる
• cout << "文字列" << endl;で文字列を出力できる
• // や /* */ でコメントを書ける

main関数

#include <bits/stdc++.h>
using namespace std;

int main() {
}

• C++のプログラムはmain関数から始まる
• C++のプログラムを起動すると、main関数の { の次の行から実行され、それに対応する } にたどり着くとプログラムが終了する

cout(シーアウト)

#include <iostream>
using namespace std;
int main(){
    // Your code here!
    cout << "アイウエオ" << "かいはけこ" << endl << "アイウエオ";
    // => アイウエオかいはけこ
    //    アイウエオ
}

• coutを使うことで、printf関数を使わなくても文字列や数値を出力できる
• C++で文字列を扱う場合、 "" で囲む必要がある
• endlは改行を表す
• 行の一番最後には ; をつける

コメントアウト

コメントアウトとは、プログラムの一部分のコードをコメントにして、その部分の実行を無効化することです。

全角文字

C++プログラムに全角文字が入るとエラーになるので、必ず半角文字で書きます。

#include <bits/stdc++.h>

#include <bits/stdc++.h> は、C++の全ての機能を読み込むための命令です。この命令でC++の全ての機能が読み込まれたおかげで、coutやendlを使うことができます。

using namespace std;

using namespace std; を書くことで、プログラムを書くときにstd::を省略することができます。

プログラムの書き方とエラー

• 書く→実行→正しく動作することを確認をして、プログラムは初めて完成と言える
• コンパイルエラー は文法のエラーで、プログラムは実行されない
• 実行時エラー は内容のエラーで、プログラムは強制終了される
• 論理エラー は内容のエラーで、プログラムは正しく動作しているように思えてしまう。

プログラムのエラーには コンパイルエラー・ 実行時エラー ・論理エラーの3種類がある。

3種類のエラーの具体例

コンパイルエラー

• セミコロン忘れなど。プログラムの文法にミスがある時に発生するエラーです。

実行時エラー

• 3 / 0 など。プログラムの文法は問題ないが内容に致命的な間違いがある時に発生するエラーです

論理エラー

• 300 + 100で400を返さないといけないのに、300-200で100を返すなど。人の勘違いやタイピングミスなどで発生するエラーです。

インデント

インデントとは、行の先頭にある連続したスペースのことです。

算術演算子

+, -, *, / のことを算術演算子と言います。

割り算の注意点

• C++で整数同士で割り算をした場合、結果は小数点以下を切り捨てた値となります。
• 小数点以下を切り捨てない結果が欲しい場合、整数に .0 をつけて実数同士の割り算にすれば良いです。

%演算子の優先順位

%演算子は、 * や / と同じ優先順位です。

同じ順位の演算子が並んでいる式の優先順位について

同じ順位の演算子が並んでいる式は、基本的に左の演算子から順に計算されます。もし計算の優先順位を変えたいなら、括弧を使います。

割り算の注意点

割り算はできるだけ後ろで行うか、括弧を使います。

変数の宣言

変数を使うには、最初に変数の宣言を行う必要があります。

変数を宣言するときは データの種類(型) と変数の名前(変数名) を指定します。データのことを 値 ということもあります。

int name;

intの部分がデータの種類が整数だと指定している部分です。

変数にアクセスする

変数の値を読み書きすることを「変数にアクセスする」と言います。

変数の初期化

変数の初期化とは、変数を宣言した後の最初の代入のことである。

変数はコピーされる

変数1 = 変数2 と書いた場合、変数の値そのものがコピーされます。 その後にどちらかの変数の値を変更しても、もう片方の変数は影響を受けません。

これはJavaScriptでも同じです。

let x = 1
const y = x

x = 5

console.log(x) // => 5
console.log(y) // => 1

利用できない変数名

• 数字から始まる
• _ 以外の記号が含まれている(+等)
• C++で既に使われているキーワード

重要な3つの型

• int
• double
• string

型	書き込むデータの種類
int	整数
double	小数(実数)
string	文字列

異なる型同士の計算

異なる型同士の計算では、型変換が行われます。 int 型とdouble型の計算結果はdouble型となります。 変換できない型同士の計算はコンパイルエラーになります(string型とint型の計算等)。

異なる型同士の代入

異なる型同士の代入でも型変換は行われます。 計算と同様、変換できない型同士の代入はコンパイルエラーになります。

string型で宣言した変数にint型の値を代入すると、型変換できなくてエラーが起きます。

初期化する前の変数の値

初期化する前のint型やdouble型の変数にアクセスする場合、どのような値になっているか分かりません。

また、string型の変数は初期化を行わなかった場合は自動的に""で初期化されます。

プログラムの実行順序

プログラムは上から下へ順番に実行される

プログラムの実行時にデータの入力を受け取る

プログラムの実行時にデータの入力を受け取るには、cin と >> を使います。

繋げて入力

cinも >>を繋げて入力できます。 複数入力したい場合、スペースか改行で区切られて入れば分解して入力してくれます。

繋げたくない場合、cinを複数書いても同じことができます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string text;
  double d;
  cin >> text;
  cin >> d;
  cout << text << ", " << d << endl;
}

入力

Hello
1.5

C++のif文

C++のif文はJavaScriptに似ています。

↓ C++

  if (条件式1) {
  } else if (条件式2) {
  } else {
  }

C++の真と偽

C++では、真のことを数値の1、偽のことを数値の0で表現します。 条件式の計算結果も真の時は1、偽の時は0になります。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  cout << (5 < 10) << endl; // => 1
  cout << (5 > 10) << endl; // => 0
}

しかし数値だと分かりづらいので、真のことをtrue、偽のことをfalseで表すことができます。

bool型

bool型のデータ型には、trueまたはfalseしか代入できません。int型の真と偽をbool型の変数に代入する場合、trueまたはfalseに変換されて代入されます。(bool型に1以上の値を入れると、trueが代入される) bool型がないと書けないプログラムはないが、bool型を使うことで、プログラムがわかりやすくなります。

ブロック

ブロックとは、{ }で囲まれた部分のことです。

スコープ

スコープとは、変数が使える範囲のことです。 変数のスコープは、変数が宣言されてからそのブロックが終わるまでです。

同じ名前の変数

ブロックが異なれば、同じ名前の変数を宣言できます。これは、ブロックごとに変数のスコープが違うから宣言できています。

同じ名前の変数のスコープが重なっている場合

同じ名前の変数のスコープが重なっていて、候補が複数考えられる場合、次の条件で使う変数が決められます。

候補の変数のうち最も内側で宣言されている

複合代入演算子

複合代入演算子とは、「演算子の左側の値と右側の値を使って計算して、その結果を左側に代入する演算子」です。

+= ・ -= ・ *=・ /= ・%= などがあります。

インクリメントとデクリメント

インクリメントとは、1増やす操作のことです。 デクリメントとは、1減らす操作のことです。

カウンタ変数とは

カウンタ変数とは、「何回目の繰り返しか」を管理する変数のことです。

N回の処理

「N回処理する」というプログラムを書く場合、「iを0からはじめ、iがNより小さいときにループする」という形式で書くのが一般的です。

while文

while(条件式) {
  処理
}

for文

for文は、「N回処理する」というような繰り返し処理でよくあるパターンをwhile文より短く書くための構文です。for文で簡潔にかける処理は、for文で書くのが一般的です。

breakとcontinueの違い

breakとcontinueを使うことで、while文とfor文を制御することができます。

breakは、ループを途中で抜けるための命令です。 continueは、後の処理を飛ばして次のループへ行くための命令です。

for文とwhile文の細かな違い

• for文のカウンタ変数のスコープは、for文のブロック内だけである。
• while文でインクリメントより前にcontinueを使うと、無限ループになってしまう。for文ではそのようなことは起きない。

文字列と文字の違い

abc や hello のように、文字が順番に並んでいるものを文字列と言います。

C++で文字列を扱うには、string型で変数を宣言します。

C++には文字型という型があり、それがchar型です。 char型は1文字のデータしか保持できません。 string型のデータは "" で囲いますが、char型のデータは ''で囲います。

文字列の長さを取得する

文字列変数.size()で文字列の長さを取得できます。 変数に格納しない場合、"文字列"s.size() のように "" の末尾にsをつける必要があります。配列でも同様のことができます。

n番目の文字を取得する

JavaScriptの場合、配列のように[n]を文字列の後ろにつけるとn番目の文字を取得できます。C++の場合、文字列変数.at(n)でn番目の文字を取得できます。文字列変数.at(n)で取得できる文字の型は、char型です。配列の要素を取得する場合も、.atが使えます。

文字列の一部を書き換える

文字列の一部を書き換える場合、char型を使います。文字列変数.at(n)に代入することで、char型の値を代入することで書き換えできます(文字列変数.at(n)で取得できるデータの型がchar型であるため)。

文字列の比較

string型には、数値型のような比較演算子が定義されています。

演算子	意味
==	2つの文字列が完全に一致しているか
!=	2つの文字列に違いがあるか
<, <=, >, >=	辞書に載っている順番による比較

文字列に別の文字列を足す

文字列に別の文字列を足した文字列を作成したい場合、 + 演算子で作成できます(char型も足せます)。また、 += でもできます。文字列の場合、 += 以外の複合代入演算子は使えないので、注意が必要です。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string text;
  text = "Hello";
  cout << text + " world" << endl; // => Hello world
  text += " good";
  cout << text << endl; // => Hello good
}

エスケープシーケンス

エスケープシーケンス	説明
\"	二重引用符 "
\'	引用符 '
\\	バックスラッシュ(または半角円記号) \
\t	タブ(水平タブ)
\r	復帰(一部の実行環境では改行に用いる)

行単位での入力

cinでは、空行や改行区切りで入力を受け付けますが、行単位で入力を受け付けたい場合、getlineを使います。

getline(cin, 文字列変数);

配列変数の宣言方法

c++ では、以下のように配列変数を宣言します。 c++の配列は、{}で表すので注意が必要です。

vector<型> 配列変数名;

vector<int> array = { 1, 2 };

TypeScriptでは、以下のように配列変数を宣言します。

// 型推論できる時
// arrayはnumber[]型の配列変数
const array = [1, 2] 

// 型推論できない場合は、型アノテーションをつける
const array: (number | string)[] = [1, 'あ']

配列の初期化

指定した要素数で配列を初期化することができます。

vector<型> 配列名(要素数);

// 配列の各要素の初期値を指定することもできる。
vector<int> vec(3, 5);

vector vec(3);はvector vec = {0, 0, 0}とほとんど同じ意味です。

配列の使い所

配列とfor文を組み合わせると、大量のデータを扱うプログラムを書くことができます。

配列に要素を追加する

配列変数.push_backを使えば、配列の末尾に要素を追加することができます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<int> vec = {1, 2};
  vec.push_back(3);
  cout << vec.at(2); // => 3
}

配列の末尾の要素を削除する

配列の末尾の要素を削除する場合、配列変数.pop_backを使います。popは飛び出すという意味があり、ポップコーンにも使われています。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<int> vec = {1, 2, 3};
  vec.pop_back();
  cout << vec.size(); // => 2
}

範囲外エラー

文字列と同様に、配列も添字の値が正しい範囲内に無いと実行時エラーになります。

STL

C++で用意されている、関数等がまとまっているもののことをSTL (Standard Template Library)と言います。STLには、min関数等、便利な関数が様々用意されています。

返り値または戻り値

関数の計算結果の値のことを返り値（かえりち）または戻り値（もどりち）と言います。

STLの関数に配列を渡す場合

STLの関数に配列を渡す場合、次の形式で渡すことが多いです。

関数名(配列変数.begin(), 配列変数.end())

関数の定義

関数を作成することを、関数を定義すると言います。 関数の定義はmain関数より前で行います。 関数は宣言した行より後でしか呼び出せないからです(プロトタイプ宣言をすれば、関数を定義するより前に関数を呼び出すことができます)。

c++

返り値の型 関数名(引数1の型 引数1の名前, 引数2の型 引数2の名前, ...) {
  処理
}

TypeScript

const 関数名 = (引数: 引数の型): 戻り値の型 => {
  処理
}

返り値がない関数

返り値がない関数は、返り値の型をvoid型で定義します。 C++の場合、return;を最後に書きます(TypeScriptの場合、返り値がない関数ではreturnを書かなくて大丈夫です)。

  void hello(string text) {
    cout << "Hello, " << text << endl;
    return;
  }

void hello(string text) {
  cout << "Hello, " << text << endl;
}

C++の場合でも、返り値がない関数の場合はreturnを省略できます。

関数を自分で定義する理由

• 処理の塊をまとめて、名前をつけられる
• 処理の重複を防げる
• 再帰関数がつけれる

return文の動作

処理がreturn文の行に到達した時点で関数の処理は終了します。

プロトタイプ宣言

プロトタイプ宣言をすると、関数を定義する前に関数を呼び出すことができます。 プロトタイプ宣言とは、「関数の名前」と「引数と返り値の型」だけを先に宣言することです。

返り値の型 関数名(引数1の型 引数1の名前, 引数2の型 引数2の名前, ...);

main関数

はじめのプログラムから出てきていたmain関数も関数の一つです。

関数のオーバーロード

「引数の型」または「引数の数」が異なる場合は、同じ名前の関数を定義することができます。これを関数のオーバーロードと言います。

#include <bits/stdc++.h>
using namespace std;

void hello(string text) {
  cout << "Hello, " << text << endl;
}

void hello(int number) {
  cout << "Hello, " << number << endl;
}

void hello(string text, int number) {
  cout << "Hello, " << text << number << endl;
}
  
int main() {
  hello("world"); // Hello, world
  hello(1); // Hello, 1
  hello("world", 2); // Hello, world2
}

関数の引数のコピー

関数を呼び出すときに、実引数に渡した値は、関数の定義元の仮引数にコピーされます。

うまくループ処理を描く方法

以下の手順で進めると、ループ処理を描きやすくできます。

1. ループを使わないで書く
2. パターンを見つける
3. ループで書き直す

範囲for文

配列の全ての要素に対して何かしらの処理を行ないたいとき、for文を用いて書くことができました。

C++には、配列の要素に対する処理を簡潔に描くことができる範囲for文という構文が用意されています。これは、JavaScriptのfor ofとやっていることは同じです。

C++

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<int> a = {1, 3, 2, 5, 8};

  // 配列変数aから要素を1つ取り出してxという変数にコピー
  // xの値を出力→次の要素をxにコピー
  // xの値を出力
  for (int x : a) {
    cout << x << endl;
  }
}

TypeScript

const func = (array: number[]) => {
  for(const x of array) {
    console.log(x);
  }
}

const array = [1, 2, 3, 4, 5]
func(array);

コンテナ

コンテナとはデータ型のことです。 文字列や配列はコンテナの1種です。 コンテナのようなデータ型に対して、範囲for文を使うことができます。

ループ構文の使い分け

for文はN回処理するというパターンをwhile文より短く描くための構文です。 以下に、各ループ構文の使い分けをまとめます。

• 配列の全ての要素に対する処理を行なう場合 → 範囲for文
• それ以外で一定回数繰り返し処理する場合 → for文
• それ以外の場合 → while文

while文はどの場面で使うのか

「整数Nがあるとき、Nが2で最大で何回割り切れるかを求める」のような、配列の要素に対する処理ではない、具体的なループ回数が決まっていない時に使います。

多重ループ

多重ループとは、ループ構文の中にさらにループ構文があるものである。 ループの内側にループがあるものを2重ループと呼びます。3重ループだったり4重ループをまとめて多重ループと呼びます。

多重ループを抜ける

ループの内側のループでbreakを使っても、内側のループしか抜けれません。もし外側のループも抜けたい場合、フラグ変数を用意して、フラグ変数の値に応じて外側のループも抜けるようにしましょう(多重ループを関数化して、内側のループでreturn文を使うことで一気に外側のループも抜けることができます)。

  bool finished = false;  // 外側のループを抜ける条件を満たしているかどうか(フラグ変数)

  for (int i = 0; i < ... ; i++) {
    for (int j = 0; j < ... ; j++) {

      /* 処理 */

      if (/* 2重ループを抜ける条件 */) {
        finished = true;
        break;  // (＊)
        // finishをtrueにしてからbreakすることで、
        //   内側のループを抜けたすぐ後に外側のループも抜けることができる
      }
    }
    // (＊)のbreakでここに来る

    if (finished) {
      break;  // (＊＊)
    }
  }
  // (＊＊)のbreakでここに来る

2次元配列

配列は、データの列を扱うための機能です。 2次元配列は、データの表を扱うための機能です。

2次元配列の宣言

2次元配列は、以下のように宣言します。

2次元配列

vector<vector<要素の型>> 変数名(行数, vector<要素の型>(列数), 初期値));
vector<vector<要素の型>> 変数名(行数, vector<要素の型>(列数));  // 初期値を省略

1次元配列

vector<型> 配列名(要素数);
vector<型> 配列名(要素数, 各要素の初期値);

大きさの取得

1次元配列で使ったsizeと同じように、2次元配列でもsizeで行数や列数を取得できます。結局、2次元配列は「1次元配列を要素とする配列」です。そのため、2次元配列に対してsizeを実行すると、行数(1次元配列の数)が取得できることが納得できます。

// 要素が整数
// 3行4列の2次元配列
vector<vector<int>> data(3, vector<int>(4));

data.size();  // 3 (行数) (12ではないことに注意!)
data.at(0).size();  // 4 (列数)

すべての要素数が必要なときは行数 * 列数で求める必要があります。

N×0の二次元配列

後から配列に要素を追加して使う場合などに、N×0の配列を宣言することがあります。

vector<vector<型>> 変数名(N);  // 「要素数0の配列」の配列

ジャグ配列

行毎に要素数の違う二次元配列のことを、ジャグ配列と言います。 長方形にならない、歪な形をしています。

多次元配列

1次元より次元の大きい配列をまとめて多次元配列と呼びます。

3次元配列の宣言方法

3次元配列の場合の宣言方法を次に示します。2次元配列とあまり変わりません。

vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3, 初期値)));
vector<vector<vector<要素の型>>> 変数名(要素数1, vector<vector<要素の型>>(要素数2, vector<要素の型>(要素数3)));  // 初期値を省略

要素を指定して初期化する

多次元配列でも、要素を指定して初期化できます。

// 2次元配列の初期化
vector<vector<int>> data1 = {
  {7, 4, 0, 8},
  {2, 0, 3, 5},
  {6, 1, 7, 0}
};

// 3次元配列の初期化
vector<vector<vector<char>>> data2 = {
  {
    {'-', '-', '-'},
    {'-', 'x', '-'},
    {'-', 'o', '-'}
  },
  {
    {'x', 'o', '-'},
    {'-', 'o', '-'},
    {'x', '-', '-'}
  }
};

2次元配列を1次元配列に変換する方法

2次元の表を1次元に変換する方法はいろいろ考えられますが、表を行ごとに分割して「1列目のデータ→2列目のデータ→3列目のデータ→...」という1次元の列に変換するのがシンプルです。 例えば縦H行、横W列の表を扱いたい時、データの個数はH×W個なので、vector<型> 変数名(H * W);と表現することができます。この場合、上からy個目、左からx個目の要素にアクセスするときは変数名.at(y * W + x)とします。

N × Nの2次元配列

初期値を-としています。

  vector<vector<char>> result(N, vector<char>(N, '-'));

参照

参照とは、ある変数に別名をつけることです。 ある変数への参照を作ったとき、参照からその変数へアクセスすることができます。

• 参照を使って、参照先の変数の値を変更できる。
• 後から参照先を変更できない。
• 参照の宣言時に参照先を指定して初期化する必要がある。

  参照先の型 &参照の名前 = 参照先;

参照のアクセス

参照に対して行った操作は、参照先に反映されます。

参照の複製

既にある参照と同じ参照先をもつ参照を作ることもできます。 「参照への参照」のようにならない点に注意してください。

int a = 123;
int &b = a;  // 変数aへの参照
int &c = b;  // 変数aへの参照

値渡し

関数へ渡した変数の値が仮引数にコピーされるような渡し方を値渡しといいます。一般的な関数の引数で用いられます。

関数の仮引数を参照にする

関数の仮引数を参照にした場合、呼び出し時に変数を渡すと、その変数が参照の初期値(参照先)になります。 渡した変数が参照引数の参照先になるような呼び出し方を参照渡しといいます。

参照渡しのメリット

関数の結果を複数返したい

関数の結果を複数返したい場合、配列に結果を入れて返しますが、参照の引数を使えば同じようなことができます(関数内で参照に対しておこなった処理が参照先に反映されるため。仮引数を参照にしていると、呼び出し時に渡した値が参照先として初期化される)。

無駄なコピーを減らす。

変数a = 変数bで変数bの値が変数aにコピーされていたように、関数呼び出し時の実引数は仮引数にコピーされます。複数回呼び出す関数で配列を値渡しすると、呼び出した分だけコピーが発生して、処理が重くなるので注意が必要です。その場合は、定義した関数の仮引数を参照で定義した方がよいです。

参照の注意点

• 参照を宣言する時に、初期化をする必要がある。
• 一度決めた参照先を変更することはできない。
• 関数の引数に用いる参照は呼び出し時に自動的に参照先が決まる。

参照を用いた範囲for文の書き方

for (配列の要素の型 &変数名 : 配列変数) {
  // 変数名 を使う(変数を経由して配列の要素を書き換え可能)
}

配列の要素を参照先にする時の注意点

変数以外にも、配列の要素を参照先にできます。 しかし、要素に対して参照を作った後に配列の要素数が変わるような操作をすると、参照が無効になるので注意が必要です。

繰り返し処理を行う方法

• ループ構文(forループ、whileループ)
• 再帰

再帰はループ構文よりも強力な繰り返し手法です。ループ構文で書くのが難しいような処理を簡潔に行うことができます。

再帰とは何か？

再帰とは、「ある関数の中で同じ関数を呼び出す」ことです。

再帰関数とは、

再帰関数とは、内部で自分自身の関数を呼び出すような関数のことです。

再帰呼び出しとは？

再帰呼び出しとは、関数内で同じ関数を呼び出す事です。

再帰関数が正しく動作理由

再帰関数が正しく動作する理由は、再帰呼び出しの連鎖に終わりがあるからです。

再帰関数内の2つの処理

再帰関数内の処理は、2つの処理に分類することが出来ます。

処理	意味
ベースケース	再帰呼び出しを行わずに完了出来る処理
再帰ステップ	再帰呼び出しを行い、その結果を用いて行う処理

// n を受け取って、0~n の総和を計算して返す関数(再帰関数)
int sum(int n) {
  // ベースケース
  if (n == 0) {
    return 0;
  }

  // 再帰ステップ
  int s = sum(n - 1);
  return s + n;
}

再帰関数を呼び出すと、再帰ステップでの再帰呼び出しを繰り返すうちに必ずベースケースに到達します。ベースケースがないと無限ループになってしまいます。

再帰関数を作るコツ

再帰関数を作る前に、引数、処理内容、返り値を事前に決めた方が良いです。

再帰ステップを実行するコツ

「引数を変えて再帰呼び出しした結果」を利用できないか考えると良いです。 「0∼nの総和」は「0∼(n−1)の総和」にnを足すことで計算できます。

ベースケースを実装する手順

1. どのような場合が、 「再帰呼び出しを行わずに完了できるか」を考える
2. if文で場合分けして、ベースケースの処理を実装する
3. 適当な引数を与えて、再帰ステップでの再帰呼び出しを実行して最終的にベースケースに到達すればOK

再帰関数を実装する手順

1. 「引数」「返り値」「処理内容」を決める
2. 再帰ステップの実装
3. ベースケースの実装

再帰関数の実装例

AからBまでの総和を求める再帰関数

引数・返り値・処理内容

項目
引数	int n, int m (n <= m)
返り値	n ~ mの総和
処理内容	n ~ mの総和を計算する

#include <iostream>
using namespace std;

int sum_range(int n, int m) {

  if(n > m) {
    int error_code = 0;
    return  error_code;
  }

  // ベースケース
  if(n == m) {
    return m;
  }
  
  // 再帰ステップ
  int s = sum_range(n + 1, m);
  return n + s;
}
  
int main(){
  cout << sum_range(1, 100) << endl; // => 5050
}

配列の要素の総和を求める再帰関数

注) JavaScriptと同じ様に配列を出力しようとすると、エラーが起きるので注意です。

引数・返り値・処理内容

項目
引数	vector b
返り値	b.at(0) ~ b.at(n)の総和
処理内容	b.at(0) ~ b.at(n)の総和を計算する

#include <bits/stdc++.h>
using namespace std;

int array_sum(vector<int> b) {
  int n = b.at(b.size() - 1);
  
  // ベースケース
  if(b.size() - 1 == 0) {
    return n;
  }
  
  // 再起ステップ
  b.pop_back();
  int s = array_sum(b);
  return n + s;
} 
  
int main(){
  vector<int> a = { 1, 2, 3 }; // => 6
  int result = array_sum(a);
  cout << result << endl;
}

木構造

組織のような構造を木構造といいます。 木構造に関する処理を行う際には再帰関数が有用なことが多いです。

スタックオーバーフロー

関数呼び出しを行うときにメモリを消費する。 ↓ プログラムを実行しているコンピュータのメモリには限りがあり、再帰呼び出しが多すぎるとメモリが足りなくなる。 ↓ メモリが足りなくなるとそれ以上プログラムを実行できなくなり、実行時エラーが起こる。この現象をスタックオーバーフローという。

計算回数

コンピュータの1回の計算にはわずかに時間が掛かる。 ↓ 計算回数が多くなる程、処理の実行時間が長くなる。 ↓ より計算回数が少ないアルゴリズムを選択することで、高速に動作する プログラムを作成できます。結果を出すための計算回数で、アルゴリズムの大まかな性能を見積ることが出来ます。