互联网门户网站是什么,图文广告设计学徒一般要学多久,网站建设工具有哪些,网站建设对宣传的意义计算机软件能力认证考试系统 问题描述
试题编号#xff1a;202309-3试题名称#xff1a;梯度求解时间限制#xff1a;1.0s内存限制#xff1a;512.0MB问题描述#xff1a; 背景 西西艾弗岛运营公司近期在大力推广智能化市政管理系统。这套系统是由西西艾弗岛信息中心研发…
计算机软件能力认证考试系统 问题描述
试题编号202309-3试题名称梯度求解时间限制1.0s内存限制512.0MB问题描述 背景 西西艾弗岛运营公司近期在大力推广智能化市政管理系统。这套系统是由西西艾弗岛信息中心研发的。它的主要目的是通过详细评估岛上各处的市政设施的状况来指导市政设施的维护和更新。这套系统的核心是一套智能化的传感器网络它能够自动地对岛上的市政设施进行评估。对市政设施的维护是需要一定成本的而年久失修的市政设施也可能给岛上的居民造成损失。为了能够平衡成本和收益信息中心研发了一款数学模型描述这些变量和损益之间的复杂数学关系。要想得到最优化的成本就要依靠梯度下降算法来求解。 梯度下降算法中求解函数在一点处对某一自变量的偏导数是十分重要的。小 C 负责实现这个功能但是具体的技术实现他还是一头雾水希望你来帮助他完成这个任务。 问题描述 设被求算的函数 uf(x1,x2,…,xn)本题目要求你求出 u 对 xi 在 (a1,a2,…,an) 处的偏导数 ∂u∂xi(a1,a2,…,an)。 求算多元函数在一点处对某一自变量的偏导数的方法是将函数的该自变量视为单一自变量其余自变量认为是常数运用一元函数求导的方法求出该偏导数表达式再代入被求算的点的坐标即可。 例如要求算 ux1⋅x1⋅x2 对 x1 在 (1,2) 处的偏导数可以将 x2 视为常数依次应用求导公式。先应用乘法的求导公式(x1⋅(x1⋅x2))′x1′(x1⋅x2)x1(x1⋅x2)′再应用常数与变量相乘的求导公式得到 x1′⋅x1⋅x2x1⋅x2⋅x1′最后应用公式 x′1 得到 1⋅x1⋅x2x1⋅x2⋅1。整理得 ∂u∂x12x2⋅x1。再代入 (1,2) 得到 ∂u∂x1(1,2)4。 常见的求导公式有 是常数c′0 c是常数 x′1 (uv)′u′v′ 是常数(cu)′cu′ c是常数 (u−v)′u′−v′ (uv)′u′vuv′ 本题目中你需要求解的函数 f 仅由常数、自变量和它们的加法、减法、乘法组成。且为程序识读方便函数表达式已经被整理为逆波兰式后缀表达式的形式。例如x1⋅x1⋅x2 的逆波兰式为 x1 x1 * x2 *。逆波兰式即为表达式树的后序遍历的结果。若要从逆波兰式还原原始计算算式可以按照这一方法进行假设存在一个空栈 S依次读取逆波兰式的每一个元素若读取到的是变量或常量则将其压入 S 中若读取到的是计算符号则从 S 中取出两个元素进行相应运算再将结果压入 S 中。最后若 S 中存在唯一的元素则该表达式合法其值即为该元素的值。例如对于逆波兰式 x1 x1 * x2 *按上述方法读取栈 S 的变化情况依次为左侧是栈底右侧是栈顶 x1 x1x1 (x1⋅x1) (x1⋅x1)x2 ((x1⋅x1)⋅x2)。 输入格式 从标准输入读入数据。 输入的第一行是由空格分隔的两个正整数 n、m分别表示要求解函数中所含自变量的个数和要求解的偏导数的个数。 输入的第二行是一个逆波兰式表示要求解的函数 f。其中每个元素用一个空格分隔每个元素可能是 一个自变量 xi用字符 x 后接一个正整数表示表示第 i 个自变量其中 i1,2,…,n。例如x1 表示第一个自变量 x1。 一个整常数用十进制整数表示其值在 −105 到 105 之间。 一个运算符用 表示加法- 表示减法* 表示乘法。 输入的第三行到第 m2 行每行有 n1 个用空格分隔的整数。其中第一个整数是要求偏导数的自变量的编号 i1,2,…,n随后的整数是要求算的点的坐标 a1,a2,…,an。 输入数据保证对于所有的 i1,2,…,nai 都在 −105 到 105 之间。 输出格式 输出到标准输出中。 输出 m 行每行一个整数表示对应的偏导数对 1097 取模的结果。即若结果为 y输出为 k则保证存在整数 t满足 ykt⋅(1097) 且 0≤k1097。 样例 1 输入 2 2 x1 x1 x1 * x2 * 1 2 3 2 3 4 样例 1 输出 15 3 样例 1 说明 读取逆波兰式可得被求导的式子是ux1⋅(x1⋅x1x2)即 ux13x1x2。 对 x1 求偏导得 ∂u∂x13x12x2。代入 (2,3) 得到 ∂u∂x1(2,3)15。 对 x2 求偏导得 ∂u∂x2x1。代入 (3,4) 得到 ∂u∂x2(3,4)3。 样例 2 输入 3 5 x2 x2 * x2 * 0 -100000 -100000 * x2 * - 3 100000 100000 100000 2 0 0 0 2 0 -1 0 2 0 1 0 2 0 100000 0 样例 2 输出 0 70 73 73 999999867 样例 2 说明 读取逆波兰式可得被求导的式子是ux2⋅x2⋅x20−(−105)⋅(−105)⋅x2即 ux23−1010x2。 因为 u 中实际上不含 x1 和 x3对这两者求偏导结果均为 0。 对 x2 求偏导得 ∂u∂x23x22−1010。 评测用例规模与约定 测试点 n m 表达式的性质 1, 2 1 ≤100 仅含有 1 个元素 3, 4 1 ≤100 仅含有一个运算符 5, 6 ≤10 ≤100 含有不超过 120 个元素且不含乘法 7, 8 ≤10 ≤100 含有不超过 120 个元素 9, 10 ≤100 ≤100 含有不超过 120 个元素 提示 C 中可以使用 std::getline(std::cin, str) 读入字符串直到行尾。 当计算整数 n 对 M 的模时若 n 为负数需要注意将结果调整至区间 [0,M) 内。 解析
参考来源第31次CCF计算机软件能力认证 - ~Lanly~ - 博客园 (cnblogs.com)
从题目中可以看逆波兰式就是表达树的后序遍历所以我们可以利用二叉树的递归遍历进行求解。
同时我们可以利用vector向量建立二叉树用链表也行但是会比较麻烦。
具体请看代码
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
using namespace std;
typedef long long LL;
#define CH 1
#define CONST 2
#define OP 3
const int mod 1e9 7;
int n, m;
vectorintlc;
vectorintrc;
vectorintinfo;
vectorintkind;
stackintstk;
vectorinta(200);
// 定义递归函数 solve计算表达式树节点的值和导数
pairint, int solve(int u, int x) {if (kind[u] CH) {return pairint, int{a[info[u]], (info[u] x)};}else if (kind[u] CONST) {return pairint, int{info[u], 0};}else {auto lans solve(lc[u], x), rans solve(rc[u], x);int sum 0, dsum 0;if (info[u] ) {sum lans.first rans.first;dsum lans.second rans.second;}else if (info[u] -) {sum lans.first - rans.first;dsum lans.second - rans.second;}else {sum 1ll*lans.first * rans.first % mod;dsum (1ll*lans.first * rans.second%mod 1ll*lans.second * rans.first%mod);//1ll 是一种常见的编码技巧用于将数字字面量转换为长长整型long long类型。}sum (sum % mod mod) % mod;dsum (dsum % mod mod) % mod;return pairint, int{sum, dsum};}
}
int main() {cin n m;string s;getline(cin, s);getline(cin, s);int cnt 0;istringstream q(s);//q 是一个 istringstream 对象用于从字符串中读取数据。//getline(qwq, s, ) 是 C 中的输入流操作//用于从输入流 qwq 中读取一行以换行符 \n 结束的一行并存储到字符串 s 中//直到遇到指定的分隔符在这里是空格 为止。while (getline(q, s, )) {if (s.size() 1 (s[0] || s[0] * || s[0] -)) {int rson stk.top();stk.pop();int lson stk.top();stk.pop();lc.push_back(lson);rc.push_back(rson);info.push_back(s[0]);kind.push_back(OP);stk.push(cnt);cnt;}else if (s[0] x) {int x stoi(s.substr(1));//subStr 是从第二个字符开始的子串,stoi 将其转换为整数。x--;lc.push_back(-1);rc.push_back(-1);info.push_back(x);kind.push_back(CH);stk.push(cnt);cnt;}else {int x stoi(s);lc.push_back(-1);rc.push_back(-1);info.push_back(x);kind.push_back(CONST);stk.push(cnt);cnt;}}int root stk.top();// 处理每个查询for (int i 1; i m; i) {int x;cin x;x--;//由于我们是从0开始记录所以这里要-1for (int j 0; j n; j) {cin a[j];}cout solve(root, x).second endl;}return 0;
}
