標準砝碼算法設計與分析實驗報告
- 實驗內容
對于給定的n 種不同砝碼，編程計算它們可以稱出多少種不同的重量。 - 實驗環境
- 數據輸入
zhanghaiyanginput.txt 
- 編程環境
環境：Eclipse 3.1 語言：Java - 算法設計
算法分析，算法流程（關鍵算法必須有），設計內容（類結構設計）
- 程序說明
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader;
public class FangMa { public static void main(String[] args) throws NumberFormatException,IOException { int sum[];//初始化稱法數組 int f[][];//二維數組，*行存放砝碼重量二行放個數 f=new int[3][3]; int line=1;//文本讀取的行控制變量 int n=0;//砝碼種數 int s=0;//表識可稱出的種稱法 int a=0,b=0,c=0,count=0;//循環變量和稱法總數 try{ FileInputStream file=new FileInputStream("D:/data/zhanghaiyanginput.txt");//創建文本輸入流對象 BufferedReader w = new BufferedReader(new InputStreamReader(file));//讀取數據流緩存區間 String tempString =null;//存放每行讀出的字符串 while((tempString = w.readLine()) != null){ if(line==1){ n=Integer.parseInt(tempString);//讀出*行的字符并轉換成砝碼種數 } if(line==2){ String str[] = tempString.split(",");//安“，"將字符串劃分成字符數組元素 for(int i=0;i<n;i++){f[0][i]=Integer.parseInt(str[i]);//將字符數組元素放入二維數組中 }} if(line==3){ String str[] = tempString.split(","); for(int i=0;i<n;i++){f[1][i]=Integer.parseInt(str[i]); }} line++; } }catch (FileNotFoundException e) { } sum=new int[20]; for( a=0;a<=f[1][0];a++){ for(b=0;b<=f[1][1];b++){ for(c=0;c<=f[1][2];c++){ s=a*f[0][0]+b*f[0][1]+c*f[0][2];//計算稱法 sum[s]=s; } } } for(int j=0;j<20;j++){ if(sum[j]!=0) } try{ FileWriter w=new FileWriter("D:/data/zhanghaiyangoutput.txt");//創建輸出文件 w.write("共有"+count+"種稱法"); w.close(); }catch(Exception e){} } }import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.IOException; import java.io.InputStreamReader;
public class FangMa { public static void main(String[] args) throws NumberFormatException,IOException { int sum[];//初始化稱法數組 int f[][];//二維數組，*行存放砝碼重量二行放個數 f=new int[3][3]; int line=1;//文本讀取的行控制變量 int n=0;//砝碼種數 int s=0;//表識可稱出的種稱法 int a=0,b=0,c=0,count=0;//循環變量和稱法總數 try{ FileInputStream file=new FileInputStream("D:/data/zhanghaiyanginput.txt");//創建文本輸入流對象 BufferedReader w = new BufferedReader(new InputStreamReader(file));//讀取數據流緩存區間 String tempString =null;//存放每行讀出的字符串 while((tempString = w.readLine()) != null){ if(line==1){ n=Integer.parseInt(tempString);//讀出*行的字符并轉換成砝碼種數 } if(line==2){ String str[] = tempString.split(",");//安“，"將字符串劃分成字符數組元素 for(int i=0;i<n;i++){f[0][i]=Integer.parseInt(str[i]);//將字符數組元素放入二維數組中 }} if(line==3){ String str[] = tempString.split(",");//三行是讀取每種砝碼對應的個數 for(int i=0;i<n;i++){f[1][i]=Integer.parseInt(str[i]); }} line++; } }catch (FileNotFoundException e) { } sum=new int[20]; for( a=0;a<=f[1][0];a++){ for(b=0;b<=f[1][1];b++){ for(c=0;c<=f[1][2];c++){ s=a*f[0][0]+b*f[0][1]+c*f[0][2];//計算稱法 sum[s]=s; } } } for(int j=0;j<20;j++){ if(sum[j]!=0) } try{ FileWriter w=new FileWriter("D:/data/zhanghaiyangoutput.txt");//創建輸出文件 w.write("共有"+count+"種稱法"); w.close(); }catch(Exception e){} } }
- 算法復雜性分析
針對具體算法，分析復雜性。該部分內容要有過程說明。
for( a=0;a<=f[1][0];a++){ for(b=0;b<=f[1][1];b++){ for(c=0;c<=f[1][2];c++){ s=a*f[0][0]+b*f[0][1]+c*f[0][2];//計算稱法 sum[s]=s; } } } 此處三重循環，循環的總次數位a*b*c
for(int j=0;j<20;j++){ if(sum[j]!=0) } 此處循環的次數為數組的長度
綜上所述，所以復雜度為a*b*c
- 實驗結果
- 輸入參數
*行為砝碼種類的個數 二行為不同重量的砝碼 三行為各個砝碼的個數
- 輸出結果
輸出可稱出重量的總數
- 實驗總結
關鍵算法為： for( a=0;a<=f[1][0];a++){ for(b=0;b<=f[1][1];b++){ for(c=0;c<=f[1][2];c++){ s=a*f[0][0]+b*f[0][1]+c*f[0][2];//計算稱法 sum[s]=s; } } } 此關鍵算法具有定的局限性，它僅是在知道不同重量的砝碼個數n確定的前提下設計循環的層數的，當n很的時候就顯得復雜了，也不好簡寫成其他的代碼，比較麻煩，并且復雜度也是成指數增長的，zui的復雜度可達m^n(m為每個不同重量的砝碼的個數) 砝碼 http://www.21fama。。ｃｏｍ/
|
