Python100本ノック 97本目~101本目(96本目~100本目)
Python100本ノック、97本目から101本目についてです。
いよいよ最終回です!!
97本目:完全数
問題:
高橋君は完全なのものが大好きです。自然数には、完全数という物があります。
完全数というのは、自分以外の約数の総和が自分と等しくなる自然数のことです。
例えば6の場合1+2+3=6となるので完全数です。それに対して、自分以外の約数の総和が
自分より小さくなる場合は不足数と言い、大きくなる場合は過剰数と言います。
高橋君には今気になっている自然数があります。高橋君のために、それが完全数なのか不足数なのか過剰数なのか判定してください。
特に問題無く解けました。
nの、n以外の約数を求める処理を、完全数か判定する関数と分けて書いてみました。
98本目:ハミング距離
問題:2つの整数が与えられます。これらを2進数に直した時の「ハミング距離」を測りなさい。※ハミング距離=2つの数字のうち、異なっている箇所の個数。
2つの整数の排他的論理和を取った結果で"1"
が何個含まれているかを数える
という方針はQiita記事のものと同じでした。
しかし、format()
で2進数に変換し忘れたため、正しく数えられていませんでした。
こんな感じで少しトラブルがありましたが、何とか解けました。
99本目:Numbers Factory
問題:2桁の整数が与えられる。その整数の約数を出力しなさい。
条件:約数は全て1桁であること。答えが複数存在する場合は、約数の個数が1番少なくなる方を出力すること。
~自分の解釈~
「答えが複数存在する場合は...」の部分がよく分かりませんでした。
「約数を出力しなさい」-> 20の場合、1桁の約数のみに絞って[1, 2, 4, 5]
を出力した。
しかし、CheckiOの問題ページも併せて読んだところ、本来の解釈と全然違ったようですw
~本来の解釈~
2桁の整数Nが与えられる。各桁の数字の積がNに等しくなる整数を探す。
例:N=20 -> 2 * 10, 4 * 5, 2 * 2 * 5。
各因数が全て1桁&その整数の最小値を選ぶ必要があるので、45を選択(4 * 5を出力)する。
...ということで、本来の解釈に従ってもう一度解き直してみました。
何とか素因数分解を実装することはできました。ライブラリ(Sympy)ではなく、今回は自分でアルゴリズムを組みました。
ただ、その後に数字の積を求める処理で頓挫しました...。
結局、Qiita記事の解法で勉強しました。
素因数分解におけるfor文のループ変数の範囲
自分では2, 3, 5, 7
に絞りました。一方、記事では9, 8, ... , 2
にしています。
合成数も含めた範囲にすると、このfor文で数字の積もまとめて求められるみたいです。int(''.join(map(str, sorted(ret))))
1.整数が格納されているリストret
を昇順にソート(sorted
)
2.リスト内の整数を全て文字列に変換(map
,str
)
3.上記で変換したデータを1つの文字列に結合(join
)
※map
をlist
で変換しなくても正常に結合できる模様。
めっちゃ時間使っても解けなくて悔しいです...。(多分3日ぐらい)
ここに来て、粘っても解けない問題が初めて現れました(>_<)
100本目:Number Base
問題:ある進数(radix)で記された数字(str_number)が与えられます。この数字を10進法に直して表示しなさい。
条件:そもそも与えられた数字が、与えられた進法で表すことができないものであった場合は"-1"と表示
例:
convert_10("AF", 16) == 175 convert_10("101", 2) == 5 convert_10("Z", 36) == 35 convert_10("AB", 10) == -1
特に問題無く解けました。
自分が解いたときの方針は、以下の通りです。
{"0": 0, "1":1, ... , "9": 9, "A": 10, "B": 11, ... , "Z": 35}
の辞書を作る。str_number
に関するfor文で...- もし、
str_numberのいずれか + 1 > radix
ならreturn -1
+1することで、radixとnumsの各値の間にあるズレを直しています。
例:"9"までなら10進法だと判別できるが、+1しなければ"A"までが10進法だと判別してしまう - 範囲内なら、
str_number
の末尾から順に、進数変換の計算を行う
result += (radix**i) * (nums[str_number[-(i+1)]])
- もし、
...が、Qiita記事のコードを見て唖然としました。
なんと、
try: return int(str_number, radix) except ValueError: return -1
...え、これだけ???
調べてみたら、組み込み関数のint
で瞬殺できるみたいですね...。
参考サイト:Pythonで2進数、8進数、16進数の数値・文字列を相互に変換 | note.nkmk.me
あの、実装できたのは嬉しいんですが、何か複雑な気分です(-_-;)
101本目:Double Substring
問題:あるテキストが与えられます。
そのテキストの内、ある文字列が2回登場した場合、その文字列の文字数を表示してください。
例:
double_substring('aaaa') ==> 2 double_substring('abc') ==> 0 double_substring('aghtfghkofgh') ==> 3 # fgh
特に問題無く解けましたが、Number Baseに続き、Qiita記事とは異なるアプローチでした。
(今回は、瞬殺できる方法が実はあったという訳ではありませんw)
自分は以下のように解いてみました。記事内の解法を読みましたが、少し難しかったです...。
文字がそれぞれ何回出現したかを記憶する辞書
count_dict
、
2回登場した文字列の文字数を返すための変数result
を定義する。引数の文字列に関するfor文で、
現在の文字がcount_dict
に含まれていなければ、count_dict[現在の文字] = 1
。
含まれていれば、count_dict[現在の文字] += 1
。
加算してcount_dict[現在の文字] = 2
になったら、
result += 1
してcount_dict[現在の文字] = 0
にリセットする。
ついに完走しました...!!
最後の問題で想定した出力が来た時、「っしゃ!」ってなりました。
ゴールに辿りつけない問題が出て悔しかったり、実は瞬殺できる方法があるのに
地道なコーディングをして拍子抜けしたりと、最後にして面白い回でしたw
~完走コメント~
回を追うごとにPythonの知識が少しずつ増えていき、楽しさも増していきました。
解くのに時間がかかるときでも、辛抱強く取り組めたのは良かったです。
この演習での経験を活かして卒業研究のクオリティを上げられたらと思います!