[讨论]广义斐波那契数

xiezhh

有一个学生问我这样一个问题：
       有这样一些数（注意不是数列），它们相邻两位数的和等于其下一位数，比如
101，1011，112，123，1123，224，2246，11235，112358
等，我们不妨称这样的数为广义斐波那契数，这样的数总共有多少个呢？
       我觉得应该从排列组合的角度去解释，可是又没有思路，请各位高手一起想想！

我通过编程倒是能找到这些数，

1. xy=[];
   
2. for x=101:112358
   
3.     y=num2str(x);
   
4.     x1=y(3:end)';   
   
5.     y=str2num(y();
   
6.     y=y(1:end-1)+y(2:end);
   
7.     y=num2str(y(1:end-1));   
   
8.     if isequal(x1,y)
   
9.         xy=[xy;x];
   
10.     end
    
11. end
    
12. xy

复制代码

风天小畜

1# xiezhh

在添加一些限定条件之前，无限个
101010101010101010101010.......................
a0a0a0a0a0a0a0a0a0a0a0a0a0...................(a可以取1~9)

xiezhh

10101010...这样的数不满足条件，因为0+1不等于下一位数0

rocwoods

我是这么想的，可以将满足条件的数按前面两个数字分成不同的类（因为每类完全由前面两个数字决定）。即10,11,12,...18;20,...27;...;90
一共有9+8+7...+1 = 45类。含有最多这样数字的类是'10'类，一共有101，1011，10112，101123，1011235，10112358六个数字。可以用循环判断这45类各含有多少个满足条件的数字。结果总和是84个数字。以下是代码：

1. 
   
2. a = (10:99)';
   
3. aa = [floor(a/10),mod(a,10)];
   
4. aa = aa(sum(aa,2)<10,;
   
5. data = cell(size(aa,1),1);
   
6. for k = 1:length(data)
   
7.    temp = aa(k,;
   
8.    n = 3;
   
9.    temp(n) = temp(n-2)+temp(n-1);
   
10.    while temp(n-1)+temp(n)<10
    
11.        n=n+1;
    
12.        temp(n) =  temp(n-2)+temp(n-1);
    
13.    end
    
14.    data{k} = temp;
    
15. end
    
16. EveryNum = cellfun(@(x) length(x)-2,data);%每类满足条件的数字的个数
    
17. TotalNum = sum(EveryNum)
    

复制代码

xiezhh

非常感谢！还是rocwoods的思路好，采用分类的思想，先找每一类最长的数，然后用最长的数的位数减2确定每一类有多少个满足条件的数，真是很受启发！