昨天面试一家蛮厉害的公司的一道题目 100分求解

Question

斐波那契数列算法
1+1=2，1+2=3，2+3=5，3+5=8，5+8=13，，，，，一直到100以内
希望输出235813
不允许用递归，不允许用逆归式，不许用迭代，
还不允许用正向推导，好像是这么说的，我记的不太清楚了
那位高手能帮帮小弟 谢谢

Answer 1

class AA{
int fibo2(int n)
{
int a =0;
int c=0;
int b = 1;
for(int i=2; i<=n; ++i){
c=a+b;a=b;
b=c;
}
return c;
} public static void main(String args[]){
for(int j=3;j<12;j++){ 
System.out.print(new AA().fibo2(j));
}
    }
}
想出来了 不过觉得不是很好 大家看看有什么可以改进的地方 谢谢

Answer 2

while(max)
{
t = a;
a += b;
b = t;
--max;
}

Answer 3

int a = 1;
int b = 2;
int s = a + b;
String str = "" + b + s;
System.out.println(s + " = " + a + " + " + b + "@" + str);
for (int i = 2 ;i < 100;i++){
a = b;
b = s;
s = a + b;
if (s > 100){
break;
}
str = str + s;
System.out.println(s + " = " + a + " + " + b + "@" + str);
}

Answer 4

那好吧，不递归——没有运行期的递归。
需要用intel 8.0以上编译器，VC7，G++可能也能编译通过，没试过。template<int v>
struct fnum 
{
    enum { val = fnum<v-2>::val + fnum<v-1>::val };
};template<>
struct fnum<0>
{
    enum { val = 1 };
};
template<>
struct fnum<-1>
{
    enum { val = 1 };
};template<int count>
struct fnumber_printer
{
static int print()
{
printf("%d", fnumber_printer<count - 1>::print());

return fnum<count>::val;
}
};
template<>
struct fnumber_printer<1>
{
static int print()
{
return fnum<1>::val;
}
};int main()
{
fnumber_printer<10> fp;
printf("%d", fp.print());
};

Answer 5

更正一下main函数int main()
{
    printf("%d", fnumber_printer<10>::print());
};

Answer 6

产生函数法
Fn =  1/√5 * [[1/(1+√5)]^n-[1/(1-√5)]^n]

Answer 7

同意gturing(G Turing)的观点，直接使用斐波那契数列算法的通项公式，这是最简单最直接的方法，个人认为问问题人的意图就是让用这个方法求解

Answer 8

X   Y    Z
1   1    2
Y   Z
1   2    3
Y   Z
2   3    5
Y   Z
3   5    8
Y   Z
5   8    13
以此类推...........
int x=1,y=1,Z=1;
Z=X+Y;
X=Y;
Y=Z;

Answer 9

不知道functional programming 行不行  你看一下这段代码
     Func<int, int, int> plus = (int x, int y) => x + y;
     Func<int, int> plus_one = (int x) => plus(x, 1);     Console.WriteLine("RESULT=" + plus_one(3));

Answer 10

int array[100];
int i = 0;
array[0] = 1;
array[1] = 1;
for(i = 2; i < 100; i++)
{
   array[i] = array[i-2] + array[i - 1];
   if(array[i] > 100)
      break;
}是不是递归我不知道.
问一下什么是逆归,什么是正向推导?小弟菜鸟也.

Answer 11

xuefeng128(右手边) 就不要卖关子了萨。学习，学习。

Answer 12

我好像想到的也是
waterx() 
的数组＋循环

Answer 13

关于斐波那契数列的算法比较  如果没看过钱能的&lt;C++程序设计教程&gt;的,下面我写的这个东西希望能给你们带来一点收获.看过钱能的书的,希望大家能多多交流.在论坛的开发语言的C++区中,有人提到过有没有人有什么有趣的C语言题目.我当时推荐了这个斐波那契(Fibonacci)数列,最开始我没看钱能的书,也没编写出具体程序,只给了个大概思路,这里,钱能用C++将几种解决方法都写出来了,看了深有启发.题目:古典题目,有一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假设所有的兔子都不死，问每个月的兔子总数为多少。对应的数列就是斐波那契(Fibonacci)数列:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n&gt; 1).思考:学习到了循环语句后老师就出了母牛问题给我们做.题目和兔子问题类似,思路也相同,程序显得相当简单.下面钱能给出了四个解决斐波那契(Fibonacci)数列的程序:
算法1:
int fibo1(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return fibo1(n-1)+fibo1(n-2);
}算法2:
int fibo2(int n)
{
int a=0,c;
for(int b=1,c,i=2; i&lt;=n; ++i)
c=a+b,a=b,b=c;
return c;
}算法3:
int fibo3(int n)
{
vector&lt;int&gt; v(n+1,0); v[1]=1;
for(int i=2; i&lt;=n; ++i)
v=v[i-1]+v[i-2];
return v[n];
}算法4:
int fibo4(int n)
{
return (pow((1+sqrt(5.0))/2,n)-pow((1-sqrt(5,0))/2,n))/sqrt(5.0);
}
这里列出了4个算法.下面就详细说明一下四个算法:
1.递归算法:最好理解的算法,和人的思路相当接近,对应的数学描述很清晰,容易编程.但是在C++语言中是使用栈机制实现的,如果使用递归函数,将会占用大量的内存资源,对内存中的栈区进行掠夺,在大量调用递归函数之后很可能造成内存崩溃,就算不崩溃,也会是长时间的运算.在调用了clock函数后,计算出了递归函数的耗时,是四个函数中最大的.而且这是个致命的缺点.时间复杂度为O(2n)(括号内为2的n次方).2.循环函数算法:这个方法需要对整个数列有一定的把握,并且能看出其中的规律,用我们班的一位同学说的&quot;就是不停的赋值& quot;.说的很形象,这样就是一个循环的过程,每次调用fibo2,都会一次次循环,时间复杂度为O(n2)(括号内为n的平方)3.循环向量函数算法:同算法2类似,都是以循环来解决问题,但是算法3用向量先分配了一定的空间来实现,然后逐个求得向量的元素,最后得到数列的第n项值,这样就比算法2耗费更多的时间来进行下标操作,所以耗时比算法2多.4.数学公式算法:使用一个数学公式来进行计算,几乎不耗什么时间,一次运算就可以得到结果,时间和n的取值没有太大关系,只和运算性能有关.具体算法写出来后,首先排除算法1,这个算法太耗时,并且没有可取之处.其他三个算法是各有千秋,但是可以人为的测试时间:
环境1:在循环加到一百万次时,分别取n为15,30,45得出算法2是最优的,时间消耗最少,少于0.3秒,算法3从1.4秒增加到3秒,算法4基本不变,始终为2.1秒左右.这样我们就可以看出,算法2虽然比较复杂,但是效率最高,程序员追求的就是这个效果,让机器运算的最快.环境2:在文件中读取自变量,比较算法2和算法3,文件中有一万个数据时算法2和算法3耗时几乎相同为1.7秒,但是文件中有三万个数据时算法2耗时5.6秒,算法3几乎没变,此时算法3显得更优.(时间复杂度的解释说明:假设某算法的计算时间是f(n),其中变量可以是输入或输出量,也可以是两者之和或者其他可以计算时间的元素,一般以运算使用次数作时间,那么如果这个算法在某台机器上运行时,所用的时间总是n,n2,2n,logn,n!,nm这些常量函数的一个常数倍,那么就说这个算法的时间复杂度对应的是n,n2,2n,logn,n!,nm.)这些常量函数为n,n的平方,2的n次方,log n ,n的阶乘,n的m次方.
如果这个算法的时间复杂度不能跨越数量级而只是成倍数增长,比如算法a的时间复杂度是n,算法b的时间复杂度是2n,那么这两个算法的时间复杂度都是n.在各种算法中,O(n)表示时间复杂度为n,其他类似.
O(1)&lt; O(logn)&lt;O(n)&lt;O(nlogn)&lt;O(n2)&lt;O(2n)&lt;O(n!)&lt;O(nn)

Answer 14

int X = 1,Y = 1,Z = 0;
    AnsiString Str = "";
    for (int i=1;i<100;i++)
    {
        Z = X + Y;
        X = Y;
        Y = Z;
        Str += (IntToStr(Z));    }

Answer 15

写错了,我上面写的不知道是不是迭代:
int array[100];
int i = 0;
array[0] = 1;
array[1] = 1;
for(i = 2; i < 100; i++)
{
   array[i] = array[i-2] + array[i - 1];
   if(array[i] > 100)
      break;
}什么是逆归,什么是正向推导?有人知道吗,教教我.

Answer 16

这公司好象是SONIC 或者是...富士施乐吧.

Answer 17

同意“xuefeng128(右手边)”
关键是你要跳出他的圈套，是不是很神秘？呵呵 

Answer 18

int X = 1,Y = 1,Z = 0;
    AnsiString Str = "";
    for (int i=1;i<100;i++)
    {
        Z = X + Y;
        X = Y;
        Y = Z;
        Str += (IntToStr(Z));    }
这个不错哈！！！！

Answer 19

public static void main(String args[]){
{ 
System.out.print("2 3 5 8 13 21 34 55 89 .......");
}
    
}
寒個先！1

Answer 20

int a=2,b=3,c;
    c=a+b;
String str=a.tostring()+b.tostring()+c.tostring();
while(c<100)
{
  a=b;
  b=c;
  c=a+b;
  str+=c.tostring();
}
System.out.println("result is:"+str);

Answer 21

最煩面試的使用這種方法面試...不允許用xxxx,不允許用xxxx,不允許用xxxx,不允許用xxxx,不允許用xxxx,意思就是只充許你用他喜歡的那種方式....同樣能實現,為什麼用不允許.......還有一種辦法,你先用手算出來,然後再System.out.print(你手寫的結果)
:)
為什麼要限制面試者的思維呢?又不象考試,就要了解你對考點的了解情況.

Answer 22

amwynifhv() 说的好..
希望输出2358。
那你就直接输出2358。你算到100然后把数打出来就是了
呵呵
这才是程序员应该有的思维.变相思维...可以看一个程序员的大脑够不够好...这样的方法可以选一个不错的程序员的说.

Answer 23

xuefeng128(右手边)  
 
 
   
呵呵，这个题考的不是你会不会递归、迭代等方法，而且让你从235813中想到点什么…………  
左手边说的正解...观察 下提干就知道了..

Answer 24

public class Test2{
    public static void main(String[] args){
boolean flag=true;
int i=1,j=1,temp;
while(flag){
    temp=i+j;
    if(temp>100)
flag=false;
    else System.out.print(temp);
            i=j;
    j=temp;       
        }
    }
}
运行结果：23581321345589
递归逆归迭代都没有 
就是不知道正向推导什么意思？
这样是不是正向推导？

Answer 25

#define Sch_Fibo_Max 128
ulong sch_fibo(ulong n)
{
static ulong seq[Sch_Fibo_Max] = { 0, 1, 1, };
static int last = 3;
         
while(last < n) {
        seq[last] = seq[last-1]+seq[last-2];
        last ++;
}
         return seq[n-1];
}这里面没有判断溢出

Answer 26

public class YBNY
{
void fibo()
{
int a = 0;
int b = 1;
int c = 1;
int max = 100;
while (c < max)
{
a = b;
b = c;
c = a + b;
if (c <= max)
System.out.print(c);
}
} public static void main(String args[])
{
new YBNY().fibo();
}}

Answer 27

void fibo4()
{
  double sqrt5= java.lang.Math.sqrt(5.0); 
  double val=0.0;
  for (int i=3;i<20;i++)
  {
  val=(java.lang.StrictMath.pow((1+sqrt5)/2,i)
   -java.lang.StrictMath.pow((1-sqrt5)/2,i))
   /sqrt5;
  if (val>100)
   break;
  System.out.println(val);
  }
}

Answer 28

int X = 1,Y = 1,Z = 0;
    AnsiString Str = "";
    for (int i=1;i<100;i++)
    {
        Z = X + Y;
        X = Y;
        Y = Z;
        Str += (IntToStr(Z));    }
顶下

Answer 29

还是感谢diannaomingong(电脑民工)  接着学习

Answer 30

class fbr
{
public static void main(String[] args)
{
int i=1;
int j=1;
int temp;
for(;;)
{
temp=j;
j=j+i;
i=temp;
if(j<100)
System.out.print(j);
else
break;
} }
}我是来拿分的 哈哈哈哈哈.....

Answer 31

system.out.print(23581321345589);老兄你这是用正向推导得到的答案吧.

Answer 32

To  kxscr(未知):哈哈,拿不了分了吧?! 所有用到循环形式的通通都算迭代.不过除了那种脑筋急转弯式的解法,好像还有位apple_snake老兄用的模板? 让编译器来做递归,是不是也算一种妙法呢?

Answer 33

往你的程序中放入一对兔子
兔子长到两岁后达到育龄，
达到育龄的兔子每年都能生育一对兔子
以后每年统计一下共有多少对兔子就可以得到斐波那契数列了#include <iostream>
#include <vector>
using namespace std;int main()
{
int i;
vector<int> rabbit;
rabbit.push_back(0);
rabbit.push_back(1);
while (rabbit.size() <= 100)
{
cout << rabbit.size();
for (i = 0; i < rabbit.size(); i++)
rabbit[i]++;
for (i = 0; i < rabbit.size(); i++)
if (rabbit[i] > 1)
rabbit.push_back(0);
}
cout << endl;
return 0;
}

Answer 34

program JJ;{$APPTYPE CONSOLE}uses
  SysUtils;var
  I, J, K : Integer;
  S : String;
begin
  I := 1;
  J := 1;
  while (I <= 100)and(J <= 100) do
  begin
    K := J;
    J := I + J;
    I := K;
    Write(J);
  end;
end.

Answer 35

怎么我算的会出问题啊？？用long型的都还嫌太小

Answer 36

int a=1,b=1;
for(;a+b<=100;)
{
    int temp=a;
    a=b;
    b=temp+a;
    cout<<b;
}
结果：23581321345589
搂主实在不行，一步一步算也才不到十次而已。

Answer 37

这样写，不知道还有没有用到迭代#include <iostream>
#include <vector>
using namespace std;int main()
{
  int i, max = 100;
  vector<int> count;    //计数器矢量
  vector<int> rabbit;   //兔子矢量
  rabbit.push_back(0);  //放入0岁的兔子一只
  rabbit.push_back(1);  //放入1岁的兔子一只
  while (rabbit.size() <= max)
  {
     cout << rabbit.size();
     i= 0;
     while (i < rabbit.size())
     {
        if (rabbit[i] == 0)
          rabbit[i] = 1;       //兔子长大一岁
        else if (rabbit[i] == 1)
          rabbit[i] = 2;
        count.push_back(0);    //计数器矢量增长
        i = count.size();    //用计数器矢量的长度来代替i的自增
     }
     count.clear();
     i = 0;
     while (i < rabbit.size())
     {
        if (rabbit[i] > 1)
           rabbit.push_back(0); //大于一岁的兔子生下小兔子
        count.push_back(0);
        i = count.size();
     }
     count.clear();
  }
  cout << endl;
  return 0;
}

Answer 38

总觉得csdn以及某些面试题正向mop风格前进！