2009年01月31日
『ナノピコ教室』：８クイーンゲーム(2)
さて、それでは本題の 8クィーンゲームです。
８×８のチェス盤に２人で交互にクィーンを置いていき、自分の手番のときに置き場所が無いほうが負けというゲームです。
なお、すでに置かれているクィーン（自分が置いたものも含め）の利き筋に新しいクィーンを置くことはできません。
前回のコードをかなりの部分(特にChessboardクラス)を流用しています。
なお、回転、鏡像のものを省くために、最初の一手については、打つ場所を限定しています。
実行した結果は、８×８の盤では、先手必勝でした。
なお、『ナノピコ教室」の解説によれば、１０×１０の盤では、後手必勝らしいのですが、僕のプログラムでは時間がかかりすぎて、途中で実行を中止してしまいました。
利き筋をその都度判定しているところを、クィーンを置いた際に、利き筋をマークするように変更することで、速度をはやくできると思いますが、時間もないので、今回はこの辺で。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。
2009/2/4 追記
バグがあったので、コードを修正しました。（最初の一手で、打つ場所を限定している部分）
それと、10×10の盤で確かめてみました。まだ実行中ですが、途中経過から判断すると、２時間ちかくかかりそうです。
あまりにも遅すぎるので、速度改善するつもりです。
８×８のチェス盤に２人で交互にクィーンを置いていき、自分の手番のときに置き場所が無いほうが負けというゲームです。
なお、すでに置かれているクィーン（自分が置いたものも含め）の利き筋に新しいクィーンを置くことはできません。
前回のコードをかなりの部分(特にChessboardクラス)を流用しています。
なお、回転、鏡像のものを省くために、最初の一手については、打つ場所を限定しています。
実行した結果は、８×８の盤では、先手必勝でした。
なお、『ナノピコ教室」の解説によれば、１０×１０の盤では、後手必勝らしいのですが、僕のプログラムでは時間がかかりすぎて、途中で実行を中止してしまいました。
利き筋をその都度判定しているところを、クィーンを置いた際に、利き筋をマークするように変更することで、速度をはやくできると思いますが、時間もないので、今回はこの辺で。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace _8QFight {
class Program {
static void Main(string[] args) {
Solver solver = new Solver(4);
char r = solver.Solve();
solver.Print();
if (r == Chessboard.Black)
Console.WriteLine("先手必勝です");
else
Console.WriteLine("後手必勝です");
}
}
class Record {
public Record Root;
public int PlaceX { get; set; }
public int PlaceY { get; set; }
public char Piece { get; set; }
public List<Record> Children { get; private set; }
public Record() {
Children = new List<Record>();
}
public void Add(Record rec) {
Children.Add(rec);
rec.Root = this.Root;
}
public void Clear() {
Children.Clear();
}
public void Print(int indent) {
if (Piece != 0)
Console.WriteLine("{0} {1} ({2},{3})", new string(' ', indent), Piece, PlaceX,PlaceY);
foreach (var x in Children)
x.Print(indent + 1);
}
public override string ToString() {
return string.Format("{0} ({1},{2})", Piece, PlaceX, PlaceY);
}
}
class Solver {
private Chessboard board;
public Record record;
private int width;
public Solver(int width) {
this.width = width;
}
public char Solve() {
int half = width / 2 - (width%2==0?1:0);
char win;
for (int y = 0; y <= half; y++) {
for (int x = y; x <= half; x++) {
int p = y * width + x;
this.board = new Chessboard(width);
record = new Record();
record.Root = record;
Record nr = Put(p, Chessboard.Black, record);
win = Evaluate(Chessboard.White, nr);
if (win == Chessboard.Black) {
return win;
}
}
}
return Chessboard.White;
}
public void Print() {
record.Print(0);
}
public char Evaluate(char piece, Record rec) {
foreach (var place in board.CanPutPlaces()) {
Record nr = Put(place, piece, rec);
try {
char win = Evaluate(Opponent(piece), nr);
if (win == piece) {
rec.Clear();
rec.Add(nr);
return piece;
}
} finally {
board.UnPut(place);
}
}
return Opponent(piece); // 候補が無い場合もここに来る。
}
private Record Put(int place, char piece, Record rec) {
board.Put(place, piece);
Record nr = new Record { PlaceX = place % width, PlaceY = place / width, Piece = piece };
rec.Add(nr);
return nr;
}
private char Opponent(char piece) {
return piece == Chessboard.Black ? Chessboard.White : Chessboard.Black;
}
}
class Chessboard {
public const char Empty = '.';
public const char White = 'O';
public const char Black = '#';
private const char Finished = '/';
private int maxsize;
private char[] cells;
public int Width { get; private set; }
public Chessboard(int width) {
this.Width = width;
this.maxsize = width * width;
cells = Enumerable.Repeat(Empty, maxsize).ToArray();
}
public int X(int now) {
return now % Width;
}
public int Y(int now) {
return now / Width;
}
public void Put(int place, char piece) {
cells[place] = piece;
}
public void UnPut(int place) {
cells[place] = Empty;
}
public void Clear(int place) {
cells[place] = Empty;
}
public bool CanPut(int place) {
var q = from x in Settled()
from p in Courses(x)
select p;
return q.All(p => place != p);
}
public IEnumerable<int> CanPutPlaces() {
for (int i = 0; i < cells.Length; i++)
if (cells[i] == Empty && (CanPut(i))) {
yield return i;
}
}
public IEnumerable<int> Settled() {
return Enumerable.Range(0, maxsize).Where(x => cells[x] != Empty);
}
public IEnumerable<int> Courses(int now) {
return Virtical(now)
.Concat(Horizontal(now))
.Concat(SlantL(now))
.Concat(SlantR(now)).Distinct();
}
private IEnumerable<int> Virtical(int now) {
int m = now % Width;
return Enumerable.Range(0, Width).Select(i => i * Width + m);
}
private IEnumerable<int> Horizontal(int now) {
return Enumerable.Range((now / Width) * Width, Width);
}
private IEnumerable<int> SlantR(int now) {
int w1 = Width - 1;
int first = now - Math.Min(w1 - X(now), Y(now)) * w1;
int last = now + Math.Min(X(now), w1 - Y(now)) * w1;
for (int i = first; i <= last; i += w1)
yield return i;
}
private IEnumerable<int> SlantL(int now) {
int w1 = Width + 1;
int first = now - Math.Min(X(now), Y(now)) * w1;
int last = now + Math.Min(Width - 1 - X(now), Width - 1 - Y(now)) * w1;
for (int i = first; i <= last; i += w1)
yield return i;
}
public void Print() {
int i = 0;
foreach (var c in cells) {
Console.Write(c);
if (++i == Width) {
Console.WriteLine();
i = 0;
}
}
Console.WriteLine();
}
}
}
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。
2009/2/4 追記
バグがあったので、コードを修正しました。（最初の一手で、打つ場所を限定している部分）
それと、10×10の盤で確かめてみました。まだ実行中ですが、途中経過から判断すると、２時間ちかくかかりそうです。
あまりにも遅すぎるので、速度改善するつもりです。
2009年01月29日
『ナノピコ教室』：８クイーンゲーム(1)
またまた、『ナノピコ教室』の問題です。
問題は、「8-Queenゲーム」で先手必勝かどうかを調べる問題なのですが、まずは、良く知れ渡っている「8-Queenパズル」をC#で解いてみることにしました。
８クイーンパズルとは、チェスのクイーンを8x8のチェス盤に、8つのクイーンを互いに取られないように配置するパズルです。
たとえば、こんな感じ。
この問題は、再帰処理の練習問題としてはとても有名ですね。
もちろん、8x8限定ではなく、任意の NxNに対応できるようなプログラムとして作成しました。
アルゴリズム的には高速化などの手法を採っていないので、オーソドックスなものだと思います。
NxNのチェスの盤は、１次元の配列として表現しています。
なお、LINQの練習を兼ねて、IEnumerable
Chessboardクラスは、もっと簡単になるような気がします。特にクイーンの通り道である縦横斜めを求める部分はもう少し簡単にならないものかな。
ちゃんと 92通りの解が求まっているので間違ってはいないと思います。
using System;
using System.Collections.Generic;
using System.Linq;
namespace _8Queen {
class Program {
static void Main(string[] args) {
Puzzle p = new Puzzle();
p.Solve(8);
}
}
class Puzzle {
private int count = 0;
public void Solve(int n) {
Chessboard board = new Chessboard(n);
SolveInner(board,0);
Console.WriteLine(count);
}
private void SolveInner(Chessboard board,int y) {
if (y >= board.Width) {
board.Print();
count++;
return;
}
foreach (int pos in board.Vacants(y)) {
if (board.CanPut(pos)) {
board.Put(pos);
SolveInner(board, y + 1);
board.Clear(pos);
}
}
}
}
public class Chessboard {
private const char Empty = '.';
private const char Queen = 'Q';
private int maxsize;
private char[] board;
public int Width { get; private set; }
public Chessboard(int width) {
this.Width = width;
this.maxsize = width * width;
board = Enumerable.Repeat(Empty, maxsize).ToArray();
}
private int X(int now) {
return now % Width;
}
private int Y(int now) {
return now / Width;
}
public void Put(int place) {
board[place] = Queen;
}
public void Clear(int place) {
board[place] = Empty;
}
public bool CanPut(int place) {
foreach (int x in Settled()) {
foreach (int p in Courses(x)) {
if (place == p)
return false;
}
}
return true;
}
public IEnumerable<int> Vacants(int y) {
return Horizontal(y * Width).Where(x => board[x] == Empty);
}
private IEnumerable<int> Settled() {
return Enumerable.Range(0, maxsize)
.Where(x => board[x] == Queen);
}
private IEnumerable<int> Courses(int now) {
return Virtical(now)
.Concat(Horizontal(now))
.Concat(SlantL(now))
.Concat(SlantR(now)).Distinct();
}
private IEnumerable<int> Virtical(int now) {
int m = now % Width;
return Enumerable.Range(0, Width)
.Select(i => i * Width + m);
}
private IEnumerable<int> Horizontal(int now) {
return Enumerable.Range((now / Width) * Width, Width);
}
private IEnumerable<int> SlantR(int now) {
int w1 = Width - 1;
int first = now - Math.Min(w1- X(now), Y(now)) * w1;
int last = now + Math.Min(X(now), w1 - Y(now)) * w1;
for (int i = first; i <= last; i += w1)
yield return i;
}
private IEnumerable<int> SlantL(int now) {
int w1 = Width + 1;
int first = now - Math.Min(X(now), Y(now)) * w1;
int last = now + Math.Min(Width - 1 - X(now), Width - 1 - Y(now)) * w1;
for (int i = first; i <= last; i += w1)
yield return i;
}
public void Print() {
int i = 0;
foreach (var c in board) {
Console.Write(c);
if (++i == Width) {
Console.WriteLine();
i = 0;
}
}
Console.WriteLine();
}
}
}
2009年01月25日
ナノピコ教室：2次元配列の回転
問題
9行9列の2次元配列aを左へ90度、180度, 270度回転したものを配列b,c,dとする。
配列e,f,g,hは、aを次のような軸の周りで、180度回転したものとする。
e: a(1,1) と a(9,9)を結ぶ線
f: a(1,9) と a(9,1)を結ぶ線
g: a(1,5) と a(9,5)を結ぶ線
h: a(5,1) と a(5,9)を結ぶ線
配列aをもとにして、b,c,d,e,f,g,hを適当な順序で書き出すプログラムを書け。
ただし、配列の要素を入れ替える時に値を一時的にしまっておく場所として使えるのは、１変数だけとする。
ーーーーーーー
１変数だけしか使えないという制約から考えると、
90度回転させる処理よりも、e,f,g,hを求める反転処理のほうが簡単そうです。
そこで、a -> eを求める処理（これを DiagRevolveとする）と、a -> g を求める処理（これを HorRevolveとする）を組み合わせることで、bからhまでの配列を求める方法を採用しました。
a.DiagRevolve
という記述を、「配列 aにDiagRevolve処理をする」と読むと、
a.DiagRevolve.HorRevolve
で、a を左に270度回転した配列bとなります。これを繰り返し、
a.DiagRevolve.HorRevolve.DiagRevolve.HorRevolve...
と DiagRevolveとHorRevolveを交互に変換処理を行うと、
a,e,b,h,c,f,d,g という順番で配列を求めることができます。
これをC#のコードに書いたのが次のコードです。「書き出せ」というプログラムなので、変換処理の最後に、配列の内容を書き出す処理を挟み込んであります。
C#3.0の拡張メソッドで書いてみました。
普段２次元配列とか使ったことがないので、縦軸をｘ軸とするのか、Y軸とするのか、どちらが普通なのかわかりません。
『ナノピコ教室』の解答編を見ると、縦軸をX軸としているようですが、僕は横軸をx軸としたので、解答と微妙に違っていましたが、考え方は全く同じでした。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。
追記
改めてコードを眺めてみると、やはり、for文で y変数が外側に来るのはやはり不自然かなと思いました。A(x,y)という配列を考えた場合、x軸が縦方向に下に向かって伸びて行くと考えたほうが、このような問題の場合は自然なのかな。
これって常識ですか？ ここ十年以上まともに２次元配列を使ったコードを書いたことがないものですから...
9行9列の2次元配列aを左へ90度、180度, 270度回転したものを配列b,c,dとする。
配列e,f,g,hは、aを次のような軸の周りで、180度回転したものとする。
e: a(1,1) と a(9,9)を結ぶ線
f: a(1,9) と a(9,1)を結ぶ線
g: a(1,5) と a(9,5)を結ぶ線
h: a(5,1) と a(5,9)を結ぶ線
配列aをもとにして、b,c,d,e,f,g,hを適当な順序で書き出すプログラムを書け。
ただし、配列の要素を入れ替える時に値を一時的にしまっておく場所として使えるのは、１変数だけとする。
ーーーーーーー
１変数だけしか使えないという制約から考えると、
90度回転させる処理よりも、e,f,g,hを求める反転処理のほうが簡単そうです。
そこで、a -> eを求める処理（これを DiagRevolveとする）と、a -> g を求める処理（これを HorRevolveとする）を組み合わせることで、bからhまでの配列を求める方法を採用しました。
a.DiagRevolve
という記述を、「配列 aにDiagRevolve処理をする」と読むと、
a.DiagRevolve.HorRevolve
で、a を左に270度回転した配列bとなります。これを繰り返し、
a.DiagRevolve.HorRevolve.DiagRevolve.HorRevolve...
と DiagRevolveとHorRevolveを交互に変換処理を行うと、
a,e,b,h,c,f,d,g という順番で配列を求めることができます。
これをC#のコードに書いたのが次のコードです。「書き出せ」というプログラムなので、変換処理の最後に、配列の内容を書き出す処理を挟み込んであります。
C#3.0の拡張メソッドで書いてみました。
普段２次元配列とか使ったことがないので、縦軸をｘ軸とするのか、Y軸とするのか、どちらが普通なのかわかりません。
『ナノピコ教室』の解答編を見ると、縦軸をX軸としているようですが、僕は横軸をx軸としたので、解答と微妙に違っていましたが、考え方は全く同じでした。
class Program {
static void Main(string[] args) {
// この初期化はいつもどちらがx軸とy軸がで混乱する....
int[,] array = {
{ 11,21,31,41,51,61,71,81,91 },
{ 12,22,32,42,52,62,72,82,92 },
{ 13,23,33,43,53,63,73,83,93 },
{ 14,24,34,44,54,64,74,84,94 },
{ 15,25,35,45,55,65,75,85,95 },
{ 16,26,36,46,56,66,76,86,96 },
{ 17,27,37,47,57,67,77,87,97 },
{ 18,28,38,48,58,68,78,88,98 },
{ 19,29,39,49,59,69,79,89,99 },
};
Console.WriteLine(array[1, 8]);
Execute(array);
}
static void Execute(int[,] array) {
array.Print();
array.HorRevolve().DiagRevolve().HorRevolve().DiagRevolve()
.HorRevolve().DiagRevolve().HorRevolve();
}
}
static class ArrayExtended {
static int temp;
public static int[,] HorRevolve(this int[,] array) {
int yLeng = array.GetLength(1);
for (int y = 0; y < yLeng / 2; y++) {
for (int x = 0; x < array.GetLength(0); x++) {
temp = array[x, y];
array[x, y] = array[x, yLeng - y - 1];
array[x, yLeng - y - 1] = temp;
}
}
array.Print();
return array;
}
public static int[,] DiagRevolve(this int[,] array) {
for (int y = 1; y < array.GetLength(1); y++) {
for (int x = 0; x < y; x++) {
temp = array[x, y];
array[x, y] = array[y, x];
array[y, x] = temp;
}
}
array.Print();
return array;
}
public static void Print(this int[,] array) {
for (int y = 0; y < array.GetLength(1); y++) {
for (int x = 0; x < array.GetLength(0); x++) {
Console.Write("{0,2} ", array[x, y]);
}
Console.WriteLine();
}
Console.WriteLine();
}
}
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。
追記
改めてコードを眺めてみると、やはり、for文で y変数が外側に来るのはやはり不自然かなと思いました。A(x,y)という配列を考えた場合、x軸が縦方向に下に向かって伸びて行くと考えたほうが、このような問題の場合は自然なのかな。
これって常識ですか？ ここ十年以上まともに２次元配列を使ったコードを書いたことがないものですから...
2009年01月21日
ナノピコ教室：13階段への道（２次元版)
13階段への道の問題は、もうひとつあります。
最初の問題は、1次元の階段でしたが、今度は、2次元の階段です。
問題は、左右どちらかに1段ずつ上り、高さ１３段（１４か所ある）へ到達する総数が一番多い場所とその総数を求めよという問題。
話を単純化するために、高さ５段の階段で考えてみます。
左下が一番低い場所で、右上が一番高い場所です。
数字がその段数を表しています。
5段の場合は、全部で６か所あり、それぞれの場場所へ行く登り方が何通りあるかを求めればよいわけです。
前回と同じように、F(n)を n段まで登る登り方の総数とすると、
F(5) = F(4) + F(4)
と表せそうですが、端っこの 5 の場合は、
F(5) = F(4)
となってうまくいきません。しばらく考えましたがうまい方法を思いつかなかったので、計算式を導き出す方法は諦めて、すべてコンピュータにやってもらうことにしました。
再帰処理で、できそうです。
すべての登り方を試し、13段までたどり着いたら、その位置に対するカウントを１増やすことで、登り方の数を求めています。
13とか14とかマジックナンバーがあるのと Executeという安易な名前にしてあるのは、ご愛敬ということで...
これで実行してみたら、以下のような結果が得られました。
場所(6,7) or (7,6)の 1716通りが最も登り方が多い場所となります。
ちなみに『ナノピコ教室』の解答編には４つの解き方が書いてありました。
その中に、bool[8192](8192 = 2の13乗)のすべてのパターンについて、trueの個数ごとに分類するというやり方がありました。なるほどそんなやり方があるのか。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。
最初の問題は、1次元の階段でしたが、今度は、2次元の階段です。
問題は、左右どちらかに1段ずつ上り、高さ１３段（１４か所ある）へ到達する総数が一番多い場所とその総数を求めよという問題。
話を単純化するために、高さ５段の階段で考えてみます。
+-+-+-+-+-+-+
|5| | | | | |
+-+-+-+-+-+-+
|4|5| | | | |
+-+-+-+-+-+-+
|3|4|5| | | |
+-+-+-+-+-+-+
|2|3|4|5| | |
+-+-+-+-+-+-+
|1|2|3|4|5| |
+-+-+-+-+-+-+
| |1|2|3|4|5|
+-+-+-+-+-+-+
左下が一番低い場所で、右上が一番高い場所です。
数字がその段数を表しています。
5段の場合は、全部で６か所あり、それぞれの場場所へ行く登り方が何通りあるかを求めればよいわけです。
前回と同じように、F(n)を n段まで登る登り方の総数とすると、
F(5) = F(4) + F(4)
と表せそうですが、端っこの 5 の場合は、
F(5) = F(4)
となってうまくいきません。しばらく考えましたがうまい方法を思いつかなかったので、計算式を導き出す方法は諦めて、すべてコンピュータにやってもらうことにしました。
再帰処理で、できそうです。
private Dictionary<int, int> dict = new Dictionary<int, int>();
public void Execute() {
Execute(0, 0);
foreach (var k in dict.Keys) {
Console.WriteLine("({0},{1}) : {2}", k / 14, k % 14, dict[k]);
}
}
public void Execute(int x, int y) {
if (x + y == 13) {
int key = y * 14 + x;
if (dict.ContainsKey(key))
dict[key] = dict[key] + 1;
else
dict[key] = 1;
return;
}
Execute(x+1, y);
Execute(x, y+ 1);
}
すべての登り方を試し、13段までたどり着いたら、その位置に対するカウントを１増やすことで、登り方の数を求めています。
13とか14とかマジックナンバーがあるのと Executeという安易な名前にしてあるのは、ご愛敬ということで...
これで実行してみたら、以下のような結果が得られました。
(0,13) : 1
(1,12) : 13
(2,11) : 78
(3,10) : 286
(4,9) : 715
(5,8) : 1287
(6,7) : 1716
(7,6) : 1716
(8,5) : 1287
(9,4) : 715
(10,3) : 286
(11,2) : 78
(12,1) : 13
(13,0) : 1
場所(6,7) or (7,6)の 1716通りが最も登り方が多い場所となります。
ちなみに『ナノピコ教室』の解答編には４つの解き方が書いてありました。
その中に、bool[8192](8192 = 2の13乗)のすべてのパターンについて、trueの個数ごとに分類するというやり方がありました。なるほどそんなやり方があるのか。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。
2009年01月19日
えっ、ラムダ式 はデリゲート型ではないため、型 'object[]' に変換できません。？
System.Windows.Threading.Dispatcherクラスの
public DispatcherOperation BeginInvoke (
DispatcherPriority priority,
Delegate method,
Object arg,
params Object[] args
)
の引数 argsにラムダ式を渡そうとしたら、
というエラーメッセージが出てきた。
そうか、object型には変換できないのか、残念。
でも、コンパイラが出すこのメッセージはなんか変？
これをこの表現どおりに読めば、デリゲート型は、object[]に変換できるということになるのだが、もちろんそんなはずはない。
代入先が（型'object' であり）デリゲートで型ではないため、ラムダ式を 型 'object' に変換できません。
ということを言いたいのだと思うのだが...
http://msdn.microsoft.com/ja-jp/library/hy74she2.aspx
の日本語は、
デリゲート型ではないため、匿名メソッド ブロックを型 '型' に変換できません
この日本語も変だ。
この原文は、
Cannot convert anonymous method block to type 'type' because it is not a delegate type
itを中途半端に省略しちゃったから変な日本語になってしまったんですね。
public DispatcherOperation BeginInvoke (
DispatcherPriority priority,
Delegate method,
Object arg,
params Object[] args
)
の引数 argsにラムダ式を渡そうとしたら、
ラムダ式 はデリゲート型ではないため、型 'object[]' に変換できません。
というエラーメッセージが出てきた。
そうか、object型には変換できないのか、残念。
でも、コンパイラが出すこのメッセージはなんか変？
これをこの表現どおりに読めば、デリゲート型は、object[]に変換できるということになるのだが、もちろんそんなはずはない。
代入先が（型'object' であり）デリゲートで型ではないため、ラムダ式を 型 'object' に変換できません。
ということを言いたいのだと思うのだが...
http://msdn.microsoft.com/ja-jp/library/hy74she2.aspx
の日本語は、
デリゲート型ではないため、匿名メソッド ブロックを型 '型' に変換できません
この日本語も変だ。
この原文は、
Cannot convert anonymous method block to type 'type' because it is not a delegate type
itを中途半端に省略しちゃったから変な日本語になってしまったんですね。
2009年01月18日
ナノピコ教室：13階段への道
問題
１３段ある階段を下から上まで登る登り方の総数を求めてください。
ただし、登り方は、１段あるいは1段おきの2通りが許されているものとします。
----
頭の働きが悪い僕は、すぐには計算式が思い浮かびません。
ためしに、階段の段数を少なくして考えてみました。
１段 : 1通り
２段 ：2通り
３段 ：3通り
４段 ：5通り
８段 ：8通り
とここまでやってわかりました。ああなるほど、N段までの上り方総数は、
N-1段までの数と、N-2段までの数を足せば良いのか。
F(1) = 1
F(2) = 2
F(n) = F(n-1) + F(n-2)
の式をコードに落とせばできそうです。
これって、フィボナッチ数列の問題だったんですね。
で、書いたコードは以下の通りです。
StepN(13)で呼び出してみたら、３７７が返ってきました。
『ナノピコ教室』の解答編には、さらに計算量を少なくできる分割統治法について書いてありました。奇数と偶数の場合に分けることで、計算量を少なくできるようです。途中まで読み進んだのですが、根気が続かなく理解するのを断念しました。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式出版社)に掲載されている問題をGushwellがC#で解いたものです。
１３段ある階段を下から上まで登る登り方の総数を求めてください。
ただし、登り方は、１段あるいは1段おきの2通りが許されているものとします。
----
頭の働きが悪い僕は、すぐには計算式が思い浮かびません。
ためしに、階段の段数を少なくして考えてみました。
１段 : 1通り
２段 ：2通り
３段 ：3通り
４段 ：5通り
８段 ：8通り
とここまでやってわかりました。ああなるほど、N段までの上り方総数は、
N-1段までの数と、N-2段までの数を足せば良いのか。
F(1) = 1
F(2) = 2
F(n) = F(n-1) + F(n-2)
の式をコードに落とせばできそうです。
これって、フィボナッチ数列の問題だったんですね。
で、書いたコードは以下の通りです。
static int StepN(int n) {
if (n == 1)
return 1;
if (n == 2)
return 2;
return StepN(n - 1) + StepN(n - 2);
}
StepN(13)で呼び出してみたら、３７７が返ってきました。
『ナノピコ教室』の解答編には、さらに計算量を少なくできる分割統治法について書いてありました。奇数と偶数の場合に分けることで、計算量を少なくできるようです。途中まで読み進んだのですが、根気が続かなく理解するのを断念しました。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式出版社)に掲載されている問題をGushwellがC#で解いたものです。
2009年01月13日
ナノピコ教室：メビウス関数(2)
さて、素数が求まったので、これを使ってメビウス関数を定義してみる。
メビウス関数とは、
(1) μ(1) = 1
(2) μ(n) = 0 （n が平方因子を持つ（平方数で割り切れる）とき）
(3) μ(n) = (-1)**k （n が相異なる k 個の素因数に分解されるとき）
n が相異なる偶数個の素数の積ならば μ(n) = 1
n が相異なる奇数個の素数の積ならば μ(n) = -1
**は累乗を表す。
とのことです。
素数と同じように、配列を使って求めたいと思います。
まず、配列を 1 で初期化。
それから、
2,3,6,8,9...
3,6,9,12,15...
5,15,20,25,30...
...
の位置の要素に、-1を掛けていきます。これで、
n が相異なる偶数個の素数の積ならば μ(n) = 1
n が相異なる奇数個の素数の積ならば μ(n) = -1
の部分を求めます。
さらに、
4,8,12,16,20...
9,18,27,36...
25,50,75...
...
の要素（素数の２乗で割りきれる数）には、0を代入して、
n が平方因子を持つ（平方数で割り切れる）ときμ(n) = 0
を求めます。
2以上の数で、上記どれにも該当しなかいのはあり得ないので、配列のすべてにメビウス関数の値が設定されることになります。
今回は、数字を列挙するのはなく、整数 n を与えると、メビウス関数の値が戻ってくるような形にしようと思います。
単独のstaticメソッドとして定義するのは、配列を使った今回の方式だと効率がよくないので、Mebiusクラスとして定義しました。
static class Mebius {
static int maxnum = 100;
static int[] mebius;
static Mebius() {
mebius = Enumerable.Repeat(1, maxnum + 1).ToArray();
foreach (int p in Primes(maxnum)) {
for (int i = p; i <= maxnum; i += p)
mebius[i] *= -1;
int p2 = p * p;
for (int pp = p2; pp <= maxnum; pp += p2)
mebius[pp] = 0;
}
}
public static int Get(int n) {
return mebius[n];
}
}
Primesメソッドは省略
Mebius.Get(30)
のようにして値を得ます。
なお、範囲チェックはやってません。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式出版社)に掲載されている問題をGushwellが独自にC#で解いたものです。
2009年01月12日
ナノピコ教室：メビウス関数(1)
『ナノピコ教室』に掲載されている第1問目を解いてみました。
第1問目は
「メビウス関数μ(n) 1<=n<=100の値を求めよ(nは整数)」
という問題です。メビウス関数とは、
(1) μ(1) = 1
(2) μ(n) = 0 （n が平方因子を持つ（平方数で割り切れる）とき）
(3) μ(n) = (-1)**k （n が相異なる k 個の素因数に分解されるとき）
n が相異なる偶数個の素数の積ならば μ(n) = 1
n が相異なる奇数個の素数の積ならば μ(n) = -1
**は累乗を表す。
とのこと。
Wikipediaによれば、「数論や組合せ論における重要な関数である」とありますがが、よくわからないので、興味にある方は、Wikipediaを参照してください。
http://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%93%E3%82%A6%E3%82%B9%E9%96%A2%E6%95%B0
さて、どんな役に立つのか僕にはわからないメビウス関数ですが、とりあえず、どうやって解くかを考えてみます。
まずは、素数を求めなくてはいけません。素数といえば「エラトステネスのふるい」ですね。
static IEnumerable<int> Primes(int maxnum) {
bool[] primes = new bool[maxnum+1];
for (int i = 0; i <= maxnum; i++)
primes[i] = true;
primes[1] = false;
int squareroot = (int)Math.Sqrt(maxnum);
for (int i = 2; i < 11; i++) {
if (primes[i]) {
for (int n = i * 2; n <= maxnum; n += i)
primes[n] = false;
}
}
for (int i = 1; i <= maxnum; i++) {
if (primes[i] == true)
yield return i;
}
}
配列の０番目の要素は処理の都合上使っていません。
Primes(100)
として呼び出せば、1から100までの素数を列挙してくれます。
なんか、思ったよりも冗長ですね。
もっと簡潔にならないかなと考えました。
・prime配列のtrue, falseを反対にすれば、最初の初期化は不要になる。
・boolではなく。intにする。
の２つの案が思い浮かびました。
２つめの案を採用した結果、以下のようなコードになりました。
一部、LINQを使っています。
static IEnumerable<int> Primes(int maxnum) {
int[] primes = Enumerable.Range(0, maxnum+1).ToArray();
primes[1] = -1; // -1 : 素数ではない
int squareroot = (int)Math.Sqrt(maxnum);
for (int i = 2; i <= squareroot; i++) {
if (primes[i] > 0)
for (int n = i * 2; n <= maxnum; n += i)
primes[n] = -1;
}
return primes.Where(n => n > 0);
}
速度的には不利かもしれませんが、これで若干すっきりしました。
本当は、Primeクラスを作りたいところですが、このままとします。
※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式出版社)に掲載されている問題をGushwellが独自にC#で解いたものです。
