深圳网站制作哪里好,广州顺德网站设计,营销官网,阜阳做网站公司目录
1. 计算阶乘的和 ★
2. 基本计算器 ★★★
3. N皇后 II ★★★
#x1f31f; 每日一练刷题专栏
C/C 每日一练 专栏
Python 每日一练 专栏 1. 计算阶乘的和
计算#xff1a;1!-2!3!-4!5!-6!7!-8!9!-10!#xff0c;并输出计算结果。
注意#xff1a;不全是…
目录
1. 计算阶乘的和 ★
2. 基本计算器 ★★★
3. N皇后 II ★★★ 每日一练刷题专栏
C/C 每日一练 专栏
Python 每日一练 专栏 1. 计算阶乘的和
计算1!-2!3!-4!5!-6!7!-8!9!-10!并输出计算结果。
注意不全是加法而是 ∑ n! * (-1)^(n-1)加减混合的“代数和”。
代码
#include stdio.h
double fun(int n)
{double sum1.0;int i;for(i1;in;i)sum*i;return sum;
}int main()
{int i,mark1;double sum0,item0;for(i1;i10;i){itemmark*fun(i);sumitem;mark-mark;}printf(1!-2!3!-4!5!-6!7!-8!9!-10! %.0lf\n,sum);return 0;
}
输出
1!-2!3!-4!5!-6!7!-8!9!-10! -3301819 也可以不用像上面原题附带的代码一样自定义阶乘函数其实只用一个循环就能搞定非常简洁
#include stdio.h
int main() { long sum0, fac-1; for(int i1;i10;i) { fac * -i; sum fac; } printf(1!-2!3!-4!5!-6!7!-8!9!-10! %ld\n, sum); return 0; } 2. 基本计算器
给你一个字符串表达式 s 请你实现一个基本计算器来计算并返回它的值。
示例 1
输入s 1 1
输出2示例 2
输入s 2-1 2
输出3示例 3
输入s (1(452)-3)(68)
输出23提示
1 s.length 3 * 10^5s 由数字、、-、(、)、和 组成s 表示一个有效的表达式
代码
#include bits/stdc.h
using namespace std;class Solution
{
public:int calculate(string s){stackint myStack;stackchar myOperator;int i;for (i 0; i s.length(); i){while (i s.length() s[i] )i;if (i s.length())break;if (s[i] || s[i] - || s[i] ()myOperator.push(s[i]);else if (s[i] )){while (myOperator.top() ! (){int element1 myStack.top();myStack.pop();int element2 myStack.top();myStack.pop();char op myOperator.top();myOperator.pop();if (op )myStack.push(element1 element2);else if (op -)myStack.push(element2 - element1);}if (!myOperator.empty())myOperator.pop();while (!myOperator.empty() (myOperator.top() ! ()){int element1 myStack.top();myStack.pop();int element2 myStack.top();myStack.pop();char op myOperator.top();myOperator.pop();if (op )myStack.push(element1 element2);else if (op -)myStack.push(element2 - element1);}}else{long long int number 0;int j i;while (j s.length() (s[j] - 0 9) (s[j] - 0 0)){number number * 10 (s[j] - 0);j;}i j - 1;myStack.push(number);while (!myOperator.empty() (myOperator.top() ! ()){int element1 myStack.top();myStack.pop();int element2 myStack.top();myStack.pop();char op myOperator.top();myOperator.pop();if (op )myStack.push(element1 element2);else if (op -)myStack.push(element2 - element1);}}}return myStack.top();}
};int main()
{Solution sol;string s 1 1;cout sol.calculate(s) endl;s 2-1 2;cout sol.calculate(s) endl;s (1(452)-3)(68);cout sol.calculate(s) endl;return 0;
}
输出
2 3 23 3. N皇后 II
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。
给你一个整数 n 返回 n 皇后问题 不同的解决方案的数量。
示例 1 输入n 4
输出2
解释如上图所示4 皇后问题存在两个不同的解法。示例 2
输入n 1
输出1提示
1 n 9皇后彼此不能相互攻击也就是说任何两个皇后都不能处于同一条横行、纵行或斜线上。
代码
#include bits/stdc.h
using namespace std;class Solution
{
public:int totalNQueens(int n){vectorint stack(n);return dfs(n, 0, stack);}
private:int dfs(int n, int row, vectorint stack){int count 0;if (row n){return count 1;}else{for (int i 0; i n; i){if (row 0 || !conflict(stack, row, i)){stack[row] i;count dfs(n, row 1, stack);}}return count;}}bool conflict(vectorint stack, int row, int col){for (int i 0; i row; i){if (col stack[i] || abs(row - i) abs(col - stack[i])){return true;}}return false;}
};int main()
{Solution sol;cout sol.totalNQueens(4) endl;cout sol.totalNQueens(1) endl;return 0;
}
输出
2 1 附录
贪心算法
又称贪婪算法 greedy algorithm 是指在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑算法得到的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解关键是贪心策略的选择。
一般步骤 ①建立数学模型来描述问题 。 ②把求解的问题分成若干个子问题 。 ③对每个子问题求解得到子问题的局部最优解 。 ④把子问题的解局部最优解合成原来解问题的一个解 。
贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。贪心算法的特点是一步一步地进行常以当前情况为基础根据某个优化测度作最优选择而不考虑各种可能的整体情况省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法采用自顶向下以迭代的方法做出相继的贪心选择每做一次贪心选择就将所求问题简化为一个规模更小的子问题通过每一步贪心选择可得到问题的一个最优解。虽然每一步上都要保证能获得局部最优解但由此产生的全局解有时不一定是最优的所以贪心算法不要回溯 。
使用条件
利用贪心法求解的问题应具备如下2个特征
1、贪心选择性质
一个问题的整体最优解可通过一系列局部的最优解的选择达到并且每次的选择可以依赖以前作出的选择但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题要确定它是否具有贪心选择性质必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2、最优子结构性质
当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。在实际应用中至于什么问题具有什么样的贪心选择性质是不确定的需要具体问题具体分析。
存在问题 贪心算法也存在如下问题 1、不能保证解是最佳的。因为贪心算法总是从局部出发并没从整体考虑 2、贪心算法一般用来解决求最大或最小解 3、贪心算法只能确定某些问题的可行性范围 。
应用实例
例如平时购物找零钱时为使找回的零钱的硬币数最少不要求找零钱的所有方案而是从最大面值的币种开始按递减的顺序考虑各面额先尽量用大面值的面额当不足大面值时才去考虑下一个较小面值这就是贪心算法。 有很多经典的应用比如霍夫曼编码普利姆和克鲁斯卡尔最小生成树算法还有迪杰斯特拉单源最短路径算法都是使用了这种思维。 (附录部分摘自百度百科) 每日一练刷题专栏
✨ 持续努力奋斗做强刷题搬运工 点赞你的认可是我坚持的动力
★ 收藏你的青睐是我努力的方向
✏️ 评论你的意见是我进步的财富
C/C 每日一练 专栏 Python 每日一练 专栏
