算法設計與基礎實驗報告（一）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();