/ interview

Interview Practice 12 - Sum from 1 to N Unconventionally

Question

Sum up 1 to n without using division, multiplication, for loop, while loop, if else, switch and condition statement (A?B:C).

Solution 1

Actually, for loop can be simulated through making use of the static property. Since static value will be stored in the class, we can increase the value every time we init a static class.

include <iostream.h> class Temp { public: Temp() { ++N; Sum += N; } static void Reset() { N = 0; Sum = 0; } static int GetSum() { return Sum; } private: static int N; static int Sum; }; int Temp::N = 0; int Temp::Sum = 0; int solution1_Sum(int n) { Temp::Reset(); Temp *a = new Temp[n]; //就是这个意思,new出n个数组。 delete []a; a = 0; return Temp::GetSum(); } int main() { cout<<solution1_Sum(100)<<endl; return 0; } //运行结果: //5050 //Press any key to continue

Solution 2

既然不能判断是不是应该终止递归,我们不妨定义两个函数。
一个函数充当递归函数的角色,另一个函数处理终止递归的情况,
我们需要做的就是在两个函数里二选一。

从二选一我们很自然的想到布尔变量,
比如ture/(1)的时候调用第一个函数,false/(0)的时候调用第二个函数。
那现在的问题是如和把数值变量n转换成布尔值。

如果对n连续做两次反运算,即!!n,那么非零的n转换为true,0转换为false。

include <iostream.h> class A; A* Array[2]; class A { public: virtual int Sum (int n) { return 0; } }; class B: public A { public: virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; } }; int solution2_Sum(int n) { A a; B b; Array[0] = &a; Array[1] = &b; int value = Array[1]->Sum(n); //利用虚函数的特性,当Array[1]为0时,即Array[0] = &a; 执行A::Sum, //当Array[1]不为0时,即Array[1] = &b; 执行B::Sum。 return value; } int main() { cout<<solution2_Sum(100)<<endl; return 0; } //5050 //Press any key to continue