《桥本分数式论文》由会员分享，可在线阅读，更多相关《桥本分数式论文（6页珍藏版）》请在金锄头文库上搜索。
1、1LiaoningLiaoning NormalNormal UniversityUniversity本本科科生生开开放放实实验验室室 作作品品创创作作说说明明题题 目：目： 桥本分数式并行运算桥本分数式并行运算学学 院：院： 计算机与信息技术学院计算机与信息技术学院专专 业：业： 计算机科学与技术计算机科学与技术学生证号：学生证号： 20091118050113学生姓名：学生姓名： 田林川田林川指导教师：指导教师： 郑晓薇郑晓薇实验室名称：多核实验室实验室名称：多核实验室2011 年年 12 月月2桥本分数式桥本分数式一、问题提出日本数学家桥本吉彦教授于 1993 年 10 月在我国山东举行
2、的中日美三国数学教育研讨 会上向与会者提出以下填数趣题：把 1,2,.,9这 9 个数字填入下式的 9 个方格中（数字 不得重复） ，使下面的分数等式成立桥本教授当即给出了一个解答。这一分数式填数趣题 究竟共有多少个解答？试求出所有解答（等式左边两个分数交换次序只算一个解答） 。桥本分数式式子递归算法的原理：一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型 复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的 程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能 力在于用有限的语句来定义对象的无限集合。用递归思想
3、写出的程序往往十分简洁易懂。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时， 递归前进；当边界条件满足时，递归返回。注意：(1) 递归就是在过程或函数里调用自身;(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。(Fibonacci 函数)(2)问题解法按递归算法实现。(回溯)3(3)数据的结构形式是按递归定义的。(树的遍历，图的搜索)递归的缺点：递归算法解题的运行效率较低。在递归调用的过程当中系统为每一层的返回点、局部 量等开辟了栈来存储。递归次数过多容易造成栈溢出等。递归算法：是一种
4、直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解 决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。递归算法的特点递归过程一般通过函数或子过程来实现。递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函 数(或过程)来表示问题的解。递归算法解决问题的特点：(1) 递归就是在过程或函数里调用自身。(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提 倡用递归算法设计程序。(4) 在递归调用的
5、过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归 次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。递归算法所体现的“重复”一般有三个要求：一是每次调用在规模上都有所缩小(通常是减半)；二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出 就作为后一次的输入)；三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调 用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环 而不能正常结束。4递归方法对桥本分数式的讲解:(1) 设计要点 设置桥本分数式递归函数 put(k): 当 k int a10,s=0;
6、void main() int put(int k);put(1); / 调用递归函数 put(1) /printf(“ 共有以上%d 个解。n“,s); / 桥本分数式递归函数 #include int put(int k) int i,j,u,m1,m2,m3;if(k=9) for(i=1;i=9;i+) / 探索第 k 个数字取值 i ak=i;for(u=0,j=1;j=k-1;j+)if(ak=aj) u=1; / 出现重复数字,则置 u=1 if(u=0) / 若第 k 个数字可为 i if(k=9 m2=a5*10+a6; m3=a8*10+a9; if(a1*m2*m3+a4
7、*m1*m3=a7*m1*m2) s+; printf(“ %2d: “,s); / 输出一个解 printf(“%d/%d+%d/%d“,a1,m1,a4,m2);printf(“=%d/%d “,a7,m3);if(s%2=0) printf(“n“); 5else put(k+1); / 若不到 9 个数字，则调用 put(k+1) return s; 数据结果分析： 串行结果：并行结果：得到加速比：415/258 约为 1.61。 反思： 数据太小，而导致结果不是足够明显。6参考文献： 1. 杨克昌 计算机常用算法与程序设计教程 人民邮电出版社 2. 杨克昌 刘志辉 趣味 C 程序集锦 中国水利水电出版社致 谢感谢我的指导老师，您们循循善诱的教导和一丝不苟的精神将是我今后学习道路上的 指明灯。感谢和我一起努力拼搏了如此长时间的同窗，有了你们，我收获的不仅仅是进步 和成长，更是弥足珍贵的友谊和挥之不去的回忆。
