标准砝码算法设计与分析实验报告
- 实验内容
对于给定的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。。ｃｏｍ/
|
