本文介绍了第一个分区的递归函数、斯特林数和切比雪夫多项式的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

所以我正在做家庭作业,我需要为分区、斯特林数(第一类和第二类)和切比雪夫多项式创建递归函数.我的程序应该能够让用户输入一个正整数 n,然后创建名为 Partitions.txt、Stirling1.txt、Stirling2.txt 和 Chebyshev.txt 的文件,这些文件创建了一个包含所有值 f(k,m) 的表对于1<=k<=n和1<=m<=n.我正在努力开始这项任务,尽管我一直在做研究并试图弄清楚,但我仍然觉得我对它一无所知.如果有人可以帮助我,我将不胜感激!谢谢!

So I'm working on a homework assignment and I need to create recursive functions for partitions, Stirling numbers(first and second kind), and Chebyshev polynomials of the first. My program should be able to have a user input a positive integer n, and then create files named Partitions.txt, Stirling1.txt, Stirling2.txt, and Chebyshev.txt, that creates a table of all values f(k,m) for 1<=k<=n and 1<=m<=n. I'm struggling just to start off the assignment and feel like I have no understanding of it even though I've been doing research and trying to figure it out. If someone can help me out, I'd really appreciate it! Thank you!

    #include <iostream>
    #include <vector>
    #include "OutputFile.h"

    using namespace std;
    using namespace OutputStream;


    int firstKindStirling();
    vector<vector<int> > getPartitions(int number, int maxElement);

    int main() {

        cout << "Welcome! Please input a number m:";
        int m;
        cin>>m;


        OFile fout("Partitions.txt");

        return 0;
    }

    vector<vector<int> > getPartitions(int number, int maxElement)
    {
        if (number < 1)
            return vector<vector<int>>();

       vector<vector<int>> partitions;

        if (number <= maxElement)
            partitions.push_back(number); //for some reason this doesn't want to work. Not sure what I'm missing here.

        for (int i = number - maxElement; i < number; ++i)
        {
            // (recursively) get the partitions of `i`, with elements no larger than `n - i`
            auto partitionsForI = getPartitions(i, number - i);

            // add `n - i` to the front of all of those partitions
            for(vector<int>& partition : partitionsForI)
            {
                partition.insert(partition.begin(), number - i);
            }

            // add these new partitions to our list.
            partitions.insert(partitions.end(), partitionsForI.begin(), partitionsForI.end());
        }
        return partitions;
    }

    int firstKindStirling(int n, int k)
    {
        if (n == 0 && k == 0) return 1;
        else if (n == 0 || k == 0) return 0;
        else return -(n-1) * firstKindStirling(n-1, k) + firstKindStirling(n-1, k-1);
    }

这是我的输出 .h 文件

And here's my Output .h file

    #ifndef OUTPUT_H
    #define OUTPUT_H

    #include <fstream>
    #include <string>
    #include <vector>
    #include <iostream>
    #include <sys/stat.h>
    #include <sstream>
    #include <memory>

    namespace OutputStream {

        class OFile {
            std::ofstream file;
        public:

            OFile(std::string filename, size_t output_precision = 10) {

                file.open(filename);
                if(file.fail()) throw std::runtime_error("Error: cannot open file");

                file.precision(output_precision);

            };

            /*
            OFile& operator<<(int x) {
                file<<x;
                return *this;
            }
            */

            /*
            OFile& operator<<(const Point2D& p) {
                file<<p;
                return *this;
            }
            */

            OFile& operator<<(const std::vector<int>& v) {

                for(auto x : v) file<<x<<std::endl;
                return *this;
            }


            template<typename T>
            OFile& operator<<(const T& p) {
                file << p;
                return *this;
            }


            ~OFile() { file.close(); };

        };


        // Strongly enumerate type
        enum class FileType { Input, Output, SafeOutput };

        // Partial Template Specialization
        template<FileType> class File;

        template<>
        class File < FileType::Input > {
        public:
            File( const std::string& filename ) : fin(filename) {

                if(fin.fail()) throw std::runtime_error("Error opening file: "+filename);
            };

            /** ...

            IFile& allows for syntax like
            fin>>a>>b>>c;
            */
            File& operator>>(int& a) {
                fin>>a;
                return *this;
            }

            /**...*/
            operator bool() {
                return !(fin.fail());
            }

            operator std::string() {
                return "Active";
            }

            // operator [data type]() {
                // code here
            //  return [object of type data type];
            // }

            friend File& getline( File& fin, std::string& line) {
                getline( fin.fin, line);
                return fin;
            }

            friend File& getrow( File& fin, std::vector<int>& rows);
            friend File& getmatrix( File& fin, std::vector< std::vector<int> >& table);

            ~File() { fin.close(); };
        private:
            std::ifstream fin;
        };

        template<>
        class File < FileType::Output > {
            std::ofstream file;
        public:

            File(std::string filename, size_t output_precision = 10) {

                file.open(filename);
                if(file.fail()) throw std::runtime_error("Error: cannot open file");

                file.precision(output_precision);

            };

            /*
            OFile& operator<<(int x) {
                file<<x;
                return *this;
            }
            */

            /*
            OFile& operator<<(const Point2D& p) {
                file<<p;
                return *this;
            }
            */

            File& operator<<(const std::vector<int>& v) {

                for(auto x : v) file<<x<<std::endl;
                return *this;
            }


            template<typename T>
            File& operator<<(const T& p) {
                file << p;
                return *this;
            }


            ~File() { file.close(); };

        };

    }

    #endif

推荐答案

这真的是几个问题合二为一,所以我会分几个部分来解决.

This is really several questions in one, so I will take it in parts.

这可能是这些任务中最难的,但如果你分解它,它是相当可行的.

This is probably the hardest of these tasks, but it's pretty doable if you break it down.

一个数 n 的所有分区是什么?每个分区中的第一个数字必须介于 1 和 n 之间.由于我们不关心顺序,让我们始终按降序排列数字.所以第一个分区列表看起来像这样:

What are all the partitions of a number n? The first number in each partition must be between 1 and n. Since we don't care about order, let's just always keep the numbers in descending order. So the first list of partitions looks something like this:

  • {n}
  • {n-1, 1}
  • {n-2, 2}, {n - 2, 1, 1}
  • {n-3, 3}, {n - 3, 2, 1}, {n - 3, 1, 1, 1}
  • ...
  • {1, 1, ..., 1}
  • {n}
  • {n-1, 1}
  • {n-2, 2}, {n - 2, 1, 1}
  • {n-3, 3}, {n - 3, 2, 1}, {n - 3, 1, 1, 1}
  • ...
  • {1, 1, ..., 1}

等等!我们可以更简单地说.那只是

But wait! We can say that more simply. That's just

  • [以n开头的分区集合]
  • [以 n - 1 开头的分区集]
  • [以 n - 2 开头的分区集]
  • ...
  • [以1开头的分区集]

对于 1 和 n 之间的所有 i,这实际上只是以 n - i 开头的所有分区.因此,如果我们能找到一种方法来获取每个 i 的每组分区,我们就可以简化事情.

Which is really just all the partitions starting with n - i for all i between 1 and n. So, if we can find a way to get each group of partitions for each i, we can simplify things.

我们怎么做?好吧,如果我们考虑一下,我们可以意识到我们可以很容易地获得以 n - i 开头的每个分区.每个分区只是 n - i 后跟一种方法来获取加起来为 i 的数字......这正是分区的含义,所以我们找到了我们的递归案例!我们通过获取 n - i 后跟 i 的每个分区来获得我们所有的分区.

How might we do that? Well, if we think about it, we can realize that we can get every partition which starts with n - i pretty easily. Each partition is just n - i followed by a way to get numbers which add up to i... which is exactly what a partition is, so we've found our recursive case! We get all of our partitions by getting n - i followed by each of the partitions of i.

现在我们只需要一个基本案例.这很简单:我们可以将零的分区定义为空集.

Now we just need a base case. That's pretty simple: we can just define the partitions for zero to be the empty set.

这看起来像什么?

vector<vector<int>> getPartitions(int number, int maxElement)
{
    if (number < 1) return vector<vector<int>>();
    vector<vector<int>> partitions;

    if (number <= maxElement) partitions.push_back({number});

    for (int i = number - maxElement; i < number; ++i)
    {
        // (recursively) get the partitions of `i`, with elements no larger than `n - i`
        auto partitionsForI = getPartitions(i, number - i);

        // add `n - i` to the front of all of those partitions
        for(vector<int>& partition : partitionsForI)
        {
            partition.insert(partition.begin(), number - i);
        }

        // add these new partitions to our list.
        partitions.insert(partitions.end(), partitionsForI.begin(), partitionsForI.end());
    }
    return partitions;
}

斯特林数

这些非常相似.如果您查看它们各自的维基百科页面,您可以找到每种类型的递归关系:

Stirling Numbers

These are pretty similar. If you look at their respective Wikipedia pages, you can find recurrence relations for each kind:

s1(n, k) = -(n - 1) * s1(n - 1, k) + s1(n - 1, k - 1)

第二类

S2(n, k) = k * S2(n - 1, k) + S2(n - 1, k - 1)

并且它们具有相同的基本情况:S(0, 0) = 1, S(n, 0) = 0S(0,n) = 0.

And they have the same base cases: S(0, 0) = 1, S(n, 0) = 0 and S(0, n) = 0.

所以你可以定义一个函数来计算它们,如下所示:

So you could define a function to calculate them something like this:

int firstKindStirling(int n, int k)
{
    if (n == 0 && k == 0) return 1;
    else if (n == 0 || k == 0) return 0;
    else return -(n-1) * firstKindStirling(n-1, k) + firstKindStirling(n-1, k-1);
}

第二种看起来非常相似.

and the one for the second kind would look very similar to that.

目前还不清楚这里的要求是什么.我将假设它是一次评估一个,而不是提出一些扩展的表示.它与斯特林数几乎相同.

It's not totally clear what the requirement is here. I'm going to assume it's to evaluate one at a point, not to come up with some expanded representation. It goes pretty much the same as the Stirling Numbers.

同样,维基百科页面有一个递归关系:

Again, the wikipedia page has a recurrence relation:

chebyshev(0, x) = 1
chebyshev(1, x) = x
chebyshev(n, x) = 2 * x * chebyshev(n-1, x)  -  chebyshev(n-2, x)

我假设您可以弄清楚如何将其变成一个函数.(提示:基本上只需将那些左侧变成 if 语句,类似于上面的示例.)

I assume you can figure out how to make that into a function. (Hint: basically all it takes is turning those left-hand sides into if statements, similar to the example above.)

这篇关于第一个分区的递归函数、斯特林数和切比雪夫多项式的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-27 16:28