すいていすうれつ

6282 ワード
python アルゴリズム#アルゴリズム# テキストリンク
作成日:2022年2月6日午後7:59

インプリメンテーションコード

# 수열 추측하기
import sys
sys.stdin = open("input.txt", "rt")

def DFS(L, sum):
    if L == n and sum == f:
        for x in p:
            print(x, end = ' ')
        sys.exit(0)
    else:
        for i in range(1, n+1):
            if ch[i] == 0:
                ch[i] = 1
                p[L] = i
                DFS(L+1, sum+(p[L]*b[L]))
                ch[i] = 0

if __name__ == "__main__":
    n, f = map(int, input().split())
    p = [0] * n
    b = [1] * n
    ch = [0] * (n+1)

    # 이항 게수
    for i in range(1, n):
        b[i] = b[i-1] * (n-i) // i

    DFS(0, 0)
  • n=4,k=16規格を例にとると、可能な限りすべてのシーケンスをチェックする必要があります.(例えば,[1,2,3,4],[1,3,2,4],...,[4,3,1,2])
  • しかし、チェックの仕方では、上のシーケンスを全部2つ加えてkであるかどうかを確認するのではなく、特定のルールがあります.
  • がこの係数です.nを4の基準とし,この係数は[1,3,1]であった.この数にそれぞれ答え[3,1,2,4]を乗じてk値16を求める.
    • したがって、
  • は、bリストに与えられたnに適合する2つの係数値を保存し、ループ再帰関数によって生成されたすべてのシーケンスの個数にb配列をそれぞれ乗じ、加算された値がkに等しい場合、整数であるため、プログラムを出力して終了する.
    • 組み合わせを求める
    シーケンスを求める