標(biāo)準(zhǔn)砝碼算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告
- 實(shí)驗(yàn)內(nèi)容
對于給定的n 種不同砝碼，編程計(jì)算它們可以稱出多少種不同的重量。 - 實(shí)驗(yàn)環(huán)境
- 數(shù)據(jù)輸入
zhanghaiyanginput.txt 
- 編程環(huán)境
環(huán)境：Eclipse 3.1 語言：Java - 算法設(shè)計(jì)
算法分析，算法流程（關(guān)鍵算法必須有），設(shè)計(jì)內(nèi)容（類結(jié)構(gòu)設(shè)計(jì)）
- 程序說明
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ù)組，*行存放砝碼重量二行放個(gè)數(shù) f=new int[3][3]; int line=1;//文本讀取的行控制變量 int n=0;//砝碼種數(shù) int s=0;//表識(shí)可稱出的種稱法 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];//計(jì)算稱法 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ù)組，*行存放砝碼重量二行放個(gè)數(shù) f=new int[3][3]; int line=1;//文本讀取的行控制變量 int n=0;//砝碼種數(shù) int s=0;//表識(shí)可稱出的種稱法 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(",");//三行是讀取每種砝碼對應(yīng)的個(gè)數(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];//計(jì)算稱法 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){} } }
- 算法復(fù)雜性分析
針對具體算法，分析復(fù)雜性。該部分內(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];//計(jì)算稱法 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ù)組的長度
綜上所述，所以復(fù)雜度為a*b*c
- 實(shí)驗(yàn)結(jié)果
- 輸入?yún)?shù)
*行為砝碼種類的個(gè)數(shù) 二行為不同重量的砝碼 三行為各個(gè)砝碼的個(gè)數(shù)
- 輸出結(jié)果
輸出可稱出重量的總數(shù)
- 實(shí)驗(yàn)總結(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];//計(jì)算稱法 sum[s]=s; } } } 此關(guān)鍵算法具有定的局限性，它僅是在知道不同重量的砝碼個(gè)數(shù)n確定的前提下設(shè)計(jì)循環(huán)的層數(shù)的，當(dāng)n很的時(shí)候就顯得復(fù)雜了，也不好簡寫成其他的代碼，比較麻煩，并且復(fù)雜度也是成指數(shù)增長的，zui的復(fù)雜度可達(dá)m^n(m為每個(gè)不同重量的砝碼的個(gè)數(shù)) 砝碼 http://www.21fama。。ｃｏｍ/
|
