Phân tích thiết kế giải thuật 8回目

2019年10月15日、Phân tích thiết kế giải thuậtの8回目授業が実施された。
この日は中間試験を行うことが知らされていた。
昨年度この先生の別な科目を受けたが、中間試験の日はまず試験を行い、休憩後に授業を行うという方式であった。
このため、この日も同様と考え、息せき切って教室に向かったが、予想に反し問題を解く時間となっていた。
結果として前半の1時間半ぐらいが通常の授業、休憩はなく試験の時間となった。
これであれば急いでくる必要はなかったかも。
とはいえこの日の授業でやったのとまったく同じ問題が試験に出たので来た意味はあったかな。
問題はこれだ。

昨年度の過去問に比べて、格段に難しくなっている。大問も増えたし。
新設されたのは問4だ。
これは対策の仕様もなかったし仕方ないが、得点源となるはずだった問2、しかも配点も20%と大きいのだが、これも昨年度より大幅に難しくなっており、最後までできなかった。
翌日になって落ち着いてやってみれば、ずっと続く部分は2のx乗分の1に集約でき、2のx乗をかけなおすことで結局は1になり、単純な形となる。
プログラミング言語でやってみたところ正しいようだ。

# include
import math
#funcation
def saiki(n):
	if(n == 1):
		return 0
	else:
		return 2 * saiki(n // 2) + n + 1
def tanbun(n):
	return int((2 ** math.log2(n)) * (math.log2(n) + 1) - 1)
def toi2(limit, kansuumei):
	print("実行する関数は", kansuumei)
	num = 1
	while(num < limit):
		print(num, kansuumei(num))
		num *= 2
# main
print("中間試験問2")
max = 100
toi2(max, saiki)
toi2(max, tanbun)

惜しむらくは試験中にこの正解までたどり着けず、得点源をみすみす逃がしてしまったことだ。