ギャスケット作成。修正の解説をお願いします。

質問

ギャスケット作成。修正の解説をお願いします。

入門書の問題で、二次元配列を使ってパスカルの三角形を作り、そこからシェルピンスキーのギャスケットを作りたいと思い、以下のプログラムを書きました。
ピクセルの指定の部分は省略します。
（↓パスカルの三角形の部分）
pas = Array.new(HEIGHT) {|i| Array.new(WIDTH, 0)}
pas[0][WIDTH / 2] = 1
for i in (1..HEIGHT - 1)
for j in (1..WIDTH - 2)
pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j + 1]
end
end

で、２行目のpas[0][WIDTH / 2] = 1の、「WIDTH / 2」がまずかったらしく、パスカルの三角形の左下と右下が残念な感じになってしまいます。左下はすっぽ抜けていますし、右下には必要ないところで三角形が入ってきています。何でこんなことになるんでしょうか？簡単な言葉で説明してくださると助かります。

答えを見ると、「WIDTH / 2」を「WIDTH」に、「WIDTH」を「WIDTH*2」にかえてうまく出来てるんですが、なんでそうなるのっていう感じです。
私が持っている入門書の解説には、「加えるべき数字が利用できないことが原因です」とだけしか解説してません。

ここからはあまり関係ないと思うのですが

ビットマップファイル作成の部分です。

File.open("gasket.bmp", "wb") do |file|
file.write(["BM", HEADERS_LEN + WIDTH * HEIGHT, 0, HEADERS_LEN].pack(BITMAPFILEHEADER))
file.write([INFOHEADER_LEN, WIDTH, HEIGHT, 1, 8, 0, 0,
0, 0, COLOR_USED, COLOR_USED].pack(BITMAPINFOHEADER))
file.write("\xff\xff\xff\0")
file.write("\0\0\0\0")
(HEIGHT - 1).downto(0) do |y|
0.upto(WIDTH - 1) do |x|
if pas[y][x] % 2 == 0
file.write("\0")
else
file.write("\x01")
end
end
end
end

uptoの前の部分が０になっていますが、正解例は３２０になっています。ちなみに、ピクセル指定の部分で、WIDTHは６４０になっています。これもなんだかよくわかりません。

私は、一行目で配列のすべてにゼロが入っているから、「加えるべき数字」である数はすべての配列に入っていて、 Nilになるところはないと思うのです。

グーグル先生には聞きましたが、わかりませんでした。一言でもかまいませんので、どうか、よろしくお願いします。

回答No.4

siffon9 · ベストアンサー

> 抜き出しているなら、はじめにWIDTHとHEIGHTを設定した時と、パスカルの三角形の中のWIDTHと HEIGHTは異なるはずではないのですか？

横方向（X）について
パスカルの三角形は、1～1280(=640*2)の範囲で作成されているのに対して
ビットマップの作成は320～959（=320.upto(960 - 1)） の範囲を使用していますね。
中央部を抜き出している様に読めます。

お礼

回答ありがとうございます。
本当だ！よく見てますね～。
解答の色が変わっていなかったので、まったくきづかなかった・・・。

ありがとうございます。
おっしゃるとおり、これは中央部分を抜き出していると見るのが正解ですね。

ということは、siffon9さんが前の質問でおっしゃってたとおり、パスカルの三角形の部分で、左右の端と三角形の斜辺部分が交わるところで、pas[i][0]の部分がおかしいということになりますね。
ただ、私はそこがおかしいという理屈がまだよくわかりません。なぜなら、pas[i][0]には０が入っているからです。ビットマップにおいて左側にいきなり空白が出来るのはなぜなんでしょうか？

まあ、あまりなぜなぜといっていると嫌われるので、この辺で終わりにしてもかまいません。が、もしこのなぞを解説してくださるならお願いします。ヒントでも、一言でもいいので、よろしくお願いします。

回答No.6

osamuy

bitmap生成からじゃなくて、文字列出力からやってみては(添付画像参照)。
また、処理がよく分からないときは、pを使って変数の中身を確認しながら処理内容を把握してみては。

初心者という事ですので、一歩一歩着実に進んでいったほうが良いかと。

お礼

回答ありがとうございます。

たしかにおっしゃるとおり、もう少し確実にやっていきたいと思います。
文字列出力からやっていきます。

本日は長々とありがとうございました。
また機会があれば、是非ともよろしくお願いします。

回答No.5

siffon9

pas[i][0]=0というのはご理解いただけているのですよね？

ウィキペディア（Wikipedia）のパスカルの三角形の項目をご覧になってください。
パスカルの三角形の最初の10段が描かれています。

例えば真ん中の頂点から左斜め下に下っていって4番目の1の場所、縦に1,5,21,84の部分を全部0固定に変えたとします。そうした場合上の段から順に計算しなおすと、0固定に変えたところから値が異常になっていくのがご理解いただけると思います。

お礼

pas[i][0]=0は大丈夫です。

値が異常になっていくこともわかります。

しかし、プログラム上、偶数と奇数を区別しているわけですから、はじめのプログラムで作ったビットマップの左下の三角形が大きく消えているのはなんだか納得がいかないような気がしたのです。
実際にかいてみて、やっと理解できたような気がします。

００００１０００００００
０００１０１００００００
００１０２０１０００００
０１０３０３０１００００
００４０９０４０１０００
０４０13０13０５０１００←
００17０26０18０６０１０

もっとパスカルの三角形を大きくしていった場合、「←」の行の左側に偶数がたまっていた結果、はじめのプログラムで作ったビットマップの左下のほうで空白ができていたということでしょうか？

回答No.3

siffon9

No.2でも左右対象ですが正常ではありませんね。

Wikipediaで調べると以下のように書いてあります。
「2のn乗行のパスカルの三角形で偶数の箇所を白く、奇数の箇所を黒く塗りつぶす。このようにしてできる図形は、nを無限大にすることで、シェルピンスキーのギャスケットとなる」

nが無限大というのがポイントですね。
プログラムではpas[480][640]の描画エリア内でパスカルの三角形を描いていくわけですが、一番外側の最大の三角形の斜辺と描画エリアの端との交点以降は正しいデータとなりません。なぜならエリア外には計算の元になる正しいデータが存在しないので。
ですからビットマップ化する際には、pas[i][j]を大きめに設定して、その中央部（？）を抜きだして使用する必要があるのではないでしょうか？

お礼

抜き出しているなら、はじめにWIDTHとHEIGHTを設定した時と、パスカルの三角形の中のWIDTHとHEIGHTは異なるはずではないのですか？・・・自信ないですが。

それと、最大の三角形の斜辺と描画エリアの端との交点以降にはそもそものパスカルの三角形がありませんので、パスカルの三角形がなければギャスケットも出来ず、合理的に出来ているように見えます・・・でもちゃんと出来てないんですよね・・・。

回答だと色分けが出来ないので不便ですが、本の回答も示しておきます。

BITMAPFILEHEADER = "a2VIV"
BITMAPINFOHEADER = "VVVvvVVVVVV"
X = 640
Y = 480
FILEHEADER_LEN = 14
INFOHEADER_LEN = 40
COLOR_USED = 2
COLORTBL_LEN = 4 * COLOR_USED
HEADERS_LEN = INFOHEADER_LEN + FILEHEADER_LEN + COLORTBL_LEN

pas = Array.new(Y) {|i| Array.new(X*2, 0)}
pas[0][X] = 1
for i in (1..Y - 1)
for j in (1..X*2 - 2)
pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j + 1]
end
end

File.open("gasket2.bmp", "wb") do |file|
file.write(["BM", HEADERS_LEN + X * Y, 0, HEADERS_LEN].pack(BITMAPFILEHEADER))
file.write([INFOHEADER_LEN, X, Y, 1, 8, 0, X*Y,
0, 0, COLOR_USED, COLOR_USED].pack(BITMAPINFOHEADER))
file.write("\xff\xff\xff\0")
file.write("\0\0\0\0")
(Y - 1).downto(0) do |y|
320.upto(960 - 1) do |x|
if pas[y][x] % 2 == 0
file.write("\0")
else
file.write("\x01")
end
end
end
end

変更部分、
「WIDTH / 2」を「X」
「WIDTH」を「X*2」
「HEIGHT」を「Y」
uptoの前の０を３２０

どうか、いましばらくお付き合いください

回答No.2

siffon9

> ピクセルの指定部分→パスカルの三角形の部分→ビットマップファイル作成の部分
と貼り付けて試してみてください。ちょっとおかしなギャスケットが出来ますので・・・。

再現しました。
パスカルの三角形の部分を
for j in (0..WIDTH - 2)
と変更すると正常に表示します。
（WIDTHに関連する変更はしていません）

Arrayの要素は、0から始まりますので、元々のプログラムではpas[i][0]に正確な数値が代入されずに0のままです。一番大きな三角を左斜め下に辿って左端にぶつかったところでpas[i][0]=1になるべきところが0のままなので、それ以降のデータがおかしくなるのだと思います。
たぶん。。。

お礼

回答ありがとうございます。仕事いってきました・・・ハハハ

三角形が端に到達してからおかしくなっているので、やはりその辺がネックなんでしょうか？
ただ、pas[i][0]=1にならないからと言うだけではちょっと納得できません。左側はいきなりポカンと抜けてますから・・・。

回答No.1

siffon9

ご質問の趣旨がわかりにくいので、ビットマップではなくテキストファイルに出力するプログラムを作って見ました。pas.txtというファイルに出力されます。ファイルの内容を見る限り（上下逆になりますが）問題なくできているように見えるのです。何が問題なのでしょうか？

HEIGHT = 100
WIDTH = 100

pas = Array.new(HEIGHT) {|i| Array.new(WIDTH, 0)}
pas[0][WIDTH/2] = 1
for i in (1..HEIGHT - 1)
for j in (1..WIDTH - 2)
pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j + 1]
end
end

File.open('pas.txt','w') do |f|
(HEIGHT - 1).downto(0) do |y|
0.upto(WIDTH - 1) do |x|
if pas[y][x] % 2 == 0
f.print(" ")
else
f.print("*")
end
end
f.puts
end
end

お礼

実際に確認しました。siffon9さんが作られたプログラムでは正常に出来るんですね・・・。ということはビットマップファイルの部分に問題があるんでしょうかね。

質問の趣旨がわかりにくくてすみません。
私が作ったプログラムでは、左右が非対称になってしまいます。それを左右対称にするために、回答例ではいくつか修正をしていて、確かにそうすると左右対称になるのですが、なぜそうなるのかがわからないんです。それを教えていただきたいと思い、質問しました。

一応、ピクセルの指定部分も書いておこうと思います。

BITMAPFILEHEADER = "a2VIV"
BITMAPINFOHEADER = "VVVvvVVVVVV"
WIDTH = 640
HEIGHT = 480
FILEHEADER_LEN = 14
INFOHEADER_LEN = 40
COLOR_USED = 2
COLORTBL_LEN = 4 * COLOR_USED
HEADERS_LEN = INFOHEADER_LEN + FILEHEADER_LEN + COLORTBL_LEN

以上です。ピクセルの指定部分→パスカルの三角形の部分→ビットマップファイル作成の部分
と貼り付けて試してみてください。ちょっとおかしなギャスケットが出来ますので・・・。

ちなみに、正解例でいじっているのは、HEIGHTとWIDTHをXとYに変えて、「WIDTH / 2」を「WIDTH」に、「WIDTH」を「WIDTH*2」にかえて、ビットマップファイルの作成の部分でuptoの前の部分の０を３２０に変えているだけのように見えます。

再回答お待ちしています。