LoginSignup
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@YuanzhongLi(yuanzhong li)

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

Last updated at Posted at 2019-11-10

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)はあやしいかもしれません...)
  • 教育的にはすごくいい問題だと思いました!
2
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?