Рекурсивные функции для разбиений, перемешивающих чисел и полиномов Чебышева первого

Поэтому я работаю над домашним заданием, и мне нужно создать рекурсивные функции для разделов, чисел Стирлинга (первого и второго рода) и полиномов Чебышева первого. Моя программа должна иметь возможность, чтобы пользователь ввел положительное целое число n, а затем создал файлы с именами Partitions.txt, Stirling1.txt, Stirling2.txt и Chebyshev.txt, которые создают таблицу со всеми значениями f (k, m) за 1<= к<= n и 1<= м<= П. Я изо всех сил пытаюсь начать задание и чувствую, что не понимаю его, хотя я занимаюсь исследованиями и пытаюсь понять это. Если кто-то может мне помочь, я действительно ценю это! Спасибо!

    #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

    #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

0

Решение

Это действительно несколько вопросов в одном, поэтому я расскажу об этом по частям.

Это, вероятно, самая трудная из этих задач, но она вполне выполнима, если вы ее сломаете.

Каковы все разделы числа n? Первое число в каждом разделе должно быть от 1 до n. Поскольку нас не заботит порядок, давайте всегда будем держать числа в порядке убывания. Итак, первый список разделов выглядит примерно так:

  • {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}

Но ждать! Мы можем сказать это проще. Это просто

  • [the set of partitions starting with n]
  • [the set of partitions starting with n - 1]
  • [the set of partitions starting with n - 2]
  • [the set of partitions starting with 1]

Что на самом деле просто все разделы, начинающиеся с n - i для всех i между 1 и n, Итак, если мы сможем найти способ получить каждую группу разделов для каждого iМы можем упростить вещи.

Как мы можем это сделать? Ну, если мы думаем об этом, мы можем понять, что мы можем получить каждый раздел, который начинается с n - i довольно легко Каждый раздел просто n - i с последующим способом получить номера, которые складываются в i… именно это и есть раздел, поэтому мы нашли наш рекурсивный случай! Мы получаем все наши разделы, получая n - i с последующим каждым из разделов i,

Теперь нам просто нужен базовый вариант. Это довольно просто: мы можем просто определить разделы для нуля как пустое множество.

Собираем все вместе

Так как же это выглядит?

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;
}

Это очень похоже. Если вы посмотрите на их соответствующие страницы в Википедии, вы можете найти повторяющиеся отношения для каждого вида:

Первый вид

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) = 0 а также S(0, n) = 0,

Таким образом, вы можете определить функцию для их вычисления примерно так:

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);
}

и тот для второго вида выглядел бы очень похожим на это.

Не совсем понятно, какое здесь требование. Я собираюсь предположить, что это оценивать один за один раз, а не придумывать какое-то расширенное представление. Это похоже на число Стирлинга.

Снова, страница википедии имеет рекуррентное отношение:

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

Я полагаю, вы можете понять, как превратить это в функцию. (Подсказка: в основном, все, что нужно, это превратить эти левые части в операторы if, как в примере выше.)

2

Другие решения


По вопросам рекламы [email protected]