おもしろいアルゴリズム(数学初心者

質問

日曜プログラマーです。
自分で使うプログラムを作っているのですが、調べる事はあっても熟考することがあまりありません。
それほどまだ難しい事ができないので、練習のため数学の簡単なアルゴリズムを教えて欲しいです。
とりあえず、作ってみたのが素数を調べるソフト。
復号できない暗号の解析するソフト。
どちらも原理としては簡単なんですが、実際作る際に頭を使いました。

プログラムの事は分からなくても、数学でおもしろい考え方や法則があれば、教えてください。
フェルマーの定理とか、何重にも複雑な方程式を解くのではなく、簡単な数式で分かりやすい結果が出るものがいいのですが。
好きなのは、ランダム(サイコロ)なんですが、ランダムでなくてもかまいません。

素数の求め方とか数学的なものから、切符の４桁の数字で１０ができるかどうかとか、そう言う簡単なもので結果の分かりやすいものでお願いします。

回答No.5

tatsumi01 · ベストアンサー

面白くないかも知れません。

(1) ゴールドバッハの予想
６以上の偶数は二つの奇素数の和で表される。これをＮまで実証せよ。
まだ証明はされていませんが、かなり大きな偶数まで実証されています。
昔、プログラムを作って１００までは確認しました（って、手ももできますけど）。
３４＝３＋３１、５＋２９、１１＋２３、１７＋１７
など、複数の解があるものも全部求めてください。

(2) ８人の女王
チェスを知っていないと問題の理解が困難です。チェスの女王は日本将棋の飛車と角行の動きを合わせて持ちます。チェスの盤は８×８です。盤上に女王を８人置いて、お互いに取られないように配置して下さい。

お礼

「ゴールドバッハの予想」おもしろそうです。
ランダムにもかなり惹かれるけど、素数もかなり惹かれます。

『「素数」を数えて落ち着くんだ。
　「素数」は１と自分の数でしか割ることのできない孤独な数字
　・・・わたしに勇気を与えてくれる。』・・・ネタです。＾＾；

Wikipediaで調べたけど、2×10^17まで証明されているんですね。
ある程度方法は想像がつくけど、いかに早く計算できるかが難しいです。

回答No.7

Trick--o--

昔、ベーマガか何かに数独（当時はナンプレのほうが一般的だった）の解答プログラムが載っていたなぁ……

数独の条件に
・外枠の対角線に同じ数字が入らない
を加えるものもあった気が。

もうご覧になってるかもしれませんが
http://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
とりあえずWikipediaでもどうぞ。

お礼

あまりＰＣの雑誌コーナーには行かないので、プログラム系の雑誌にはそう言った初心者の練習問題もあるのかな？
数学にも少し興味があったので、あえて数学のカテゴリーで聞きました。
少し時間がかかるので、事後報告はできませんでしたが、どこかのＨＰで見かけたら、そのソースをみて笑ってやってください。＾＾
一応、Delphiで細々と、かなり局地戦用のソフトを公開しています。

とりあえず、「素因数分解」「ゴールドバッハの予想」「数独」、そして最終的には「ライフゲーム」を自作で作りたいと思います。

回答No.6

tatsumi01

数独を解くのはどうでしょうか。
数独はよく週刊誌のクイズ欄に載っていますが、９×９の行列（そのうちのいくつかは数字で埋まっている）で空白で残っている各要素に(1) １～９の数字を埋め
(2) どの行にも同じ数字はない
(3) どの列にも同じ数字はない
(4) ９個に区切った３×３の小行列のどれにも同じ数字はない
という条件で解くものです。

ただ、問題を解くより、問題を作る方が難しいような気がします。もし、問題を作るプログラムができたら、ニコリに持ち込んだらいかがでしょう。

欧米では数独のファンが増えているようで、専門の雑誌も出ています。先日海外出張の際に実見しました。

お礼

魔法陣みたいなものなんですかね。
問題を作るプログラム、すでにあると思いますが。
でも、人気ならＨＰとかで発表したら、アクセスも増えるのかな？
これはこれでおもしろそうですね。

回答No.4

noname#20377

#1です。何か書きたくなったから戻ってきた。
有名で簡単なの・・・

●ハノイの塔
http://web2.incl.ne.jp/yaoki/hanoi.htm

●ソート(並び替え)

●迷路からの脱出
http://www.algolab.co.jp/~lum/pcnyumon/hosoku04.htm

(類題:ソフトウェア開発技術者 平成16年度午後II
http://情報処理試験.jp/index-H16.html)

===
各予備校で配布されているセンター試験「情報関連基礎」の第3問あたりとかのアルゴリズムもそれなりに面白かったような気もする。
=====
少し難しくなるけど・・・

昔どこかでトランプのアルゴリズムが載っていたな。
同じ仕組みで麻雀とかもできるかな？
定期的にユーザーはキーを入力してゲームが進んでいく

#VB6時代、ぷよぷよもどき作ろうとして挫折しました。重いし(DirectDrawでFlipしてたが)何か描写がちかちかしてたしし、ユーザーのコントローラ操作を見張るタイミングも最悪で、まともにプレイできるプログラムとは言えなかったけど、考えていた時期はそれなりに面白かった。

お礼

＞考えていた時期はそれなりに面白かった。
私も、考えるのだけは楽しいです。
Delphiでプログラムを作っているのですが、今のところグラフィカルなものを作ったことがないです。(画像ビュワーや、線画なら多少。
トランプやぷよぷよは、まだまだ難しそうです。

補足

迷路からの脱出、挑戦してみました。
上下左右を決める。
分岐した位置と方向を記録する。
行き止まりなら、一つ前の分岐に戻る。
・・・ただ、図形は行き止まらないんですよね。＾＾；

そもそも、いきなり迷路に放り込まれる訳だから、行き止まりがあるとか、どのくらいの大きさとかさえわからないんですよね？

そうなると、どの分岐が行ったことがあるかどうかを調べる方法を考えないと。
そうなると、最初に分岐した所を"１"と、分岐の数を記録。1-1,1-2
1-1を進んで分岐していたら記録保存1-1-1,1-1-2、記録したら分岐"１"に戻り1-1へ。
1-2を進んで分岐していたら記録保存1-2-1,1-2-2。
１段階の分岐をすべて記録したら、1-1-1に進む。
それが分岐していたら、1-1-1-1,1-1-1-2と記録。
1-1-1に戻って、1-2-1に進む。
1-2-1-1,1-2-1-2
(もちろん、３つの分岐ならその分増やす。)
分岐を見つけたら、記録して。
新しい分岐が見つかるまで進んで、前の分岐に戻る。
これを繰り返して行ったことのない道をシラミつぶせば、出口に出られるはず。

進化の樹状分岐図のように、１段階目の分岐、２段階目の分岐、３段階目の分岐・・・・と分岐をすべて保存して、そのすべての分岐に行くってのはどうでしょう？
考えつくのに３０分くらいかかったし、どういうプログラム、データー構造にしていいのかもわかりませんが。＾＾

回答No.3

neKo_deux

遺伝的アルゴリズムは動作の見た目が面白いです。
選択、交叉や突然変異の方法なんか、研究してみても良いですし。

アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/

他にはモンテカルロ法とか、ニューラルネットワークとか。

参考URL：

http://www.microsoft.com/japan/msdn/academic/Articles/Algorithm/05/

お礼

「遺伝的アルゴリズム」は、おもしろそうですね。
でも、ちょっと私にはまだレベルが高いかも。＾＾；
私は、Ｄｅｌｐｈｉなんですが、クラスが今ひとつピントきてなくって。
いや、便利なのはわかるんだけど、どう使うのが本当に便利なのかと。
ありがとうございます。

回答No.2

elttac

簡単なものがご希望のようですね。

　でしたら，いくつか掲げてみますので，必要ならお調べになってみてください。

■ 素因数分解
　エラトステネスのふるいができたら，与えられた数を素因数分解してみましょう。
　ひたすら素数で割っていくのですが，素数表が用意できない場合どうしますか？ また，ひじょうに大きい素数を入力するとひじょうに時間がかかります。うまく短い時間で終了させる方法はないでしょうか。

■ エジプトの分数
　古代エジプトでは，分子が 1 の分数（1/2，1/3，1/4，……）しか使いませんでした。それ以外の分数は，分子が 1 の分数の和として表していました。
　1 つの分数に対して，この表し方は無数に存在しますが，自明（たとえば，3/5 ＝ 1/5 ＋ 1/5 ＋ 1/5）でない組み合わせ以外で，与えられた分数を「分子が 1 の分数の和」に分解する方法を調べて，プログラムとして表してみてください。

■ 2 次方程式を解く
　2 次方程式 x^2 ＋ ax ＋ b ＝ 0 は，中学校で習う「解の公式」で解を求められますが，単純な方法ではうまくいきません。「虚数解」が出ることがあるからです。そこで，これを考慮して，コンピュータに 2 次方程式を解かせてみましょう。

■ ユークリッドの互除法
　No. 1 のご回答にもありますが，ユークリッドの互除法は，最大公約数を求める方法です。数学的な証明は少しややこしいのですが，機械的に最大公約数が求められるということをお試しください。

■ ピタゴラス数
　三平方の定理 x^2 ＋ y^2 ＝ z^2 を満たす自然数は，(3, 4, 5) の組み合わせをはじめとして無数にありますが，その中で x，y，z の最大公約数が 1 のものを原始ピタゴラス数といいます。
　原始ピタゴラス数は，特定の手順で無数に生み出すことができます。その方法を調べて，プログラムで表してみてください（途中にユークリッドの互除法が使うことになると思います）。

■ 乱数で円周率
　正方形を描いて，その中に内接する円を描きます。正方形の中にばらばらと石を落としていくと，全体の「円周率 ÷ 4」の割合で，円の中に石が落ちます。
　乱数で石の落ちる位置を決めて，円の中・外を判定していくと，円周率が推定できることになります。
　この方法は，「モンテカルロ法」といいます。ウェブを「モンテカルロ 円周率」で調べると，問題の詳細がわかります。

■ 最強の 2 山くずし
　碁石を 2 つの山に分け，片方の山からなら好きなだけ取ってよい，ただし最後の 1 個を取ったら負け，というゲームがあります。
　これは，特定の手順をコンピュータに踏ませると，最強になります（条件によってはコンピュータは無敵，そうでない条件では人間が 1 度でもヘマをしたら人間は絶対敗北）。この手順を見つけて，最強の 2 山くずしプレーヤーを作ってください。

お礼

まったくの文系なので、このくらいが練習としては楽しいです。＾＾；
素因数分解、エジプトの分数、乱数で円周率は、興味を覚えました。
「最強の 2 山くずし」は、古畑任三郎で出た１５を答えた方が負けと同じ方法かな？

＞うまく短い時間で終了させる方法はないでしょうか。
数学の知識＆プログラム経験があまりないので、うまくとか、短時間というのが、難しいです。
考えるのは楽しいのですが、。

最終的には、楽しいLifeGameが作れると楽しいのですが、そこまではまだ修行が続きそうです。＾＾；
ありがとうございます。

回答No.1

noname#20377

ダイクストラ法
http://www5e.biglobe.ne.jp/~aji/3min/ex/sup03.html
逆ポーランド記法と電卓
http://www.di.takuma-ct.ac.jp/~miyatake/open/calc/calcsimu.html
ユークリッド互除法
http://www2e.biglobe.ne.jp/~tanabe/kai20.htm

敢えてソースは出していません。これは有名すぎたかなぁ・・・

お礼

ソースは、自分で考えますから必要はないです。
なんだかんだで「エラトステネスのふるい」もどきも1ヶ月くらいかかりました。
ただ、あげられた２つ意味が意味が分かりません。
すいません、完全な文系なもので。＾＾；

最短経路決定は、変数の与え方から考えないといけないので、面倒と言えば面倒。(これは私個人のプログラム的な問題なので、こういう回答も歓迎です。

鶴亀算もよく分からないくらい、数学は素人です。
ありがとうございました。

補足

ちょっと「ユークリッド互除法」じゃないけど、最大公約数の求め方について考えてみました。
約数の定義が私の中で曖昧ですが・・・。＾＾；

a , b , c の中で一番小さい数を求めて、その数(ｘ)で３つを割る。
３つともあまりが０でなければ、ｘ-1で再度繰り返して。
３つが割り切れたものが最大公約数って事かな。
ｘが１になれば、最大公約数はなしって事で。

低レベルな(ＰＣの処理能力を当てにした力押しの)アルゴリズムだとは思いますが、このくらいのが考えるのが楽しいのですが。＾＾；