算法题目---最长平台

数学是思维的体操，那算法对于程序员来讲，意义又如何呢？
从今天开始，把买的一本书上的题目贴一下，把自己写的程序也贴一下，希望有共同爱好的人可以指点一二。
                             最长的平台
已知一个已经从小到大排序的数组，这个数组中的一个平台(Plateau)就是连续的一串值相同的元素，并且这一串元素不能再延伸。例如，在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)程序语句也要越少越好。
这个问题曾经困扰过David Gries这位知名的计算机科学家。本题与解答取自Dacid Gries编写的有关程序设计的专著。

评论

3 楼 SavageGarden 2008-08-20  

java版

public static void newPlateau(int[] array){
		int length=1;
		int value=0;
		for(int i=1;i<array.length;i++){
			if(array[i]==array[i-length]){
				value=array[i];
				length++;
			}
		}
		System.out.println("max="+length+" and value="+value);
	}

2 楼 SavageGarden 2008-08-20  

看了答案，原来是数组是已经排好序的，于是就有了答案里的解法，再看自己的程序，实在是汗颜。

#include <stdio.h>
main(){
	int x[20]={1,2,2,3,3,3,3,4,4,5,6,6,6,7,7,7,7,8,8,8};
	int max=longest_plateau(x,20);
	printf("%d\n",max);
}
int longest_plateau(int x[],int n){
	int length=1;
	int i=1;
	for(i=1;i<n;i++){
		if(x[i]==x[i-length])
			length++;
	}
	return length;
}

fedora8下gcc编译通过

1 楼 SavageGarden 2008-08-16  

public class MyTest {
	public static void main(String args[]){
		int[] array={1,2,2,3,3,3,4,5,5,6,6,6,6,6,7,7};
		plateau(array);
	}
	/**
	 * 查找数组中最长的平台
	 * 定义HashMap型变量hm，记录元素和元素的个数
	 * 定义三个int型变量,x记录元素,y记录元素个数,max记录个数最多的元素的个数
	 * 遍历数组
	 * 如果当前值不等于x值,则判断y是否已经大于max值，是则记录x、y于HashMap,并改变max值
	 * 	然后改变x值为当前值，并将y重置为1
	 * 如果当前值等于x值，而且当前元素并不是数组的最后一个值，则将y自加
	 * 如果当前值等于x值，而且当前元素并是数组的最后一个值，则判断y是否已经大于max值，是则记录x、y于HashMap,并改变max值
	 * @param array
	 */
	public static void plateau(int[] array){
		HashMap hm = new HashMap();
		int x=0;int y=0;int max=0;
		if(array.length>0){
			x=array[0];
			for(int i=0;i<array.length;i++){
				if(array[i]!=x){
					if(y>max){
						max=y;
						hm.put(max, x);
					}
					x=array[i];
					y=1;
				}else if(i!=array.length-1){
					y++;
				}else{
					y++;
					if(y>max){
						max=y;
						hm.put(max, x);
					}
				}
			}
			System.out.println("max="+max+" and value="+hm.get(max));
			StringBuffer sb=new StringBuffer();
			for(int i=0;i<max;i++){
				if(i!=max-1){
					sb.append(hm.get(max)+".");
				}else{
					sb.append(hm.get(max));
				}
			}
			System.out.println(sb.toString());
		}else{
			System.out.println("输入的数组长度不能为0");
		}
	}
}