標(biāo)準(zhǔn)砝碼算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告

1. 實(shí)驗(yàn)內(nèi)容

對(duì)于給定的n 種不同砝碼，編程計(jì)算它們可以稱(chēng)出多少種不同的重量。

1. 實(shí)驗(yàn)環(huán)境
   1. 數(shù)據(jù)輸入

    zhanghaiyanginput.txt                        

1. 編程環(huán)境

環(huán)境：Eclipse  3.1

語(yǔ)言：Java   

1. 算法設(shè)計(jì)

算法分析，算法流程（關(guān)鍵算法必須有），設(shè)計(jì)內(nèi)容（類(lèi)結(jié)構(gòu)設(shè)計(jì)）

1. 程序說(shuō)明

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[];//初始化稱(chēng)法數(shù)組

              int f[][];//二維數(shù)組，*行存放砝碼重量二行放個(gè)數(shù)

        f=new int[3][3];

        int line=1;//文本讀取的行控制變量

        int n=0;//砝碼種數(shù)

        int s=0;//表識(shí)可稱(chēng)出的種稱(chēng)法

        int a=0,b=0,c=0,count=0;//循環(huán)變量和稱(chēng)法總數(shù)

     try{

            FileInputStream file=new FileInputStream("D:/data/zhanghaiyanginput.txt");//創(chuàng)建文本輸入流對(duì)象

        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ì)算稱(chēng)法

                          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+"種稱(chēng)法");

            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[];//初始化稱(chēng)法數(shù)組

              int f[][];//二維數(shù)組，*行存放砝碼重量二行放個(gè)數(shù)

        f=new int[3][3];

        int line=1;//文本讀取的行控制變量

        int n=0;//砝碼種數(shù)

        int s=0;//表識(shí)可稱(chēng)出的種稱(chēng)法

        int a=0,b=0,c=0,count=0;//循環(huán)變量和稱(chēng)法總數(shù)

     try{

            FileInputStream file=new FileInputStream("D:/data/zhanghaiyanginput.txt");//創(chuàng)建文本輸入流對(duì)象

        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(",");//三行是讀取每種砝碼對(duì)應(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ì)算稱(chēng)法

                          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+"種稱(chēng)法");

            w.close();

     }catch(Exception e){}

}

}

1. 算法復(fù)雜性分析

針對(duì)具體算法，分析復(fù)雜性。該部分內(nèi)容要有過(guò)程說(shuō)明。

 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ì)算稱(chēng)法

                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ù)組的長(zhǎng)度

綜上所述，所以復(fù)雜度為a*b*c

1. 實(shí)驗(yàn)結(jié)果
   1. 輸入?yún)?shù)

*行為砝碼種類(lèi)的個(gè)數(shù)

二行為不同重量的砝碼

三行為各個(gè)砝碼的個(gè)數(shù)

1. 輸出結(jié)果

   輸出可稱(chēng)出重量的總數(shù)

1. 實(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ì)算稱(chēng)法

                sum[s]=s;

            }

         }

     }

  此關(guān)鍵算法具有定的局限性，它僅是在知道不同重量的砝碼個(gè)數(shù)n確定的前提下設(shè)計(jì)循環(huán)的層數(shù)的，當(dāng)n很的時(shí)候就顯得復(fù)雜了，也不好簡(jiǎn)寫(xiě)成其他的代碼，比較麻煩，并且復(fù)雜度也是成指數(shù)增長(zhǎng)的，zui的復(fù)雜度可達(dá)m^n(m為每個(gè)不同重量的砝碼的個(gè)數(shù))

 砝碼  http://www.21fama。。ｃｏｍ/