Yet Another C++ Problems (2)
●問題11
int 型の配列 buff の中から引数 x と等しい要素があるか探索する関数 member, 位置を返す関数 position, 個数を数える関数 count を定義してください。等しい要素が見つからない場合、member は false を、position は -1 を返すものとします。
bool member(int x, int buff[], int size); int position(int x, int buff[], int size); int count(int x, int buff[], int size);
●問題12
int 型の配列の中から最大値を求める関数 maximum と最小値を求める関数 minimum を定義してください。
int maximum(int buff[], int size); int minimum(int buff[], int size);
●問題13
int 型の配列 buff から重複要素を取り除く関数 remove_dup を定義してください。
int remove_dup(int buff1[], int n1, int buff2[], int n2);
remove_dup は buff1 から重複していない要素を取り出して buff2 に格納します。引数 n1, n2 は配列 buff1, buff2 の大きさで、返り値は buff2 に書き込んだ要素数とします。もし、配列 buff2 をオーバーする場合は -1 を返すものとします。
●問題14
「集合 (set)」はいくつかの要素を集めたものです。一般に、集合は重複した要素を含まず、要素の順番に意味はありません。なお、要素の重複を許す集合は「多重集合 (multi set) 」と呼ばれます。たとえば、集合 {1, 3, 5, 7} は {7, 5, 3, 1} や {5, 3, 1, 7} と表すこともできます。このように、要素は適当に並べてもかまわないのですが、ある規則で要素を整列させておく場合 (正規化) もあります。
int 型の配列を集合 (set) とみなして、集合 xs が集合 ys の部分集合ならば真を返す関数 subsetp と、xs と ys が等しい集合ならば真を返す関数 set_equal を定義してください。
bool subsetp(int xs[], int x, int ys[], int y); bool set_equal(int xs[], int x, int ys[], int y);
引数 x は集合 xs の要素数、引数 y は集合 ys の要素数を表します。
●問題15
int 型の配列 xs, ys を集合 (set) とみなして、和集合、積集合、差集合を求める関数 set_union, set_intersection, set_difference を定義してください。
int set_union(int xs[], int x, int ys[], int y, int zs[], int z); int set_intersection(int xs[], int x, int ys[], int y, int zs[], int z); int set_difference(int xs[], int x, int ys[], int y, int zs[], int z);
結果は引数の配列 zs に格納し、zs に書き込んだ要素数を返すものとします。引数 x, y は xs, ys の要素数で、引数 z は配列 zs の大きさを表します。zs をオーバーランする場合は -1 を返すものとします。
●問題16
要素を昇順に並べた 2 つの int 型配列 xs, ys を一つの配列 zs に併合 (マージ) する関数 merge を定義してください。
int merge(int xs[], int x, int ys[], int y, int zs[], int z);
引数 x, y, z は xs, ys, zs の大きさを表します。merge は zs に書き込んだ要素数を返します。もし、zs をオーバーランする場合は -1 を返します。
マージについて簡単に説明しておきましょう。次の図を見てください。
図 : マージの考え方
2 つの配列 a と b があります。これらの配列はソート済みとしましょう。これらの配列をソート済みの配列にまとめることを考えます。 a と b はソート済みなので先頭のデータがいちばん小さな値です。したがって、上図のように先頭のデータを比較し、小さい方のデータを取り出して順番に並べていけば、ソート済みの配列にまとめることができます。途中でどちらかの配列が空になったら、残った配列のデータをそのまま追加します。
●問題17
int 型の配列を「二分探索 (バイナリサーチ：binary searching)」する関数 binary_search を定義してください。
bool binary_search(int x, int buff[], int size);
線形探索の実行時間は要素数 N に比例するので、N が大きくなると時間がかかるようになります。これに対し、二分探索は log2 N に比例する時間でデータを探すことができます。ただし、探索するデータはあらかじめ昇順に並べておく必要があります。これを「ソート (sort)」といいます。二分探索は最初にデータをソートしておかないといけないので、線形探索に比べて準備に時間がかかります。
二分探索の動作を下図に示します。
図 : 二分探索
二分探索は探索する区間を半分に分割しながら調べていきます。キーが 66 の場合を考えてみましょう。まず区間の中央値 55 とキーを比較します。データが昇順にソートされている場合、66 は中央値 55 より大きいので区間の前半を調べる必要はありません。したがって、後半部分だけを探索すればいいのです。
あとは、これと同じことを後半部分に対して行います。最後には区間の要素が一つしかなくなり、それとキーが一致すれば探索は成功、そうでなければ探索は失敗です。ようするに、探索するデータ数が 1 / 2 ずつ減少していくわけです。上図の場合、線形探索ではデータの比較が 6 回必要になりますが、二分探索であれば 4 回で済みます。また、データ数が 1,000,000 個になったとしても、二分探索を使えば高々 20 回程度の比較で探索を完了することができます。
●問題18
「ソート (sort)」はある規則に従ってデータを順番に並べ換える操作です。たとえば、データが整数であれば大きい順に並べる、もしくは小さい順に並べます。ソートは昔から研究されている分野で、優秀なアルゴリズムが確立しています。ここでは簡単なソートアルゴリズム (遅いソート) を実際にプログラムしてみましょう。
バブルソート (buble sort) は泡がぶくぶくと浮いてくるように、いちばん小さいデータが後ろから前に浮かび上がってくるアルゴリズムです。隣接する 2 つのデータを比較して、順序が逆であれば入れ換えます。これを順番に後ろから前に行っていけば、いちばん小さなデータは頂上に浮かび上がっているというわけです。先頭が決まったならば、残りのデータに対して同じことを行えば、2 番目には残りのデータの中でいちばん小さいものが浮かび上がります。これをデータ数だけ繰り返せばソートが完了します。
9 5 3 7 6 4 8 交換しない
~~~
9 5 3 7 6 4 8 交換する
~~~
9 5 3 7 4 6 8 交換する
~~~
9 5 3 4 7 6 8 交換しない
~~~
9 5 3 4 7 6 8 交換する
~~~
9 3 5 4 7 6 8 交換する
~~~
3 9 5 4 7 6 8 いちばん小さいデータが決定する
+ 残りのデータに対して同様な操作を行う
図 : バブルソート
int 型の配列をバブルソートする関数 buble_sort を定義してください。
void buble_sort(int buff[], int size);
●問題19
選択ソート (selection sort) は、ソートしていないデータの中から最小値（または最大値）を見つけ、それを先頭のデータと交換する、という手順を繰り返すことでソートを行います。最初は、すべてのデータの中から最小値を探し、それを配列の先頭 buff[0] と交換します。次は、buff[1] 以降のデータの中から最小値を探し、それを buff[1] と交換します。これを繰り返すことでソートすることができます。
[9 5 3 7 6 4 8] 3 と 9 を交換する
+ +
3 [5 9 7 6 4 8] 5 と 4 を交換する
+ +
3 4 [9 7 6 5 8] 9 と 5 を交換する
+ +
3 4 5 [7 6 9 8] 7 と 6 を交換する
+ +
3 4 5 6 [7 9 8] 7 と 7 を交換する
+
3 4 5 6 7 [9 8] 9 と 8 を交換してソート終了
+ +
図 : 選択ソート
int 型の配列を選択ソートする関数 select_sort を定義してください。
void select_sort(int buff[], int size);
●問題20
単純挿入ソートの考え方はとても簡単です。ソート済みの配列に新しいデータを挿入していくことでソートを行います。次の図を見てください。
[9] 5 3 7 6 4 8 5 を取り出す
[9] * 3 7 6 4 8 5 を[9]の中に挿入する
[5 9] 3 7 6 4 8 9 をひとつずらして先頭に 5 を挿入
[5 9] * 7 6 4 8 3 を取り出して[5 9]の中に挿入する
[3 5 9] 7 6 4 8 先頭に 3 を挿入
[3 5 9] * 6 4 8 7 を取り出して[3 5 9] に挿入
[3 5 7 9] 6 4 8 9 を動かして 7 を挿入
残りの要素も同様に行う
図 : 挿入ソート
最初は先頭のデータひとつがソート済みと考えて、2 番目のデータをそこに挿入することからスタートします。データを挿入するので、そこにあるデータをどかさないといけません。そこで、挿入位置を決めるため後ろから順番に比較するとき、いっしょにデータの移動も行うことにします。
int 型の配列を単純挿入ソートする関数 insert_sort を定義してください。
void insert_sort(int buff[], int size);
●解答11
リスト : 配列の線形探索
bool member(int x, int buff[], int size)
{
for (int i = 0; i < size; i++)
if (x == buff[i]) return true;
return false;
}
int position(int x, int buff[], int size)
{
for (int i = 0; i < size; i++ )
if (x == buff[i]) return i;
return -1;
}
int count(int x, int buff[], int size)
{
int c = 0;
for (int i = 0; i < size; i++)
if (x == buff[i]) c++;
return c;
}
プログラムは簡単です。配列の先頭から順番にデータを比較していくだけです。これを「線形探索 (linear searching)」といいます。member はデータを発見したとき return で true を返します。for ループを終了した場合、データが見つからなかったので false を返します。position はデータが見つかったとき、要素の位置 (添字) を返します。見つからなかった場合は -1 を返します。count はデータを見つけたら変数 c を +1 します。最後に return で c を返すだけです。
●解答12
リスト : 最大値と最小値
// 最大値
int maximum(int buff[], int size)
{
int max = buff[0];
for (int i = 1; i < size; i++)
if (max < buff[i]) max = buff[i];
return max;
}
// 最小値
int minimum(int buff[], int size)
{
int min = buff[0];
for (int i = 1; i < size; i++)
if (min > buff[i]) min = buff[i];
return min;
}
プログラムは簡単です。buff の先頭要素を変数 max (または min) に格納します。そして、for ループで 1 番目から順番に要素を取り出して、変数と比較します。buff[i] が max よりも大きい (または min よりも小さい) 場合は変数の値を buff[i] に書き換えます。最後に return で変数の値を返すだけです。
●解答13
リスト : 重複要素の削除
int remove_dup(int buff1[], int n1, int buff2[], int n2)
{
int k = 0;
for (int i = 0; i < n1; i++) {
if (!member(buff1[i], buff2, k)) {
if (k >= n2) return -1;
buff2[k++] = buff1[i];
}
}
return k;
}
関数 remove_dup は member を使うと簡単です。for ループで、buff1 から要素を順番に取り出し、要素 buff[i] が buff2 に含まれているか member でチェックします。含まれていない場合は buff[i] を buff2 に追加します。変数 k が buff2 に書き込んだ個数を表すことに注意してください。要素を buff2 に書き込むとき、k が n2 以上の場合はオーバーランするので -1 を返します。最後に k を返します。
●解答14
リスト : 部分集合と等値の判定
// xs は ys の部分集合か
bool subsetp(int xs[], int x, int ys[], int y)
{
if (x > y) return false;
for (int i = 0; i < x; i++) {
if (!member(xs[i], ys, y)) return false;
}
return true;
}
// xs と ys は等しいか
bool set_equal(int xs[], int x, int ys[], int y)
{
return subsetp(xs, x, ys, y) && subsetp(ys, y, xs, x);
}
// 別解
bool set_equal_(int xs[], int x, int ys[], int y)
{
reutrn x != y ? false : subsetp(xs, x, ys, y);
}
subsetp は member を使うと簡単です。最初に xs の個数が ys の個数よりも大きいかチェックし、そうであれば ys に含まれていない要素があるので false を返します。あとは、for ループで xs の要素を取り出し、それが ys に含まれているか member でチェックします。含まれていなければ部分集合ではないので false を返します。for ループを終了したら true を返します。
set_equal は簡単で、xs が ys の部分集合で、かつ ys が xs の部分集合であれば、xs と ys が等しいことがわかります。今回は集合の要素数がわかるので、別解のように x と y が等しいことをチェックし、等しい場合は subsetp(xs, x, ys, y) をチェックするだけで等値を判定することができます。
●解答15
リスト : 和集合
// 集合のコピー
int set_copy(int xs[], int x, int ys[], int y)
{
int k = 0;
for (int i = 0; i < x; i++) {
if (k >= y) return -1;
ys[k++] = xs[i];
}
return k;
}
// 和集合
int set_union(int xs[], int x, int ys[], int y, int zs[], int z)
{
int k = set_copy(xs, x, zs, z);
for (int i = 0; i < y; i++) {
if (!member(ys[i], zs, k)) {
if (k >= z) return -1;
zs[k++] = ys[i];
}
}
return k;
}
set_union の場合、最初に xs を関数 set_copy で zs にコピーします。そして、ys から要素を順番に取り出し、それが zs に含まれているか member でチェックします。そうであれば、要素を zs に追加します。
リスト : 積集合
int set_intersection(int xs[], int x, int ys[], int y, int zs[], int z)
{
int k = 0;
for (int i = 0; i < x; i++) {
if (member(xs[i], ys, y)) {
if (k >= z) return -1;
zs[k++] = xs[i];
}
}
return k;
}
set_intersection の場合、xs から要素を順番に取り出し、それが ys に含まれているか member でチェックします。そうであれば、zs に要素を追加します。これで、重複した要素を zs に集めることができます。
リスト : 差集合
int set_difference(int xs[], int x, int ys[], int y, int zs[], int z)
{
int k = 0;
for (int i = 0; i < x; i++) {
if (!member(xs[i], ys, y)) {
if (k >= z) return -1;
zs[k++] = xs[i];
}
}
return k;
}
set_difference は set_intersection と似ています。違いは、xs の要素が ys に含まれていなければ、その要素を zs に追加するところです。これで、xs から ys の要素を取り除くことができます。
●解答16
リスト : マージ
int merge(int xs[], int x, int ys[], int y, int zs[], int z)
{
if (x + y > z) return -1;
int i = 0, j = 0, k = 0;
while (i < x && j < y) {
zs[k++] = xs[i] <= ys[j] ? xs[i++] : ys[j++];
}
if (i < x) {
while (i < x) zs[k++] = xs[i++];
} else {
while (j < y) zs[k++] = ys[j++];
}
return k;
}
最初に、zs の大きさが x + y 以上あることを確認します。そうでなければ -1 を返します。変数 i が配列 xs の先頭要素の位置、変数 j が配列 ys の先頭要素の位置、変数 k が配列 zs に書き込む位置を表します。i と j が配列の範囲内にある間、xs[i] と ys[j] を比較して、小さいほうを zs に書き込みます。
while ループを終了したら、残った配列の要素を zs に書き込みます。i < x ならば xs の要素を zs に、そうでなければ ys の要素を zs に書き込みます。最後に return で k を返します。
●解答17
リスト : 二分探索
bool binary_search(int x, int buff[], int size)
{
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (buff[mid] == x)
return true;
else if (buff[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return false;
}
最初に、探索する区間を示す変数 low と high を初期化します。low を 0 に、最後の要素の位置 (size - 1) を high にセットします。次の while ループで、探索区間を半分ずつに狭めていきます。まず、区間の中央値を求めて変数 mid にセットします。if 文で mid の位置にある要素と x を比較し、等しい場合は探索成功です。return で true を返します。
x が大きい場合は区間の後半を調べます。変数 low に mid + 1 をセットします。逆に、x が小さい場合は前半を調べるため、変数 high に mid - 1 をセットします。これを二分割できる間繰り返します。low が high より大きくなったら分割できないので繰り返しを終了し false を返します。
二分探索はデータを高速に探索することができますが、あらかじめデータをソートしておく必要があります。このため、途中でデータを追加するには、データを挿入する位置を求め、それ以降のデータを後ろへ移動する処理が必要になります。つまり、データの登録には時間がかかるのです。
したがって、二分探索はプログラムの実行中にデータを登録し、同時に探索も行うという使い方には向いていません。途中でデータを追加して探索も行う場合は、他の高速な探索アルゴリズムを検討してみてください。
●解答18
リスト : バブルソート
void buble_sort(int buff[], int size)
{
for (int i = 0; i < size; i++) {
for (int j = size - 1; j > i; j--) {
if (buff[j] < buff[j - 1]) {
int temp = buff[j];
buff[j] = buff[j - 1];
buff[j - 1] = temp;
}
}
}
}
最初のループで size 回だけ繰り返します。2 番目のループで buff の後ろから前に向かって、確定していないデータを比較していき、もしも順番が逆になっていたら交換します。とても簡単ですね。
バブルソートの実行時間はデータの個数の 2 乗に比例する遅いソートです。
●解答19
リスト : 選択ソート
#include <stdio.h>
void select_sort(int buff[], int size)
{
for (int i = 0; i < size - 1; i++) {
int min = buff[i];
int n = i;
for (int j = i + 1; j < size; j++) {
if (buff[j] < min) {
min = buff[j];
n = j;
}
}
buff[n] = buff[i];
buff[i] = min;
}
}
最初のループで変数 i の値は 0 から size - 1 まで動きます。2 番目のループで buff[i] から buff[size - 1] までの中から最小値を探し、それを buff[i] と交換します。最小値とその位置は変数 min と n に格納します。2 番目のループを終了したら、buff[i] と buff[n] の値を交換します。
選択ソートも実行時間はデータの個数の 2 乗に比例します。
●解答20
リスト : 単純挿入ソート
#include <stdio.h>
void insert_sort(int buff[], int size)
{
for (int i = 1; i < size; i++) {
int j, temp = buff[i];
for (j = i - 1; j >= 0 && temp < buff[j]; j--) {
buff[j + 1] = buff[j];
}
buff[j + 1] = temp;
}
}
最初のループで挿入するデータを選びます。ソート開始時は先頭のデータひとつがソート済みと考えるるので、2 番目のデータ（添字では 1）を取り出して挿入していきます。2 番目のループで挿入する位置を探しています。探索は後ろから前に向かって行います。このとき、挿入位置の検索と同時にデータの移動も行っています。ループが最後まで回れば、そのデータは先頭に挿入されることになります。
単純挿入ソートもデータの個数の 2 乗に比例する遅いソートですが、面白い特徴があって、ソート済みのデータは高速にソートできることが知られています。データがソートされていれば、2 番目のループは繰り返しを行わずに終了するため、最初のループの繰り返し回数でソートが完了することになります。したがって、与えられたデータが大まかにでもソートされていれば、2 番目のループで繰り返す回数が少なくなり、挿入ソートでも高速にソートすることができます。
●プログラムリスト
//
// yecp2.cpp : Yet Another C++ Problems (2)
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include <iostream>
using namespace std;
// Q11
bool member(int x, int buff[], int size)
{
for (int i = 0; i < size; i++)
if (x == buff[i]) return true;
return false;
}
int position(int x, int buff[], int size)
{
for (int i = 0; i < size; i++ )
if (x == buff[i]) return i;
return -1;
}
int count(int x, int buff[], int size)
{
int c = 0;
for (int i = 0; i < size; i++)
if (x == buff[i]) c++;
return c;
}
// Q12
// 最大値
int maximum(int buff[], int size)
{
int max = buff[0];
for (int i = 1; i < size; i++)
if (max < buff[i]) max = buff[i];
return max;
}
// 最小値
int minimum(int buff[], int size)
{
int min = buff[0];
for (int i = 1; i < size; i++)
if (min > buff[i]) min = buff[i];
return min;
}
// Q13
// 重複要素の削除
int remove_dup(int buff1[], int n1, int buff2[], int n2)
{
int k = 0;
for (int i = 0; i < n1; i++) {
if (!member(buff1[i], buff2, k)) {
if (k >= n2) return -1;
buff2[k++] = buff1[i];
}
}
return k;
}
// Q14
// xs は ys の部分集合か
bool subsetp(int xs[], int x, int ys[], int y)
{
if (x > y) return false;
for (int i = 0; i < x; i++) {
if (!member(xs[i], ys, y)) return false;
}
return true;
}
// xs と ys は等しいか
bool set_equal(int xs[], int x, int ys[], int y)
{
return subsetp(xs, x, ys, y) && subsetp(ys, y, xs, x);
}
// Q15
// 集合のコピー
int set_copy(int xs[], int x, int ys[], int y)
{
int k = 0;
for (int i = 0; i < x; i++) {
if (k >= y) return -1;
ys[k++] = xs[i];
}
return k;
}
// 和集合
int set_union(int xs[], int x, int ys[], int y, int zs[], int z)
{
int k = set_copy(xs, x, zs, z);
for (int i = 0; i < y; i++) {
if (!member(ys[i], zs, k)) {
if (k >= z) return -1;
zs[k++] = ys[i];
}
}
return k;
}
// 積集合
int set_intersection(int xs[], int x, int ys[], int y, int zs[], int z)
{
int k = 0;
for (int i = 0; i < x; i++) {
if (member(xs[i], ys, y)) {
if (k >= z) return -1;
zs[k++] = xs[i];
}
}
return k;
}
// 差集合
int set_difference(int xs[], int x, int ys[], int y, int zs[], int z)
{
int k = 0;
for (int i = 0; i < x; i++) {
if (!member(xs[i], ys, y)) {
if (k >= z) return -1;
zs[k++] = xs[i];
}
}
return k;
}
// Q16
// マージ
int merge(int xs[], int x, int ys[], int y, int zs[], int z)
{
if (x + y > z) return -1;
int i = 0, j = 0, k = 0;
while (i < x && j < y) {
zs[k++] = xs[i] <= ys[j] ? xs[i++] : ys[j++];
}
if (i < x) {
while (i < x) zs[k++] = xs[i++];
} else {
while (j < y) zs[k++] = ys[j++];
}
return k;
}
// Q17
// 二分探索
bool binary_search(int x, int buff[], int size)
{
int low = 0, high = size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (buff[mid] == x)
return true;
else if (buff[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return false;
}
// Q18
void buble_sort(int buff[], int size)
{
for (int i = 0; i < size; i++) {
for (int j = size - 1; j > i; j--) {
if (buff[j] < buff[j - 1]) {
int temp = buff[j];
buff[j] = buff[j - 1];
buff[j - 1] = temp;
}
}
}
}
// Q19
void select_sort(int buff[], int size)
{
for (int i = 0; i < size - 1; i++) {
int min = buff[i];
int n = i;
for (int j = i + 1; j < size; j++) {
if (buff[j] < min) {
min = buff[j];
n = j;
}
}
buff[n] = buff[i];
buff[i] = min;
}
}
// Q20
void insert_sort(int buff[], int size)
{
for (int i = 1; i < size; i++) {
int j, temp = buff[i];
for (j = i - 1; j >= 0 && temp < buff[j]; j--) {
buff[j + 1] = buff[j];
}
buff[j + 1] = temp;
}
}
// バッファの表示
void print_buffer(int buff[], int n)
{
for (int i = 0; i < n; i++)
cout << buff[i] << " ";
cout << endl;
}
int main()
{
int a[10] = {0,1,2,1,2,3,1,2,3,4};
cout << "Q11" << endl;
cout << member(0, a, 10) << endl;
cout << member(2, a, 10) << endl;
cout << member(4, a, 10) << endl;
cout << member(5, a, 10) << endl;
cout << position(0, a, 10) << endl;
cout << position(2, a, 10) << endl;
cout << position(4, a, 10) << endl;
cout << position(5, a, 10) << endl;
cout << count(0, a, 10) << endl;
cout << count(2, a, 10) << endl;
cout << count(4, a, 10) << endl;
cout << count(5, a, 10) << endl;
cout << "Q12" << endl;
cout << maximum(a, 10) << endl;
cout << minimum(a, 10) << endl;
cout << "Q13" << endl;
int xs[10] = {0,1,2,1,2,3,1,2,3,4};
int ys[10];
int k = remove_dup(xs, 10, ys, 10);
print_buffer(ys, k);
cout << "Q14" << endl;
int xs0[8] = {1,2,3,4,5,6,7,8};
int ys0[8] = {8,7,6,5,4,3,2,1};
int zs0[7] = {1,2,3,4,5,6,7};
cout << subsetp(zs0, 7, xs0, 8) << endl;
cout << subsetp(zs0, 7, ys0, 8) << endl;
cout << subsetp(xs0, 8, zs0, 7) << endl;
cout << subsetp(xs0, 8, ys0, 8) << endl;
cout << subsetp(ys0, 8, xs0, 8) << endl;
cout << set_equal(xs0, 8, ys0, 8) << endl;
cout << set_equal(ys0, 8, xs0, 8) << endl;
cout << set_equal(zs0, 7, ys0, 8) << endl;
cout << "Q15" << endl;
int xs1[4] = {1, 2, 3, 4};
int ys1[4] = {3, 4, 5, 6};
int zs1[8];
k = set_union(xs1, 4, ys1, 4, zs1, 8);
print_buffer(zs1, k);
k = set_intersection(xs1, 4, ys1, 4, zs1, 8);
print_buffer(zs1, k);
k = set_difference(xs1, 4, ys1, 4, zs1, 8);
print_buffer(zs1, k);
cout << "Q16" << endl;
k = merge(xs1, 4, ys1, 4, zs1, 8);
print_buffer(zs1, k);
cout << "Q17" << endl;
int a1[9] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
cout << binary_search(10, a1, 9) << endl;
cout << binary_search(50, a1, 9) << endl;
cout << binary_search(90, a1, 9) << endl;
cout << binary_search(0, a1, 9) << endl;
cout << binary_search(100, a1, 9) << endl;
cout << binary_search(55, a1, 9) << endl;
cout << "Q18" << endl;
int a2[10] = {5,6,4,7,3,8,2,9,1,0};
buble_sort(a2, 10);
print_buffer(a2, 10);
cout << "Q19" << endl;
int a3[10] = {5,6,4,7,3,8,2,9,1,0};
select_sort(a3, 10);
print_buffer(a3, 10);
cout << "Q20" << endl;
int a4[10] = {5,6,4,7,3,8,2,9,1,0};
insert_sort(a4, 10);
print_buffer(a4, 10);
}
●実行結果
$ clang++ yacp2.cpp $ ./a.out Q11 1 1 1 0 0 2 9 -1 1 3 1 0 Q12 4 0 Q13 0 1 2 3 4 Q14 1 1 0 1 1 1 1 0 Q15 1 2 3 4 5 6 3 4 1 2 Q16 1 2 3 3 4 4 5 6 Q17 1 1 1 0 0 0 Q18 0 1 2 3 4 5 6 7 8 9 Q19 0 1 2 3 4 5 6 7 8 9 Q20 0 1 2 3 4 5 6 7 8 9
改訂 2023 年 4 月 15 日