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