网站建设皿金手指谷哥壹柒,做销售平台哪个网站好,重庆奉节网站建设公司推荐,新乡网站建设新乡202309-3-梯度求解 题目链接 http://118.190.20.162/view.page?gpidT173 最近刚刚在上数据结构二叉树 跟这道题真的是强相关 然后在就是涉及到了数学求导 这基本上是我复学两个月做的最久的题了 感觉做完这道题对栈和二叉树理解比以前清晰了很多 不摆了 上代码 ** 题目思路T173 最近刚刚在上数据结构二叉树 跟这道题真的是强相关 然后在就是涉及到了数学求导 这基本上是我复学两个月做的最久的题了 感觉做完这道题对栈和二叉树理解比以前清晰了很多 不摆了 上代码 ** 题目思路 题意是给我们一个后缀表达式 显然我们就可以写出这个表达式 那么怎么来实现求导呢 不妨讨论常数求导equal 0 偏导的未知数求导equal 1 其他符号 a ±b求导equal a导 ±b导 这样我们是不是就可以递归实现求导呢 分析可得做题步骤 1利用栈来建立二叉树存表达式因为是后缀表示所以唯一可以考虑只使用一个栈 2dfs遍历求导并将结果存在二叉树里面 3带入计算最重要的是要取模运算可恶 **
/*
*/
#includebits/stdc.h
using namespace std;
#define ll long long
typedef pairint,int pi ;
#define if1(x) for(int i 1 ;ix;i)
#define if0(x) for(int i 0;ix;i)
#define jf0(x) for(int j 0;jx;j)
const int mod 1e97;
const int inf 0x3f3f3f3f;
int m,n,idx;
struct node{int vis_num;//1表示他是数字0表示他是未知数//2表示他是操作符号,3表示求偏导的未知数int x;ll val;char op;//既然要存树那么不妨使用数组来存树int fa;int l;int r;int myself;
};
node tree[550];
//vectornode tree;
vectorint xs(200);
int xans;//存储偏导未知数的位置
string s;
node retu0,retux,retu1;
stacknode sta_num;
void push_num(string x){int num stoi(x);node te *new(node);te.vis_num1;te.val num;te.fa te.l te.r -1;tree[idx] te;te.myself idx;// tree.push_back(te)sta_num.push(te);}
node dfs(node root){
//分析讨论vis的三种状态
//当节点未数字时求导直接返回0if(root.vis_num1) return retu0;//数字求导的结果就是0//当节点遇到x时求导时应该分两种情况判断else if(root.vis_num0){
//若x是我们所求的偏导我们就应该返回retuxif(root.xxans) return retu1;
//若x不是是我们所求未知数的偏导
//则我们应该视为常数我们就应该返回0else return retu0;}//ok写到这里应该是此代码最复杂的一部分
//a*b)求导a导*bb导*aelse if(root.op*){//注意我们还应该给新分配的三个节点一个idx来存下来node rnode *new(node);node lnode *new(node);node father *new(node);// tree.push_back(rnode);// tree.push_back(lnode);// tree.push_back(father);//先写一下左边巴lnode.vis_num2;lnode.op *;lnode.l root.l;lnode.r dfs(tree[root.r]).myself;lnode.fa father.myself;tree[idx] lnode;lnode.myself idx;//写右边rnode.vis_num 2;rnode.op*;rnode.r root.r;rnode.l dfs(tree[root.l]).myself;rnode.fa father.myself;tree[idx] rnode;rnode.myself idx;//写她爹father.vis_num 2;father.op ;father.r rnode.myself;father.l lnode.myself;tree[idx] father;father.myself idx;return father;}//op是-的时候很明显就是l导-r导else{node father *new(node);father.fa father.l father.r -1;father.vis_num2;father.op root.op;father.r dfs(tree[root.r]).myself;father.l dfs(tree[root.l]).myself;father.myself idx;tree[idx] father;return father;}
}
void init(){retu0.fa retu0.lretu0.r-1;retu0.vis_num1;retu0.val0;retu0.myself -2;//特殊给0retu1.fa retu1.rretu1.l-1;retu1.vis_num1;//特殊给一个。retu1.val 1;retu1.myself-4;retux.fa retux.l retux.r-1;retux.vis_num 3;retux.myself -3;//特殊给未知数的下标return;
}
ll caculate(node root){if(root.vis_num1)return root.val;//遇到计算偏导x时else if(root.vis_num3)return xs[xans];//通过处理我们可以肯定dfs后再无vis——num0就是未知数的情况了//写在后面根本特殊处理不了一点点//因为它有些是在*-里面的未知数else if(root.vis_num0) return xs[root.x];else{//现在就是开始运算了ll a , b ;if(root.l0){if(root.l -2) a0;else if(root.l -3) a xs[xans];else if(root.l-4) a 1;}else a caculate(tree[root.l]);if(root.r0){if(root.r -2) b0;else if(root.r -3) b xs[xans];else if(root.r -4) b 1;}else b caculate(tree[root.r]);if(root.op){return ((a%mod)(b%mod))%mod;}else if(root.op-){return ((a%mod)-(b%mod))%mod;}else{return (a%mod)*(b%mod)%mod;}}
}
void solve(){init();cinnm;//n-自变量m-求偏导的次数getchar();getline(cin,s);int le s.size();if0(le){//split 操作int j i1;while(s[j]! jle)j;string temp s.substr(i,j-i);//为数字if((temp[0]0temp[0]9)||temp[0]-ji1){push_num(temp);}//为未知数的时候else if(temp[0]x){int te stoi(temp.substr(1,temp.size()-1));node tt *new(node);tt.vis_num0;tt.xte;tt.fa tt.l tt.r -1;tree[idx]tt;tt.myself idx;//tree.push_back(tt);sta_num.push(tt);}else {//通过简单分析哈我们在遇到操作符号的时候可以更新//一下树不如直接存树node te *new(node);te.vis_num2;te.op temp[0];te.fa -1;te.r sta_num.top().myself;sta_num.pop();te.l sta_num.top().myself;sta_num.pop();tree[idx] te;te.myself idx;sta_num.push(te);}ij;//1st--bug因为for它自己已经加一辣}//存树结束if0(m){int temp_idx idx;//考虑后面我们可以释放一波内存//既然写的这么认真了那么在内存方面也可以考虑变得更优。cinxans;//读入偏导xjf0(n)cinxs[j1];//读入x的赋值因为我们在建树的时候//我们直接存的是x的下标所以未便于调用从1开始存。//简单讨论最后栈的唯一元素便是根节点。node ans dfs(sta_num.top());ll res caculate(ans)%mod;res (resmod)%mod;coutresendl;idx temp_idx;}}
int main(){solve();// getchar();return 0;
}
