第三周测验简单的整数划分问题和Boolean Expressions

快来打我* 2022-05-09 03:10 216阅读 0赞

## 006:简单的整数划分问题 ##

描述

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。  
正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。

输入

标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。

输出

对于每组测试数据，输出N的划分数。

样例输入

样例输出

提示

5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

思路参考：[http://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html][http_www.cnblogs.com_dolphin0520_archive_2011_04_04_2005098.html]

整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分，是指把一个正整数n写成如下形式：

n=m1+m2+...+mi; （其中mi为正整数，并且1 <= mi <= n），则\{m1,m2,...,mi\}为n的一个划分。

如果\{m1,m2,...,mi\}中的最大值不超过m，即max(m1,m2,...,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);

> f(n,m)表示将n划分为最大数不超过m的正整数之和的个数。

例如但n=4时，他有5个划分，\{4\},\{3,1\},\{2,2\},\{2,1,1\},\{1,1,1,1\};

注意4=1+3 和 4=3+1被认为是同一个划分。

该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,m)的方法;

递归法：

1. 当n=1时，此时只有1种解\{1\}；

2. 当m=1时，此时也只有1种解\{1,1,1，……\}；

3. 当n > m时，要分为最大数包含m和不包含m两种情况。

*  包含m：此时就是\{m,x1,x2,x3……\}，其中x1+x2+x3+……=n-m，就相当于求和为n-m，最大值为m的划分个数: f(n-m,m)
 *  不包含m：此时最大数最大为m-1，相当于把n划分为最大数为m-1的划分个数：f(n,m-1)

因此：当n>m时划分个数为f（n-m,m）+f (n,m-1)

4. 当n=m时，此时也要分为两种情况，包含m和不包含m。

*  包含m，此时就只有一种情况，\{m\}
 *  不包含m，此时最大值为m-1，f(n,m-1)

因此：当n=m时，划分个数为1+f（n，m-1）；

5. 当n<m时，此时不可能包含m，最大值最大就是n,最大划分个数为f（n,n）。

也可以分为包含n和不包含n两种情况：

*  包含n，此时就只有一种情况，\{n\}；
 *  不包含n，最大值是n-1，f(n,n-1)

因此可以写成1+f(n,n-1).

总结：

f(n, m) = 1; (n=1 or m=1)

f(n,m) = f(n, n); 或者f(n,m)=1+f(n,n-1) (n<m)

1+ f(n, m-1); (n=m)

f(n-m,m)+f(n,m-1); (n>m)

两种代码都正确：

#include<iostream>
    using namespace std;
    
    int f(int n,int m)
    {
    	if(n == 1 || m == 1)
    		return 1;
    	if(n < m)
    		return f(n,n);
    	if(n == m)
    		return 1+f(n,m-1);
    	if(n > m)
    		return f(n-m,m) + f(n,m-1);
    }
    int main()
    {
    	int n;
    	while(cin >> n)
    	{
    		cout << f(n,n) << endl;
    	}
    	return 0;
    }

#include<iostream>
    using namespace std;
    
    int f(int n,int m)
    {
    	if(n == 1 || m == 1)
    		return 1;
    	if(n < m)
    	//	return f(n,n);
    		return 1+f(n,n-1);
    	if(n == m)
    		return 1+f(n,m-1);
    	if(n > m)
    		return f(n-m,m) + f(n,m-1);
    }
    int main()
    {
    	int n;
    	while(cin >> n)
    	{
    		cout << f(n,n) << endl;
    	}
    	return 0;
    }

### 005:Boolean Expressions ###

描述

The objective of the program you are going to produce is to evaluate boolean expressions as the one shown next:

Expression: ( V | V ) & F & ( F | V )

where V is for True, and F is for False. The expressions may include the following operators: ! for not , & for and, | for or , the use of parenthesis for operations grouping is also allowed.  
  
To perform the evaluation of an expression, it will be considered the priority of the operators, the not having the highest, and the or the lowest. The program must yield V or F , as the result for each expression in the input file.

输入

The expressions are of a variable length, although will never exceed 100 symbols. Symbols may be separated by any number of spaces or no spaces at all, therefore, the total length of an expression, as a number of characters, is unknown.  
  
The number of expressions in the input file is variable and will never be greater than 20. Each expression is presented in a new line, as shown below.

输出

For each test expression, print "Expression " followed by its sequence number, ": ", and the resulting value of the corresponding test expression. Separate the output for consecutive test expressions with a new line.  
  
Use the same format as that shown in the sample output shown below.

样例输入

( V | V ) & F & ( F| V)
    !V | V & V & !F & (F | V ) & (!F | F | !V & V)
    (F&F|V|!V&!F&!(F|F&V))

样例输出

Expression 1: F
    Expression 2: V
    Expression 3: V

来源

México and Central America 2004

> 思路：本题可以用栈或者递归解决。用递归时，和之前解决的表达式求值问题一样[https://blog.csdn.net/yanyanwenmeng/article/details/82892681][https_blog.csdn.net_yanyanwenmeng_article_details_82892681]， 将一个字符串根据优先级不同，看成三个部分：表达式、项和因子。
> 
> 表达式:项&项、项|项
> 
> 项：！因子
> 
> 因子：（表达式&表达式）、（表达式|表达式）、或者是单独的&|！组成
> 
> 这样就实现了递归调用。

#include<iostream>
    #include<cstring>
    using namespace std;
    
    bool exp();
    bool term();
    bool factor();
    char s[1000] = {0};
    int m = 0;
    
    bool exp()
    {
    	bool result = term();
    	bool more = true;
    	while(more)
    	{
    		char c = s[m];//相当于cin.peek()只看不取走 
    		if(c == '&' || c == '|')
    		{
    			m++;//取走 
    			bool value = term();
    			if(c == '&')
    				result = result&value;
    			if(c == '|')
    				result = result|value;
    		}
    		else
    			more = false;
    	}
    	return result;
    }
     
    bool term()//！的运算级更高，把他看为一项 
    {
    	bool result;
    	char c = s[m];
    	if(c == '!')
    	{
    		m++;
    		result = !factor();
    	} 
    	else
    	{
    		result = factor();
    	}
    	return result;
    }
     
     
    bool factor()//单独的&|！或者（）看成一个因子 
    {
    	bool result;
    	char c = s[m];
    	if(c == '(')
    	{
    		m++;
    		result = exp();
    		m++;
    	}
    	else if(c == 'V')
    	{
    		result = true;
    		m++;
    	}
    	else if(c == 'F')
    	{
    		result = false;
    		m++;
    	}
    	else if(c == '!')
    	{
    		result = term();
    	}
    	return result;
    }
     
    
    void jieguo()
    {
     	int k = 0;
     	while (cin.getline(s,1000))
     	{
     		char t[1001]={0};
     		int len = strlen(s);
     		for(int i = 0, k = 0; i < len; ++i)
     		{
     			if(s[i] != ' ')
     				t[k++] = s[i];
    		 }
    		 len = strlen(t);
    	 	for(int i = 0; i < len; ++i)
    	 	{
    	 		s[i] = t[i];
    	 	}
    		s[len] = '\0';
    		//去除s[]中的空格 
    		cout << "Expression " << ++k << ": " << (exp()?"V":"F") << endl;
    		//初始化 
    		m = 0;
    		memset(s,0,1000);
    	}
    }
     
    int main()
    {
    	jieguo();
    	return 0;
    }

[http_www.cnblogs.com_dolphin0520_archive_2011_04_04_2005098.html]: http://www.cnblogs.com/dolphin0520/archive/2011/04/04/2005098.html
[https_blog.csdn.net_yanyanwenmeng_article_details_82892681]: https://blog.csdn.net/yanyanwenmeng/article/details/82892681