ウサギの生仔とサイダーの瓶を換える二つのアルゴリズム.
3585 ワード
一、うさぎの赤ちゃん
もともとはウサギの赤ちゃんの定数アルゴリズムを見つけたいです.再帰式を繰り返せば定数アルゴリズムが得られると思います.
しかし自分で基礎を分析するのはあまりにも悪くて、要領を得ないで、しかし途中で1つの計算方法を噴き出して、線形の計算方を得ることができます.
ウサギの赤ちゃんは再帰的な複雑な構造に見えますが、ウサギは13種類の状態(12年半)しかないです.一生が短いからです.
0.0うさぎちゃん
0.5ウサギ
1.0大兎
1.5うさぎの生うさぎ
2.0ウサギの生ウサギ(2.0生は2つのウサギがいます)
2.5うさぎの生ウサギ
3.0うさぎの生うさぎ
3.5大きいウサギはウサギを生みます.
4.0うさぎの生兎
4.5うさぎの生うさぎ
5.0大きいウサギはウサギを生みます.
5.5うさぎ
6.0大兎(>=6.0兎死亡)
この十三の状態は先進先の列で、年齢を重ねるにつれて、状態は後ろにしか移動しません.
新たに加入した状態(新生ウサギ)は、8つの繁殖期の状態の合計です.
最後の状態は、死の状態です.
全部で何匹のウサギが生きているかを知るには、最後のマスを除いた数を統計します.nはいくらに等しいかに関わらず、2*nの状態を更新するだけでいいです.
コード:
二、サイダーを瓶に換える
サイダーの瓶を換えるのも再帰的な構造ですが、単純な代数変換によって、再帰的でない公式が得られます.
3空き瓶=1水+1空き瓶--2空き瓶=1水
問題はこのような置き換えには前提条件があります.つまり、置き換える時にはまず空き瓶が3つ以上あることを保証しなければなりません.前提条件が満たされていないと、後の公式も意味がありません.
どのように保証しますか?空き瓶を3つ持ってきて、片側に置いてもいいです.1+3=4は4つ残っています.4つは正規式によって計算しやすいです.最後に空き瓶が2つ残っています.
実はもう一歩進めばいいです.空き瓶を一つ持ってきてもいいです.変換する前に少なくとも2つの空き瓶があります.その中から残したほうがいいです.
だから:999/2=499....1+1=余2.
飲むサイダー:499+1000=1499.
このアルゴリズムの利点は、剰余を気にしないで計算してください.
コード:
もともとはウサギの赤ちゃんの定数アルゴリズムを見つけたいです.再帰式を繰り返せば定数アルゴリズムが得られると思います.
しかし自分で基礎を分析するのはあまりにも悪くて、要領を得ないで、しかし途中で1つの計算方法を噴き出して、線形の計算方を得ることができます.
ウサギの赤ちゃんは再帰的な複雑な構造に見えますが、ウサギは13種類の状態(12年半)しかないです.一生が短いからです.
0.0うさぎちゃん
0.5ウサギ
1.0大兎
1.5うさぎの生うさぎ
2.0ウサギの生ウサギ(2.0生は2つのウサギがいます)
2.5うさぎの生ウサギ
3.0うさぎの生うさぎ
3.5大きいウサギはウサギを生みます.
4.0うさぎの生兎
4.5うさぎの生うさぎ
5.0大きいウサギはウサギを生みます.
5.5うさぎ
6.0大兎(>=6.0兎死亡)
この十三の状態は先進先の列で、年齢を重ねるにつれて、状態は後ろにしか移動しません.
新たに加入した状態(新生ウサギ)は、8つの繁殖期の状態の合計です.
最後の状態は、死の状態です.
全部で何匹のウサギが生きているかを知るには、最後のマスを除いた数を統計します.nはいくらに等しいかに関わらず、2*nの状態を更新するだけでいいです.
コード:
//
//0,1,2,3,4,5,6,7,8,9,10,11,12
static int ( uint n )
{
//
uint[] states = new uint[13];
//
int start = 0;//0 ~ 11
states[start] = 1; // 0
//n
for ( int i = 0; i < n; i++ )
{
//
AddAge(ref start);
//
states[start] = states[getIndex( start, 10 )] + states[getIndex( start, 3 )] + states[getIndex( start, 4 )] + states[getIndex( start, 5 )]
+ states[getIndex( start, 6 )] + states[getIndex( start, 7 )] + states[getIndex( start, 8 )] + states[getIndex( start, 9 )];
//
Console.Write(" " + ((float)(i+1) / 2).ToString("{0.0}") + " :");
for ( int j = 0; j < 13; j++ )
{
Console.Write(states[getIndex(start, j)] + ", ");
}
Console.WriteLine();
}
//
uint count = 0;
for ( int i = 0; i < 12; i++ )
{
count += states[getIndex( start, i )];
}
return (int)count;
}
static void AddAge( ref int index )
{
index--;
if ( index < 0 )
index += 13;
}
static int getIndex( int start, int index )
{
return (start + index)%13;
}
二、サイダーを瓶に換える
サイダーの瓶を換えるのも再帰的な構造ですが、単純な代数変換によって、再帰的でない公式が得られます.
3空き瓶=1水+1空き瓶--2空き瓶=1水
問題はこのような置き換えには前提条件があります.つまり、置き換える時にはまず空き瓶が3つ以上あることを保証しなければなりません.前提条件が満たされていないと、後の公式も意味がありません.
どのように保証しますか?空き瓶を3つ持ってきて、片側に置いてもいいです.1+3=4は4つ残っています.4つは正規式によって計算しやすいです.最後に空き瓶が2つ残っています.
実はもう一歩進めばいいです.空き瓶を一つ持ってきてもいいです.変換する前に少なくとも2つの空き瓶があります.その中から残したほうがいいです.
だから:999/2=499....1+1=余2.
飲むサイダー:499+1000=1499.
このアルゴリズムの利点は、剰余を気にしないで計算してください.
コード:
static Tuple<int,int> ( int n,int p,int k )
{
Tuple<int, int> t = ( n, p,k );
Tuple<int, int> result = new Tuple<int, int>( t.Item1 + n, t.Item2 );
return result;
}
//n =
//p k
private static Tuple<int,int> ( int n, int p, int k )
{
int = ( n - k ) / ( p - k );
int = k + (n-k) % ( p - k );
return new Tuple<int,int>( , );
}