プログラミング Tips

ITエンジニアの雑記ブログ。
IT関連ニュースの考察や、プログラミングに関するTipsの備忘録として…
育児や日常の雑記帳としても、記事を投稿していきます。

プログラミングと日常生活に関する情報を発信しています。

2017年10月

乱数を生成するアルゴリズムを勉強してみた!!

アプリやゲームをプログラミングする時、しばしば乱数を使用する。
ほとんどのプログラミング言語で、乱数を生成する標準ライブラリが準備されているが、内部的にどのように生成しているのかを考えたことはなかった…

そこで乱数を生成するアルゴリズムを勉強してみようと思った。


擬似乱数

PC, プログラム自らは情報を生み出すことはできず、何らかの計算式を使って、見かけ上ランダムな数値を生成する。このような乱数を「擬似乱数」と呼ぶ。

例えば、C言語の標準ライブラリには0〜32767の範囲で乱数を生成するrand関数がある。
乱数生成前のウォーミングアップとして、rand関数を使用してみる。以降では、擬似乱数を単純に「乱数」と表現する。

rand関数を使用する前に準備すべきことがある。それは乱数を生成する式の中で使われる最初の値を変えることである。この値を「乱数の種」と呼ぶ。

乱数の種

「乱数の種」を変えないと、rand関数は毎回同じパターンの数列を返す。
C言語は、srand関数を使って乱数の種を設定できる。srand関数の引数に、乱数の種を与える。

乱数の種には、time関数の戻り値を使うのが定番テクニック。

time関数は、1970年1月1日0:00からの経過時間を返す。この値は、プログラムを起動するたびに異なるため、毎回値を変えるべき乱数の種として好都合。

srand関数とrand関数の使い方を示すプログラムを示す。実行すると10個の乱数を表示する。

どのような乱数になるか?はプログラムを実行したタイミング(時間)次第。

ちなみに、8行目を"/* */"で囲んでコメントアウトしてみると、面白い結果が得られる。
何度プログラムを実行しても、毎回同じ結果が表示される。

#include <stdio.h>
#include <stdlib.h> //srand関数とrand関数のため
#include <time.h>   //time関数のため

int main(int argc, char* argc[]) {
    int i;
    //乱数の種を設定する
    srand((unsigned int)time(NULL));

    //乱数を10個生成、表示する
    for (i = o; i < 10; i++) {
        printf("%d\n", rand());
    }
    return 0;
}

乱数生成アルゴリズム⑴ ー線形合同法

C言語のrand関数内部で使用されていることで有名な「線形合同法」。
以下の斬化式(数列の1つ前の値で、その次の値を求める式)で乱数を生成する方法。

この式は、n番目の乱数Xnを、その1つ前の乱数X(n-1)を使った計算で得ることを示している。

modは割り算のあまりを求める演算子(C言語では%演算子)。

Xn = (A x Xn-1 + B) mod M

この式において、A, B, Mは、0より大きな整数の定数。
X0が「乱数の種」に相当する。

X0を式の右辺において得られる計算結果が、最初の乱数X1になる。
以下同様に、X1を右辺においてX2を得る。X2を右辺においてX3を得る…と繰り返し計算する。

#include <stdio.h>

//1つ前の乱数
int random;

//乱数の種を設定する関数
void srand2(unsigned int seed) {
    random = seed;
}

//乱数を生成する関数
int rand2() {
    random = (2 * random + 3) % 7;
    return random;
}

int main(int argc, char* argv[] {
    int i;
    //乱数の種を設定する
    srand2(3);
    //乱数を10個生成する
    for (int i = 0; i < 10; i++) {
        printf("%d\n", rand2());
    }
    return 0;
}

上記において、A = 2, B = 3, M = 7 として生成した乱数生成rand2関数と、乱数の種を設定するsランD2関数。
C言語の標準ライブラリの関数と間違えないように、関数名の末尾に2を付けた。

グローバル件数randomに格納するだけ。rand2関数は、線形合同法の式に従って乱数を計算し、その値をグローバル変数randomに格納し、戻り値として返す。

テスト用のmain関数では、srand2関数の引数に、time関数の戻り値ではなく3(適当に選定)を与えている。

擬似乱数には周期性がある

rand2関数の

random = (2 * random + 3) % 7;

の部分を見れば、乱数生成の仕組みがわかる。
直前に生成された値を2倍して3を加えることによってできる数列が、乱数のようにみえる。

ただし7で割った余りのため、生成される乱数の範囲は、0~6に制限される。
この結果、同じ数列が繰り返されることがわかる。

擬似乱数の特徴であり、「周期性」と呼ばれている。

多くの選択肢から最適解を見つける方法を勉強してみた!!

最適化問題とも言われ、たくさんある選択肢の中から、最適な解を選び出す手法で、「グリーディ法」と呼ばれている。

グリーディ法は近似アルゴリズムの一種で、最適解ではなくてもそれほど悪くない解を(近似解)を得る手順のことで、"BEST"より"BETTER"を探し出す手法と言うとわかりやすいと思う。

最適解を得るのに、膨大な計算を要する場合、短時間で解を得るために、近似アルゴリズムが用いられることがある。

実際において、近似解であっても無駄がなければ(誤差が一定以内)十分と判断できるはずであり、短時間で効率的に「解を得る」場合に用いられることになる。


まずは【硬貨の交換問題】から!

問題

あるお店で、、税込213円の商品を購入した場合、お客さんは1000円札を出しました。
お釣りは、

1000 - 213 = 787

です。
できるだけ少ない枚数でお釣りを返すには、どのような組み合わせにすべきでしょうか?

解答例

この問題の答えは、

  • 500円 x 1
  • 100円 x 2
  • 50円 x 1
  • 10円 x 3
  • 5円 x 1
  • 1円 x 2

となる。この解を得るためには、「できるだけ大きな硬貨を使う」と考えたと思う。

つまりこれが『グリーディ法』である。

グリーディ(Greedy)とは、「貪欲な」という意味で、「可能な限り大きな硬貨を使う」というアイデアを『貪欲』と表現しているのである。

プログラム例

ではこれを実際のプログラムにするとどのようになるのか?
例を以下に記してみる。

#include <stdio.h>

int main(int atgc, char* argv[]) {
    //お釣り、枚数、枚数の合計、ループカウンタ
    int change, n, sum, i;

    //硬貨の種類
    int val[] = {500, 100, 50, 10, 5, 1};

    printf("お釣りは?");
    scanf("%d", &change);

    sum = 0;
    for (i = 0; i < 6; i++) {
        n = change / val[i];
        printf("%d円硬貨 : %d枚", val[i], n);
        sum += n;
        change %= val[i];
    }

    printf("硬貨の合計枚数: %d枚\n", sum);

    return 0;
}

このように、"%"の計算を用いて、除算の余りを得る演算を繰り返すことで、より小さい硬貨へ交換するための残金を求めることができる。

現在の日本の硬貨であれば、「できるだけ大きな硬貨を使う」というグリーディ方で、最適解が得られる。

もしも新たにな硬貨が追加されたらどうなる?

グリーディ法では最適解が得られない場合が生ずる。

例えば、400円硬貨が追加された場合どうだろう?

先ほどのプログラム例で、

int val[] = {500, 400, 100, 50, 10, 5, 1};

for (i = 0; i < 6; i++)

の部分を

for (i = 0; i < 7; i++)

に健康して、お釣り800円を置き換える硬貨の枚数を求めてみる。

400円硬貨があるなら、

  • 400円 x 2

が、最適解となるが、プログラム実行の結果は、

  • 500円 x 1
  • 400円 x 0
  • 100円 x 3
  • 50円 x 0
  • 10円 x 0
  • 5円 x 0
  • 1円 x 0

となる。「できるだけ大きな硬貨を扱う」というグリーディ法では、最適解を得られないことがあるというのが特徴。
ただし、

  • 1円 x 800

といったおかしな解にもなりません。

これと比較した時、今回の例では、硬貨の枚数が2枚でも4枚でも大きな差はないと言え、「4枚という近似解は十分に実用的」と言える。

以上から、

「プログラミングをする以上、正確無比な最適解を常に求めなければならない!!」と思いがちではあるが、実生活において、「最適解を求めるまでに、時間を要するのであれば、近似解を1秒で求めた方が実用的だ!」と判断する場面は多い。

このことからプログラムにおいても、『実用性』を考慮した設計・仕様が重要と言える。

効率よくデータを並べ換える方法を勉強してみた!

プログラムを開発していて、配列はよく使うが、効率よく並べ換えるアルゴリズムに「クイックソート」がある。
アルゴリズムは知っているが、プログラムにおこすとなると少し難易度が上がる。

「クイックソート」アルゴリズムとは?

クイックソートは、配列を整列するアルゴリズムの一種。
概要は、
配列の適当な要素を基準値にして、より小さい要素が前、より大きい要素が後ろになるように移動する。
基準値の前側の部分配列と、後ろ側の部分配列で、同じ処理を繰り返し行う。
である。

プログラムに落とし込むのは少し困難

クイックソートのプログラムを書くポイントは、基準値との大小関係において、配列を2つの部分配列に分けることにあるが、
これだけでプログラムに表現していくことは困難。よって、ここではこの書き方を習得していく。

書き方には複数のバリエーションがあるが、ここでは簡単な方法を書く。

そのために…

  • 適当な要素とは何番目の要素なのか?
  • 前側や後ろ側に移動するにはどうしたらよいか?
  • 基準値と同じ値の要素の処理はどうすればいいか?

という疑問が残る

これらの疑問を解決しよう!

適当な要素とは?

配列の先頭の要素を基準値にすればいい!!
残りの"要素を先頭+1"(先頭の次)、および末尾から1つずつチェックして、大小関係に応じて両者を入れ替えれば、要素の移動ができる。
この際に「より小さい」「より大きい」ではなく。「以下」「以上」で比較すれば、基準値と同じ値の要素も処理できる。

変数leftは、配列の要素を先頭+1からたどるループカウンタ。変数rightは、配列の要素を末尾からたどるループカウンタ。

ループの終了条件は、"left>= right"となる。
"left > right"ならチェックが終わっているが、最終的にleftとrightが同じ要素を示す場合もあり得るため、left>=rightという終了条件になる。

処理の最後に、rightが示す要素と基準値を入れ替えることにも注意。

ループ終了時のrightは、基準値以下の要素を指す。基準値は、rightが指す要素より大きい場合があるので入れ替える。

この手順を"arrangerArray"関数にまとめると以下のようになる。

あとでクイックソートを行う際に、繰り返し適応するので、部分配列の先頭の要素を引数"head"、末尾の要素を引数"tail"で指定する。

int arrangerArray(int a[], int head, int tail) {
    int pivot, left, right, temp;

    pivot = a[head];    //基準値
    left = head + 1;    //先頭+1からたどるループカウンタ
    right = tail;       //末尾からたどるループカウンタ

    //大小関係に応じて要素を入れ替える
    while(-1) {
        //配列を先頭+1からたどる
        while (left < tail && pivot > a[left]) left++;

        //配列の末尾からたどる
        while (pivot < a[right]) right--;

        //ループの終了
        if (left >= right) break;

        //leftとrightが刺す要素を入れ替える
        temp = a[left];
        a[left] = a[right];
        a[right] = temp;

        //次の要素チェックに進む
        left++;
        right--;
    }

    //最後に基準値とrightが指す要素を入れ替える
    a[head] = a[right];
    a[right] = pivot;

    //部分配列を区切る要素の番号を返す
    return right;
}

クイックソートを行う関数を作成してみる

部分配列に繰り返しarrangeArray関数を適応する処理は、再帰呼び出しを使って書くと容易。

quickSort関数の引数startとendには、ソートを行う配列の先頭と末尾の要素番号を指定する。
最初にquickSort関数を呼び出すときには、これらの引数に配列全体の先頭と末尾の要素番号を指定する。
quickSort関数が再帰呼び出しされる時、これら引数に部分配列の先頭と末尾の要素b何号が指定される。

void quickSort(int a[], int start, int end) {
    int p;  //部分配列を区切る要素番号

    //要素が2つ以上ある配列なら処理を行う
    if (start < end) {
        //基準値と大小関係に応じて2つの部分配列に分ける
        p = arrengeArray(a, start, end);

        //前側の部分配列に同じ処理を適応する
        quickSort(a, start, p - 1)

        //後側の部分配列に同じ処理を適応する
        quickSort(a, p + 1, end);
    }
}

あらかじめ"arrangeArray"関数を作っておいたので、quickSort関数を作成したため、
"quickSort"関数の処理をスッキリ書けた。

"arrangerArray"関数で行なっている処理が、クイックソートのポイント。

input要素は、type属性の指定によって表示形態がことなる。

例えば、フォームの中で'<input type="text">'と記述すれば、テキスト欄が表示される。
また'type="submit"'と記述すれば、送信ボタンになる。

type属性にはいくつかの指定要素が存在するが、その中に"hidden"がある。
"hidden"を指定されたinput要素は、ブラウザの画面上に何も表示されない。

hiddenを指定しても改行をともなわず、タグ位置にスペースが入ることもない。
HTMLドキュメントを描画する際には完全に無視された存在になっている。

描画された画面からはわからないが、リストのフォームから送信すると、きちんとaction属性で指定されたページに、hidden要素が指定されたinput要素も送信される。

書籍や雑誌に掲載されれているサンプルコードにhiddenを入れている例は少ない。
一方、実際にWEBサイトを構築するとhidden要素の使用頻度は想像以上に高い。

hiddenは、閲覧者に意識させることなく裏側でデータをサーバーに送信する

例えば1ページに1問ずつ回答、合計3問のアンケートサイトの場合。
実際にデータを送信するのは、3ページ目の処理になる。

この場合、1ページ目の入力内容を2ページ目、3ページ目でも維持しておけなければならない。
1ページ目でテキストを入力、2ページ目はその結果をhiddenに入れておく、3ページ目に送信するといった処理を行う必要がある。 

このように、直前のページから得た入力値をブラウザの画面に見せることなく、次のページに引き継ぐ手法としてhiddenは有効。
 
ただし、データを引き継ぐためにはJavaScript、またはサーバーサイドの処理が必要。
POSTで送信する場合、JavaScript(GETしか処理できない)が使用できない

尚、POSTで送信するとhiddenで指定された入力値は画面上には表示されないが、HTMLドキュメントのソースを見られてしまうと値がみえてしまう。よって完璧に隠すこそはできない。

よってhidden指定値は、簡易的にログイン状態の保持などに使用できるが、IDやパスワードを格納しておく使い方は危険であることがわかる。

更新:CES 関連情報

これまでに、CESに関連する記事を色々投稿してきた。読んでいただいた方々からの感謝・励ましの声もいただけたり、PVに表れたりしているので感謝感謝です!!

ここで、これまでに投稿したCES関連記事を集約してみる。情報集約によって、有効かつ簡単な情報ができ、より便利に活用でてもらえたら幸いである。

まとめ情報に関して、要望や質問があったらぜひ一報してほしい。



以前の投稿で、最安値ホテルにサーカスサーカスを紹介!!

そこで今回のCESではこのホテルに宿泊することに決定! 

同じホテルに泊まる方のお役に立てれば…ってことでまとめの記事。

入り口はCES2018オフィシャルサイトのリンクから

肝心カナメの第一歩!!
ここを間違えると私が泊まる価格と異なる可能性があるので、大注意!!!

以前の記事「CES 2018 のホテルを最安値で予約する方法」にも書いたが、
CES2018のオフィシャルサイトにある、オフィシャルホテルページから入ることが必須!!

各ホテルのホームページとは異なるCES訪問者限定の予約ページが設けられているため、
通常より安い値段が提示されたり、「満室」でも空室が案内されたりする。

ってことで、サーカスサーカスのサイトへ入る。

ここからがスタート!!

CESオフィシャルホテル サーカスサーカスの予約手順

予約サイトへ移動

"MAKE A RESERVATION"をクリック

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_01

日程を設定

"Check in"と"Check out"に日程を入れる。
CES2018_オフィシャルホテル_サーカスサーカスの予約方法_02

 私の場合は、1/9入国、1/13出国のフライトなので、以下のようになる。
"FIND"を選択して、空室状況を確認。
 CES2018_オフィシャルホテル_サーカスサーカスの予約方法_03

部屋を選択

予約可能な部屋の一覧が表示されるので、希望のタイプを選択。
ちなみにこの時は下記一種類しか選択されなかった。
"SELECT"を選択して、次の手続きへ!
CES2018_オフィシャルホテル_サーカスサーカスの予約方法_04

総額を確認

宿泊期間中の料金が表示される。
1/9, 1/10の両平日が週末よりも高いことには驚いた!

CES会期中、ラスベガスの街全体がかき入れ時の証拠だろう。

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_06

画面右側には、総額が表示されている。
ちなみにこの金額は、税金が含まれていない。最終金額はもう少し上がるので注意!

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_05


宿泊者情報の入力

次に、宿泊者情報の入力が求められるので、(*)印欄を埋めていく。
最後に、ページ下段のチェックボックスにチェックを入れて、"NEXT"をクリック

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_07

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_08


支払い情報の入力

左側にクレジットカードの情報、右側には請求先の住所を入力する。
ちなみに請求先住所は、前のページで入力した住所情報が引き継がれていた。

私は会社の住所を登録していたので、請求先住所情報は変更が必要だった。
変更した場合には、"SAVE"のクリックをお忘れなく!!

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_09

予約確認

以上で、予約情報の入力は完了!
このページで、入力内容に間違いがないことを確認して、問題なければ
ページ最後の"SAVE&CONFIRM"をクリック。

場合によっては、"SUBMIT"と表示されるかもしれないが、何でも問題はない!!

ここまで完了すると、さっき登録したメールアドレスに予約情報が送られてくるので、
それを印刷してチェックインの時に提示してあげればOK!!


CES2018_オフィシャルホテル_サーカスサーカスの予約方法_11

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_12

CES2018_オフィシャルホテル_サーカスサーカスの予約方法_13

右側には宿泊費の合計
総額:929.71ドル(宿泊代712ドル+税金217.71ドル)になった!
税金高っ!!!と思うけど、法律だから仕方ない…

ちなみに下の"ACKNOWLEDGEMENT NUMBER"はメモしておくといいと思う。
「予約管理番号」みたいなもんなので、困ったらこの番号を使って問い合わせできるし、当日のチェックインもできるから。メールにも記載されているから、メモ忘れてもご安心を!!
CES2018_オフィシャルホテル_サーカスサーカスの予約方法_10


ちなみに…

気になる"ポリシー"訳してみた

キャンセルポリシーやら、TAX(税金)ポリシーやら書いてあって、気になる人もいると思うので、なんとなく訳してみた。

TAX POLICY(タックスポリシー)


Room Rates shown do not include 13.38% Hotel Room State Tax per night (subject to change) and any applicable resort fees.  A daily resort fee of $27.00 (subject to applicable tax), will be added to your room account upon check-in.
訳:
表示されている客室料金には、1泊につき13.38%のホテル客室税(変更の可能性あり)および該当するリゾート料金は含まれていません。 チェックインの際、1日ごとのリゾート料金27.00ドル(対象税の対象となります)がお客様の客室アカウントに加算されます。

CANCEL POLICY(キャンセルポリシー)


A deposit of the 1st night room and tax will be charged to your credit card immediately.  Please cancel 72 hours prior to arrival for a full refund of 1st night room and tax.  Reservations canceled within 72 hours of arrival are subject to a penalty of 1st night room and tax..

You have the option to change your check out date at any time prior to check-in or at check-in without being charged an early departure assessment.  However, in the event you decide to check out prior to your confirmed departure date, you will be charged an early departure assessment in the amount equal to the applicable rate and taxes you were quoted for the night you are departing.
訳:
1泊目の宿泊料金と税金は、すぐにクレジットカードに請求されます。 到着の72時間前までにキャンセルしてください。1泊分の部屋と税金を全額払い戻しします。 ご到着の72時間以内にキャンセルされた予約は、1泊分の客室料金と税金が課されます。
あなたは、チェックインまたはチェックインの前にいつでも、早期の出発を請求されることなく、チェックアウト日を変更することができます。 ただし、確認された出発日前にチェックアウトする場合は、宿泊数に応じた早期出発査定額が請求されます。


予約情報の変更もできる

全ての完了すると以下の画面が表示される。
今後、キャンセルしたり日程変更したりは、この画面からできる。

この画面の表示方法は、送られて来たメールの中にあるURLをクリックすると表示される!!


CES2018_オフィシャルホテル_サーカスサーカスの予約方法_14


ということで、今回はオフィシャルホテル「サーカスサーカス」の予約方法をまとめてみた!!

まだ空きはあると思うけれど、なるべく出費を抑えるためには早めの予約をオススメしたい。


↑このページのトップヘ