Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

東京大学大学院情報理工学系研究科 創造情報学専攻 2013年度夏 プログラミング試験

More than 1 year has passed since last update.

2013年度夏の院試の解答例です
※記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。

出題テーマ

  • アセンブリ

問題文

※ 東大の公式アーカイブにはすでにのっていなく、ここでは他のアーカイブサービスから取得したものを公開しますが、東京大学側から指摘があった場合は問題文を削除いたします。
Screen Shot 2019-11-10 at 15.51.21.png
Screen Shot 2019-11-10 at 18.11.14.png

※ prog.txtは公開されていないので以下は筆者が適当に作ったものです(prog5.txtはきついので作りませんでした)

配布ファイル

prog1.txt

SET x 1

prog2.txt

SET x 1
SET y 0
ADD x y
PRN x y
PRN 30 y

prog3.txt

SET x 1
SET y 0
ADD x y
ADD 1 x
CMP x 10
JMP -3 0
PRN x y

prog4.txt(サブルーチンからサブルーチンを呼ぶように後はテキトーに作った)

SET x 0
SET y 1
SUB 4 0
CMP 10 y
ADD y x
JMP 5 0
SUB 2 0
BAK 0 0
ADD 1 y
BAK 0 0
PRN x y

(1)

file_path = 'prog1.txt'
def solve(file_path):
    with open(file_path, encoding='ascii') as f:
        line1 = f.readline()
        code_array = line1.split(' ')
        order = code_array[0]
        operand1 = code_array[1]
        operand2 = code_array[2]    
        print(operand1)

(2)以下のコードを説明するだけ

y = 0
x = 1
while (x != 10):
    y += x
    x += 1

print(x, y)

(3)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog2.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    register = { 'x': 0, 'y': 0 }
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)

    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            if (isn.isNumber(op1)):
                register[op2] += isn.STRtoNumber(op1)
            else:
                register[op2] += register[op1]
        elif (order == 'PRN'):
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register[op2])
            else:
                if (isn.isNumber(op2)):
                    print(register[op1], isn.STRtoNumber(op2))
                else:
                    print(register[op1], register[op2])

        elif (order == 'SET'):
            if (isn.isNumber(op2)):
                register[op1] = isn.STRtoNumber(op2)
            else:
                register[op1] = register[op2]
    for i in range(0, len(orders)):
        order = orders[i][0]
        op1 = orders[i][1]
        op2 = orders[i][2]        
        compileOrder(order, op1, op2)

(4)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog3.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    register = {}
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)

    # python のglobal変数が使い辛すぎるのでこうした
    next_order = { 'num': 0 }        

    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                register[op2] += isn.STRtoNumber(op1)
            else:
                register[op2] += register[op1]
        elif (order == 'PRN'):
            next_order['num'] += 1            
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register[op2])
            else:
                print(register[op1], register[op2])
        elif (order == 'SET'):
            next_order['num'] += 1                    
            if (isn.isNumber(op2)):
                register[op1] = isn.STRtoNumber(op2)
            else:
                register[op1] = register[op2]
        elif (order == 'CMP'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    if (isn.STRtoNumber(op1) == isn.STRtoNumber(op2)):
                        next_order['num'] += 1
                else:
                    if (isn.STRtoNumber(op1) == register[op2]):
                        next_order['num'] += 1                        
            else:
                if (isn.isNumber(op2)):
                    if (register[op1] == isn.STRtoNumber(op2)):
                        next_order['num'] += 1                        
                else:
                    if (register[op1] == register[op2]):
                        next_order['num'] += 1                        
        elif (order == 'JMP'):
            if (isn.isNumber(op1)):
                next_order['num'] += isn.STRtoNumber(op1)
            else:
                next_order['num'] += register[op1]            

    while (next_order['num'] < len(orders)):
        order = orders[next_order['num']][0]
        op1 = orders[next_order['num']][1]
        op2 = orders[next_order['num']][2]
#         print(order, op1, op2)
        compileOrder(order, op1, op2)

(5)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog4.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    register = {}
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)

    # python のglobal変数が使い辛すぎるのでこうした
    next_order = { 'num': 0 } 
    sub_order_stack = []    

    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                register[op2] += isn.STRtoNumber(op1)
            else:
                register[op2] += register[op1]
        elif (order == 'PRN'):
            next_order['num'] += 1            
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register[op2])
            else:
                print(register[op1], register[op2])
        elif (order == 'SET'):
            next_order['num'] += 1                    
            if (isn.isNumber(op2)):
                register[op1] = isn.STRtoNumber(op2)
            else:
                register[op1] = register[op2]
        elif (order == 'CMP'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    if (isn.STRtoNumber(op1) == isn.STRtoNumber(op2)):
                        next_order['num'] += 1
                else:
                    if (isn.STRtoNumber(op1) == register[op2]):
                        next_order['num'] += 1                        
            else:
                if (isn.isNumber(op2)):
                    if (register[op1] == isn.STRtoNumber(op2)):
                        next_order['num'] += 1                        
                else:
                    if (register[op1] == register[op2]):
                        next_order['num'] += 1                        
        elif (order == 'JMP'):
            if (isn.isNumber(op1)):
                next_order['num'] += isn.STRtoNumber(op1)
            else:
                next_order['num'] += register[op1]
        elif (order == 'SUB'):
            # 次のorderをstackに保存
            sub_order_stack.append(next_order['num']+1)
            compileOrder('JMP', op1, op2)             
        elif(order == 'BAK'):
            next_order['num'] = sub_order_stack.pop()

    while (next_order['num'] < len(orders)):
        order = orders[next_order['num']][0]
        op1 = orders[next_order['num']][1]
        op2 = orders[next_order['num']][2]
#         print(order, op1, op2)
        compileOrder(order, op1, op2)

(6)

import sys
sys.path.append('..')
import IsStrNumber as isn

file_path = 'prog3.txt'
def solve(file_path):
    max_order = 100
    orders = [] 
    with open(file_path, encoding='ascii') as f:
        for i in range(0, max_order):
            line = f.readline()
            if (line != ''):
                line = line.rstrip('\n')
                code_array = line.split(' ')
                orders.append(code_array)

    # python のglobal変数が使い辛すぎるのでこうした
    next_order = { 'num': 0 } 
    sub_order_stack = []   

    # register_stack[0]をglobal register(実際のレジスタ)とする
    register_stack = [{}]
    # register_stackの最後尾のregisterオブジェクトを使用することによって局所レジスタを実現

    def compileOrder(order, op1, op2):
        if (order == 'ADD'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                register_stack[len(register_stack)-1][op2] += isn.STRtoNumber(op1)
            else:
                register_stack[len(register_stack)-1][op2] += register_stack[len(register_stack)-1][op1]
        elif (order == 'PRN'):
            next_order['num'] += 1            
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    print(isn.STRtoNumber(op1), isn.STRtoNumber(op2))
                else:
                    print(isn.STRtoNumber(op1), register_stack[len(register_stack)-1][op2])
            else:
                print(register_stack[len(register_stack)-1][op1], register_stack[len(register_stack)-1][op2])
        elif (order == 'SET'):
            next_order['num'] += 1                    
            if (isn.isNumber(op2)):
                register_stack[len(register_stack)-1][op1] = isn.STRtoNumber(op2)
            else:
                register_stack[len(register_stack)-1][op1] = register_stack[len(register_stack)-1][op2]
        elif (order == 'CMP'):
            next_order['num'] += 1                    
            if (isn.isNumber(op1)):
                if (isn.isNumber(op2)):
                    if (isn.STRtoNumber(op1) == isn.STRtoNumber(op2)):
                        next_order['num'] += 1
                else:
                    if (isn.STRtoNumber(op1) == register_stack[len(register_stack)-1][op2]):
                        next_order['num'] += 1                        
            else:
                if (isn.isNumber(op2)):
                    if (register_stack[len(register_stack)-1][op1] == isn.STRtoNumber(op2)):
                        next_order['num'] += 1                        
                else:
                    if (register_stack[len(register_stack)-1][op1] == register_stack[len(register_stack)-1][op2]):
                        next_order['num'] += 1                        
        elif (order == 'JMP'):
            if (isn.isNumber(op1)):
                next_order['num'] += isn.STRtoNumber(op1)
            else:
                next_order['num'] += register_stack[len(register_stack)-1][op1]
        elif (order == 'SUB'):
            # 次のorderをstackに保存
            sub_order_stack.append(next_order['num']+1)
            compileOrder('JMP', op1, op2)             
        elif (order == 'BAK'):
            next_order['num'] = sub_order_stack.pop()
        elif (order == 'CAL'):
            sub_order_stack.append(next_order['num']+1)
            new_register = { 'in': 0 }
            if (isn.isNumber(op2)):
                new_register['in'] = isn.STRtoNumber(op2)
            else:
                new_register['in'] = register_stack[len(register_stack)-1][op2]
            compileOrder('JMP', op1, op2)
            # JMPしてから局所レジスタをスタックに追加
            register_stack.append(new_register)
        elif (order == 'RET'):
            next_order['num'] = sub_order_stack.pop()
            # 局所レジスタを消去
            old_register = register_stack.pop()
            # 局所を抜けた後にoutを使用できるように、抜けた直後の局所registerにoutを追加
            if (isn.isNumber(op1)):
                register_stack[len(register_stack)-1]['out'] = isn.STRtoNumber(op1)
            else:
                register_stack[len(register_stack)-1]['out'] = old_register[op1]

    while (next_order['num'] < len(orders)):
        order = orders[next_order['num']][0]
        op1 = orders[next_order['num']][1]
        op2 = orders[next_order['num']][2]
#         print(order, op1, op2)
        compileOrder(order, op1, op2)

感想

  • 正直筆者は知識としてアセンブリ言語を知っているだけで、実際に書いたことはあまりなく(パタヘネOS自作入門などでちょこちょこと書いたことがあるくらい...)、そのため解くのには結構時間がかかりました。
  • おそらくアセンブリに全く触れたことがない人はスタックで管理するという概念がないので(5),(6)で詰む気がします。(なんなら(4)で詰むかもしれません)。
  • (5), (6)については考え方は多分あっていると思うのですが、配布ファイルがないため検証ができないので間違ってる可能性がやや高いです。(特に(6)はあやしいかもしれません...)
  • 教育的にはすごくいい問題だと思いました!
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away