非递归循环条件判断求解1+2+…+n问题

2017-03-26 19:17 阅读 572 次 评论 0 条

发散思维的特点是思维活动的多向性和交通性,也就是我们在思考问题时注重运用多思路、多方案、多途径地解决问题,我们可以从不同的方向、侧面和层次,采用探索、转换、迁移、组合和分解等方法,提出多种创新的解法。

求1+2+3+...+n

求1+2+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。这道题出自剑指offer的面试题,是一道不错的能够考察应聘者发散思维能力的题目,对于快要毕业的我们,的确是一个挑战。

之前我们求解这样的问题无非就是套用公式,或者循环,递归求解,既然限制了这些方法的实现,那是否还有更为巧妙的方法呢?下面为大家列举出四种方法。

1.利用构造函数求解

我们先定义一个类型,接着创建n个该类性的实例,那么这个类型的构造函数将确定会被调用n次。我们可以将与累加相关的代码放到构造函数中,下面代码正是基于这个思路。

2.利用虚函数求解

既然不能再一个函数中判断是不是应该终止地柜,那么我们不妨定义两个函数,一个函数充当递归函数的角色,另一个函数终止递归的情况,利用布尔变量,值为true时调用第一个函数,值为false调用第二个函数。如果对n连续两次反运算,即!!n,那么非零的n转换为true,0转换为false。请看下面的代码:

这种思路是用虚函数来实现函数的选择。当n不为零时,调用函数B::Sum,当n等于零时,调用函数A::Sum。

3.利用函数指针求解

在C语言的范畴内,是没有虚函数这个概念的,因此我们可以使用函数指针来模拟,这样代码可能还更加直观一些。

4.利用模板类型求解

既然不能使用递归来求解,那么我们让编译器帮助完成类似于递归的计算,比如下面的代码:

SumSolution<100>::N就是1+2+...+100的结果,当编译器看到SumSolution<100>时,就会为模板类SumSolution以参数100生成该类性的代码,但以100为参数的类型需要得到以99为参数的类型,因为SumSolution<100>::N=SumSolution=SumSolution<99>::N+100。这个过程会递归一直到参数为1的类型,由于该类型已经显示定义,编译器无须生成,递归编译到此结束。

但是这种方法的弊端就在于,输入n必须是在编译期间就能确定的常量,不能动态输入,而且编译器对递归编译代码的递归深度是有限制的,也就是说n不能太大。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:非递归循环条件判断求解1+2+…+n问题 | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情