Introduction

Summary

How to determine the analytical formula? The original undetermined coefficient method not only has small scalability, but also has a large amount of calculation, and it performs poorly in computer science design operations. The Lagrangian interpolation method can solve this problem. This article first introduces the Lagrangian interpolation method, and explores the process of using the Lagrange interpolation method to solve the problem. It discusses the application of Lagrangian interpolation in the four aspects of basic function properties, factorization, proof of algebraic identities, and finding the relationship between the serial numbers and numerical values ​​of several ordered and regular numbers.

Symbol Convention

1. $$$\prod$$$ means accumulative multiplication operation, generally its subscript will be used as the condition of accumulative multiplication;

2. $$$\sum\limits^n_{i=1}i$$$ means $$$1+2+3+\cdots+n$$$;

3. $$$f(k)$$$ represents the value of the function of $$$x$$$ when $$$x=k$$$;

4. $$$y=f(x)$$$ means that $$$y$$$ is a function of $$$x$$$.

Source of the problem

In class, the teacher talked about using the method of undetermined coefficients to find the analytical formula of a function. If it is a linear function, set it to the form of $$$f(x)=y=kx+b$$$, and the result can be obtained after substituting two sets of values. For higher power functions, the undetermined coefficient method is also feasible, but the increase in the number of elements in the solution equations makes the undetermined coefficient method lose its original simplicity. Therefore, we will discuss how to determine the analytical expression of a function in combination with polynomials. Let's first study how many points on the graph of a given function, we can determine a unique function. The functions explored here are all polynomial functions, that is, the functions are polynomials.

Lemma

$$$n+1$$$ points determine a polynomial function of degree $$$n$$$.

Proof

We consider the most primitive method of undetermined coefficients. Suppose a polynomial function of degree $$$n$$$ $$$y=f(x)=\sum\limits_{i=0}^na_ix^i$$$ is the required function, and we finally have the sum in the equation system composed of the undetermined coefficient method A system of equations with the same number of a$. Therefore, it takes $$$n+1$$$ equations to solve all $$$a$$$.

Then we will give $$$n$$$ points below and ask to determine a polynomial function of degree $$$n-1$$$.

Questions raised

Given $$$n$$$ points on the function graph $$$P_i(x_i,y_i)(i=1,2,\cdots,n)$$$, at most $$$n-1$$$ degree polynomials passing through these $$$n$$$ points The function is set to $$$y=f(x)=\sum\limits_{i=0}^{n-1}a_ix^i$$$, and find: (1) When $$$x=k$$$, the value of $$$y$$$; (2) Find the function expression of $$$y$$$ and $$$x$$$.

Problem solving

The undetermined coefficient method is indeed a method, but it is too cumbersome. Even if it is solved in a computer, the asymptotic function of the time complexity is $$$\Theta(n^3)$$$, which is not efficient. So, is there a more efficient method? Below we introduce Lagrangian interpolation and its application.

Suppose $$$y$$$ is the required function of $$$x$$$ (its image is represented by a black line), and we use $$$P_i(x_i,y_i)$$$ to make the perpendicular line of the $$$x$$$ axis intersect the $$$x$$$ axis at $$$H_i(x_i, 0)$$$, for each $$$i$$$, construct the following function $$$g_i(x)$$$ (the image is represented by a colored line) so that its image passes through all the points $$$H$$$ except $$$H_i$$$ and passes Click $$$P_i$$$.

If we consider describing such a function, we can find that the value of the function $$$g_i(x)$$$ at $$$x_i$$$ is $$$g_i(x_i)=y_i$$$, and the other values ​​at $$$x_j(i\neq j)$$$ $$$g_i(x_j)=0$$$, so we can define the function $$$g_i(x)$$$ like this:

It is easy to construct its analytical formula

among them

It is called the interpolation basis function, which satisfies $$$\ell_i(x_i)=1$$$, $$$\ell_i(x_j)(i\neq j)=0$$$.

Theorem

The final function $$$y=f(x)=\sum\limits_{i=0}^{n-1}a_ix^i$$$ is the sum of all $$$g_i(x)$$$. Formally,

Proof

Since the image of $$$g_i(x)$$$ passes $$$P_i$$$, and the others pass $$$H_j(i\neq j)$$$, the function image of the sum of all $$$z_i$$$ must pass all $$$P_i$$$, and the final function is determined .

In the process of solving the above problems, we also got the Lagrangian formula, that is, the Lagrangian interpolation method is used to express the form of the function. This will be very common in the following applications. It is also a common method to prove algebraic identities by comparing the coefficients of the same term in different representations of functions (using Lagrange formula here).

Lagrange formula

That is the $$$(*)$$$ formula.

Description

All of the above $$$i,j=1,2,\cdots,n$$$ and $$$i\neq j$$$.

Lagrangian interpolation and the application of Lagrangian formula

We can extend Lagrangian interpolation to other mathematical applications, so that it is not only used to find functional analytical expressions. For example, the following factorization problem:

Example

Decompose the factor $$$a^2(m-b)(m-c)(c-b)+b^2(m-c)(m-a)(a-c)+c^2(m-a)(m-b)(b-a)$$$.

Analysis

Observe the form of factorization and find that it is a bit like the form on the right side of the Lagrangian formula of $$$f(x)=x^2$$$. Consider using the Lagrangian formula.

Answer

Note that by the Lagrangian interpolation method, let $$$a, b, c$$$ be the abscissa of a given point $$$x_1, x_2, x_3$$$, then the ordinate of the given point $$$y_1, y_2, y_3$$$ is $$$f( a),f(b),f(c)$$$, $$$y=f(x)=x^2$$$ are the functions on the left side of the Lagrange formula, then

So there is

In the above formula, let $$$x=m$$$ to get

The following is an example of using the Lagrange formula to prove the effect of algebraic identities by comparing the coefficients of a certain term.

Example

(Olympic classics and algebra problems in Olympic mathematics) $$$^2$$$ Let $$$a,b,c$$$ be the three sides of non-isosceles $$$\triangle ABC$$$, and $$$S$$$ is the area, verify: $$$\dfrac{a^3}{(a-b)(a-c)}+\dfrac{b^3}{(b-c)(b-a)}+\dfrac{c^3}{(c-a)(c-b)}>2\times \sqrt{\sqrt{3}^3}\sqrt{S}$$$.

Analysis

First deal with the denominators of the fractions on the left side of the inequality, and observe that it is in the form of an interpolation basis function, so we can construct a function so that the elements on the right side of the Lagrangian formula are the content on the left side of the inequality sign, so we consider constructing a quadratic function . Furthermore, it can be found that the coefficient of $$$x^2$$$ in the Lagrangian interpolation representation of the quadratic function $$$y=f(x)=x^3-(x-a)(x-b)(x-c)$$$ is exactly on the left side of the inequality sign Formula, which is equal to $$$a+b+c$$$, so the Helen formula is considered. The result can be obtained by using Helen's formula.

Proof

Consider the following function $$$y=f(x)=x^3-(x-a)(x-b)(x-c)$$$, consider setting $$$a,b,c$$$ as the abscissa of a given point $$$x_1,x_2,x_3$$$ , The ordinate $$$y_1, y_2, y_3$$$ of the given point are respectively $$$a^3, b^3, c^3$$$. Consider the Lagrangian representation of the function, that is, the sum of all the above $$$g_i(x)$$$, we can get

Compare the coefficient of $$$x^2$$$ to get

So the original question is transformed into proof $$$a+b+c<2\times \sqrt{\sqrt{3}^3}\sqrt{S}$$$. The following is a geometric problem, the proof is omitted.

The following is an example of using the Lagrangian formula to find the formula of $$$a_i$$$ for any $$$n$$$ given $$$a_i$$$.

Example

Given that $$$a_1=14,a_2=58,a_3=166,a_4=368$$$, for $$$n=1,2,3,4$$$, try the polynomial with the highest degree of 3 containing $$$n$$$ to express $$$a_n$$$ .

Answer

Consider setting the general term formula as $$$a_n=f(n)$$$, then $$$f(1)=14, f(2)=58, f(3)=166, f(4)=368$$$.

The following regards $$$1,2,3,4$$$ as the abscissa of a given point $$$x_1,\dots,x_4$$$, and $$$14,58,166,368$$$ as the ordinate of a given point $$$y_1,\cdots,y_4$$$, then

The following example is about discussing the range of a certain point value of a polynomial.

Example

Given the function $$$f(x)=x^3+px^2+qx+r$$$, where $$$p,q,r$$$ are real numbers. Proof: One of the $$$|f(1)|,|f(2)|,|f(3)|,|f(4)|$$$ must be no less than $$$\dfrac{3}{4}$$$.

Analysis

Consider the Lagrangian formula of the polynomial function, take $$$x_1, x_2, x_3, x_4$$$ as $$$1,2,3,4$$$ respectively; take $$$y_1, y_2, y_3, y_4$$$ respectively to the value of the corresponding function, and finally Then consider the coefficient of $$$x^3$$$.

Proof

Take $$$x_1,x_2,x_3,x_4$$$ as $$$1,2,3,4$$$ respectively; take $$$y_1,y_2,y_3,y_4$$$ respectively as the value of the corresponding function, which is obtained by Lagrangian formula

Comparing the coefficients around $$$x^3$$$ in the above formula, we can get

So

The following example is still about the range of a point value of the polynomial.

Example

The known function $$$f(x)=ax^3+bx^2+cx+d$$$, if $$$p\leq f(-1)\leq q,p\leq f(1)\leq r,q\leq f(2)\leq s,t\leq f(3)\leq p$$$, use $$$p,q,r,s,t$$$ to denote the value range of $$$f(4)$$$.

Analysis

Considering that for the cubic polynomial function, $$$4$$$ corresponding value ranges are given, and the conditions required for Lagrangian interpolation are met, you can take $$$x_1=-1,x_2=1,x_3=2,x_4=3$$$ , So we can use Lagrangian interpolation to express $$$f(4)$$$ (see the question), and then according to the value range of the four function values, we can get that when $$$x=4$$$, The value range of $$$y$$$.

Answer

Take $$$x_i=-1,1,2,3$$$, which can be obtained by Lagrangian formula

So $$$\dfrac{9}{4}p-5q+\dfrac{5}{4}t\leq f(4)\leq -\dfrac{1}{4}q+\dfrac{5}{2}r- 5s+\dfrac{5}{4}p$$$.

References

[1] OI Wiki. Lagrangian interpolation [EB/OL].

[2] Shen Wenxuan, Zhang Yao, Leng Gangsong. Olympiad Classics · Algebraic Problems in Olympic Mathematics [M]. Changsha: Hunan Normal University Press, 2009.5: 322.

If you have some more applications of the Lagrange Interpolation in Informatics or Mathematics, please comment here and make this post better.

Thanks to ghoshsai5000 for the two sample questions!

I would like to share two CodeForces problems which use Interpolation in their solutions

• Cowmpany Compensation
• Faulhaberg's Sums

How to estimate the running time of an algorithm based on the time complexity of an algorithm and the value range of some variables?

Is it possible that there are some formulas to calculate the running time of the algorithm based on some hardware configurations and the above information?

Or is it possible that there is a table (referring to the hardware configuration of the general evaluation machine) to judge?

For example: $$$O(\log n)$$$ can pass when $$$n≤10^{13}$$$, $$$O(n)$$$ can pass when $$$n≤$$$___... Can the above ideas realize the problems raised above?

If you can, please advise the specific method; if not, please enlighten me.

Thank you!

UPD: There is another idea I don't know if it is feasible: get the time for the hardware to execute a statement, and then directly multiply it by the time complexity of the algorithm to get the final result? This method should work as long as the average execution time of a statement is known.

UPD: UPD: I now know that the normal evaluation machine can perform $$$10^7 \sim 10^8$$$ operations per second. The problem is solved like this! Thank you!

My code is here:

#include <bits/stdc++.h>

using namespace std;

int r, g, b, r1, g1, b1;
int R[1000], G[1000], B[1000], ans;

namespace luosw {
namespace IO {
    template < typename T >
    inline T read() {
        T    ret = 0, f = 1;
        char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-')
                f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
            ret = ret * 10 + ch - '0', ch = getchar();
        return ret * f;
    }
    template < typename T >
    void write(T x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        T y = 10, len = 1;
        while (y <= x) {
            y *= 10;
            len++;
        }
        while (len--) {
            y /= 10;
            putchar(x / y + 48);
            x %= y;
        }
    }
    template < typename T >
    void write(T x, bool flag) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        T y = 10, len = 1;
        while (y <= x) {
            y *= 10;
            len++;
        }
        while (len--) {
            y /= 10;
            putchar(x / y + 48);
            x %= y;
        }
        if (flag)
            putchar('\n');
    }
}  // namespace IO
namespace tools {
    template < typename T >
    T cmax(T a, T b) {
        return max(a, b);
    }
    template < typename T >
    T cmin(T a, T b) {
        return min(a, b);
    }
    template < typename T >
    T cgcd(T a, T b) {
        return __gcd(a, b);
    }
    template < typename T >
    T clcm(T a, T b) {
        return a * b / cgcd(a, b);
    }
}  // namespace tools
}  // namespace luosw
bool cmp(int a, int b) {
    return a > b;
}
int max(int a, int b, int c) {
    if (a > b && a > c)
        return a;
    if (b > a && b > c)
        return b;
    if (c > a && c > b)
        return c;
}
bool check() {
    if (r == r1 - 1 && g == g1 - 1)
        return 0;
    if (g == g1 - 1 && b == b1 - 1)
        return 0;
    if (r == r1 - 1 && b == b1 - 1)
        return 0;
    return 1;
}
signed main() {
    cin >> r >> g >> b;
    memset(R, 0, sizeof(R));
    memset(G, 0, sizeof(G));
    memset(B, 0, sizeof(B));
    for (int i = 0; i < r; i++) {
        cin >> R[i];
    }
    for (int i = 0; i < g; i++) {
        cin >> G[i];
    }
    for (int i = 0; i < b; i++) {
        cin >> B[i];
    }
    sort(R, R + r + 5, cmp);
    sort(B, B + b + 5, cmp);
    sort(G, G + g + 5, cmp);
    while (check()) {
        if (max(R[r1], G[g1], B[b1]) == R[r1]) {
            if (max(G[g1], B[b1]) == G[g1]) {
                ans += R[r1++] * G[g1++];
            }
            else {
                ans += R[r1++] * B[b1++];
            }
        }
        else if (max(G[g1], B[b1]) == G[g1]) {
            if (max(R[g1], B[b1]) == R[g1]) {
                ans += R[r1++] * G[g1++];
            }
            else {
                ans += G[g1++] * B[b1++];
            }
        }
        else {
            if (max(R[g1], G[b1]) == R[g1]) {
                ans += R[r1++] * B[b1++];
            }
            else {
                ans += G[g1++] * B[b1++];
            }
        }
    }
    cout << ans << endl;
#ifdef debug
    system("pause");
#endif
    return 0;
}

Runtime Error, I don't know why. Please tell me the bug in my code. Thank you!

CarYon: генератор тестовых данных OI / ACM на основе C ++

  

Предисловие

Для чего это?

При проведении своего собственного конкурса OI, вы столкнулись со следующими проблемами

• Хотите быстро сгенерировать абзац текста?
• Хотите быстро выполнить математические операции для генерации данных?
• Хотите генерировать тестовые данные по очереди, не дожидаясь freopen?
• Хотите сгенерировать набор случайных данных или рядов?
• Быстро генерировать данные для соответствия двум программам?

Затем вы можете использовать CarYon и C ++ для быстрой генерации данных. В настоящее время поддерживаются следующие функции:

• Случайно генерировать абзац, несколько слов, несколько букв
• Без ограничений RAND_MAX, свободно составлять случайные числа Разрабатываемая математическая библиотека поддерживает несколько функций
• Создайте несколько кругов, правильных многоугольников и дробей и используйте их для расчетов

Выполните test.cpp для создания надежных данных в течение 1 минуты

Я надеюсь, что вы все можете помочь улучшить этот проект. Надеюсь, что этот проект поможет всем сэкономить время!

что-то не так?

Перейдите в репозиторий Github, чтобы опубликовать вопрос, чтобы задать вопросы, и вы можете опубликовать эту статью.

Мой номер Луогу: luosw

Инструкции по использованию

Как установить?

установка npm (стабильная версия)

Вы можете перейти в репозиторий GitHub, чтобы загрузить последнюю версию, ссылка находится в следующем заголовке, и ее также можно использовать с установленным node-js:

$ npm install datamaker-caryon --save

Установите стабильную версию этого генератора данных.

GitHub репозиторий (последняя версия)

https://github.com/luosiwei-cmd/caryon

Пожалуйста, не забудьте пометить ~

exe установка (стабильная версия)

Посетите http://luosw.fun/caryon/caryon-setup.exe, чтобы загрузить установочный пакет, запустить установочный пакет, в установочном каталоге (по умолчанию C: // Program Files (x86) / CarYon) вы можете найти соответствующий caryon.h файл.

Генерация данных

Следующие основные операции должны включать файл заголовка caryon.h. Обратите внимание, что папка каталога программы должна содержать файлcaryon.h.gch, сгенерированный после того, как файл заголовка скомпилирован перед использованием генератора данных.

makein (1,10) {
    csh();
ххххх;
}

Эта операция используется для генерации файла: 1.in-10.in, вы можете свободно изменять два параметраmakein для замены. Например, makein (3,5) сгенерирует 3.in-5.in.

Когда мы выполним test.cpp, мы обнаружим, что в корневом каталоге есть дополнительная папка, которая содержит файлы из1.in ~ 10.in, что является результатом изготовления.

csh(); Команда не должна быть изменена или заменена!

Последующий:

dataname = "";

Это необходимо для заполнения префикса, такого как следующая программа:

#include "caryon.h"
using namespace  std;
using namespace ca;
int main () {
  dataname = "chen_zhe-ак-ioi";
  makein (1,10) {
    csh();
    ххх;
  }
}

Он сгенерирует chen_zhe-ak-ioi1.in ~ chen_zhe-ak-ioi10.in в папкеdata-chen_zhe-ak-ioi в корневом каталоге.

**Обратите внимание, что из-за новой версии пробелы не могут появляться в поле dataname! ! **

После того, как все наши вещи сделаны, не забудьте использовать

closefile ();

Функция для освобождения места в памяти. (Эффект похож на fclose, вам не нужно его писать)

Мы научились создавать в файлах, как создавать соответствующие файлы? Давайте обогатим предыдущий пример:

#include "caryon.h"
using namespace std;
using namespace ca;
int main () {
  dataname = "chen_zhe-ак-ioi";
  makein (1,10) {
        csh();
        ххх;
     }
  makeout (1,10);
}

В это время в каталоге, где находится test.cpp, должен быть файлstd.exe, который обычно называют стандартной программой. Обратите внимание, что стандартной программой должен быть скомпилированный файл std.exe, прежде чем можно будет создать соответствующий файл out.

Давайте создадим случайное число ниже:

cyrand (а, b);

Его функция — возвращать случайное число между a иb.

MT19337 (или метод вращения Мейсона), используемый этим случайным числом, преодолевает ограничение RAND_MAX, которое поставляется с C ++.

(Если вы хотите сгенерировать случайное число в диапазоне «long long», используйте cyrand_ll ()).

Давайте посмотрим, как хранить целочисленные переменные во входном файле:

inint ();
instring ("");

Обе эти функции используются для ввода данных в файл in. Если мы хотим ввести случайное число, мы пишем:

inint (cyrand ());

Вот и все.

Например, следующая программа:

#include "caryon.h"
using namespace std;
using namespace ca;
int main () {
    dataname = "test";
    makein (1,10) {
        csh();
        inint (cyrand (0100));
    }
}

Вы найдете файл test1.in-test10.in в папке data-test в каталоге. Откройте эти файлы с помощью Блокнота, и вы найдете случайное число в каждом файле.

Если вы не знаете, как открыть файл in и файлout с помощью Блокнота, щелкните правой кнопкой мыши файл и выберите Открыть метод, чтобы найти свой Блокнот. Или вы можете использовать Dev-C ++, открыть программное обеспечение и перетащить в него файл in.

Для этой программы, если мы напишем std.cpp так:

#include <bits/stdc++.h>
using namespace std;
int main () {
    int a;
    cin >> а;
    cout << а + 10;
    return 0;
}

После компиляции измените test.cpp на:

#include "caryon.h"
using namespace std;
using namespace ca;
int main () {
    dataname = "test";
    makein (1,10) {
        csh();
        inint (cyrand (0100));
    }
    makeout (1,10);
}

Затем используйте Блокнот, чтобы открыть файлы in иout соответственно, и вы можете обнаружить, что это результат добавления $$$ 10 $$$ к числу каждого файла in.

Благодаря поддержке функций новой версии, при создании файла будет отображаться подсказка, поэтому вам не нужно беспокоиться о том, какой черный ящик продолжает прыгать и прыгать!

Так работает весь генератор данных.

Мы также можем генерировать много случайных вещей, таких как:

cyrand_bool (); // Случайное логическое значение
cyrand_engs (); // Случайные английские строчные буквы
cyrand_engb (); // Случайные английские заглавные буквы
cyrand_formatc (); // случайный escape-символ
cyrand_word (a); // Случайное слово длины a
cyrand_article (a); // Случайный абзац со словарем
cyrand_letter (); // Случайные символы

Эти вещи можно использовать, чтобы представить себе DIY и достичь желаемого эффекта.

Соответствие программы

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

Теперь CarYon наконец-то поддерживает функцию съемки! ! !

Соответствие программы можно условно разделить на следующие этапы:

1. Напишите myprogram.cpp в текущем каталоге и скомпилируйте его в файлmyprogram.exe;
2. Напишите test.cpp иstd.cpp в соответствии с модулем генерации данных;
3. Добавьте строку после test.cpp:

debug(/ * начало * /, / * конец * /);

Например, вы уверенно отправляете свои высокоточные a + b. В настоящее время вам необходимо сопоставить вашу программу с низкими значениями точности.

Сначала поместите следующую высокоточную версию a + b в ваш myprogram.cpp и скомпилируйте ее в myprogram.exe:

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	string a,b;
	int xa[500]={},xb[500]={},tot[500]={};
	cin>>a>>b;
	for(int i=0;i<a.length();i++)
		xa[i]=a[a.length()-i-1]-'0';
	for(int i=0;i<b.length();i++)
		xb[i]=b[b.length()-i-1]-'0';
	int len=max(a.length(),b.length());
	for(int i=0;i<len;i++)
		tot[i]=xa[i]+xb[i];
	for(int i=0;i<len;i++)
	{
		tot[i+1]+=tot[i]/10;
		tot[i]%=10;
	}
	if(tot[len]) cout<<tot[len];
	for(int i=len-1;i>=0;i--)
		cout<<tot[i];
	cout<<endl;
}

Затем заполните простейшие a + b вstd.cpp;

И напишите test.cpp так:

#include "caryon.h"
// Уже включаем универсальные заголовочные файлы
using namespace  std;
using namespace имен ca; // Namespace


int main () {
  dataname = "a+btest"; // Напишите здесь свой префикс
  makein (1,10) {
    csh ();
    / * Пожалуйста, посмотрите здесь документ на использование и два тестовых примера самостоятельно * /
  }
  makeout(/ * начало * /, / * количество раз * /);
   debug (/ * start * /, / * количество раз * /); // команда соответствия программы, вам не нужно писать
// Значение makeout должно быть меньше или равно makein
// Пожалуйста, скомпилируйте std и поместите его в эту папку, там должен быть exe-файл
	//Спасибо за Вашу поддержку
  return 0;
}

Обратите внимание, что из-за новой версии пробелы не могут появляться в поле dataname! ! !

После запуска можно обнаружить не только папку data-a + btest, но такжеa+btest1.in / out-a + btest10.in / out, но и новую папку debug-a + btest folder, inside — это выводa + btest1.ans-a + b10.ans с помощью myprogram.exe, и затем вы можете использовать функцию comp в cmd, чтобы сравнить размер этих двух файлов!

test.cpp Инструкция по применению

Исходная информация test.cpp в корневой директории выглядит следующим образом:

#include "caryon.h"
// Уже включаем универсальные заголовочные файлы
using namespace  std;
using namespace имен ca; // Namespace

int main () {
  dataname = ""; // Напишите здесь свой префикс
  makein (1,10) {
    csh();
    / * Пожалуйста, посмотрите здесь документ на использование и два тестовых примера самостоятельно * /
  }
  makeout(/ * начало * /, / * количество раз * /);
  debug (/ * start * /, / * количество раз * /); // команда соответствия программы, вам не нужно писать
// Значение makeout должно быть меньше или равно makein
// Пожалуйста, скомпилируйте std и поместите его в эту папку, там должен быть exe-фай
//Спасибо за Вашу поддержку
  return 0;
}

Помните, что не следует менять общую структуру программы, иначе у ваших результатов выполнения будут проблемы

1. dataname — это префикс входных и выходных файлов, если вы оставите это поле пустым, префикса не будет;
2. Число раз в makein () — количество сгенерированных файлов;
3. csh; в makein не должен быть изменен. При изменении произойдут неизвестные ошибки;
4. Количество раз в makeout должно быть меньше, чем вmakein, и по умолчанию формируются файлы out, начиная сprefix 1.in, что можно продолжить.

Перед запуском программы обязательно поместите файл std exe в ту же папку.

Генерируем a + b проблемные данные test.cpp пишем демонстрацию

#include "caryon.h"
// Уже включаем универсальные заголовочные файлы
using namespace std;
using namespace ca; // Namespace


int main () {
  dataname = "a+b test"; // Напишите здесь свой префикс
  makein (1,10) {
    csh();
    inint (cyrand (-1000,1000));
    instring ("");
    inint (cyrand (-1000,1000));
  }
  makeout (1,10);
  return 0;
}

Объяснение: Данные a + b представляют собой два случайных числа (с пробелами между ними), поэтому для добавления пробелов вам необходимо использовать функцию instring (" "); а затем есть два случайных числа.

Для высокоточных данных их можно сгенерировать в следующем цикле:

inint (cyrand (1,9));
for (int i = 0; i <длина высокоточных данных-1; i ++) {
    inint (cyrand (0,9));
}

Вышеуказанная программа может генерировать только высокоточные данные.

Вышеуказанного контента достаточно для генерации данных noip-плееров, поэтому я не буду говорить об этом позже и подожду, пока пользователи сами исследуют. Если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение на этом интерфейсе, спасибо!

CarYon: An OI/ACM Contest Test Data Generator based on C++

Front

Have you ever encountered the following problems when holding a self-contained OI match:

• Want to quickly produce a paragraph of text?
• Want to quickly perform mathematical operations to generate data?
• Want to generate test data one by one without using freopen?
• Want to generate a set of random data or series?
• Quickly generate data to match the two programs?

Then, you can use CarYon and C++ to quickly generate data. Previously supported features are:

• Randomly generate a chapter, some words, some words
• Get out of the limitation of RAND_MAX, freely draft random numbers
• Mathematics library under development, supporting multiple features
• Create some circles, regular polygons and fractions, and use it to perform calculations

Perform test.cpp in real 1 within minutes to have the intensity data

Hope you guys can help improve this project. Hope this item can help everyone save time!

Something wrong?

You are welcome to send an issue to the Github repository to ask questions, and you are also welcome to post in this chapter.

Instructions for use

How to install?

npm installation (stable version)

You can go to the GitHub repository to download the latest version, the link is in the next title, and it can also be used with node-js installed：

$ npm install datamaker-caryon --save

nstall the stable version of this data generator.

GitHub repository (latest version)

https://github.com/luosiwei-cmd/caryon

Everyone, remember to star~

exe installation (stable version)

Visit http://luosw.fun/caryon/caryon-setup.exe to download the installation package, run the installation package, in the installation directory (the default isC://Program Files(x86)/CarYon) can find the corresponding caryon.h file.

Data generation

You should know that nearly all functions are in the namespace ca.

The basic operations below are to include the header file caryon.h . Note that the header file must be included in the program’s directory folder after being compiled

Only the caryon.h.gch file produced later can the data generator be used.

makein(1,10){
    csh();
	xxxxx;
}

This operation is used to create files: 1. In-10.in , you can freely change the two parameters of makein for replacement. E.gmakein(3,5) is to produce 3.in-5.in .When we finish test.cpp , we will find that there is an extra folder in the root directory. There are files from 1.in to 10.in. This isIs the result of manufacturing

csh();The command must not be changed or replaced!

Here:

dataname="";

This is to fill in the prefix, such as the following program:

#include"caryon.h"
using namespace std;
using namespace ca;
int main(){
	dataname="chen_zhe-ak-ioi";
	makein(1,10){
		csh();
		xxx;
	}
}

It will be created in the folder data-chen_zhe-ak- ioi of the root directory into chen_zhe-ak-ioi1.in~chen_zhe-ak-ioi10.in .

Note that due to the new version, no spaces can appear in the dataname field! ! !

After all our things are done, remember to us

closefile();

Function to free up memory space. (The effect is similar to fclose, you don’t need to write it)

We have learned to createin files, how to create correspondingoutfiles? Let's enrich the previous examples:

#include"caryon.h"
using namespace std;
using namespace ca;
int main(){
	dataname="chen_zhe-ak-ioi";
	makein(1,10){
		csh();
		xxx;
	}
    makeout(1,10);
}

At this time, there must be a std.exe file in the directory where test.cpp is located , which is commonly known as a standard program. Note that it must be the standard.

After the program is compiled, the std.exe file can produce the corresponding out file.

Let's create a random number below:

cyrand(a,b);

Its function is to return a random number between a and b .

The MT19337 (or Mason rotation method) used by this random number breaks through the limitation of C++'s native RAND_MAX.

(If you want to generate a random number in the long long range, use cyrand_ll()).

Let's take a look at how to store integer variables in the input file:

inint(a);
instring(b);

Both of these functions are used to input things into the in file. If we want to input a random number, we write:

inint(cyrand());

That's it.

For Example:

#include"caryon.h"
using namespace std;
using namespace ca;
int main(){
    dataname="test";
    makein(1,10){
        csh();
        inint(cyrand(0,100));
    }
}

Of Contents will find in the data-test folder in the display will appear test1.in-test10.in files, Using Notepad to open these files,

You will find that every file has a random number.

If you don’t know how to use Notepad to open in files and out files, please right-click the file, click Open Mode, and find your note

this. Or you can use Dev-C++, open the software, and drag the in file into it.

For this program, if we write std.cpp like this :

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a;
    cin>>a;
    cout<<a+10;
    return 0;
}

After compiling, change test.cpp to:

#include"caryon.h"
using namespace std;
using namespace ca;
int main(){
    dataname="test";
    makein(1,10){
        csh();
        inint(cyrand(0,100));
    }
    makeout(1,10);
}

Then use Notepad to open the in and out files separately , you can find that the number of each in file is added $$$10$$$ the result is out.

Due to the support of the new version's features and features, there will be a prompt when the file is created, so you don't have to worry about which frame is jumping and jumping!

This is the working principle of the entire data generator.

We can also generate many random things, such as:

cyrand_bool (); //Random Boolean type value
cyrand_engs (); //Random English lowercase letters
cyrand_engb (); //Random English uppercase letters
cyrand_formatc (); //random escape character
cyrand_word ( a ); //A random word of length a
cyrand_article ( a ); //A random paragraph with a vocabulary
cyrand_letter (); //random character

These things can be used to DIY and achieve the desired effect.

Graph and tree Graph and tree

CarYon supports the function of creating graphs.

Create a graph

You can create a graph with the following command:

template<typename T> //No need to write this line
graph<T> example;

This generates a graph with edge weight type T.

Join the edge

To add edges to the generated graph, you need:

example.addedge(/*start*/,/*end*/,cyrand(/*min*/,/*max*/))

Make a random graph

rand_graph(n,m,min,max,randfunc);

It can return a random graph with npointsm edges and side weights between min and max.

If you want to assign a value to the generated graph, directly:

example=rand_graph(n,m,min,max);

Graph class member functions

Here are some useful functions:

example.is_connect();

This function returns a Boolean value, which represents whether the graph is connected.

example.output();

Output this graph.

example=rand_dag(n,m,min,max,randfunc);

Returns a directed acyclic graph.

example=rand_tree(n,k,min,max,randfunc);

Return a k-ary tree with n points.

example=connect_graph(n,m,min,max,randfunc);

Make a random connected graph.

Tool function

For the needs of data generation, CarYon provides some simple tool functions.

1. The choice function:

The parameter is an array, a starting index, and a ending index.

Eventually, a random value between the two subscripts of this array will be returned.

E.g:

choice(a,1,10);

1. The doubleRandom function:

Returns a floating point number between 0 and 1.

E.g:

doubleRandom();

Commonly used constants

CarYon provides some commonly used constants.

PI

That is the value of pi. 3.1415926...

E

The value of the natural base. 2.7182818...

ALPHABET_SMALL

A string containing all lowercase letters. "abcdefghijklmnopqrstuvwxyz".

ALPHABET_CAPITAL

A string containing all capital letters. "ABCDEFGHIJKLMNOPQRSTUVWXYZ".

ALPHABET

A string containing all letters. "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ".

NUMBERS

A string containing all numbers. "0123456789".

There is also a math library.

Program match

In the course of the competition, in order to check whether the algorithm with low complexity is correct, it is usually used to compile a low-level algorithm to solve the same problem.

Then use a large sample at the same time to shoot the results of these two programs.

Now CarYon finally supports the camera-matching function! ! !

The matching of the program can be divided into the following steps:

1. Write myprogram.cpp in the current directory and compile it into a myprogram.exe file;
2. Write test.cppand std.cpp according to the data generation module ;
3. Add a line aftertest.cpp：

debug(/*start*/,/*end*/);

For example, if you are confidently submitting the high-precision a+b, you need to use low-precision values to match your program.

First, put the following high-precision version a+b into your myprogram.cpp and compile it into myprogram.exe :

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	string a,b;
	int xa[500]={},xb[500]={},tot[500]={};
	cin>>a>>b;
	for(int i=0;i<a.length();i++)
		xa[i]=a[a.length()-i-1]-'0';
	for(int i=0;i<b.length();i++)
		xb[i]=b[b.length()-i-1]-'0';
	int len=max(a.length(),b.length());
	for(int i=0;i<len;i++)
		tot[i]=xa[i]+xb[i];
	for(int i=0;i<len;i++)
	{
		tot[i+1]+=tot[i]/10;
		tot[i]%=10;
	}
	if(tot[len]) cout<<tot[len];
	for(int i=len-1;i>=0;i--)
		cout<<tot[i];
	cout<<endl;
}

Then fill in the simplest a+b in std.cpp ;

And write test.cpp like this

#include"caryon.h"//Already include universal header files
using namespace std ;
using namespace ca ; //Namespace
int main (){
    dataname = "a+btest" ; //Write your own prefix here
    makein ( 1 , 10 ){
        csh ();/*Please look at the use document and two test examples by yourself here*/
    }
    makeout ( /*start*/ , /*number of times*/ );
    debug ( /*start*/ , /*number of times*/ );
    //program matching command, you don’t need to write
    //The value of makeout must be less than or equal to makein
    //Please compile std and put it in this folder, there must be an exe file
    //thank you for your support
    return 0 ;
}

Note that due to the new version, no spaces can appear in the dataname field! ! !

After the operation, you can find that not only the data-a+btest folder, but also a+btest1.in/out-a+btest10.in/out , but also A new folder debug-a+btest appears , the folder is a+btest1.ans- a+btest10.ansoutput by myprogram.exe , and then you can use cmd 's comp function to compare these two files!

Instructions for use oftest.cpp

The original information of test.cpp in the root directory is as follows:

#include"caryon.h"//Already include universal header files
using namespace std ;
using namespace ca ; //Namespace
int main (){
    dataname = "a+btest" ; //Write your own prefix here
    makein ( 1 , 10 ){
        csh ();/*Please look at the use document and two test examples by yourself here*/
    }
    makeout ( /*start*/ , /*number of times*/ );
    debug ( /*start*/ , /*number of times*/ );
    //program matching command, you don’t need to write
    //The value of makeout must be less than or equal to makein
    //Please compile std and put it in this folder, there must be an exe file
    //thank you for your support
    return 0 ;
}

Remember not to change the overall framework of the program, otherwise there will be problems with your execution results

1. dataname is the prefix of the input and output files, if you leave it blank , there will be no prefix;

2. The number of times in makein() is the number of in files generated;

3. Csh in makein ; remember that it cannot be changed, there will be an unknown error when changing;

4. The number of times in makeout must be smaller than that in makein , and the default is to form out files starting from the prefix 1.in , which can be continued

a + b problem data test.cpp preparing model

#include"caryon.h"
using namespace std;
using namespace ca;	


int main(){
	dataname="a+b test";	
	makein(1,10){
		csh();
		inint(cyrand(-1000,1000));
        instring(" ");
        inint(cyrand(-1000,1000));
	} 
	makeout(1,10);
	return 0;
}

Explanation: The data of a+b are two random numbers (with spaces in between), so you need to use the instring(" "); function to add spaces, if you need to change the line, you need to use instring("\n");, and then there is a problem of two random numbers.

For high-precision data, it can be generated in the following cycle:

inint(cyrand(1,9));
for(int i=0;i<LEN-1;i++){
    inint(cyrand(0,9));
}

The above program can only generate a high-precision data.

The above content is enough to generate the data selected by noip, so I won't talk about it later, and wait for the user to explore it myself. If you have any questions, please comments, thank you!

There is an important patch, plase re-download it if you like it.

Thank you!