Algorithm Archive

２つの数値から最大公約数を求めるアルゴリズムを、While loopを使って求める方法と再帰的なループを求める方法の２種類紹介します。

Theis algorithm to find Greater Common dinominator of two integer. One is reflexive way and another one is using "while loop" to find the answer.

Continue reading

１つだけ重いコインが混じっているN個のコインを天秤にかけて最小回数の計量で重いコインを見つけるアルゴリズムを紹介します。今回紹介するのは、N個のコインの中で偽のコインは重いと分かっているということを仮定したものです。重いか軽いか分からないコインを見つけるアルゴリズムは後々紹介しようと思います。

The algorithm which finds only one heavy coin in number of coin(N) by the minimum times measurement.

Continue reading

パスカルの三角形アルゴリズムの前に Shortest path problem 最短経路問題を紹介します。

Start から Goal までの最短経路でどれだけのパターンがあるかという問題です。下の図は、３５通りの最短経路があります。各辺を辿って、クロスした点に到着できたところで数値を付けています。この問題は３５通りの経路がありますが、数値を書き込まなくてもソースコードに書いているPascalC(8,4)-->"nCk"で求めることが出来ます。

次に、下の図は赤い丸のポイントが通れない場合、どういった方法で問題を解くかを説明しています。赤い丸の地点は通れないので経路のパターンは０となります。Goal近くにあるととても最短経路が少なくなります。

この方法は、ずい分以前に授業で発見した方法で、教科書に載っている方法とは違ってました。今の教科書にはどういった方法が記載されているか分かりませんが、面白い方法だと思いますので紹介しています。

下の図は、シェルピンスキーの三角形を表示したものです。公理=A ルール：(A → B−A−B), (B → A+B+A)奇数の場合は空白としたフラクタル図形です。これはパスカルの三角形の公式を利用して描かれたものです。

The image below is Sierpiński triangle. Rule is A = B−A−B, B = A+B+A that means In the case of odd number, the fractal figure made blank.

Continue reading

前の記事で、数値を２進数から３６進数に変換するソースコードを紹介しました。今回は、少しコードを書き換えてInputBox に数値を入力すると変換するようにしました。

Continue reading

アルゴリズムとは、JIS規格のX-0001の定義では、「明確に定義された有限個の規則の集まりで、有限回適用することにより問題を解くもの」、「問題を解くために明確に定義され、順序付けられた有限個数の規則からなる集合」とあります。

最近、流行なのか何でもアルゴリズムと言う名称がつけられてますが不思議です。こういった明確に定まっている貴重な名称は崩されるべきではないと思います。

時間の経過によって使えなくなるものはシステム（使えなくなった古いシステム＝レガシーシステム）であって、それらをアルゴリズムとは呼べません。アルゴリズムは天と地がひっくり返らない限り使いものにならなくなることはありません。時間が真実を選り分けるでしょう。

一般的に、システムとは社会の中で役割を持った歯車のようなもので他の歯車とかみ合うことで生産性(入力から出力が生じる状態)をもつものです。優れたシステムを構築しても社会の中の大小の歯車とかみ合うことが出来なければ何も生み出せません。逆に劣った構造をしたシステムであっても、他とのかみ合いが良ければ高い生産性をもつでしょう。社会（文明）というシステムは、そういった異なった大小の機能（歯車）が密接に関係し合うことで多くの機能を搭載した集合体で、高度に生産性のあるものです。

English translation about this article is difficult for me. Please ask someone who is professional for translation.

C言語で書かれたシェルソート・アルゴリズムをVBで書きました。改良版のシェルソートはさすがに高速です。考案者のシェル(Donald Shell)が着目したのは、挿入ソートで並び替える場合、配列の中に挿入する要素が近くにあるとき高速で並び替えが行えるという長所でした。そこで、挿入ソートを行う前に、離れたところにある要素を予め近くに寄せておくことを考えたのです。

At this article, I wrote Shell Sort Algorithm which is written by C.

Continue reading

ハノイの塔は、インドの神話では「ブラフマーの塔」と呼ばれ天地創造のとき神が６４枚の金の円盤を重ね、移し替えが終わったときに世界が終焉するといわれたことに由来します（ブラフマー神は創造の神、ヴィシュヌ神は維持の神、シヴァ神は破壊の神）。ルールは下の円盤が常に上に重なる円盤よりも大きな円盤になるようにします。６４枚の円盤を移し変えるには最小で2⁶⁴-1回(18,446,744,073,709,551,615回)の移動が必要です。

今回の記事では、その移し変えのアルゴリズムを紹介します。下の画像は３枚のディスクを左のロッドから右のロッドに移し替えた場合のイメージです。

Algorithm of "Tower of Hanoi" which is written by VB as shown below, click "Continue Reading". The images below is how to move the three disks from a left rod to a right rod.

1

2

3

4

5

6

7

8

Continue reading

１０進数の数値を２進数から３６進数までの数値に変換するソースコードを紹介します。

Introducing Numeral system Algorithm. The source code will convert the a decimal number to a value from a binary number to 36decimal.

Continue reading

素数を判定して求めるアルゴリズムを紹介します。素数を求める数列式は現在のところ見つかっていませんので、求めた素数で割り切れるかどうかで判定します。改良されたアルゴリズムは、最小限の除算による判定回数で素数を求めることが出来ます。その２種類のプロシージャと、素数判定ファンクションのソースコードを紹介しています。

This algorithm is to judge and asks for a prime number. Since the sequence-of-numbers type which asks for a prime number is not yet found at present, it is judged whether it can divide among the prime number. The improved algorithm will find out a prime number by the minimum times of a judgment.Two kinds of the procedure and a function are shown below.

Continue reading

2分検索ファンクションのVBAソースコードを紹介します。配列の最初から順番に目的の要素を探す場合は、最大でN回の比較検索が必要です。しかしこの２分検索アルゴリズムは最大でlog*N回の比較検索で探します。何度も言いますがソートなどの並び替えと同じく、アルゴリズムを構築する場合はとても長い配列を想定しなければいけません。

アルゴリズムとシステムについて：少し内容が逸れます。 アルゴリズムは「システム」とは違い失敗や漏れがあってはアルゴリズムとして成り立ちません。そういった理に適っている洗練されたアルゴリズムは人類のとても貴重な財産です。宝石やお金などの光り物は常に価値が変動したり時に失ったりすることがありますが、理となって顕現しているものは決して動いたり失うことがありません。不動の理（支点）がないと何も動かすことが出来ません。一方、ビジネスのツールや社会のルールとなるシステムは時間の経過と共にに想定外の事態が起こった場合、切捨てなければならない部分が生じます。株価の例を挙げると、上げ下げの材料は時間にほぼ比例するように増えていきます。

もしすべての条件を最初から想定できる社会システムを創ることが出来れば、公共の福祉（弱者救済)のための司法機関は必要なくなるでしょう。残念ながらシステムである以上それはありえません。通常、システムは常に多数を選択します。それでコツコツと（多数と少数の）鞘の部分に貯まりだす利益を生み出します。

話が逸れましたが、アルゴリズムはとても価値あるもので人生というジグソーパズルの中の定まった貴重なパーツにもなりうるということを理解してください。

The VBA source code of "Binary search" function is shown below.To find for the target element in an order from the beginning of array, N comparison search is required at the maximum. However, this "Binary search" algorithm will find target element at log*N time at the maximum. Although repeatedly said, when building an algorithm, you have to assume very long array.

About an algorithm and a system: The contents swerve for a while. Algorithm is different from "System", and bugs never occur in the algorithm. Such refined rational algorithms are human beings' very precious property. Although value jewelry or money may always fluctuate,and also may sometimes be lost, algorithm is truth and it will never change, or is not lost. Anything can be moved if there is no immovable truth (fulcrum). On the other hand, when the situation besides assumption happens to progress of time, the portion which must be cut off when produces the system used as the tool of business, or a social rule. If the example of a stock price is given, the material of taking up and down will increase mostly proportional to time.

The machinery of law for public welfare will become unnecessary if the social system which can assume all the conditions from the beginning can be predicted. Though regrettable, a system cannot be created perfectly like algorithm. Usually, a system always chooses a large number. After then, the profits (a large number and small number) which begin to accumulate in the portion of a difference are produced.

What I meant was, I want you to understand that an algorithm is very valuable and it can also become the fixed precious part of a jigsaw puzzle in your life.

ソースコードを紹介します。ヒープソートなどと比べるととても簡単なものです。

Continue reading

訂正：２０％効率化されたヒープソート・アルゴリズムと書いていましたが、どうにも腑に落ちなかったので、C言語で書かれた専門書を買って調べたところ、ここに書いているコード（効率化されたヒープソートと書いたコードとほぼ同じもの）が本に書かれていました。

この記事の前に書いたヒープソートのコードは、Wikipediaや海外の複数のサイトで紹介されていたC言語のアルゴリズムを参考にしたものでした。それらが間違っているとは言い切れないし、難しいところです。ただ、効率化された新しいヒープソートと紹介した部分は間違っていますので、ここで訂正します。

簡単な時間測定で、通常のヒープソートよりも時間が短縮されます。コムソート１１よりも少しだけ早くなりました。100万個の配列での相対的比較です。処理数は最低で13,815,511回となりますので単純計算で１万個の配列のソートテストを少なくとも150回して平均値を取ったのとほぼ同じになります。10,000,000*log(10,000,000)/10,000*log(10,000)=150（テストは乱数で作った配列の並び替えです）

アルゴリズム的には当然、O(N*log N) の範囲内での改善になります。コードは以下に紹介しています。

According to the HeapSort algorithm, the portion of the comparison & swap was all done in loop. I have removed the portion of compare & swap from the loop. As a result, large amounts of processings of sorting have been improved. New HeapSort is equivalent to CombSort11 or became more than it.

Continue reading

今回のソート・アルゴリズムはCombSort と呼ばれるものです。これも、N * Log N の計算量です。エクセルVBAで、1,000,000 の数値の配列を２０数秒で並び替えます。ヒープソート(Heapsort)も、アルゴリズムの理論値が同じですから、ほぼ同じような結果になります。N²のアルゴリズムのソート方法では、10,000の並び替えに同じくらいの時間がかかりました。その方法で、1,000,000 の数値配列の並び替えは無理かもしれません（実験しようとも思いません）。アルゴリズムを構築する者があまりハードウェアの分野に入り込まない方がいいかもしれません。

This sorting algorithm is called CombSort. The quantity of calculation is also N*LogN,and the array of the numerical value of 1,000,000 is sorted in about twenty seconds by Excel VBA. Heapsort also brings the almost same result, because of same theoretical value of an algorithm. By the sorting algorithm of N², sorting of 10,000 took about the same time. So that, by that method, sorting of the numerical array of 1,000,000 may be unreasonable. I think those who build an algorithm had better not seldom enter into the field of hardware.

Continue reading

ヒープソート(Heap Sort)のVBAコードを紹介します。クイックソート(Quick Sort) をVBAで使うとエラーが発生するので、長い配列の並び替えをする場合にこのコードがあるととても重宝すると思います。N² の原始的なソート方法とは比較にならないほど早いです。

Quick Sort Algorithm (クイックソート)

ソートのアルゴリズムについて： ソートのアルゴリズムの計算量は、分かりやすいように大きく２つに分類すると、N²とN*Log N に分けられます。アルゴリズムを構築する場合、この "N" はとても大きな数値だと仮定しなければいけません。下のテーブルのように、計算量がN² の 1/100 となったとしてもアルゴリズム上の理論値は N²です。

The VBA code of heap sort is end of this article. I think that it is found useful very much if there is this code when sorting long array, because an error will occur if quick sort is used by VBA. It is so fast that it cannot be compared with the primitive method.

下のコードはに、３つの N² のアルゴリズムのソートです。１つ目のソートは、順番に小さい数値を見つけて挿入していくソートです。このソートは、N² * 1/2 の計算量です。２つ目は、最初と最後を比較していくソートで、３つ目は一番小さい数値と大きな数値を見つけて挿入するソートです。このソートは、N² * 1/4 の計算量です。4つ目は、一番小さい数値と大きな数値を２つ見つけて挿入するソートです。計算量は、N² * 1/6 になります。膨大な量のデータをこういった原始的なアルゴリズムで並び替えようとすると大変なことになります。

These are 4 samples of primitive method which takes quantity of calculation N².

下のリンクに続きます。

Continue reading

先日書いたクイックソートの記事で少し勘違いしてた部分がありましたので書き換えました。今回は、Procedure と Function の両方のコードを紹介します。ExcelVBAのレベルでは、今のところこういったソートを個人レベルで利用することはあまり必要ではありませんが、多くの人が使うアドインなどに組み込む場合は必要です。クイックソートの他にヒープソート(Heap Sort)と呼ばれる（これも計算量：N*Log N）で安定したソート方法がありますので次の記事で紹介します。

Heap Sort（ヒープソート）記事

QuickSort のアルゴリズムを用いたVBA 用のコードを紹介します。このアルゴリズムは配列に適しています。クイックソートはある条件下において、効率が悪くなることがあります。このアルゴリズムは、比較するためのPivotを配列の中心の値にしてますが、本来のPivot の位置は配列の先頭の値です。この場合だと、降順を昇順に、または昇順を降順にソートする場合に処理量がN²となってしまいます。Pivotの位置を変えても、一定の条件下では効率が悪くなることがあります。イントロソートと呼ばれるソート方法がありますが、これはクイックソートの効率が悪くなる条件の場合、ヒープソートに切り替えるものです。

しかし、平均的に、N*Log N の処理量を実現してますので、とても優秀なアルゴリズムです。しかしながら、エクセルVBA のレベルでは、配列が大きくなったとき、「スタック領域・・・」とエラーが出て、あまり使えそうにありません。長い配列を使う場合はヒープソートを使うといいと思います。本来は、本当に処理速度を追求するのであれば、配列なんて便利なものは使えません。便利なものは必ず何かを犠牲にします。

クイックソートが作られた時代に配列などはなく、データ構造はレコードをポインターで繋いだ構造でした。ポインターを使うことでとても自由なプログラミングが可能になりますが、一度ポインターが切れるとデータは２度と捕まえることが出来ません。その環境で書かれたプログラムは、アルゴリズムが完成してないと、厄介なプログラムになってしまいます。 ２０年前に、ポインターをネットワーク状に張り巡らせたソートプログラムを作りました。少しだけメモリを使いますが、安定したプログラムでした。機会があったら紹介したいと思います。

I rewrote this article, since there was a portion which misunderstood with the article of quick sort written the other day. Although it is not so much required on the level of ExcelVBA to use such sorting on an individual level for the moment. It is called the "Heap Sort" other than quick sort which is the stable sorting method, it introduces with the following article.

Heap Sort

This is code of QuickSort Function & Procedure which is written in VBA. This algorithm is suitable for sorting array. Since quick sort has realized the amount of processings of N*Log N, it is a very excellent algorithm on the average, also sometimes its efficiency may worsen under a certain condition. Although this algorithm makes Pivot for comparing the value of the center of arrangement, the position of original Pivot is a value of the head of arrangement. The amount of processings will be N² if quicksort sort an ascending order to descending order. Even if it changes the position of Pivot, efficiency may worsen under certain conditions. Although there is the sorting method called "intro sort". this method will change to a heap sort, when the efficiency of quick sort is the worsening conditions. if processing speed is pursued truly, a convenient thing cannot be used. convenience sometimes sacrifice something.

I was writing Pascal. It's very free programming is attained by using a pointer. The program written in the environment will turn into a troublesome program, if the algorithm is not completed. 20 years ago, I have made the sorting program which spread the pointers around in the shape of a network. it was the more stabilized program than quick sort. I want to introduce, when there is an opportunity.

Continue reading