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

古城微笑少年丶 2024-04-19 15:12 67阅读 0赞

算法分析与设计实验报告  
第 一 次实验  
姓名 裴朵朵 学号 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();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c2=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c3=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c4=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c5=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c6=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c7=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c8=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
int c9=test.solve();  
int c10=test.solve();  
System.out.println(“元素之间比较的次数是：”+c1);  
System.out.println(“平均比较的次数是：”+(c1+c2+c3+c4+c5+c6+c7+c8+c9+c10)/10);

}
    
    public 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.求无序序列中第k小的元素  
编写一个实验程序，利用priority\_queue(优先队列）求出一个无序整数序列中第k小的元素。  
package a;  
import java.util.Queue;  
import java.util.PriorityQueue;  
/\*

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

public class Test09 \{

static int k=3;
    //static int i=0;
    public static void main(String[] args) {
    	// TODO Auto-generated method stub
    	int a[]=new int[6];//定义int类型数组存放队列前k个元素
    	PriorityQueue<Integer>pq=new PriorityQueue<>(6);
        pq.add(3);
        pq.add(11);
        pq.add(4);
        pq.add(12);
        pq.add(1);
        pq.add(23);
       // System.out.println("此时优先队列中的元素是: ");
       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.出栈第k个元素  
编写一个实验程序，对于一个含n（n>1)个元素的queue队列容器qu，出队从队头到队尾的第k（1<=k<=n)个元素，其他队列元素不变  
package a;  
import java.util.PriorityQueue;  
/\*

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

public class Test10 \{  
static int k=4;  
static PriorityQueue qu=new PriorityQueue();  
static PriorityQueue que=new PriorityQueue();

public static void main(String[] args) {
    	// TODO Auto-generated method stub
    	
    	qu.add("f");
    	qu.add("e");
    	qu.add("b");
    	qu.add("d");
    	qu.add("c");
    	qu.add("a");
    	
    	Test10 test=new Test10();
    	test.solve();
    	
    
    }
    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(j==k) {
    			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.正整数n(n>1)可以写成质数乘积的形式，称为整数的质因数分解。例如，12=2*2*3，18=2*3*3，11=11.设计一个算法求n这样分解后各个质因数出现的次数。  
package a;  
import java.util.Scanner;  
import java.util.Iterator;  
import java.util.HashMap;  
import java.util.Map;  
public class Test004 \{  
static Map<Integer,Integer> map=new HashMap<>();  
public static void main(String\[\] args) \{  
// TODO Auto-generated method stub  
Scanner sc=new Scanner(System.in);  
//Test04 test=new Test04();  
for(int j=0;j<100;j++) \{  
System.out.print(“请输入正整数：”);  
int m=sc.nextInt();  
prim(m);

}
    	sc.close();
    }
    public static void prim(int m) {
    	int i=0;//计数
    	int k=2;//最小质因数
    	/*对质因数m进行分解，首先应找到一个最小的质数k,
    	 * 1.如果m=这个质数，则说明分解结束，打印出这个质数即可
    	 * 2.如果m>k,但能被k整除，则应打印k值，并用m/k作为新的m值重复第一步
    	 * 3.如果m>k,但m不能被k整除，则k+1作为新的k值，重复执行第一步
    	 */
    	while(k>1||i!=0)
    	{
    		if(m%k==0)
    		{
    			i++;
    			m=m/k;
    		}
    		else
    		{
    			if(i>0)
    			{
    				map.put(k,i);
    				System.out.println("质因数"+k+"出现"+i+"次");
    				
    			}
    			  i=0;
    			  k++;
    		}
    	}
    }

1-10.有一个map<string,int>容器，其中已经存放了较多元素，设计一个算法求出其中重复的value值并返回重复value的个数。  
package a;  
import java.util.TreeMap;  
import java.util.Map;  
import java.util.Iterator;  
import java.util.ArrayList;  
import java.util.Vector;

public class Test006 \{  
//Vectormyv;  
static TreeMap<String,Integer> map =new TreeMap<String,Integer>();  
static TreeMap<Integer,Integer> tr =new TreeMap<Integer,Integer>();

public static void main(String[] args) {
    	// TODO Auto-generated method stub
        map.put("zhangsan", 2);
        map.put("lisi", 5);
        map.put("wangwu", 2);
        map.put("zhaoliu", 4);
        map.put("fengqi", 2);
        map.put("tianxian", 1);
        map.put("meili", 4);
        map.put("yinshui", 2);
        
        ChongFu();
       // System.out.println(" v");
        
    }
    /*
     * 将前一个集合map中的value作为后一个集合tr的key值，
     * 遍历map，累计关键字相同出现的次数
     */
    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);
    }

项目 比例 成绩  
学习态度 10% 积极 一般 较差  
算法设计及结果 50% 功能正确 功能基本正确 错误  
内容完整性 20% 完整 基本完整 不完整  
报告规范性 20% 规范 基本规范 不符合要求  
成绩