愛媛県宇和島市 みんなのパソコン教室 代表の松井です。今回もプログラミングやアルゴリズムを学んでいる中高生向けにアルゴリズムとコーディングのサンプルを掲載します。
前回に引き続き基数変換についてアルゴリズムを考えてみました。
今回はn進数を10進数に変換する方法です。この考えは高校の授業「情報」でも、ITパスポート、基本情報技術者の資格取得にも必要な考え方です。アルゴリズムの勉強にも最適だと思います。
AtCoderのコンテストに出題された内容をもとにコーディングしていきます。
n進数→10進数
だいぶ省略して書きますが、n進数から10進数に変換する方法は、それぞれの位に対して「重み」をかけ、それを合算することで求めることができます。
「重み」とは、数値の下位の位から1桁あがるごとに増えていく値で2進数の場合は2倍、3進数の場合は3倍のことです。
わかりにくい説明で申し訳ありません。
例えば2進数の1011を10進数に変換する計算は以下の通りになります。
一番下位(右)の位から
(1×20) + (1×21) + (0×22) + (1×23)
=1 + 2 + 0 + 8
=11
2進数の1011は10進数では11になります。
7進数の123を10進数に変換すると
(3×70) + (2×71) + (1×72)
=3 + 14 + 49
= 66
となります。
以下はAtCoder Beginner Contest 220 B – Base Kの問題です。
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
整数 A,B が K 進法表記で与えられます。
A×B を 10 進法表記で出力してください。
注記
K 進法表記については、Wikipedia「位取り記数法」 を参照してください。
制約
- 2≤K≤10
- 1≤A,B≤105
- A,B は K 進法表記で与えられる
入力
入力は以下の形式で標準入力から与えられる。
K A B
出力
答えを出力せよ。
AtCorder , AtCoder Beginner Contest 220
https://atcoder.jp/contests/abc220
解答例
# n進数(basenum)の数値(num)を引数に渡すことで、数値を10進数に変換する関数を定義します
def decimal(num,basenum):
amari =[]
ans = 0
# 数値を10で割った余りをリストに追加することで各桁の数値を抽出します
while num > 0:
amari.append(num % 10)
num = num // 10
# 数値の下位の桁の数字から（数値×基数の０乗）＋（数値×基数の1乗）＋・・・と桁数分繰り返し計算します
# リスト内の数値を左から数値×(基数の添字を累乗)することで実現できました
for i,x in enumerate(amari):
ans += x * basenum**i
return ans
K = int(input())
A,B = map(int,input().split())
ans = decimal(A,K)*decimal(B,K)
print(ans)私が思いついたのは上記のとおり各桁の数値を抽出するために10で割った余りを求めましたが、後でほかの方の解答例を見たときにあpythonのlist関数で文字列から各桁の数値を抽出する方法もありました。
def decimal(num,basenum):
amari =[]
ans = 0
amari = list(map(int,(str(num))))
amari.reverse()
for i,x in enumerate(amari):
ans += x * basenum**i
return ans
K = int(input())
A,B = map(int,input().split())
ans = decimal(A,K)*decimal(B,K)
print(ans)宇和島市の中高校生向けのプログラミングはこちらから
宇和島ウエノマチハックスタジオ プログラミング部
宇和島市の小学生向けのプログラミングはこちらから
みんなのパソコン教室宇和島本校 ジュニアプログラミング講座