|
|
发表于 2003-7-1 05:33:56
|
显示全部楼层
无
数学建模论文
参赛人： 田开 20024279信息与计算机科学
单位分数模型论文
一、引理：分子为1的分数称为单位分数。
二、 引言:
科学技术的发展使得许多循环(穷举)问题的重要性日益显示出来,而计算机又使这些问题的具体求解有了可能,同时在计算机发展过程中有提示出了不少需要解决的穷举问题.
要利用计算机解决某一穷举问题，首先要有一个好的算法,一般地说,"算法"就是一组有穷的规则.对于属于它解决范围内的要求解决的每个具体问题,任何人只要会正确地执行规则要求的操作,并循环规则的指示一步一步的前进,在有限步后就能得到该问题的解.
三、问题的提出：
将一个正分数之和有多少种方法？特别地，将k/n写为1/x+1/y+1/z(x,y,z,是自然数）
有多少本质不同的方法？即给定n,k的方程k/n=1/x+1/y+1/z
有多少组本质不同（不能由x,y,z之间的置换导出）的自然数的解？
四 、问题的分析：
因为给定n,k的方程k/n=1/x+1/y+1/z且x,y,z,是自然数；同时不能由x,y,z之间的置换
导出；
讨论: 令k,n,x,y,z都为整数。给定n,k为什么形式的整数，即k,n为不定形式的整数，(可为负整数或正整数或k=0,n!=0)。
1)当k=0,n!=0时,显然不满足方程k/n=1/x+1/y+1/z(x,y,z,是自然数）;显然当n=0,无意义。
2)当k,n都为正整数时，x,y,z全为任意非0整数（负整数或正整数或不全为同号数）。
3)当k*n<0时，x,y,z全为任意非0整数（负整数或正整数或不全为同号数）。
4）当k,n都为负整数时，与k,n都为正整数的情形相同。
5)显然n!=1
五、假设：为了问题的简化我们可以
1）令k=4;n,x,y,z是正整数即有：
4/n=1/x+1/y+1/z (ss)
由于x,y,z的解不能由方程（1）x,y,z之间的置换导出；
2）为了大大节约程序运行的时间，x,y,z之间的置换导出，我们又可以假设x<=y<=z
六、模型的建立与求解：
1）、算法:
（1)判断n是否为正整数,若是转(2),若否退出并打印”this can't ”.
(2)对unm给初值=0，
同时执行循环: 1) x =Floor[n/4]+1开始执行循环,进入2)
2)y =x开始循环;进入3)令y自增,当y>Ceiling[2*n*x/(4*x-n)]退出.
3)解出z=4/n-1/x-1/y时，进行对z判断是否是正整数.且z大于等于y为整数,对unm计数解的组数，并打印方程（ss）
4）后转1）对x自加，转2）直到x<=Ceiling[3*n/4]时停；
5）打印{x,y,z}的解的组数的个数
2）方程（ss）的程序可写为：[mathematic编]
p程序：
h[n_]：=If[
n=!IntegerQ[n],Print["this can't"],
unm=0;
For[
x=Floor[n/4]+1,x<=Ceiling[3*n/4],x++,
For[
y=x,y<=Ceiling[2*n*x/(4*x-n)],y++,
z=n*x*y/(4*x*y-n*y-n*x);
If[
IntegerQ[z]&&z>=y,z=n*x*y/(4*x*y-n*y-n*x); unm=unm+1;
Print["4/",n,"=1/",x,"+1/",y,"+1/",z]
]
]
]；Print["unm=",unm]
]；
Timing[h[n];]
3）、应用统计学知识对输入n值进行计时及解的组数有以下数据图表：
输入n 解 time time time time time 平均time
n=31 19组 0.14s 0.201s 0.49s 0.55s 0.5s 0.3762s
n=61 11组 0.541s 0.52s 0.66s 0.77s 0.71s 0.6402s
n=211 30组 10.335s 10.795s 10.415s 11.42s 11.31s 10.855s
n=421 16组 33.098s 34.61s 32.872s 43.55s 34.28s 35.673s
n=842 38组 147.031s 146.841s 146.891s 157.69s 157.53s 151.197s
n=1681 49组 653.149s 654.662s 648.863s 649.234s 648.553s 651.697s
4）、算法的效率与可行性：
对于初次编写这种有限循环次数（组合问题）很大的程序问题的人，可能回产生这种想法，现在的电子计算机不是有很快的计算速度吗？组合问题一般都是要求从有限多个可行解找出一个需要的解，让计算机把所有的循环都要进行一次才可以找到所有的可行解？
产生这种错误想法的一个主要的原因是对实际问题中产生的“有限循环”的大小估计过低，事实上，一各看起来简单的问题，它产生的“有限循环”的基数也有可能达到“天文数字”。
那么我们对所编写的程序中循环的次数就提出了很高的要求，即是在过程中循环的次数越少越好，但是又必须找到所有的可行解，因此这就对我们这些编程人员提出了更高的要求。现在随着计算机的CPU的类型的不同，程序所用的时间就不同，但是这只是一个次要的因素，其主要是取决于算法的复杂度。
算法的复杂度是衡量一个算法好坏的标准，它是以计算时间的多少来划分，花费太多时间的算法不能认为是一个好算法.计算时间多少实际是指执行该算法所含有的所有初等运算、比较转移等的总次数。另外，用同一种算法计算同一类型的问题时，由于同类型中各种具体的规模和数据不同，也影响计算的速度，数据对计算时间的影响，可采用不同数据造成的不同计算时间中时间最长的作为计算时间。
当然，设计一个好的算法应该考虑正确性（算法应该满足具体问题的请求）还应该考虑可读性，健壮性，效率和低存储量需求，对 同一个问题如 有多个算法可以解决，执行时间短的算法效率高。
一个程序的执行时间的度量可以利用事后统计的方法，但主要是事前分析 估算的方法，一个哟功能高级语言 编写的程序在计算机上运行是所消耗的是取决于下列因素：1：依据的算法选用何种策略；2 问题的规模；3 书写程序的语言，4 编译程序所产生的机器代码的质量，5机器执行指令的速度；而在本题中则问题规模是相当大的，同时执行的次数也是相当多的。
一个算法是由控制结构和原操作（指固有 数据类型的操作）构成，则算法时间取决于两者的综合效果。
随问题的规模n的增长，算法执行时间的增长率和问题规模的增长率相同，对于本题的增长率，则是逐渐递增的。
5）数据分析与猜想：
通过对数据的分析我发现，随着n的增大，{x,y,z}的解的组数并不是增加的，是一种波动变化很大的，我猜想可能是象股市行情波动图形，在那里有很大的变动
七 、 模型的推广：
此模型推广到任意的数都可以进行用一个程序计算出各自全部可行解，即即给定n,k的方程k/n=1/x+1/y+1/z
有多少组本质不同（不能由x,y,z之间的置换导出）的自然数的解
1)当k,n都为正整数时，x,y,z全为任意非0整数（负整数或正整数或不全为同号数）。
2)当k*n<0时，x,y,z全为任意非0整数（负整数或正整数或不全为同号数）。
3）当k,n都为负整数时，与k,n都为正整数的情形相同。
都考虑到程序编写中去可以识别与计算全部可行解，因此我们可以对p程序简单的改进，就可以得到：
q程序：
h[n_,k_]：=If[
n=!Integer[n]&&k=!Integer[k],Print["this can't"],
unm=0;
For[
x=Floor[n/k]+1,x<=Ceiling[3*n/k],x++,
For[
y=x,y<=Ceiling[2*n*x/(k*x-n)],y++,
z=n*x*y/(k*x*y-n*y-n*x);
If[
IntegerQ[z]&&z>=y,z=n*x*y/(k*x*y-n*y-n*x); unm=unm+1;
Print[k,"/",n,"=1/",x,"+1/",y,"+1/",z]
]
]
]；Print["unm=",unm]
]；
Timing[h[n,k];]
八 、模型优缺点：
我们对给定n,k的方程k/n=1/x+1/y+1/z且x,y,z,是自然数；同时不能由x,y,z之间的置换
导出所编写的 q程序可以看出：
1）本人通过严格的数学逻辑推理、数学分析等知识对k,n,x,y,z进行数字组合与分析得出该程序，并通过多次的运行与改进此程序步骤使其更加简单明了，不仅大大减少了阅读人员的工作量，跟重要的是在执行本程序的时候，其执行循环次数很少，也就大大节约了运行时间，
可以称的上一个很好的程序
2）对k,n进行讨论时，我们可以用调用数学软件里面的现成函数来简化，这就给编程人员代来了很多的方便，为此这也对编程人员对数学知识、软件了解程度、程序语言提出了个更高的要求，当然对一般的数学软件都有这些调用函数。因此对各种编写软件普遍实用。
3）在编写中本人又对x进行了简化处理为x=Floor[n/4]+1即是对n/k可否整除进行讨论而对x付循环初值，把1/y、1/z无限接近于0，有：
（1）当n/k可以整除时，即x=Floor[n/4]+1
（2）当n/k不可以整除时，即x=Floor[n/4]+1
（3）由于x<=y<=z，即可把1/x,1/y,1/z无限接相等，可知x的最大值是Ceiling[3*n/k]；
（4）同理对y进行3）的讨论取范围；
5）我在考虑x,y,z的分子时没有进行推广到任意整数，当然这有将会对运行这种程序花费大量的时间进行循环，因此对计算机中CPU等的型号
又提出了更高的要求，为此本人提出对各个变量再次进行精密的数学分析得出它们之间的关系，来减少循环次数提高算法，减少运行时间。
6）在模型的推广中还可以将等式右边的项取很多，同理也有5）的想法。
7）对此本人提出可否把它们转换成为：（1）生成函数；（2）对数函数....等对进行简化讨论找出其中的规律进行程序进一步的优化处理。
九、建模的该感受：
通过这次竞赛使我深深体会到了建模精神------"创新意识,奋斗精神".这几天以来,我既紧张又活泼,也深深地体会到了21世纪奋斗的重要性.特别是在确定方案的时候,有自己独到的见解.通过在深入的研讨过程中,就一些具体的细节问题得出解决的方案.在具体的执行过程中,每个都要充分的发挥出自己的特长,以便尽快得出自己的解决方案.
在这里,我也很感激学院给我这个锻炼机会。在这次建模比赛当中,我也认识到了自己的优,缺点.在解决问题的过程中,我们取长补短,不断完善自己,在以后的学习和生活中,我有自己明确的目标,我将矢志不移的朝自己的目标努力奋斗!
|
|
