算法问题(一)–确定数组子序列奇偶性

用递归和非递归方式各写一布尔函数，由该函数获取一个以0或1为元素的数组，并要求确定每个连续为1的序列的大小是否为偶数。

• 形式化地描述该问题，确定采用的数据结构；
• 用递归的思想写出求解该问题的伪码算法；
• 用非递归的思想写出求解该问题的伪码算法；
• 用C++或JAVA等高级程序语言实现上述伪码算法；
• 比较递归和非递归实现的结果，验证算法的正确性，并作时空复杂性分析。

递归思想伪码：

 

main()
{
	if(recursionTest(递归向量))
		返回判断类型
	else
		返回判断类型
}

bool recursionTest(递归向量)
{
	for(循环递归向量中的元素)
	{
		if(元素为0)
			删除元素;
		else
			for(循环递归向量中剩余元素)
			{
				if(元素为1)
					统计次数
					删除元素
				else
					跳出两层循环
			}
	}

	if(向量中的元素为空)
		跳至flag处，跳过接下来的判断，递归出口;

	if(recursionTest(递归向量))
		返回判断类型
	else
		返回判断类型

	flag：
		根据统计次数，判断奇偶
}

非递归思想伪码：

 

main()
{
	while(非递归向量不为空)
	{
		if(iterationTest(非递归向量)
			判断奇偶
		else
			判断奇偶
	}
}

bool iterationTest(非递归向量)
{
	for(循环递归向量中的元素)
	{
		if(元素为0)
			删除元素;
		else
			for(循环递归向量中剩余元素)
			{
				if(元素为1)
					统计次数
					删除元素
				else
					跳出两层循环
			}
	}

	if(根据统计次数，判断奇偶)
		return;
	else
		return;
}

代码实现：实现语言C++：

/*
题目：
用递归和非递归方式各写一布尔函数，
由该函数获取一个以0或1为元素的数组，并要求确定每个连续为1的序列的大小是否为偶数。
（1）形式化地描述该问题，确定采用的数据结构；
（2）用递归的思想写出求解该问题的伪码算法；
（3）用非递归的思想写出求解该问题的伪码算法；
（4）用C++或JAVA等高级程序语言实现上述伪码算法；
（1）比较递归和非递归实现的结果，验证算法的正确性，并作时空复杂性分析。
*/

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>//提供反转方法
using namespace std;

bool iterationTest(vector<int> &b);
bool recursionTest(vector<int> &c);
static int reCountOder = 1;//递归方法的第几个序列
static int countOder=1;//迭代方法的第几个序列

int main()
{
	/*元素为0和1的固定数组*/
	int a[20]={1,0,0,1,1,1,1,0,0,1,1,0,1,1,0,0,0,0,1,1};
	int a_temp[20];//复制数组，两个数组分别为递归方法和非递归方法使用

	cout<<"a向量:";
	for(int i=0;i<20;i++)
	{
		a_temp[i]=a[i];
		cout<<a[i]<<" ";
	}
	cout<<endl;

	/*分别为迭代方法和递归方法定义两个向量*/
	vector<int> b(a,a+20);
	vector<int> c(a_temp,a_temp+20);
	reverse(c.begin(),c.end());

	/*迭代方法，循环获取*/
	cout<<"迭代方法:"<<endl;
	while(!b.empty())
	{
		if(iterationTest(b))
			cout<<"第"<<countOder<<"个序列是:奇数"<<endl;
		else
			cout<<"第"<<countOder<<"个序列是:偶数"<<endl;
		countOder++;
	}

	/*递归方法*/
	cout<<"递归方法:"<<endl;
	if(recursionTest(c))
		cout<<"第"<<reCountOder<<"个序列是:奇数"<<endl;
	else
		cout<<"第"<<reCountOder<<"个序列是:偶数"<<endl;

	cin.get();
	return 0;
}

bool recursionTest(vector<int> &b)
{
	int count=0;//统计次数
	for(vector<int>::iterator iter=b.begin();iter != b.end();)
	{
		if(*iter==0)
			iter = b.erase(iter);//删除为0的元素
		else
		{
			while(iter != b.end())
			{
				if(*iter==1)
				{
					count++;
					iter = b.erase(iter);//为1的元素删除
				}
				else
				{
					goto flag;//跳出两个循环
				}
			}
			flag:break;			
		}
	}

	/*如果向量中的元素已经删除完毕，那么就不再递归，返回这次运行的结果*/
	if(b.empty())
		goto reflag;//递归出口

	if(recursionTest(b))
		cout<<"第"<<reCountOder<<"个序列是:奇数"<<endl;
	else
		cout<<"第"<<reCountOder<<"个序列是:偶数"<<endl;
	reCountOder++;

	reflag:
	if(count % 2)//当count值为偶数时，返回真值
		return true;
	else
		return false;
}

bool iterationTest(vector<int> &b)
{
	int count=0;//统计1出现的次数
	for(vector<int>::iterator iter=b.begin();iter != b.end();)
	{
		if(*iter==0)
			iter = b.erase(iter);
		else
		{
			while(iter != b.end())
			{
				if(*iter==1)
				{
					count++;
					iter = b.erase(iter);
				}
				else
				{
					goto flag;
				}
			}
			flag:break;
		}
	}
	if(count % 2)//当count值为偶数时，返回真值
		return true;
	else
		false;
}

时间复杂度：

非递归方法：

在main函数中有一个while循环，时间复杂度为N，在迭代函数中的有两个for循环，但这两个for循环不是N平方关系，当向量中的元素为0时，删除元素，此时元

素减少，当元素为1时，进入第二个for循环，删除元素，当元素为0时，跳出两层循环。所以此时的时间复杂度也为N。

所以非递归方法的时间复杂度T(n)=O(n2 )

注：其实这里的while循环时间复杂度也并不为N，因为元素在不断得减少，不一定会循环N次。（之后再计算时间复杂度）

递归方法：

在main函数中，if条件句为时间常量，在递归函数中，有两个for循环，与迭代方法同理，这两个for循环的时间复杂度为N。

所以递归方法的时间复杂度为T(n)=O(n)