Поэтому я работаю над домашним заданием, и мне нужно создать рекурсивные функции для разделов, чисел Стирлинга (первого и второго рода) и полиномов Чебышева первого. Моя программа должна иметь возможность, чтобы пользователь ввел положительное целое число 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
Это действительно несколько вопросов в одном, поэтому я расскажу об этом по частям.
Это, вероятно, самая трудная из этих задач, но она вполне выполнима, если вы ее сломаете.
Каковы все разделы числа 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, как в примере выше.)