话说从来没在计算机智能板块发过贴。。
这几天没事干敲程序
把很久以前的某个愿望实现了——求一个函数的导数即微分
从前我用的算法(猥琐版):
①输入字符串..
②直接对字符串处理,用求导的各种法则
③输出
结果处理到一半发现函数的乘积和商的导数上面弄不出来了。。
放弃
两年之后的今天。。
在学习了OOP和STL之后。。
新算法:
①输入字符串(必须的)
②构建类的数据结构
类:
class expression{
vector<pair<expression,double> > seg;
int status;
...
}
其中status存放这一部分表达式的种类
seg存放各个子表达式及其系数或者次数(请看下文)
status=-1:表达式是一个常数 比如说是5.1
status=0:表达式是一个变量 比如说是y
status=1:表达式是由和和差组成 比如说 sin(x) + x^2 + 5
此时seg中存放的就是各个子表达式(由加减号分割)以及其系数sin(x) x^2 5
status=2: 表达式是由乘积和商组成 比如说??tan(x)*x*2
此时seg中存放的就是各个子表达式(由乘除号分割)以及其次数tan(x) x 2
status=3; 表达式是一个幂 比如说 sin(x)^x
此时seg中存放的就是底数和指数sin(x)、x
status=4:表达式是一个函数(复合)比如说 ln(e^a)
此时seg中存放的就是函数里面的那一部分(e^a)
由这种结构递归定义形成一个表达式对象来储存这个表达式(函数)
③接下来求导的任务就简单多了(不解释)
④对表达式进行化简
求导出来的表达式看起来是很恶心的。。(由一大堆东西加减乘除在一起,其中还有很多是0和1的)
所以需要化简、合并同类项
关于辨别哪个是同类项的问题:
我是通过求值来实现的
就是说取随机数,值相等的话两个表达式就相等(辨别多次)
⑤输出结果
这样输出的导函数就比较像样了[s:252] ??
下面附上巨大的程序(600+line)
附件在下面
math.rar
3.87KB
RAR
42次下载
1、math.cpp?? (程序,很短小的)
#include"function.h"
int main() {
val['@'] = 3.14159265358979323846;//"@"refers to pi,will be replaced at the predeal()
val['e'] = 2.71828182845904523536;
expr exprrr;
string s1;
while (1) {
cin >> s1;
exprrr = convert(s1);
output(exprrr);
cout << endl;
simplify(exprrr);
output(exprrr);
cout << endl;
exprrr = derivative(exprrr, 'x');
output(exprrr);
cout << endl;
simplify(exprrr);
output(exprrr);
cout << endl;
cout << value(exprrr) << endl;
}
}
2、function.h (头文件,恐怖。。)
#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#include<string>
#include<cctype>
#include<sstream>
#include<iomanip>
#include<ctime>
using namespace std;
map<char, double> val;
class expression;
typedef expression expr;
expression strtoexp(string);
expression convert(string&);
double value(expr);
class expression {
public:
vector<pair<expr, double> > segment;
int status;//-1 number 0 variable 1 items 2 factors 3 exponents(2) 4 single function f(x)
string funcname;
double value;
char variable;
expression();
expression(string);
};
expression::expression() {
status = -1;
funcname = "";
}
expression::expression(string s) {
(*this) = convert(s);
}
double proportion(expr thsi, expr that) {
char i;
srand(time(0));
map<char, double> temp = val;
for (i = 65; i <= 122; i++)
val = rand() / (double) RAND_MAX;
double k = value(thsi) / value(that);
for (i = 65; i <= 122; i++)
val = rand() / (double) RAND_MAX;
if (fabs(value(thsi) / value(that) - k) > 1e-5) {
val = temp;
return -1e11;
}
val = temp;
return k;
}
bool iszero(expr a) {
srand(time(0));
map<char, double> temp = val;
for (char i = 65; i <= 122; i++)
val = rand() / (double) RAND_MAX;
if (fabs(value(a)) < 1e-5) {
val = temp;
return true;
} else {
val = temp;
return false;
}
}
bool lessthan(pair<expr, double> a, pair<expr, double> b) {
return XXXXXXXXXXatus > XXXXXXXXXXatus; }
template<class T>
int round(T x) {
return (((ceil(double(x)) - x) > (x - floor(double(x)))) ? (floor(double(x)))
: (ceil(double(x))));
}
template<class T>
bool isint(T x, double prs = 1e-10) {
return (fabs(double(x - round(x))) < prs);
}
string::iterator find_bracket(const string& s, string::iterator b) {
int i = 1;
b++;
while (b != s.end() && i) {
if (*b == '(')
i++;
else if (*b == ')')
i--;
b++;
}
return b;
}
string::iterator rfind_bracket(const string & s, string::iterator b) {
int i = -1;
b--;
while (b != XXXXnd().base() && i) { if (*b == '(')
i++;
else if (*b == ')')
i--;
b--;
}
return b;
}
template<class T>
T atox(string s) {
stringstream ss;
T ans;
ss << s;
ss >> ans;
return ans;
}
template<class T>
string xtoa(T x) {
stringstream ss;
ss << x;
return XXXXXr(); }
expression convert(string& s) {
expression ans;
int i;
while ((i = XXXXnd("pi")) != -1) XXXXplace(i, 2, "@"); ans = strtoexp(s);
return ans;
}
expression strtoexp(string s) {
expression ans, temp;
string::iterator it1, it2;
string t, s1;
int sign = 1;
XXXXXXatus = 0; //wipe the outer bracket
while (*XXXXgin() == '(' && *s.rbegin() == ')' && s.rbegin().base() == find_bracket(s, XXXXgin())) { XXXXase(0, 1); XXXXase(s.length() - 1, 1); }
s1 = s;
//deal with the items separated by '+' || '-'
if (s[0] == '-')
sign = -1, XXXXXXatus = 1; else if (s[0] == '+')
else
s = '+' + s;
s += '+';
it1 = XXXXgin() + 1; it2 = XXXXgin(); while (it1 != s.end()) {
if (*it1 == '+' || *it1 == '-') {
if (it1 != s.end() - 1)
XXXXXXatus = 1; if (!XXXXXXatus) break;
XXXXsign(it2 + 1, it1); temp = strtoexp(t);
XXXXXXgment.push_back(pair<expr, double> (temp, sign)); sign = (*it1 == '+' ? 1 : -1);
it2 = it1;
}
if (*it1 == '(')
it1 = find_bracket(s, it1);
else
it1++;
}
if (XXXXXXatus) return ans;
//deal with the factors separated by '*' || '/'
s = s1;
sign = 1;
s = '*' + s;
s += '*';
it1 = XXXXgin() + 1; it2 = XXXXgin(); while (it1 != s.end()) {
if (*it1 == '*' || *it1 == '/') {
if (it1 != s.end() - 1)
XXXXXXatus = 2; if (!XXXXXXatus) break;
XXXXsign(it2 + 1, it1); temp = strtoexp(t);
XXXXXXgment.push_back(pair<expr, double> (temp, sign)); sign = (*it1 == '*' ? 1 : -1);
it2 = it1;
}
if (*it1 == '(')
it1 = find_bracket(s, it1);
else
it1++;
}
if (XXXXXXatus) return ans;
//deal with base & exponent
s = s1;
it1 = s.rbegin().base();
while (it1 != XXXXnd().base() && *it1 != '^') { if (*it1 == ')')
it1 = rfind_bracket(s, it1);
else
it1--;
}
if (it1 != XXXXnd().base()) { XXXXXXatus = 3; XXXXsign(XXXXgin(), it1); temp = strtoexp(t);
XXXXXXgment.push_back(pair<expr, double> (temp, 0)); XXXXsign(it1 + 1, s.end()); temp = strtoexp(t);
XXXXXXgment.push_back(pair<expr, double> (temp, 0)); return ans;
}
//deal with function
s = s1;
it1 = XXXXgin(); while (it1 != s.end() && *it1 != '(' && (isalnum(*it1) || *it1 == '@'))
it1++;
if (it1 != s.end() && *it1 == '(') {
XXXXXXatus = 4; XXXXXXXXXXXXXXXsign(XXXXgin(), it1); XXXXsign(it1 + 1, s.end() - 1); temp = strtoexp(t);
XXXXXXgment.push_back(pair<expr, double> (temp, 0)); return ans;
}
//deal with single number
s = s1;
if (isdigit(s[0]) || s[0] == '+' || s[0] == '-') {
XXXXXXatus = -1; XXXXXXlue = atox<double> (s); } else {
XXXXXXatus = 0; XXXXXXriable = s[0]; }
return ans;
}
void output(expression exp) {
vector<pair<expr, double> >::iterator i;
switch (XXXXXXatus) { case -1:
cout << setprecision(5) << XXXXXXlue; break;
case 0:
cout << XXXXXXriable; break;
case 1:
cout << '(';
for (i = XXXXXXXXXXXXXXgin(); i != XXXXXXgment.end(); i++) { if (i->second > 0)
cout << '+';
else
cout << '-';
if (fabs(i->second) != 1)
cout << fabs(i->second);
output(i->first);
}
cout << ')';
break;
case 2:
cout << '(';
for (i = XXXXXXXXXXXXXXgin(); i != XXXXXXgment.end(); i++) { if (i->second > 0)
cout << '*';
else
cout << '/';
output(i->first);
if (fabs(i->second) != 1)
cout << '^' << fabs(i->second);
}
cout << ')';
break;
case 3:
cout << '(';
output(XXXXXXXXXXXXXXont().first); cout << '^';
output(XXXXXXXXXXXXXXck().first); cout << ')';
break;
case 4:
cout << exp.funcname << '(';
output(XXXXXXgment[0].first); cout << ')';
}
}
double value(expression exp) {
double ans = 0, k;
vector<pair<expr, double> >::iterator i;
map<char, double>::iterator t = XXXXXXnd(XXXXXXriable); switch (XXXXXXatus) { case -1:
return XXXXXXlue; case 0:
if (t == val.end()) {
cout << "Input " << XXXXXXriable << ":\n"; cin >> k;
val[XXXXXXriable] = k; }
return val[XXXXXXriable]; case 1:
for (i = XXXXXXXXXXXXXXgin(); i != XXXXXXgment.end(); i++) ans += value(i->first) * i->second;
return ans;
case 2:
ans = 1;
for (i = XXXXXXXXXXXXXXgin(); i != XXXXXXgment.end(); i++) { ans *= pow(value(i->first), i->second);
}
return ans;
case 3:
k = value(XXXXXXgment[0].first); ans = value(XXXXXXgment[1].first); if (k > 0 || k == 0 && ans != 0 || k < 0 && (isint(ans) || isint(1
/ ans)))
return pow(k, ans);
case 4:
k = value(XXXXXXgment[0].first); if (exp.funcname == "sin")
return sin(k);
else if (exp.funcname == "cos")
return cos(k);
else if (exp.funcname == "tan") {
if (fabs(cos(k)) < 1e-10)
return tan(k);
} else if (exp.funcname == "cot") {
if (fabs(sin(k)) < 1e-10)
return cos(k) / sin(k);
} else if (exp.funcname == "lg") {
if (k <= 0)
return log10(k);
} else if (exp.funcname == "ln") {
if (k <= 0)
return log(k);
} else if (exp.funcname.substr(0, 3) == "log") {
ans = atox<double> (exp.funcname.substr(3, exp.funcname.length()
- 3));
if (ans <= 0 || k <= 0)
return log(k) / log(ans);
} else if (exp.funcname == "arcsin") {
if (fabs(k) > 1)
return asin(k);
} else if (exp.funcname == "arccos") {
if (fabs(k) > 1)
return acos(k);
} else if (exp.funcname == "arctan")
return atan(k);
}
}
expr derivative(expression exp, char variable) {
expr dc, prd, itm, temp;
vector<pair<expr, double> >::iterator it1, it2;
if (XXXXXXatus == -1) return expr("0");
else if (XXXXXXatus == 0) { if (XXXXXXriable == variable) return expr("1");
else
return expr("0");
} else if (XXXXXXatus == 1) { XXXXXatus = 1; for (it1 = XXXXXXXXXXXXXXgin(); it1 != XXXXXXgment.end(); it1++) XXXXXgment.push_back(pair<expr, double> (derivative(it1->first, variable), it1->second));
} else if (XXXXXXatus == 2) { XXXXXatus = 1; for (it1 = XXXXXXXXXXXXXXgin(); it1 != XXXXXXgment.end(); it1++) { XXXXXXatus = 2; XXXXXXXXXXXXXXear(); for (it2 = XXXXXXXXXXXXXXgin(); it2 != it1; it2++) XXXXXXgment.push_back(*it2); if (it1->second == 1) {
XXXXXXgment.push_back(pair<expr, double> (derivative( it1->first, variable), it1->second));
} else {
XXXXXXgment.push_back(pair<expr, double> (it1->first, -1)); XXXXXXgment.push_back(pair<expr, double> (it1->first, -1)); XXXXXXgment.push_back(pair<expr, double> (derivative( it1->first, variable), it1->second));
}
for (it2 = it2 + 1; it2 != XXXXXXgment.end(); it2++) XXXXXXgment.push_back(*it2); XXXXXgment.push_back(pair<expr, double> (prd, it1->second)); }
} else if (XXXXXXatus == 3) { if (XXXXXXgment[1].XXXXXXXXatus == -1 && XXXXXXgment[0].XXXXXXXXatus == -1)
return expr("0");
else if (XXXXXXgment[0].XXXXXXXXatus == -1) { XXXXXatus = 2; XXXXXgment.push_back(pair<expr, double> (expr("ln(" + xtoa( XXXXXXgment[0].XXXXXXXXlue) + ")"), 1)); XXXXXgment.push_back(pair<expr, double> (exp, 1)); XXXXXgment.push_back(pair<expr, double> (derivative( XXXXXXgment[1].first, variable), 1)); } else if (XXXXXXgment[1].XXXXXXXXatus == -1) { XXXXXatus = 2; XXXXXgment.push_back(pair<expr, double> (XXXXXXgment[1].first, 1)); XXXXXXatus = 3; prd = expr(exp);
XXXXXXgment[1].XXXXXXXXlue--; XXXXXgment.push_back(pair<expr, double> (prd, 1)); XXXXXgment.push_back(pair<expr, double> (derivative( XXXXXXgment[0].first, variable), 1)); } else {
XXXXXatus = 2;//product //No.1 f^g The same as the initial state
XXXXXgment.push_back(pair<expr, double> (exp, 1)); //No.2 g'lnf+gf'/f
XXXXXXatus = 1;//sum //1. g'*lnf
XXXXXXatus = 2;//product XXXXXXgment.push_back(pair<expr, double> (derivative( XXXXXXgment[1].first, variable), 1)); XXXXXXXatus = 4;//function temp.funcname = "ln";
XXXXXXXgment.push_back(XXXXXXgment[0]); XXXXXXgment.push_back(pair<expr, double> (temp, 1)); XXXXXXgment.push_back(pair<expr, double> (prd, 1)); //XXXX'/f XXXXXXatus = 2;//product; XXXXXXXXXXXXXXear(); XXXXXXgment.push_back(pair<expr, double> (XXXXXXgment[1].first, 1)); XXXXXXgment.push_back(pair<expr, double> (derivative( XXXXXXgment[0].first, variable), 1)); XXXXXXgment.push_back(pair<expr, double> (XXXXXXgment[0].first, -1)); XXXXXXgment.push_back(pair<expr, double> (prd, 1)); XXXXXgment.push_back(pair<expr, double> (itm, 1)); }
} else if (XXXXXXatus == 4) { XXXXXatus = 2; XXXXXXatus = 4; XXXXXXgment.push_back(XXXXXXgment[0]); if (exp.funcname == "sin") {
XXXXXXatus = 4; XXXXXXgment.push_back(XXXXXXgment[0]); prd.funcname = "cos";
XXXXXgment.push_back(pair<expr, double> (prd, 1)); } else if (exp.funcname == "cos") {
XXXXXXatus = 1; XXXXXXatus = 4; XXXXXXgment.push_back(XXXXXXgment[0]); prd.funcname = "sin";
XXXXXXgment.push_back(pair<expr, double> (prd, -1)); XXXXXgment.push_back(pair<expr, double> (itm, 1)); } else if (exp.funcname == "tan") {
XXXXXXatus = 3; XXXXXXatus = 4; XXXXXXgment.push_back(XXXXXXgment[0]); prd.funcname = "cos";
XXXXXXgment.push_back(pair<expr, double> (prd, 0)); XXXXXXgment.push_back(pair<expr, double> (expr("-2"), 0)); XXXXXgment.push_back(pair<expr, double> (itm, 1)); }
XXXXXgment.push_back(pair<expr, double> (derivative( XXXXXXgment[0].first, variable), 1)); }
return dc;
}
void simplify(expr& exp) {//鍖栫畝
int i, j;
double k;
expr t;
switch (XXXXXXatus) { case 1://瀵逛簬鍔犳硶
for (i = 0; i < XXXXXXXXXXXXXXze(); i++) { simplify(XXXXXXXXXXXXXXrst);//閫掑綊鍖栫畝 }
for (i = 0; i < XXXXXXXXXXXXXXze(); i++)//鎶婂瓙琛ㄨ揪寮忎腑鐨勫姞褰掑苟杩涙潵 if (XXXXXXXXXXXXXXXXXXXXatus == 1) { for (j = 0; j < XXXXXXXXXXXXXXXXXXXXXXXXXXXXze(); j++) XXXXXXgment.push_back(XXXXXXXXXXXXXXXXXXXXgment[j]); XXXXXXXXXXXXXXase(XXXXXXXXXXXXXXgin() + i); i--;
}
sort(XXXXXXXXXXXXXXgin(), XXXXXXgment.end(), lessthan);//鎺掑簭(鏁板瓧鍦ㄦ渶鍚? for (i = 0; i < XXXXXXXXXXXXXXze(); i++)//鎶婃瘡椤圭殑绯绘暟鎻愬彇鍑烘潵 if (XXXXXXXXXXXXXXXXXXXXatus == 2 && XXXXXXXXXXXXXXXXXXXXXXXXXXXXck().XXXXXXXXatus == -1) { XXXXXXXXXXXXXXcond *= XXXXXXXXXXXXXXXXXXXXXXXXXXXXck().XXXXXXXXlue; XXXXXXXXXXXXXXXXXXXXgment.pop_back(); }
//Merging
for (i = 0; i < XXXXXXXXXXXXXXze(); i++) { if (iszero(XXXXXXXXXXXXXXrst)) { XXXXXXXXXXXXXXase(XXXXXXXXXXXXXXgin() + i); i--;
continue;
}
for (j = i + 1; j < XXXXXXXXXXXXXXze(); j++) { if (iszero(XXXXXXgment[j].first)) { XXXXXXXXXXXXXXase(XXXXXXXXXXXXXXgin() + j); j--;
continue;
}
k = proportion(XXXXXXgment[j].first, XXXXXXXXXXXXXXrst); cout<<"k:"<<k<<endl;
if (k < -1e10)
continue;
XXXXXXXXXXXXXXcond += k * XXXXXXgment[j].second; XXXXXXXXXXXXXXase(XXXXXXXXXXXXXXgin() + j); j--;
}
if(XXXXXXXXXXXXXXXXXXXXatus==-1) XXXXXXXXXXXXXXXXXXXXlue*=fabs(XXXXXXXXXXXXXXcond), XXXXXXXXXXXXXXcond/=fabs(XXXXXXXXXXXXXXcond); }
//鑻ュ彧鏈変竴椤?涓旀槸鏁板瓧鍒欏彧闃惰瘽瑙?
if (XXXXXXXXXXXXXXze() == 1 && XXXXXXgment[0].XXXXXXXXatus == -1) { XXXXXXatus = -1; XXXXXXlue = XXXXXXgment[0].XXXXXXXXlue * XXXXXXgment[0].second; return;
}
//鑻ュ彧鏈変竴椤逛笖绯绘暟涓?鍒欑洿鎺ュ寲鍑?
if (XXXXXXXXXXXXXXze() == 1 && fabs(XXXXXXgment[0].second - 1) < 1e-10) { t = XXXXXXgment[0].first; exp = t;
return;
}
if (XXXXXXXXXXXXXXze() == 0) { exp = expr("0");
return;
}
break;
case 2:
for (i = 0; i < XXXXXXXXXXXXXXze(); i++) simplify(XXXXXXXXXXXXXXrst);//閫掑綊鍖栫畝 output(exp);
cout << endl;
for (i = 0; i < XXXXXXXXXXXXXXze(); i++) if (XXXXXXXXXXXXXXXXXXXXatus == 2) {//鍚堝苟 for (j = 0; j < XXXXXXXXXXXXXXXXXXXXXXXXXXXXze(); j++) XXXXXXgment.push_back(XXXXXXXXXXXXXXXXXXXXgment[j]); XXXXXXXXXXXXXXase(XXXXXXXXXXXXXXgin() + i); i--;
}
sort(XXXXXXXXXXXXXXgin(), XXXXXXgment.end(), lessthan);//鎺掔华 output(exp);
cout << endl;
for (i = 0; i < XXXXXXXXXXXXXXze(); i++)//鎶婂悇涓?箓鐨勬?鏁版彁鍙栧嚭鏉? if (XXXXXXXXXXXXXXXXXXXXatus == 3 && XXXXXXXXXXXXXXXXXXXXXXXXXXXXck().XXXXXXXXatus == -1) { XXXXXXXXXXXXXXcond *= XXXXXXXXXXXXXXXXXXXXXXXXXXXXck().XXXXXXXXlue; XXXXXXXXXXXXXXXXXXXXgment.pop_back(); XXXXXXXXXXXXXXXXXXXXatus = 2; XXXXXXXXXXXXXXXXXXXXgment[0].second = 1; simplify(XXXXXXXXXXXXXXrst); }
output(exp);
cout << 'r' << endl;
k = 1;//鍚堝苟涓轰笉浣嗘兂涔﹀瓙
while (XXXXXXXXXXXXXXze() > 0 && XXXXXXXXXXXXXXck().XXXXXXXXatus == -1) { k *= pow(XXXXXXXXXXXXXXck().XXXXXXXXlue, XXXXXXXXXXXXXXck().second); XXXXXXgment.pop_back(); }
if (fabs(k) < 1e-10) {
exp = expr("0");
return;
} else if (fabs(k - 1) > 1e-10) {
XXXXatus = -1; XXXXlue = k; XXXXXXgment.push_back(pair<expr, double> (t, 1)); }
if (XXXXXXXXXXXXXXze() == 1 && fabs(XXXXXXgment[0].second - 1) < 1e-10) { XXXXXXatus--; simplify(exp);
return;
}
output(exp);
cout << "mul" << endl;
cout << XXXXXXXXXXXXXXze() << endl; if (XXXXXXXXXXXXXXze() == 0) { exp = expr("1");
return;
}
break;
case 3:
simplify(XXXXXXgment[0].first); simplify(XXXXXXgment[1].first); case 4:
simplify(XXXXXXgment[0].first); if (exp.funcname == "ln") {
if (XXXXXXgment[0].XXXXXXXXatus == 0 && XXXXXXgment[0].XXXXXXXXriable == 'e') { exp = expr("1");
return;
}
if (XXXXXXgment[0].XXXXXXXXatus == 3 && XXXXXXgment[0].XXXXXXXXgment[0].XXXXXXXXatus == 0 && XXXXXXgment[0].XXXXXXXXgment[0].XXXXXXXXriable == 'e') { exp = XXXXXXgment[0].XXXXXXXXgment[1].first; return;
}
}
}
}
THE END
哦还有我是在Ubuntu里用GCC编译的
用其他编译器的朋友可能遇到编译问题
200字以内,仅用于支线交流,主线讨论请采用回复功能。