[白俊]2661号:良好な数列/Python/遡及
良数
質問する
数字1,2,3のみからなる数列があります.任意の長さの隣接する2つの部分の数列が同じである場合、その数列を悪数列と呼ぶ.そうでなければ、数列は良い数列です.
次は悪い数列の例です.
33
32121323
123123213
次は良い数列の例です.
2
32
32123
1232123
長さNの好数列をNビット整数として、その中で最も小数を表す数列を求めるプログラムを作成します.例えば、1213121および212312はいずれも良い数列であるが、小数を表す数列は1213121である.
入力
入力は1つの数字Nからなる.Nは1以上80以下である.
しゅつりょく
1行目に1、2、3の長さNのみの好数列には、最小数を表す数列のみが出力される.数列の1,2,3の間にスペースを残さない.
私の答え
def getResult(idx):
global isExit
if isExit: return
if idx >= n:
# 정답 출력
print(''.join(result))
# 첫번째 반환되는 수열이 가장 작으므로 종료하도록 설정
isExit = True
else:
for i in ['1', '2', '3']:
result[idx] = i
# 현재 채워진 인덱스까지 좋은 수열인지 확인, 좋은 수열이면 다음 숫자 찾기
if isGood(result[:idx + 1]):
getResult(idx + 1)
# 좋은 수열인지 판단하는 함수
def isGood(nums):
# 1부터 수열 길이의 절반까지 범위를 늘려가면서 구간 비교
for tkn_size in range(1, len(nums) // 2 + 1):
if nums[-tkn_size:] == nums[-(2 * tkn_size):-tkn_size]:
return False
return True
n = int(input())
result = [0] * n
isExit = False
getResult(0)
Reference
この問題について([白俊]2661号:良好な数列/Python/遡及), 我々は、より多くの情報をここで見つけました https://velog.io/@dhelee/일일코테-Day9テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol