首页 > 代码库 > 每日一小练——最长平台问题

每日一小练——最长平台问题

2024-07-04 00:21:19   225人阅读

上得厅堂，下得厨房，写得代码，翻得围墙，欢迎来到睿不可挡的每日一小练！


题目：最长平台问题


内容：一直一个已经从小到大排序的数组，这个数组中的一个平台就是连续的一串相同的元素，并且这个元素不能再延伸。

例如，在1,2,2,3,3,3,4,5,5,6中1,2,2,3,3,3,4,5,5,6都是平台.试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。在这个例子中, 3,3,3就是该数组的中的最长的平台。


说明：
这个程序十分简单，但是编写好却不容易，因此在编写程序时应注意考虑下面几点：
  1.使用变量越少越好
  2.能否只把数组的元素每一个都只查一次就得到结果。
  3.程序语句越少越好。

ps：这个问题曾经困扰过David Gries这位知名的计算机科学家。


我的解法：上来没多想，打开vs2013就敲了起来，问题果然很简单，分分钟就超神。。奥，不对就解决了！

#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	int index = 0;             //数组下标索引
	int indexEnd = 0;          //目标索引
	int count = 0;             //计数器
	int tempCount = 0;         //临时计数器
	int arrayNum[100] = { 0 }; //零不算输入元素，所以结尾判零即可
	cout << "请输入一个数字序列，数字间以空格隔开，用0表示输入结束:" << endl;
	while((cin >> arrayNum[index])&&arrayNum[index]!=0)
		++index;
	index = 0;
	while (arrayNum[index] != 0)
	{		
		//cout << arrayNum[index] << endl;
		if (arrayNum[index + 1] != 0)
		{
			if (arrayNum[index] == arrayNum[index + 1])
			{
				tempCount++;
			}
			else
			{
				if (tempCount > count)
				{
					count = tempCount;
					indexEnd = index;
				}
				tempCount = 0;
			}
		}
		++index;
	}
	cout << "输入数字序列为：" << endl;
	index = 0;
	while (arrayNum[index] != 0)
	{
		cout << arrayNum[index];
		++index;
	}
	cout << endl;
	cout << "最大的平台是：" << endl;
	cout << arrayNum[indexEnd] <<endl;
	cout << "连续次数为：" << endl;
	cout << count + 1 << endl;
	getchar();
	getchar();
	return 0;
}

实验结果：



然后看了下答案，瞬间觉得自己应该在多考虑一下这个问题，计算机科学家的解法确实代码少了很多。。。

#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	int index = 0;             //数组下标索引
	//int indexEnd = 0;          //目标索引
	int length = 1;            //平台长度
	int arrayNum[100] = { 0 }; //零不算输入元素，所以结尾判零即可
	cout << "请输入一个数字序列，数字间以空格隔开，用0表示输入结束:" << endl;
	while((cin >> arrayNum[index])&&arrayNum[index]!=0)
		++index;
	index = 0;
	for (index = 1; arrayNum[index] != 0;index++)
	{		
		if (arrayNum[index] == arrayNum[index - length])
			length++;
	}
	cout << "输入数字序列为：" << endl;
	index = 0;
	while (arrayNum[index] != 0)
	{
		cout << arrayNum[index];
		++index;
	}
	cout << endl;
	cout << "连续次数为：" << endl;
	cout << length << endl;
	getchar();
	getchar();
	return 0;
}

实验结果：



为了是能更好的对比我和科学家的差距，我把程序的核心代码对比一下

//科学家的
for (index = 1; arrayNum[index] != 0;index++)
{		
	if (arrayNum[index] == arrayNum[index - length])
		length++;
}
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//我的
while (arrayNum[index] != 0)
{		
	if (arrayNum[index + 1] != 0)
	{
		if (arrayNum[index] == arrayNum[index + 1])
		{
			tempCount++;
		}
		else
		{
			if (tempCount > count)
			{
				count = tempCount;
				indexEnd = index;
			}
			tempCount = 0;
		}
	}
	++index;
}

因为数组顺序已经排好了所以科学家用一个变量直接探测平台最远点的想法确实精妙。嘿嘿，慢慢学习哈~加油！


                   -End-

参考文献：《c语言名题精选百则》


联系
我们