算法设计与基础实验报告（一）java版

算法分析与设计实验报告

第一次实验

姓名裴朵朵学号 5001170016 班级 17计科1班

时间 2019.09.14 地点

实验名称算法基础（STL编程）

实验目的掌握顺序容器、关联容器、适配器容器使用及其应用，通过练习提高编程能力，锻炼逻辑思维和解决问题的能力

实验原理 1-1.利用string 类型的变量存储字符串，判断回文的方法封装在solve()中，使用toCharArray()方法遍历字符串

1-2.通过sort()方法可以实现自动排序的原理

1-3.利用数组存储元素，利用sort排序

1-4.先递增排序，再求相邻元素差，比较最小元素差，累计最小元素差的个数

1-5.创建一个临时栈sta栈，将st的第k个元素出栈并进栈到sta中，再出栈sta得到第k个元素，最后将sta的所有元素出栈并进栈到st中

1-6.利用数组存取10个随机数，依次遍历比较，暂时假设数组的第一个值a[0]是最大值和最小值，比当前的最大值大，则将其设置成最大值，直到比较结束。

1-7.利用优先队列自动排序的原理。

1-8.利用队列存储元素，优先队列自动排序，但是java中没有直接访问队列特定位置元素的方法，所以需要将队列的前k个元素出栈到另外一个队列

1-9.利用map存储质因数及其出现的次数

1-10.创建一个新的treemap类型的变量tr，将map中的value值作为tr中的key值

实验步骤 1-1.通过判断给定的字符串对应位置上的字符是否相同，若相同，则比较下一个对应位置上的字符是否相同，依次进行；若不相同，直接确定不是回文。

1-2.创建一个int类型的数组，并为其赋值，通过sort()方法将数组内的整数排序，通过输出语句检验是否实现排序的功能，测试使用k=13，即判断随机给定的数组中有没有两数之和为13的整数，排序好的整数根据if else语句判断与k值的大小,不断调整两数之和的大小，直到和是13或者数组里面整数验证全部结束。

1-3.利用数组a[],b[]存储两组元素，使用sort()对数组排序，从a[]数组和b[]数组的第一个位置开始比较，若相同，则存进c[]数组，若a[]数组的元素大于b[]数组，则a数组的第一个元素与b数组的第二个元素比较，依次进行，直到数组a或b中的元素遍历结束，此时c数组中的元素即为所求。

1-4.创建一个int类型的数组，并为其赋值，通过sort()方法将数组内的整数排序，通过输出语句检验是否实现排序的功能，刚开始将数组中第一个数和第二个数的差作为最小差，count记录最小差出现的次数，然后求第三个数与第二个数的差，得到的差值与暂定的最小差比较大小，若比最小差小，则将其设置为新的最小差，count增加1，依次进行，直到遍历结束。

1-5.栈的特点是：后进先出，不能顺序遍历；创建一个临时栈sta栈，将st的第k个元素出栈并进栈到sta中，出栈sta得到第k个元素，最后将sta的所有元素出栈并进栈到st中

1-6.利用Math.random()随机产生[0.0,1.0)之间的数存在数组a中，暂时假设数组的第一个值a[0]是最大值和最小值，依次比较数组中的元素，若比当前的最大值大，则将其设置成最大值，直到比较结束，最小值的选取同理。

1-7.优先队列中的元素默认按自然顺序排列，创建一个int类型的优先队列，向其中增加若干元素，假设需要输出的是队列中的第k个元素，设置一个变量i,i依次增加，判断i值与k值是否相等，若不相等，直接输出，若相等，则输出提示语句，并且输出第k个值。

1-8.创建一个队列，依次让从队头到队尾的k个元素出栈，出栈的元素保存到另外一个队列que中，que中的元素出栈，第一个元素即为所求，que中的元素依次出栈到qu中

1-9.对质因数m进行分解，首先应找到一个最小的质数k,如果m=这个质数，则说明分解结束，打印这个质数及其出但能被k整除，则应打印k值，并用m/k作为新的m值重复第一步,如果m>k,但m不能被k整除，则k+1作为新的k值，重复执行第一步现的次数即可；如果m>k

1-10.创建一个新的treemap类型的变量tr，将map中的value值作为tr中的key值，通过containsKey()方法判断map中是否存在两个或多个相同的value值，最后输出所有的值，及其出现的次数

关键代码 1-1.public static boolean solve(String str) {//判断字符串是否是回文

int i=0;

int j=str.length()-1;

char c[]=str.toCharArray();

while(i<j) {

if(c[i]!=c[j]) {

System.out.println(“该字符串不是回文”);

return false;

}
		i++;
		j--;
	}
	System.out.println("该字符串是回文");
	return true;
}

1-2.//实现排序及判断是否存在符合要求的数的方法

public boolean PaiXu(int a[]) {
	Arrays.sort(a,0,a.length);
	System.out.println("该数组按升序排序后的顺序是：");
	for(int i=0;i<a.length;i++) {
		System.out.print(a[i]+" ");
	}
	
	int k=13;
	int j=a.length;//a.length返回数组的长度；a.length()返回字符串长度
	int s=a[0];
	while(s<j) {
		if(s+j==k) {
			System.out.println("存在");
			return true;
		}
		else if(s+j<k) {
			s++;
		}
		else {
			j--;
		}
	}
	return false;
}

1-3.public void ChongFu(int a[],int b[])

{

int i=0;

int j=0;

//int q=s;

int c[]=new int[10];

int m=0;

while(i<a.length&&j<b.length)
	{
		if(a[i]==b[j]) {
			c[m]=a[i];
			m++;
			//System.out.print("数组a和数组b重复的元素是："+c[m]);
			i++;
			j++;
		}
		else if(a[i]>b[j])
		{
			j++;
		}
		else 
		{
			i++;
		}
	}
	System.out.print("数组a和数组b重复的元素是：");
	for(int q=0;q<m;q++) {
		System.out.print(c[q]+" ");
	}

}

1-4.int solve(int a[]) {

int count=1;

min=a[1]-a[0];

for(int j=2;j<a.length;j++) {

int m=a[j]-a[j-1];

if(m<min) {

count=1;

min=m;

}

else if(m==min){

count++;

}

//System.out.print(“相差最小的是：”+min+“出现的次数是：”+count);

return count;

1-5.public void solve() {

Stackst=new Stack();

Stacksta=new Stack();//定义一个临时栈

//入栈

st.push(“a”);

st.push(“c”);

st.push(“f”);

st.push(“b”);

st.push(“h”);

//出栈st中的前k个元素，放到sta中

for(int i=0;i<k;i++) {

e=st.pop();//移除栈顶的元素

sta.push(e);

}

//出栈sta中的第一个元素，即是st中的第k个元素

System.out.println(“栈中的第3个元素是：”+sta.pop());

//将sta中的其他元素重新放到st栈中

for(int j=0;j<sta.size();j++) {

s=sta.pop();

st.push(s);

}

//输出st中的栈顶元素验证是否成功将sta中的剩余元素转移到st中

System.out.println(“栈顶元素是：”);

System.out.println(" "+st.pop());

}

1-6.ublic int solve() {

int a[]=new int[10];

int i;

System.out.println("产生的10个随机数是 “);

for(i=0;i<a.length;i++) {

a[i]=(int)(Math.random()*20+1);

System.out.print(” "+a[i]);

}
		int max=a[0];
		int min=a[0];
		for(int j=1;j<a.length;j++) {
			count++;//比较一次，count增加1
			if(a[j]>max) {
				max=a[j];
			}
			else {
				count++;//比较一次count加1，下面是比较后的结果
				if(a[j]<=min) {
					min=a[j];
				}
			}
		}
		System.out.println("最大值是  "+max+"最小值是："+min);
		return count;
}

1-7.for(int i=1;i<6;i++) {

if(i!=k)

System.out.print(pq.poll()+" ");

else {
    		System.out.println("队列中第 "+k+"个元素是："+pq.poll());
    		break;
         }
    }   
}

1-8.public void solve() {

//利用队列先进先出的特点(FIFO)

//Object arr[]=new Object[10];

for(int i=0;i<k;i++) {

que.add(qu.poll());//将qu中的前k个元素移到que中

}

for(int j=1;j<=k;j++) {

if(jk) {

System.out.println(“qu队列中的第”+k+“个元素是：”+que.poll());

}

else {

qu.add(que.poll());//将不是第k个元素的元素重新放回qu队列

}

for(int s=0;s<5;s++) {

System.out.println(“qu队列中的元素是：”+qu.poll());

}

1-9.public static void prim(int m) {

int i=0;//计数

int k=2;//最小质因数

while(k>1||i!=0)

{

if(m%k0)

{

i++;

m=m/k;

}

else

{

if(i>0)

{

map.put(k,i);

System.out.println(“质因数”+k+“出现”+i+“次”);

}
			  i=0;
			  k++;
		}
	}
}

1-10.public static void ChongFu() {

//Iterator value=map.values().iterator();//通过values()方法获取map中所有value值的视图

for (Map.Entry<String,Integer> entry:map.entrySet()){

if (tr.containsKey(entry.getValue())){

tr.put(entry.getValue(),tr.get(entry.getValue())+1);

}

else{

tr.put(entry.getValue(),1);

}

System.out.println(tr);

}

测试结果 1-1.

1-2.

1-3.

1-4.

1-5.

1-6.

1-7.

1-8.

1-9.

1-10.

实验心得通过此次实验，复习了java的基础编程以及数据结构中的map，iterator等相关知识，另外，学习了算法第一章的栈，学会了栈、顺序容器、关联容器、适配器容器等的基本使用。

由于对C++的知识了解较少，所以此次实验使用java语言完成，但是C++中的某些知识点在java中不能使用，通过本次实验我学习了在某些方法的使用上，java与C++的不同。

最后，这次试验锻炼了我的逻辑思维和解决问题的能力

附录：完整程序代码，依次按照题目序号 1-1 1-2

1-1.一个字符串采用String对象存储，设计一个算法判断该字符串是否为回文。

package a;

public class Test01 {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	
	String str1="abcd";
	String str2="abcdcba";
	solve(str1);
	solve(str2);
	
}

public static boolean solve(String str) {//判断字符串是否是回文
	int i=0;
	int j=str.length()-1;
	char c[]=str.toCharArray();
	while(i<j) {
		if(c[i]!=c[j]) {
			System.out.println("该字符串不是回文");
			return false;
			
		}
		i++;
		j--;	}
}
	System.out.println("该字符串是回文");
	return true;
	
}

}

1-2.有一个整数序列，设计一个算法判断其中是否存在两个元素的和恰好等于给定的整数k。

public class Test02 {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	int a[]= {12,11,14,63,21,33,43,5,1,3};
	Test02 t=new Test02();
	t.PaiXu(a);
}
//实现排序及判断是否存在符合要求的数的方法

public boolean PaiXu(int a[]) {
	Arrays.sort(a,0,a.length);
	System.out.println("该数组按升序排序后的顺序是：");
	for(int i=0;i<a.length;i++) {
		System.out.print(a[i]+" ");
	}
	
	int k=13;
	int j=a.length;//a.length返回数组的长度；a.length()返回字符串长度
	int s=a[0];
	while(s<j) {
		if(s+j==k) {
			System.out.println("存在");
			return true;
		}
		else if(s+j<k) {
			s++;
		}
		else {
			j--;
		}
	}
	return false;
}

}

1-3.有两个整数序列，每个整数序列中所有元素均不相同，设计一个算法求他们的公共元素，要求不使用STL的集合算法。

package a;

import java.util.Arrays;

public class Test003 {

public static void main(String[] args) {
	// TODO Auto-generated method stub
	
	Test003 test=new Test003();
	int a[]= {4,34,13,32,22,15};
	int b[]= {1,22,3,23,4,11};
	Arrays.sort(a);//对数组a排序
	Arrays.sort(b);//对数组b排序
	
	System.out.print("数组a排序后的元素是：");
	for(int i:a) {//对数组a中的元素，一个一个进行循环
		System.out.print(i+" ");
	}
	
	System.out.print("数组b排序后的元素是：");
	for(int j:b) {
		System.out.print(j+" ");
	}
	
	test.ChongFu(a,b);

}
public	void ChongFu(int a[],int b[])
{
	int i=0;
	int j=0;
	//int q=s;
	int c[]=new int[10];
	int m=0;
	
	while(i<a.length&&j<b.length)
	{
		if(a[i]==b[j]) {
			c[m]=a[i];
			m++;
			//System.out.print("数组a和数组b重复的元素是："+c[m]);
			i++;
			j++;
		}
		else if(a[i]>b[j])
		{
			j++;
		}
		else 
		{
			i++;
		}
	}
	System.out.print("数组a和数组b重复的元素是：");
	for(int q=0;q<m;q++) {
		System.out.print(c[q]+" ");
	}
}

}

1-4.有一个整数序列，所有元素均不相同，设计一个算法求相差最小的元素对的个数。例如序列4，1，2，3的相差最小的元素对的个数是3，其元素对是（1，2）、（2，3）、（3，4）。

package a;

import java.util.Arrays;

public class Test05 {

//定义全局变量

static int min;

public static void main(String[] args) {

// TODO Auto-generated method stub

Test05 test=new Test05();

int a[]= {4,12,3,6,2,23,11,13,21};

Arrays.sort(a);//对数组a进行排序

System.out.print(“排序好的序列是：”);

for(int i=0;i<a.length;i++) {

System.out.print(a[i]+" ");

}

int count=test.solve(a);

System.out.print(“相差最小的是：”+min+“出现的次数是：”+count);

}
int solve(int a[]) {
	int count=1;
	min=a[1]-a[0];
	for(int j=2;j<a.length;j++) {
		int m=a[j]-a[j-1];
		if(m<min) {
			count=1;
			min=m;
		}
		else if(m==min){
			count++;
		}
	}
	//System.out.print("相差最小的是："+min+"出现的次数是："+count);
	return count;
	
}

}

1-5.假设有一个含n(n>1)个元素的stack栈容器st，设计一个算法出栈从栈顶到栈底的第k（1<=k<=n)个元素，其他栈元素不变。

package a;

import java.util.Stack;

public class Test07 {

int k=3;

String e;

String s;

public static void main(String[] args) {

// TODO Auto-generated method stub

Test07 test=new Test07();

test.solve();

}

public void solve() {

Stackst=new Stack();

Stacksta=new Stack();//定义一个临时栈

//入栈

st.push(“a”);

st.push(“c”);

st.push(“f”);

st.push(“b”);

st.push(“h”);

//出栈st中的前k个元素，放到sta中

for(int i=0;i<k;i++) {

e=st.pop();//移除栈顶的元素

sta.push(e);

}

//出栈sta中的第一个元素，即是st中的第k个元素

System.out.println(“栈中的第3个元素是：”+sta.pop());

//将sta中的其他元素重新放到st栈中

for(int j=0;j<sta.size();j++) {

s=sta.pop();

st.push(s);

}

//输出st中的栈顶元素验证是否成功将sta中的剩余元素转移到st中

System.out.println(“栈顶元素是：”);

System.out.println(" "+st.pop());

}

1-6.统计求最大、最小元素的平均比较次数

编写一个实验程序，随机产生10个1~20的整数，设计一个高效算法找其中的最大元素和最小1元素，并统计元素之间的比较次数。调用该算法执行10次并求元素的平均比较次数。

package a

import java.util.*;

public class Test08 {

int count=0;

public static void main(String[] args) {

// TODO Auto-generated method stub

Test08 test=new Test08();

int c1=test.solve();