[解答]アルゴリズム問題学習5回
標準手順に従って問題を解く
手順6:関数
質問リスト
1. 15596号:整数n個和
2. 4673番:セルフサービス番号
1. 15596号:整数n個和
質問する
n個の整数を指定すると、n個の和を求める関数を作成します.
作成する関数は次のとおりです. Python 2, Python 3, PyPy, PyPy3: def solve(a: list) -> int
a:n個の整数を含むリスト(0≦a[i]≦1000000,1≦n≦300000)であり、ここでn個の整数は合計しなければならない
戻り値:aに含まれるn個の整数の和(整数) 🙋♀️ マイコード
質問する
セルフサービス番号は1949年にインドの数学者D.R.Kaprekarによって命名された.正の整数nについて、d(n)がnおよびnの各ビット数の関数を定義する.例えば、d(75)=75+7+5=87である.
正の整数nが与えられると、その数からn、d(n)、d(d(n)、d(d(d(n))、...無限数列を生成できます.
たとえば、33で始まると、次の数字は33+3+3=39、次の数字は39+3+9=51、次の数字は51+5+1=57となります.このようにして、次の数の列を生成できます.
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...
nをd(n)の生成者と呼ぶ.上の数列において、33は39の生成者、39は51の生成者、51は57の生成者である.生成者が1つより多い場合もあります.例えば、101には2つの構造関数(91および100)がある.
生成されていない数字を自動番号と呼びます.100未満のセルフサービス番号は全部で13個です.1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97
10000以下のセルフ・サービス番号を出力するプログラムを作成します.
入力
入力なし
しゅつりょく
10000以下の自己符号を行ごとに1つ追加する順序で出力します.
🙋♀️ マイコード
その後11が増えると思い、そのままコードを書きました.
でも違うようです.
リストを並べて、後ろの[:20]を印刷すると、違います.
それを反映した数列が必ずあると思い、探すかどうか悩んでいたら、急にわかった.
この問題の意図は何ですか.
私はこの問題を通じて何を知るべきですか.
この「関数」問題セットでは、最初の問題は簡単すぎるからです.defの使い方を身につけることです.
では、今回の問題は?
ターゲットはクラスのselfをどのように利用するかを知ることですよね?
最初は生成者法則も再帰関数のように結果値を再取得しなければならないからだ.
しかし,ここでは終了せず,これらの結果が適用されない差集がこの問題の正解である.
そのため、生成者の数列を求める. 10000セットのうちの1.で求めた数列から減算された差セットを求める. この2つのプロセスを経たコードを記述します.
この過程で、私は「以前推測した問題の意図」に基づいてクラスとself,init(書きたいと思っていたが、役に立たなかったので、勉強だけして、書かないで、勉強するので、メリットがあります!)を書きます.
🙋♀️ 再挑戦
手順6:関数
質問リスト
1. 15596号:整数n個和
2. 4673番:セルフサービス番号
1. 15596号:整数n個和
質問する
n個の整数を指定すると、n個の和を求める関数を作成します.
作成する関数は次のとおりです.
a:n個の整数を含むリスト(0≦a[i]≦1000000,1≦n≦300000)であり、ここでn個の整数は合計しなければならない
戻り値:aに含まれるn個の整数の和(整数)
def solve(a):
return sum(a)
2. 4673番:セルフサービス番号 質問する
セルフサービス番号は1949年にインドの数学者D.R.Kaprekarによって命名された.正の整数nについて、d(n)がnおよびnの各ビット数の関数を定義する.例えば、d(75)=75+7+5=87である.
正の整数nが与えられると、その数からn、d(n)、d(d(n)、d(d(d(n))、...無限数列を生成できます.
たとえば、33で始まると、次の数字は33+3+3=39、次の数字は39+3+9=51、次の数字は51+5+1=57となります.このようにして、次の数の列を生成できます.
33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...
nをd(n)の生成者と呼ぶ.上の数列において、33は39の生成者、39は51の生成者、51は57の生成者である.生成者が1つより多い場合もあります.例えば、101には2つの構造関数(91および100)がある.
生成されていない数字を自動番号と呼びます.100未満のセルフサービス番号は全部で13個です.1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97
10000以下のセルフ・サービス番号を出力するプログラムを作成します.
入力
入力なし
しゅつりょく
10000以下の自己符号を行ごとに1つ追加する順序で出力します.
🙋♀️ マイコード
cnt = round((10/2)+(9980/11))
i = -1
i_list = []
for _ in range(cnt):
if i < 8 :
i += 2
else :
i+= 11
i_list.append(i)
print(i_list[:20],sep='\n')
元々、自作番号ルールは10までに2を増やしていた.その後11が増えると思い、そのままコードを書きました.
でも違うようです.
リストを並べて、後ろの[:20]を印刷すると、違います.
それを反映した数列が必ずあると思い、探すかどうか悩んでいたら、急にわかった.
この問題の意図は何ですか.
私はこの問題を通じて何を知るべきですか.
この「関数」問題セットでは、最初の問題は簡単すぎるからです.defの使い方を身につけることです.
では、今回の問題は?
ターゲットはクラスのselfをどのように利用するかを知ることですよね?
最初は生成者法則も再帰関数のように結果値を再取得しなければならないからだ.
しかし,ここでは終了せず,これらの結果が適用されない差集がこの問題の正解である.
そのため、
この過程で、私は「以前推測した問題の意図」に基づいてクラスとself,init(書きたいと思っていたが、役に立たなかったので、勉強だけして、書かないで、勉強するので、メリットがあります!)を書きます.
🙋♀️ 再挑戦
s = set()
nn = set(range(1,10001))
def d(n):
num = n + sum(map(int,str(n)))
s.add(num)
for i in range(1,10001):
if d(i) not in nn :
print(i)
もっと短く/もっと早く挑戦したい!(速度もメモリも同じ...)def d(n):
num = n + sum(map(int,str(n)))
return num
nn = set(range(1,10001))
for i in range(1,10001):
nn.discard(d(i))
print(*nn,sep ='\n')
Reference
この問題について([解答]アルゴリズム問題学習5回), 我々は、より多くの情報をここで見つけました https://velog.io/@ohjiae/문제풀기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol