1

入力「N」が与えられました。次に追加される数がこれまでに追加された最大数より最大で1多いように、1から始まる長さNのリストの数を見つける必要があります。例えば、

N = 3、可能なリスト=>（111、112、121、122、123）、[113、または131は、リストに「3」を追加している間は不可能であり、リストに存在する最大数は「1」になります。 、したがって、追加できるのは1つまたは2つだけです]。

N = 4の場合、リスト1213が可能です。3を追加すると、リストの最大数は「2」になるため、3を追加できます。

問題は、与えられた入力「N」に対して可能なそのようなリストの数を数えることです。

私のコードは：-

public static void Main(string[] args)
        {
            var noOfTestCases = Convert.ToInt32(Console.ReadLine());
            var listOfOutput = new List<long>();
            for (int i = 0; i < noOfTestCases; i++)
            {
                var requiredSize = Convert.ToInt64(Console.ReadLine());
                long result;
                const long listCount = 1;
                const long listMaxTillNow = 1;
                if (requiredSize < 3)
                    result = requiredSize;
                else
                {
                    SeqCount.Add(requiredSize, 0);
                    AddElementToList(requiredSize, listCount, listMaxTillNow);
                    result = SeqCount[requiredSize];
                }
                listOfOutput.Add(result);
            }
            foreach (var i in listOfOutput)
            {
                Console.WriteLine(i);
            }
        }

        private static Dictionary<long, long> SeqCount = new Dictionary<long, long>();

        private static void AddElementToList(long requiredSize, long listCount, long listMaxTillNow)
        {
            if (listCount == requiredSize)
            {
                SeqCount[requiredSize] = SeqCount[requiredSize] + 1;
                return;
            }
            var listMaxTillNowNew = listMaxTillNow + 1;
            for(var i = listMaxTillNowNew; i > 0; i--)
            {
                AddElementToList(requiredSize, listCount + 1,
                    i == listMaxTillNowNew ? listMaxTillNowNew : listMaxTillNow);
            }
            return;
        }

これはブルートフォース方式です。問題に最適なアルゴリズムは何か知りたいですか？PS：そのようなリストの数だけを知りたいので、すべてのリストを作成する必要はないと確信しています。（コードでのやり方）私はアルゴリズムがまったく得意ではないので、長い質問を許してください。

4

2 に答える 2

3

この問題は、動的計画問題の典型的な例です。

関数dp（k、m）を、最大数がmである長さkのリストの数として定義すると、漸化式が得られます。

dp(1, 1) = 1
dp(1, m) = 0, for m > 1
dp(k, m) = dp(k-1, m) * m + dp(k-1, m-1)

実際、長さ1のリストは1つだけで、その最大要素は1です。最大要素mで長さkのリストを作成する場合、max = mの（k-1）リストのいずれかを取得して追加できます。 1または2または....またはm。または、最大要素m-1の（k-1）リストを取得してmを追加することもできます。最大要素がm-1未満の（k-1）リストを取得する場合、ルールにより、要素を1つだけ追加しても最大mを取得することはできません。

で動的計画法を使用して、すべてのk = 1、...、Nおよびm = 1、...、N + 1のdp（k、m）を計算できます。O(N^2)そうすると、質問に対する答えは次のようになります。

dp(N,1) + dp(N,2) + ... + dp(N,N+1)

したがって、アルゴリズムはO(N^2)です。

C＃でのdp計算の実装については、以下を参照してください。

        int[] arr = new int[N + 2];
        for (int m = 1; m < N + 2; m++)
            arr[m] = 0;
        arr[1] = 1;

        int[] newArr = new int[N + 2];
        int[] tmp;
        for (int k = 1; k < N; k++)
        {
            for (int m = 1; m < N + 2; m++)
                newArr[m] = arr[m] * m + arr[m - 1];
            tmp = arr;
            arr = newArr;
            newArr = tmp;
        }

        int answer = 0;strong text
        for (int m = 1; m < N + 2; m++)
            answer += arr[m];

        Console.WriteLine("The answer for " + N + " is " + answer);
于 2012-04-07T19:56:59.697 に答える
0

さて、私は今日の午後（本当に！）火事に邪魔されましたが、FWIW、これが私の貢献です：

    /*
     * Counts the number of possible integer list on langth N, with the
     * property that no integer in a list(starting with one) may be more
     * than one greater than the greatest integer preceeding it in the list.
     * 
     * I am calling this "Semi-Factorial" since it  is somewhat similar to
     * the factorial function and its constituent integer combinations.
     */
    public int SemiFactorial(int N)
    {
        int sumCounts = 0;

        // get a list of the counts of all valid lists of length N,
        //whose maximum integer is listCounts[maxInt].
        List<int> listCounts = SemiFactorialCounts(N);

        for (int maxInt = 1; maxInt <= N; maxInt++)
        {
            // Get the number of lists, of length N-1 whose maximum integer
            //is (maxInt):
            int maxIntCnt = listCounts[maxInt];

            // just sum them up
            sumCounts += maxIntCnt;
        }

        return sumCounts;
    }

    // Returns a list of the counts of all valid lists of length N, and
    //whose maximum integer is [i], where [i] is also its index in this
    //returned list. (0 is not used).
    public List<int> SemiFactorialCounts(int N)
    {
        List<int> cnts;
        if (N == 0)
        {
            // no valid lists, 
            cnts = new List<int>();
            // (zero isn't used)
            cnts.Add(0);
        }
        else if (N == 1)
            {
                // the only valid list is {1}, 
                cnts = new List<int>();
                // (zero isn't used)
                cnts.Add(0);
                //so that's one list of length 1
                cnts.Add(1);
            }
            else
            {
            // start with the maxInt counts of lists whose length is N-1:
            cnts = SemiFactorialCounts(N - 1);

            // add an entry for (N)
            cnts.Add(0);

            // (reverse order because we overwrite the list using values
            // from the next lower index.)
            for (int K = N; K > 0; K--) 
            {
                // The number of lists of length N and maxInt K { SF(N,K) }
                // Equals K times # of lists one shorter, but same maxInt,
                // Plus, the number of lists one shorter with maxInt-1.
                cnts[K] = K * cnts[K] + cnts[K - 1];
            }
        }

        return cnts;
    }

他のものとかなり似ています。これを「古典的な動的計画法」とは言いませんが、単に「古典的な再帰」とは呼びません。

于 2012-04-07T21:26:34.350 に答える