マイムーブ![]()
(注)
コンピュータ将棋開発者のみに向けた発信ページです。
関係者以外にもわかる内容にするつもりはありません。
内容の質や量よりも更新頻度に力を入れるつもりです。
なので、日記みたいな内容になるときもあることでしょう。
このページへのリンクはご自由にお貼りください。
作者のページあなたは 341381 人目の訪問者です。
本日では 27 人目の訪問者です。
No.1790 シャッフル(その2) 2010年6月3日(木) 13時13分2秒 ここを読んだら、
1.1から10,000の番号を行列に書き込むと、書いてありました。確かにそうですわ。
2.ランダムに一つ選ぶ...そしてその数字を記録する。
3.(2)で選んだ数字を行列から消す... 行列の最後の数字で上書きします。そして行列のサイズを一つ縮める。(正確には行列の最後の位置を覚えておく...ですね。)
4.数字が無くなるまで(2) と(3)を繰り返す
私が書いたのよりも上手いやり方がありそうだなとは思っていたのですが、駄目だな自分。
以下のようになります。
#include <stdio.h>あと、前回の myRand 関数を汎用的にした、0〜大きな自然数nまでの乱数を生成する関数を作りたいような、面倒臭いような、というのも気を揉ませています。Visual BASIC では、Rnd 関数が0以上1未満の小数値なので Int(Rnd() * n) のようにすれば良さそう(とは言っても詳しく検証してません)なのですが、Cの rand 関数は整数を返すので。
#include <stdlib.h>
#include <time.h>
#define NUM_ITEMS 54
int main() {
int r, temp[NUM_ITEMS], result[NUM_ITEMS];
srand((unsigned)time(NULL));
for(int i = 0; i < NUM_ITEMS; i++) {
temp[i] = i + 1;
}
for(int i = 0; i < NUM_ITEMS; i++) {
r = rand() % (NUM_ITEMS - i);
result[i] = temp[r];
temp[r] = temp[NUM_ITEMS - 1 - i];
}
return(0);
}
# mkomiya 『flashで作ってる7ならべでは、カード全体から2枚抜き出して
カードを入れ替える作業を10回ぐらいやってシャッフルしてます。
単純にランダムに取り出すと却って時間がかかりますね
モンテカルロ囲碁でランダムに石を置く場合も
速度優先なら色々とテクニックがありそうですね
』 2010年6月9日(水) 9時43分21秒
# マイムーブ西村 『例の開発中のmixiアプリですか。
10回ぐらいって少なくないですか(ランダムに取り出してもO(n)でできるので)。
上の配列 temp は無しで、配列 result だけでできることもわかりました(駄目だな自分)。』 2010年6月9日(水) 20時59分2秒
# mkomiya 『もう公開済のらき☆すた7並べです。
mixiアプリには基本部分は流用する予定です
ソースを確認したら20回ぐらいやってました。
52枚だと半分の26回ぐらいやると良さそうですね』 2010年6月11日(金) 16時20分4秒
No.1789 シャッフル 2010年6月2日(水) 22時33分12秒 ここを読んで、よくゼミ生が卒業制作で Visual BASIC とかで例えばトランプをシャッフルするために0〜53の番号をランダムに(重複なしで)生成する必要とかがあるので、いろいろ考えを巡らせました。
シャッフル用の0〜53の番号列(重複無し)を作る方法としては、これまではあまり深く考えていなかったので、配列に0〜53を入れておき、それをランダムに抜き出していけばいいだろうと考えていました。以下のようにです。
#include <stdio.h>(乱数のところは本当はこれではいけませんが、とりあえず、いいことにする)
#include <stdlib.h>
#include <time.h>
#define NUM_ITEMS 54
int main() {
int r, temp[NUM_ITEMS], result[NUM_ITEMS];
srand((unsigned)time(NULL));
for(int i = 0; i < NUM_ITEMS; i++) {
temp[i] = i + 1;
}
for(int i = 0; i < NUM_ITEMS; i++) {
r = rand() % (NUM_ITEMS - i);
result[i] = temp[r];
for(int j = r; j < NUM_ITEMS - 1; j++) {
temp[j] = temp[j + 1];
}
}
return(0);
}
配列の要素数が54くらいならこれで問題ないですが、大きくなると速度が問題になります。そこで、ランダムに抜き出した後に配列を詰める処理を毎回行うのは効率が悪いことに気が付きました。つまり、以下のようにしたらいいだろうと考えました。
#include <stdio.h>これだと、配列の要素数を 100,000 とかにしても、瞬時に終わってくれます(しかし、単に NUM_ITEMS を 100000 にしただけだと乱数に問題があって無限ループ入りしました)。
#include <stdlib.h>
#include <time.h>
#define NUM_ITEMS 54
int main() {
int r, rest, half;
int temp[NUM_ITEMS], result[NUM_ITEMS];
srand((unsigned)time(NULL));
for(int i = 0; i < NUM_ITEMS; i++) {
temp[i] = i + 1;
}
int j = 0;
while(j < NUM_ITEMS) {
rest = NUM_ITEMS - j;
half = (rest + 1) / 2;
for(int k = 0; k < half; k++) {
do {
r = rand() % rest;
} while(temp[r] < 0);
result[j++] = temp[r];
temp[r] = -1;
}
int l = 0;
for(int k = 0; k < rest - half; l++) {
if(temp[l] > 0) {
temp[k++] = temp[l];
}
}
}
return(0);
}
1〜100,000 の乱数をちゃんと作るべきか。
int myRand() {間違っているかもしれませんが、考えるのが面倒臭くなってきました。暇だと思われても嫌ですしね。
int r, value;
while(1) {
r = rand();
if(r < (RAND_MAX - (RAND_MAX % 101))) break;
}
value = (r % 101) * 1000;
while(1) {
r = rand();
if(r < (RAND_MAX - (RAND_MAX % 1000))) break;
}
value += (r % 1000);
return(value);
}
ちなみにゼミ生にこのようなことを理解させるのは難しいので、54枚くらいのカードのシャッフルなら、その中からランダムに2枚を選び、入れ換える、というのを1,000回くらい繰り返させたりしています(Visual BASIC で)。
No.1788 予想すればよかった(今年の最強決定戦) 2010年1月14日(木) 9時10分43秒 今日から今年も最強決定戦が行われますが、今日は大雪じゃあないですか。広島でもうちの大学は10cmくらい積もっています。
今年に限って予想してなかったら、大雪になるなんて、皮肉ですね。
(昨年までの予想)
あとは開始が遅れるか、ですね。
# 森岡@GA将!!!! 『予想していなかったのは残念でした。まるでマーフィーの法則ですね。』 2010年1月14日(木) 18時0分21秒
# マイムーブ西村 『マーフィーの法則ですか。なるほど。』 2010年1月17日(日) 23時27分27秒
No.1784 理事の里 2009年10月18日(日) 5時7分20秒
計数将棋学的ドライブ 第11弾 −シリーズ最長距離の旅(全10回)−
第7回 理事の里
「津田の松原SA」
んっ! これって某CSA理事の里?
今回はそれとは別の人をいじりに来たのだが、偶然にも理事の里を見つけてしまった。前にも理事の里を見つけたので、これが2つ目の理事の里である
それはそれとして、いい風景である。
(第8回「踏切」へとつづく)
No.1782 パーキングエリアの島 2009年10月16日(金) 7時20分12秒
計数将棋学的ドライブ 第11弾 −シリーズ最長距離の旅(全10回)−
第5回 パーキングエリアの島
建物の中はパーキングエリアというよりも道の駅に似ている。それもそのはず、ここは第2駐車場で、本来のパーキングエリアは第1駐車場にあるのだ。
これが第2駐車場。平日のため利用者は少ない。
正にパーキングエリアの島である。あるいは橋台の島と呼ぶべきか。
平日ゆえ交通量は少ないが、タンクローリーが走っているのが見える。
(第6回「四国上陸」へとつづく)