2009年2月22日日曜日

C/C++でポインタによる多次元配列を連続したメモリ領域に作成する

このブログ記事をはてなブックマークに追加

下記のようにC/C++の配列で多次元配列を作れば連続したメモリ領域となるが、動的に大きさを変えられないし、関数に渡したりするのも大変だ。

int a[N][M];

一方、ポインタを使った下記の方法だと確保したメモリ領域が不連続となる。

int **a = new int*[N]; for (int i = 0; i < N; i++) a[i] = new int[M];

動的にメモリ確保して連続したメモリ領域にしたい場合、以下のようにすれば良い。

int **a = new int*[N]; a[0] = new int[N * M]; for (int i = 1; i < N; i++) a[i] = a[0] + i * M;

ここで、a[i][j](*a)[i*M+j] は同じ値を示す。

二次元配列、三次元配列を扱った実際のコード(C/C++)を最後に載せておく。

Cバージョン:

#include <stdio.h> #include <stdlib.h> /* NX*NYの二次元配列およびNX*NY*NZの三次元配列. */ #define NX 5 #define NY 6 #define NZ 7 int main() { int **x2; int ***x3; int cnt2 = 0; int cnt3 = 0; int i, j, k; /* 二次元配列の作成 */ x2 = (int**)malloc(NX * sizeof(int*)); x2[0] = (int*)malloc(NX * NY * sizeof(int)); for (i = 1; i < NX; i++) x2[i] = x2[0] + i * NY; /* 三次元配列の作成 */ x3 = (int***)malloc(NX * sizeof(int**)); x3[0] = (int**)malloc(NX * NY * sizeof(int*)); x3[0][0] = (int*)malloc(NX * NY * NZ * sizeof(int)); for (i = 0; i < NX; i++) { x3[i] = x3[0] + i * NY; for (j = 0; j < NY; j++) x3[i][j] = x3[0][0] + i * NY * NZ + j * NZ; } /* 配列に数値を代入 */ for (i = 0; i < NX; i++) { for (j = 0; j < NY; j++) { x2[i][j] = cnt2++; for (k = 0; k < NZ; k++) x3[i][j][k] = cnt3++; } } /* 配列を表示 */ for (i = 0; i < NX; i++) { for (j = 0; j < NY; j++) { printf("x2[%d][%d] = %d\n", i, j, x2[i][j]); printf("(*x2)[%d*NY+%d] = %d\n", i, j, (*x2)[i*NY+j]); for (k = 0; k < NZ; k++) { printf("x3[%d][%d][%d] = %d\n", i, j, k, x3[i][j][k]); printf("(**x3)[%d*NY*NZ+%d*NZ+%d] = %d\n", i, j, k, (**x3)[i*NY*NZ+j*NZ+k]); } } } free(x2[0]); free(x2); free(x3[0][0]); free(x3[0]); free(x3); return 0; }

C++バージョン:

#include <iostream> // NX*NYの二次元配列およびNX*NY*NZの三次元配列. const int NX = 5; const int NY = 6; const int NZ = 7; int main() { // 二次元配列の作成. int **x2; x2 = new int*[NX]; x2[0] = new int[NX * NY]; for (int i = 1; i < NX; i++) x2[i] = x2[0] + i * NY; // 三次元配列の作成. int ***x3; x3 = new int**[NX]; x3[0] = new int*[NX * NY]; x3[0][0] = new int[NX * NY * NZ]; for (int i = 0; i < NX; i++) { x3[i] = x3[0] + i * NY; for (int j = 0; j < NY; j++) x3[i][j] = x3[0][0] + i * NY * NZ + j * NZ; } // 配列に数値を代入. int cnt2 = 0; int cnt3 = 0; for (int i = 0; i < NX; i++) { for (int j = 0; j < NY; j++) { x2[i][j] = cnt2++; for (int k = 0; k < NZ; k++) x3[i][j][k] = cnt3++; } } // 配列を表示. for (int i = 0; i < NX; i++) { for (int j = 0; j < NY; j++) { std::cout << "x2[" << i << "][" << j << "] = " << x2[i][j] << std::endl; std::cout << "(*x2)[" << i << "*NY+" << j << "] = " << (*x2)[i*NY+j] << std::endl; for (int k = 0; k < NZ; k++) { std::cout << "x3[" << i << "][" << j << "][" << k << "] = " << x3[i][j][k] << std::endl; std::cout << "(**x3)[" << i << "*NY*NZ+" << j << "*NZ+" << k << "] = " << (**x3)[i*NY*NZ+j*NZ+k] << std::endl; } } } delete[] x2[0]; delete[] x2; delete[] x3[0][0]; delete[] x3[0]; delete[] x3; return 0; }

続きを読む...

2009年2月21日土曜日

PS3: デモンズソウルと末弥純の世界

このブログ記事をはてなブックマークに追加

平成の世も既に20年以上が過ぎた。名作、駄作と呼ばれる様々なゲームをプレイしてきたが、初めてウィザードリィをプレイしたときの感動を今になって得られるとは思いもしなかった。

PS3のゲームソフト、デモンズソウル(Demon's Souls)はまさに末弥純(すえみじゅん)の描いたウィザードリィ(Wizardry)の世界そのままだ。初代ウィザードリィをプレイしてその面白さに虜になった自分だが、生粋のウィザードリィフリークでもある末弥純のイラストはまさにその世界を的確に表現している。

そんな末弥純の世界を生きているかのように錯覚させるデモンズソウルだが、このゲームは本当に面白いと思う。メーカー側が事前にほとんど宣伝していなかったにもかかわらず、初週売り上げ4万本で消化率9割超だそうだ。メーカー側も在庫を切らすほど。因みに消化率と云うのは店に卸した本数に対して実際売れた本数のことで、それが9割超というのはほとんどの店で売り切れている異常事態だそうだ。つまり口コミでそれだけ売れるほどデキが良いのだ。まあ、実際のゲームレビューや感想はamazonのレビューでも見てもらったほうが早いだろう。

甲冑の擦れ、軋む音、剣先があたる鋭い金属音、何かが這いずる鈍い音、遠くから聞こえる人の声、物の落ちる音、悲鳴や哄笑、等々。これらはただのBGMではない。すべての音には理由がある。デモンズソウルは、世界が息づいていることを実感できる得がたいゲームの一つだ。

続きを読む...

2009年2月5日木曜日

Project Eulerを150問解いてみた

このブログ記事をはてなブックマークに追加

最近、Project Eulerを再び解き始めた。8ヶ月以上のブランクだ。前回の最後にGoogle App Engineの招待状が届かないと文句を言っていたのだが、その後、すぐに届いてそちらの方にはまってしまった。で、Project Eulerについてはそのまま忘れてしまっていた。

再開してみたはいいが、ブランクがあったせいなのか、いまいち頭の回転が落ちたように感じる。問題がなんだか難しく感じるのだ。それとも以前よりも本当に問題が難しくなっているのだろうか。何はともあれProject Eulerは頭の体操には持って来いだし、最近いじっていないC++を錆びつかせないようにするのにも役立っている。とは言ってもクラスの設計が必要なほど大規模なプログラムにはならないけど。

現在、230問中150問解き、やっとレベル4になった。日本人の中では515人中24位。10日間ほどで30問弱を解いたが、このペースだと疲れる。もう少しゆっくり解こう。

問題114は、ブロックを組み合わせる問題。組合せの関数とハッシュで実行時間は一瞬。

問題115も、ブロックの組み合わせ。問題114が解ければ問題なし。

問題116も、問題114/115の類似問題。

問題117も、ブロックの組み合わせの応用。問題なし。

問題121は、順列を用いた関数を作って対処。実行時間は一瞬。

問題122は、掛け合わせが最も少ない組み合わせを探すアルゴリズムを考えるのがちょっと面倒だった。改良の余地があると思う。実行時間は約25秒。

問題124は、因数を使って解く。正解者も多く、簡単だと思う。

問題125は、素直に調べた。実行時間は一瞬。正解者は多め。

問題126は、立体図形の問題。キューブの増え方の規則が分かれば解ける。図形問題は好みだなぁ。実行時間は一瞬。正解者は少なめ。

問題127は、最小公倍数に関する問題。ちょっと苦労した。実行時間がかかったので改良の余地あり。

問題128は、効率の良いヘックスタイルの生成関数を作れば解ける。これは面白かった。実行時間は約1秒。

問題130問題132問題133は、レピュニット(repunit)に関する問題。苦労した。これは苦手だ。あと、問題129もレピュニットに関する問題だがまだ解けていない。

問題131は、素数に関する問題。与えられた式をいじって素数候補を絞った。実行時間は一瞬。

問題134は、素直に計算した。もっと効率的なアルゴリズムがあると思う。

問題135は、式を変形させ計算量を減らし解いた。それでも少し実行時間がかかったので改良の余地あり。

問題136も、式を変形させて計算量を減らした。式の変形は解法の基本かな。実行時間は約8秒。

問題137は、10番目まで出力させ、それらの数列から規則を見つけた。

問題138は、図形問題だが実は問題137と似ている。規則を見つけよう。

問題139も、問題137/138と類似している。少し複雑になっているが大したことはないと思う。

問題140は、完全に問題137の応用。規則を見つければ良い。

問題141は、数が大きくて、計算量を減らしたつもりだったが時間がかかった。改良の余地あり。

問題142は、式を変形させて解いた。実行時間は約40秒。もう少し改良できるかも。

問題143は、三角関数を使って解いた。最初、問題文を読み違えて苦労した。計算量を減らすためにやや工夫したが、それでも計算時間は6分半ほどかかった。正解者はかなり少なめ。

問題144は、素直に入射角と接線から反射角を求め、それと楕円との交点の計算を繰り返して解いた。計算時間は一瞬。

問題145は、普通に数え上げた。もっと良い方法があると思う。正解者は多め。

問題148は、シンプルだけど醜いコードになった。気分的にすっきりしないなぁ。実行時間は約3秒。

問題173は、正解者が多いだけあって簡単だった。実行時間は2秒弱。

問題187は、普通に数え上げた。正解者は多め。

続きを読む...