作业8-栈与递归(防止题目重复)

野性酷女 2022-12-27 01:19 212阅读 0赞

2-1  
令P代表入栈，O代表出栈。若利用堆栈将中缀表达式3\*2+8/4  
转为后缀表达式，则相应的堆栈操作序列是：©  
A.PPPOOO  
B.POPOPO  
C.POPPOO  
D.PPOOPO  
\[解析\]没看懂题目什么意思  
(ps: 我好想又看懂了, 栈用来存放暂时没有进行运算的 运算符,  
另外还有一个存放输出内容的队列, 输出的内容就是后缀表达式)  
栈:\# \*§ (O) + § /§ (O) (O)  
输出队列:3 2 \* 8 4 / +  
所以答案是POPPOO

2-2  
若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，  
当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？()  
A.+(*\+  
B.+(+  
C.++(+  
D.abcde  
\[解析\]  
https://blog.csdn.net/qq\_27445903/article/details/73195561

2-3  
表达式a\*(b+c)-d的后缀表达式是：(A)  
A.a b c + \* d -  
B.a b c d \* + -  
C.a b c \* + d -  
D.- + \* a b c d  
\[解析\]  
至此,我在重新重新总结一下 如何根据中缀表达式 求 后缀表达式  
首先 往栈 压入 \#(最低级符号)  
然后遇到数字直接 放到队列中  
遇到运算符: 若 此时的运算符 比 栈顶的运算符等级 低 或 相等  
那么将 栈顶元素弹出 并放入 队列中  
然后 再将 刚才的运算符 和栈顶元素 比较  
只到 此时的运算符 的等级 比栈顶元素 等级要高, 然后 向栈内 压入 该符号  
对于 ( 直接 压入 栈内, 之后 和 正常操作一样, 该压栈压栈,该出栈出栈  
直到 访问到 ) 将 则直接将栈中元素弹出并输出直到遇到”(“为止。

输出队列:a b c + \* d  
栈:

#  #

P(*) \# \*  
P(() \# \* (  
P(+) \# \* ( +  
O(+) \# \* (  
O(() \# \*  
O(*) \#

6-1 递归实现指数函数 (15分)

本题要求实现一个计算xn（n≥1）的函数。  
函数接口定义：

double calc\_pow( double x, int n );

函数calc\_pow应返回x的n次幂的值。建议用递归实现。  
题目保证结果在双精度范围内。

#include <stdio.h>
    
    double calc_pow( double x, int n )
    {
        
    	if (n == 0) return 1;
    	return 	x * calc_pow(x, n-1);
    }
    
    int main()
    {
        
        double x;
        int n;
    
        scanf("%lf %d", &x, &n);
        printf("%.0f\n", calc_pow(x, n));
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

6-2 递归计算Ackermenn函数 (15分)

本题要求实现Ackermenn函数的计算，其函数定义如下：

函数接口定义：

int Ack( int m, int n );

其中m和n是用户传入的非负整数。  
函数Ack返回Ackermenn函数的相应值。题目保证输入输出都在长整型

范围内。  
裁判测试程序样例：

#include <stdio.h>
    
    int Ack( int m, int n )
    {
        
    	if (m == 0) return n + 1;
    	else if (n == 0 && m > 0) return Ack(m-1, 1);
    	else if (n > 0 && m > 0) return Ack(m-1, Ack(m, n-1));
    }
    
    int main()
    {
        
        int m, n;
    
        scanf("%d %d", &m, &n);
        printf("%d\n", Ack(m, n));
    
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

6-3 递归求Fabonacci数列 (10分)

本题要求实现求Fabonacci数列项的函数。Fabonacci数列的定义如下：

f(n)=f(n−2)+f(n−1) (n≥2)，其中f(0)=0，f(1)=1。  
函数接口定义：

int f( int n );

函数f应返回第n个Fabonacci数。题目保证输入输出在长整型范围内。建议用递归实现。  
裁判测试程序样例：

#include <stdio.h>
    
    int f( int n )
    {
        
    	if (n == 0) return 0;
    	else if (n == 1) return 1;
    	else return f(n-2) + f(n-1);
    }
    
    int main()
    {
        
        int n;
    
        scanf("%d", &n);
        printf("%d\n", f(n));
    
        return 0;
    }

/\* 你的代码将被嵌在这里 \*/

6-4 十进制转换二进制 (15分)

本题要求实现一个函数，将正整数n转换为二进制后输出。  
函数接口定义：

void dectobin( int n );

函数dectobin应在一行中打印出二进制的n。建议用递归实现。  
裁判测试程序样例：

#include <stdio.h>
    #include <iostream>
    using namespace std;
    
    //说实话,这里我并不太理解,我在思考一下
    void dectobin( int n )
    {
        
    	//我改成了我能理解的 代码
    	当 输入的 十进制数 是0 的时候 直接输出 0
    	if (n == 0)
    	{
        
    		cout << 0;
    		return ;
    	}
    	若 参数n 不是0
    	else 
    	{
        
    		如参数是1 不再递归
    		否则继续递归
    		if (n == 1)
    			dectobin(n / 2);
    		递归完 在输出本位的值, 类似于 出栈
    		cout << n % 2;
    	}
    }
    
    int main()
    {
        
        int n;
    
        scanf("%d", &n);
        dectobin(n);
    	system("pause");
        return 0;
    }

6-5 递归计算P函数 (15分)

本题要求实现下列函数P(n,x)的计算，其函数定义如下：

函数接口定义：

double P( int n, double x );

其中n是用户传入的非负整数，x是双精度浮点数。函数P返回P(n,x)函数的相应值。题目保证输入输出都在双精度范围内。  
裁判测试程序样例：

#include <stdio.h>
    #include <iostream>
    using namespace std;
    
    double P( int n, double x )
    {
        
    	if (n == 0) return 1;
    	else if (n == 1) return x;
    	else if (n > 1) 
    	{
        
    		return ((2*n-1) * P(n-1, x) - (n-1) * P(n-2, x)) / n;
    	}
    }
    int main()
    {
        
        int n;
        double x;
    
        scanf("%d %lf", &n, &x);
        printf("%.2f\n", P(n,x));
    	system("pause");
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */

7-1 整数分解为若干项之和 (20分)

将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。  
输入格式：

每个输入包含一个测试用例，即正整数N (0<N≤30)。  
输出格式：

按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N1=\{n1,n2,⋯\}和N2=\{m1,m2,⋯\}，若存在i使得n1=m1,⋯,ni=mi，但是ni+1<mi+1,则N1序列必定在N2序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。  
输入样例：

输出样例：

7=1+1+1+1+1+1+1;7=1+1+1+1+1+2;7=1+1+1+1+3;7=1+1+1+2+2  
7=1+1+1+4;7=1+1+2+3;7=1+1+5;7=1+2+2+2  
7=1+2+4;7=1+3+3;7=1+6;7=2+2+3  
7=2+5;7=3+4;7=7

#include <iostream>
    
    using namespace std;
    const int MAXNUM = 1e3 + 5;
    
    int cnt = 0;
    int n;
    int arr[MAXNUM];
    
    void f(int pos, int last, int left)
    {
        
    	if (left == 0)
    	{
        
    		cnt++;
    		for (int i = 1; i < pos; i++)
    		{
        
    			if (i == 1)
    				cout << n << "=" << arr[i];
    			else 
    				cout << "+" << arr[i];
    		}
    		if (cnt % 4 == 0)
    			cout << endl;
    		else 
    			cout << ";";
    	}
    	else 
    	{
        
    		for (int i = last; i <= left; i++)
    		{
        
    			arr[pos] = i;
    			f(pos + 1, i, left - i);
    		}
    	}
    }
    int main()
    {
        
    	cin >> n;
    	for(int i = 1; i <= n/2; i++)
    	{
        
    		arr[1] = i;
    		f(2, i, n - i);
    	}
    	
    	cnt++;
    	cout << n << "=" << n << endl;
    	system("pause");
    	return 0;
    }

7-2 输出全排列 (20分)

请编写程序输出前n个正整数的全排列（n<10），并通过9个测试用例（即n从1到9）观察n逐步增大时程序的运行时间。  
输入格式:

输入给出正整数n（<10）。  
输出格式:

输出1到n的全排列。每种排列占一行，数字间无空格。排列的输出顺序为字典序，即序列a1,a2,⋯,an排在序列b1,b2,⋯,bn之前，如果存在k使得a1=b1,⋯,ak=bk 并且 ak+1<bk+1。  
输入样例：

输出样例：

123  
132  
213  
231  
312  
321

#include <iostream>
    #include <cstring>
    using namespace std;
    const int MAXNUM = 1e3 + 5;
    int vis[MAXNUM];
    int arr[MAXNUM];
    int n;
    void f(int pos)
    {
        
    	if (pos > n)
    	{
        
    		for (int i = 1; i <= n; i++)
    			cout << arr[i];
    		cout << endl;
    	}
    	else 
    	{
        
    		for (int i = 1; i <= n; i++)
    		{
        
    			if (vis[i] != 1)
    			{
        
    				arr[pos] = i;
    				vis[i] = 1;
    				f(pos + 1);
    				vis[i] = 0;
    			}
    		}
    	}
    }
    int main()
    {
        
    	memset(vis, 0, sizeof(vis));
    	cin >> n;
    	f(1);
    	system("pause");
    	return 0;
    }

7-3 求前缀表达式的值 (25分)

算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3\*(7-4)+8/4的前缀表达式是：+ + 2 \* 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。  
输入格式:

输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、\*、/以及运算数，不同对象（运算数、运算符号）之间以空格分隔。  
输出格式:

输出前缀表达式的运算结果，保留小数点后1位，或错误信息ERROR。  
输入样例:

*   *  2 \* 3 - 7 4 / 8 4

输出样例:

13.0

#include <iostream>
    #include <string>
    #include <sstream>
    using namespace std;
    const int MAXNUM = 1e2 + 5;
    const int STACK_INIT_SIZE = 100;
    const int STACKINCREMENT = 10;
    
    #define OVERFLOW -2
    #define OK 1
    #define FALSE 0
    typedef int Status;
    typedef double SElemType;
    typedef struct 
    {
        
    	SElemType *base;
    	SElemType *top;
    	int stacksize;
    }Stack;
    
    void InitStack(Stack &S)
    {
        
    	S.base = (SElemType*)malloc(sizeof(SElemType) * STACK_INIT_SIZE);
    	if (S.base == NULL) exit(OVERFLOW);
    	S.top = S.base;
    	S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(Stack &S)
    {
        
    	free(S.base);
    	S.base = NULL;
    	S.top = NULL;
    	S.stacksize = 0;
    }
    
    Status Push(Stack &S, SElemType e)
    {
        
    	if (S.top - S.base == S.stacksize)
    	{
        
    		S.base = (SElemType*)realloc(S.base, sizeof(SElemType) * (S.stacksize + STACKINCREMENT));
    		if (S.base == NULL) exit(OVERFLOW);
    		S.stacksize += STACKINCREMENT;
    	}
    	*S.top = e;
    	S.top++;
    	return OK;
    }
    
    Status Pop(Stack &S, SElemType &e)
    {
        
    	if (S.base == S.top) return FALSE;
    	else 
    	{
        
    		e = *(S.top - 1);
    		S.top--;
    		return OK;
    	}
    }
    
    bool EmptyStack(Stack S)
    {
        
    	if (S.base == S.top) return true;
    	else return false;
    }
    int StackLength(Stack S)
    {
        
    	return S.top - S.base;
    }
    
    void getTop(Stack S, SElemType &e)
    {
        
    	e = *(S.top - 1);
    }
    int n = 0;
    string elem[MAXNUM];
    int main()
    {
        
    	int errors = 0;
    	string str;
    	Stack S;
    	InitStack(S);
    	
    	getline(cin, str);
    	stringstream ss(str);
    	while (ss >> elem[n]) {
         n++; }
    	
    	for (int i = n-1; i >= 0; i--)
    	{
        
    		if (elem[i][0] == '+' || elem[i][0] == '-'|| elem[i][0] == '*'|| elem[i][0] == '/')
    		{
        
    			if (StackLength(S) <= 1)
    			{
        
    				errors++;
    				break;
    			}
    			else 
    			{
        
    				double temp1, temp2;
    				Pop(S, temp1);
    				Pop(S, temp2);
    				if (elem[i][0] == '+')
    					Push(S, temp1 + temp2);
    				else if (elem[i][0] == '-')
    					Push(S, temp1 - temp2);
    				else if (elem[i][0] == '*')
    					Push(S, temp1 * temp2);
    				else if (elem[i][0] == '/')
    				{
        
    					if (temp2 == 0)
    					{
        
    						errors++;
    						break;
    					}
    					Push(S, temp1 / temp2);
    				}
    			}
    			
    		}
    		else 
    		{
        
    			double num;
    			num = atof(elem[i].c_str());
    			Push(S, num);
    		}
    	}
    	if (errors > 0 || (errors == 0 && StackLength(S) != 1))
    	{
        
    		cout << "ERROR" << endl;
    	}
    	else 
    	{
        
    		double num;
    		getTop(S, num);
    		printf("%.1lf\n", num);
    	}
    	system("pause");
    	return 0;
    }