裏 RjpWiki

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

数列の判定

2016年10月14日 | ブログラミング

締め切りが 2016/10/24 10:00 AM なので,その 1 分後に投稿されるように予約。
当初の締め切りが延期されても,当方は一切関知しない。

【問題】
スペース区切りで 5個の10 進数が並んでいます。
与えられた数列が以下のいずれの数列(の、途中の連続した5項)なのかを判別するプログラムを書いてください。
記号     名称
G     等比数列
A     等差数列
F     フィボナッチ数
x     G, A, F のいずれにも該当しない

出力は、G, A, F, x のいずれかを出力してください。


【例】
入力     出力
1 2 4 8 16     G
1 2 3 4 5     A
3 5 8 13 21     F
1 2 123 1234 9999     x



【補足】
入力に含まれる値は、1以上、100億以下の整数です。
入力は、全て狭義単調増加列になっています。
不正な入力に対処する必要はありません。
G, A, F は大文字ですが、 x は小文字です。
1, 4, 5, 9, 14, 23, ... という数列はフィボナッチではありません。

f = function(s) {
    mul = function(x, y) { # 等比数列の各項が大きな値のとき,等比になっているかどうかは,ある項の二乗が前後の二項の積に等しいかどうかを見ないといけない
        x = rev(as.integer(unlist(strsplit(as.character(x), ""))))
        y = rev(as.integer(unlist(strsplit(as.character(y), ""))))
        l.x = length(x)
        l.y = length(y)
        z = integer(l.x+l.y)
        for (i in 1:l.x) {
            for (j in 1:l.y) {
                z[i+j-1] = z[i+j-1]+x[i]*y[j]
            }
        }
        for (i in 1:(l.x+l.y-1)) {
            z[i+1] = z[i+1] + z[i] %/% 10
            z[i] = z[i] %% 10
        }
        paste(rev(z), collapse="")
    }
    sqr = function(x) { # 二乗する関数
        mul(x, x)
    }
    d = as.numeric(unlist(strsplit(s, " ")))
    dif = diff(d)
    if (all(dif[1] == dif)) {
        cat("A")
    } else if (mul(d[1], d[3]) == sqr(d[2]) && # a[i-1] * a[i+1] == a[i]^2
               mul(d[2], d[4]) == sqr(d[3]) &&
               mul(d[3], d[5]) == sqr(d[4])) {
        cat("G")
    } else {
        n = 1:49
        fib = round((((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n) / sqrt(5))
        i = which(fib == d[1])
        if (length(i) != 0 && all(d == fib[i[1]+0:4])) {
            cat("F")
        } else {
            cat("x")
        }
    }
}
f("160816114 194672138 235655746 285267482 345323794") # G
f("9845600625 9876856500 9908211600 9939666240 9971220736") # G
f("9715064832 9751864320 9788803200 9825882000 9863101250") # G
f("1234 6912 12590 18268 23946") # A
f("9999999990 9999999991 9999999992 9999999993 9999999994") # A
f("1 2000000000 3999999999 5999999998 7999999997") # A
f("13 21 34 55 89") # F
f("121393 196418 317811 514229 832040") # F
f("1134903170 1836311903 2971215073 4807526976 7778742049") # F
f("9983848527 9987006973 9990166419 9993326864 9996488308") # x
f("969323029 1568397607 2537720636 4106118243 6643838879") # x
f("1032569015 1670731762 2703300777 4374032539 7077333316") # x

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

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

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