裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

「トライアングル・メイズ」問題

2016年09月29日 | ブログラミング

締め切りが 2016/09/29 10:00 AM なので,その 1 分後に投稿されるように予約

設問

次のルールで生成される迷路を考えます。

レベル 1 の迷路から始めましょう。レベル 1 の迷路を M1 と呼びます。M1 は、3 つの点を L の字の形につないだものです。
左上の点がスタートで、右下の点がゴールです。

レベル 2 の迷路 M2 は、M1 を 3 つつなげて作ります。
M1 を 1 つ置き、さらにその上と右に 1 つずつ M1 をつなげたものです。
左上の点がスタートで、右下の点がゴールです。

レベル 3 の迷路 M3 は、M2 を 3 つつなげて作ります。
M2 を 1 つ置き、さらにその上と右に 1 つずつ M2 をつなげたものです。
左上の点がスタートで、右下の点がゴールです。

以降同様に、レベル k の迷路 Mk を、レベル k-1 の迷路 Mk-1 を 3 つつなげることで定義します。



さて、この迷路を、点と線をたどってスタートからゴールまで着く方法を考えます。
自然数 n に対し、迷路 Mn を最短距離でゴールするたどり方の数を F(n) と定義します。

例えば F(1) = 1,F(2) = 2 です。



同様に、F(3) = 6,F(4) = 42 です。
さらに、F(10) を 1000003(=10^6+3) で割った余りは 998593 となることが確かめられます。

標準入力から、自然数 n(1 ≦ n ≦ 10^8)が与えられます。
標準出力に F(n) を 1000003 で割った余り を出力するプログラムを書いてください。

=====

いつもの定石,すなわち,小さな問題の解を求め規則性を見つける。a(n) = a(n-1) * (a(n-1)+1)
ただし,真っ正直に計算するのでは n がばかでかいときには時間が掛かりすぎる。
ここでは,「1000003 で割った余り」を求めよということなので,答えの数列は一度ループにはまると,ループをぐるぐる回ることになるということ(これも定石)。
1~213 はループの外,214 項目の数値と同じ数値は1169 項目と同じになる(これは調べる)。
すなわち,214~1168, 1169~2123, ... は長さ955 のループ(同じ数字列の繰り返し)。

f = function(n) {
    m = 1168
    k = 1000003
    a = numeric(m)

    options(scipen=100)
    a[1] = f1 = 1
    a[2] = f2 = 2
    for (i in 3:m) {
        f3 = ((f2 %% k) * ((f2+1) %% k)) %% k
        a[i] = f3
        f1 = f2
        f2 = f3
    }
    if (n >= 214) {
        n = (n-214) %% 955 + 214
    }
    cat(a[n], " ")
}

> f(10)
998593  

> f(100000000)
342482  

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村