[PYTHON] Graduate School of Information Science and Technology, The University of Tokyo, Department of Creative Informatics, Winter 2014 Programming Exam

This is an example of the answer to the 2014 winter hospital exam.

• The contents of the description are personally solved by the author and do not guarantee the correct answer, and are not related to the University of Tokyo or the organization involved in providing the contents of this examination.

Question theme

--Numerical calculation

Problem statement

• If the University of Tokyo points out, the problem statement will be deleted.

(1)

def solve1(x):
    if (x <= 2):
        return 1
    else:
        return solve1(x - 1) + solve1(x - 2)

(2)

memo = [0] * 100
memo[0], memo[1] = 0, 1
def init():
    for i in range(2, 99):
        memo[i] = memo[i - 1] + memo[i - 2]
def solve2(x):
    init()
    return memo[x]

(3)

def solve3(s1, s2):
    carry = 0
    ret = ''
    for i in range(32):
        ch1 = s1[31 - i]
        ch2 = s2[31 - i]
        n1 = int(ch1)
        n2 = int(ch2)
        a = n1 + n2 + carry
        if (a >= 10):
            carry = 1
        else:
            carry = 0
        b = a % 10
        ret += str(b)
    return ret[::-1]

(4)

memo = [0] * 141
memo[0], memo[1] = 0, 1
def init():
    for i in range(2, len(memo)):
        memo[i] = memo[i - 1] + memo[i - 2]
def solve4(x):
    init()
    return memo[x]

(5)

def solve5(s1, s2):
    n1 = int(s1)
    n2 = int(s2)
    return n1 / (10**(31 - n2))

(6)

def root(x):
    x = float(x)
    right = x
    left = 0.0
    esp = 1e-7
    while (abs(right - left) > esp):
        mid = (right + left) / 2
        if (mid * mid > x):
            right = mid
        else:
            left = mid
    return right        

def solve6():
    return (1 + root(5)) / 2

(7)

# (a + b * root(5) / 2)**2 a, b
def func1(a, b):
    new_a = int((a ** 2 + (b**2)*5) / 2)
    new_b = int(a * b)
    return new_a, new_b

# (a + b * root(5) / 2) * (c + d * root(5) / 2)
def func2(a, b, c, d):
    new_a = int((a * c + b * d * 5) / 2)
    new_b = int((a * d + b * c) / 2)
    return new_a, new_b

root5 = root(5)

class obj:
    def __init__(self, a, b):
        self.a = a
        self.b = b
    def __repr__(self):
        return '({0} + {1} * root5) / 2'.format(self.a, self.b)
    def cal(self):
        return (self.a + self.b * root5) / 2
    def f1(self):
        new_a, new_b = func1(self.a, self.b)
        return obj(new_a, new_b)

# (1+roo5/2)2 index-Stores square obj
memo1 = [obj(0, 0)] * 9
memo1[1] = obj(1, 1)
def init_memo1():
    # 128 (2^7)Calculate up to
    for i in range(2, len(memo1)):
        memo1[i] = memo1[i - 1].f1()

init_memo1()

# ex) 139 = 128(2^7) + 8(2^3) + 2(2^1) + 1(2^0) = [1, 1, 0, 1, 0, 0, 0, 1]
def func3(x):
    ret = [0] * 8
    if (x >= 128):
        ret[7] = 1
        x -= 128
    if (x >= 64):
        ret[6] = 1
        x -= 64
    if (x >= 32):
        ret[5] = 1
        x -= 32
    if (x >= 16):
        ret[4] = 1
        x -= 16
    if (x >= 8):
        ret[3] = 1
        x -= 8
    if (x >= 4):
        ret[2] = 1
        x -= 4
    if (x >= 2):
        ret[1] = 1
        x -= 2
    if (x >= 1):
        ret[0] = 1
        x -= 1  
    return ret

def obj_mul(obj1, obj2):
    a = obj1.a
    b = obj1.b
    c = obj2.a
    d = obj2.b
    new_a, new_b = func2(a, b, c, d)
    return obj(new_a, new_b)

# (1+roo5/2)Stores index-th power obj
memo2 = [obj(0, 0)] * 141
memo2[1] = obj(1, 1)

for i in range(2, len(memo2)):
    digit2 = func3(i)
    obj_array = []
    for (index, j) in enumerate(digit2):
        if (j == 1):
            obj_array.append(memo1[index+1])
    tmp = obj_array[0]        
    for k in range(1, len(obj_array)):
        tmp = obj_mul(tmp, obj_array[k])
    memo2[i] = tmp

def g(x):
    return memo2[x].cal() / root5

(8)

def f(x):
    return solve4(x)

def solve8():
    Max = 0.0    
    for i in range(1, 141):
        Max = max(abs(f(i) - g(i)), Max)
    return Max

Impressions

--Because python can do something like (3) by default, (4), (5) ... This is the good thing about python lol -(8) was solved on the assumption that x is an integer, but in the case of an interval, both increase exponentially, so it is expected that the difference will be maximum when x = 140. --In the case of an interval, that is the only way to find f (x) and g (x), differentiate f (x) --g (x), and use Newton's method. ――It took about an hour because the python specifications helped me a lot. If (8) is an interval specification, it will be mathematics.