算法设计与分析第2版第一章

r囧r小猫 2024-04-18 13:12 37阅读 0赞

8.一个字符串采用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;
    	
    }

![在这里插入图片描述][20190907093617659.png]  
9.有一个整数序列，设计一个算法判断其中是否存在两个元素的和恰好等于给定的整数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;
    }

\}  
![在这里插入图片描述][20190907150903450.png]  
10.有两个整数序列，每个整数序列中所有元素均不相同，设计一个算法求他们的公共元素，要求不使用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]+" ");
    	}
    }

\}  
![在这里插入图片描述][20190907203818462.png]  
另外，本体、题刚开始想用TreeSet集合存储整数序列，因为 set可以自动排序而不用专门排序，但是后面需要定位到整数序列的每个位置，set无法实现，所以代码无法进行。。。。希望直到怎样修改这个代码的大神看到的话帮帮忙，想学习另外一种解决这个题目的方法。  
package a;  
import java.util.\*;

public class Test03 \{

public static void main(String[] args) {
    	// TODO Auto-generated method stub
    	Test03 test=new Test03();
    
    	TreeSet<Integer> ts1=new TreeSet<>();
    	TreeSet<Integer> ts2=new TreeSet<>();
    	ts1.add(2);
    	ts1.add(12);
    	ts1.add(14);
    	ts1.add(31);
    	ts1.add(11);
    	ts2.add(10);
    	ts2.add(14);
    	ts2.add(2);
    	ts2.add(1);
    	
    	test.ChongFu(ts1,ts2);			
    }
    
    	/*将有序整数序列ts1和ts2中重复的元素存储到数组a中*/
    public static void ChongFu(TreeSet ts1,TreeSet ts2,int u,int v)
    {
    	int s=(int)ts1.first();
    	int a[]=new int[10];
    	int i=s;
    	int j;
    	j=u+1;
    	int q=s;
    	int b=0;
    	while(i<=u&&j<=v) {
    		if(i==j) {
    			a[b]=i;
    			b++;
    		}
    		else if(i<j) {
    			i++;
    		}
    		else {
    			j++;
    		}
    	}
    	//输出储存在数组a中的所有重复元素
    	for(;b<a.length;b++) {
    	   System.out.println(a[b]);;
    		}
    }

\}  
11.正整数n(n>1)可以写成质数乘积的形式，称为整数的质因数分解。例如，12=2*2*3，18=2*3*3，11=11.设计一个算法求n这样分解后各个质因数出现的次数，采用vector向量存放结果。  
12.有一个整数序列，所有元素均不相同，设计一个算法求相差最小的元素对的个数。例如序列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;
    	
    }

![在这里插入图片描述][20190909085943968.png]  
13.有一个map<string,int>容器，其中已经存放了较多元素，设计一个算法求出其中重复的value值并返回重复value的个数。

15.假设有一个含n(n>1)个元素的stack栈容器st，设计一个算法出栈从栈顶到栈底的第k（1<=k<=n)个元素，其他栈元素不变。  
package a;  
import java.util.Stack;  
/\*

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

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() {
    		Stack<String>st=new Stack<String>();
    		Stack<String>sta=new Stack<String>();//定义一个临时栈
    		//入栈
    		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());
    	}

![在这里插入图片描述][2019091108111036.png]  
实验1.统计求最大、最小元素的平均比较次数  
编写一个实验程序，随机产生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;
    }

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);

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70 1]  
实验2：求无序序列中第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;
             }
        }   
    }

\}  
![在这里插入图片描述][20190915110613878.png]  
实验3：出栈第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());
    	}		
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70 2]  
实验4：设计一种好的数据结构I编写一个实验程序，设计一个好的数据结构，尽可能高效的实现元素的插入、删除、按值查找和按序号查找（假设所有元素值不相同）

[20190907093617659.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2708391869bb4a38906420307c7de4f0.png
[20190907150903450.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/bc331846dd0944058d7a8c6b3e258b56.png
[20190907203818462.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3747a4ee9ec645b08451b9f528596e63.png
[20190909085943968.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6256bad6617547f1808fa905a2c61c92.png
[2019091108111036.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/590e38fcd52345079628ec6da03c2312.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190911112619817.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b3238767e983469ea8dd584af94e02ce.png
[20190915110613878.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d8e95cd5786f4e13af801a8b244f4c23.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c8194bf041f645409379b5d9943d3004.png