网上看到的一个题目：数字迷阵

caterpilla

一道编程题，当个练习做做！
小可可参观科学博物馆时，看到一件藏品，上面有密密麻麻的数字，如下所示：
1    2    3    5    8    13    21    34    55    89    144 ...
4    7    11  18    29    47    76    123  199    322    521 ...
6    10  16  26    42    68    110  178  288    466    754 ...
9    15  24  39    63    102  165  267  432    699    1131 ...
12  20  32  52    84    136  220  356  576    932    1508 ...
14  23  37  60    97    157  254  411  665    1076  1741 ...
17  28  45  73    118  191  309  500  809    1309  2118 ...
19  31  50  81    131  212  343  555  898    1453  2351 ...
22  36  58  94    152  246  398  644  1042  1686  2728 ...
25  41  66  107  173  280  453  733  1186  1919  3105 ...
27  44  71  115  186  301  487  788  1275  2063  3338 ...
...
仔细一分析，发现还挺有规律。
原来，第一行是Fibonacci数列。即，该行中除了第一个和第二个数分别为1和2之外，其他数都是其左侧相邻的两个数之和。
其后各行也类似于Fibonacci数列。只是第i行的第一个数是前 行中未出现的最小正整数，而其第二个数与该行第一个数以及所在行的编号相关，即A[i,2]=A[i,1]*2-(i-1) 。如在第一行中未出现的最小正整数为4，前三行中未出现的最小正整数为9。故第二行以4和7开头，而第四行以9和15开头。
小可可高兴地把这个发现告诉了爷爷。爷爷问道：你能否一口报出第i行、第j列的那个数对m取模的结果是多少呢？
聪明的小可可通过心算就能知道答案。你是否能编写程序求解呢？

输入：每行有三个分别用一个空格隔开的正整数，分别是i、j和m。
其中，i, j<=1000000000 ，2<=m<=10000 。
输出：每行输出对应的第i行、第j列的那个正整数对m取模的结果。

样例：
(1) 输入（matrix.in）：
    1 2 99
输出（matrix.out）：
    2
(2) 输入（matrix.in）：   
9 1 999
输出（matrix.out）：
    22


原贴见：
http://bbs.chinaunix.net/viewthr ... 6amp%3Btypeid%3D134

hflywolf

/:014 /:014 /:014

以前做过这题......
大概就是这样
第一步:求第I行第一个数
用A(I,1)代表第I行的第一个数.
那A(I,1) = (I - 1) + I * ((1 + sqrt(5))/2)

第二步:求第I行第二个数
用A(I,2)代表第I行的第二个数
那A(I,2) = A(I,1) * 2 - (I - 1)

第三步:求第I行第J个数
用A(I,J)代表第I行的第J个数
根据Fibonacci(斐波那契)序列的通项公式构造一个递归方程（如果要优化的话，可以用迭代的方法求）
A(I,J) = A(I,J - 1) + A(I,J - 2)(其中I=1,2,3,4.....；J= 3,4,5..........)

算法就不写了。。。/:017 /:017 /:017

[ 本帖最后由 hflywolf 于 2008-7-18 16:09 编辑 ]

caterpilla

原帖由 hflywolf 于 2008-7-18 16:05 发表
/:014 /:014 /:014

以前做过这题......
大概就是这样
第一步:求第I行第一个数
用A(I,1)代表第I行的第一个数.
那A(I,1) = (I - 1) + I * ((1 + sqrt(5))/2)

第二步:求第I行第二个数
用A(I,2)代表第I行的第 ...

好象没看清题目的样子，每行是FIBNACCI数列，不过每行的起始数的产生是有要求的。

hflywolf

原帖由 caterpilla 于 2008-7-19 09:57 发表

好象没看清题目的样子，每行是FIBNACCI数列，不过每行的起始数的产生是有要求的。

/:L /:L /:L

我当然知道每行是类似FIBNACCI数列.......
可能是我没表达好吧...
你再好好看一下我给的思路........

先求出每行前两个数,每行以后的数就用FIBNACCI数列的通项公式就可以求出了.

每行第一个数(也就是第一列的数)即1,4,6,9,12,14,17,19,22,25,27,.........,.......
用这个公式就可以求出A(I,1)=(I - 1) + 取整(I * ((1 + sqrt(5))/2))(I代表行数)
如果用语言描述就是,每行第一个数等于行数减去一再加上(行数*黄金分割率)的整数部份(黄金分割率=(1+sqtr(5))/2)

每行第二个数(也就是第二列的数)即2,7,10,15,20,23,28,31,36,41,44,.......,.......
用这个公式就可以求出A(I,2) = A(I,1) * 2 - (I - 1)
如果用语言描述就是,每行第二个数等于每行第一个数乘于2再减去(行数减一)

最后再给LZ此迷阵的通项公式:
M(I,J) = (I-1)*F(J) +F(J+1)*取整数部分(I*((1+sqrt(5))/2))
其中F(n)是(1,1,2,3,5,8,13,21,34.....,.....)的第N项

BTW:LZ可以根据上面的公式求出的数对照你贴子里矩阵中的对应的数看是否正确

[ 本帖最后由 hflywolf 于 2008-7-20 01:41 编辑 ]

caterpilla

原帖由 hflywolf 于 2008-7-19 13:28 发表

/:L /:L /:L

我当然知道每行是类似FIBNACCI数列.......
可能是我没表达好吧...
你再好好看一下我给的思路........

先求出每行前两个数,每行以后的数就用FIBNACCI数列的通项公式就可以求出了.

每行第一 ...

/:good /:good /:good 是我错了，没读懂你的文章。我原来是用个笨方法做的。按你方法编，确实如此。找规律还是很重要的。
给出个代码：

00000: ＃include<iostream>
00001: ＃include<vector>
00002: ＃include<cmath>
00003: using namespace std;
00004: int main(int argc,char *argv[]){
00005: int rows,cols,i,j,m;
00006: cin>>rows>>cols>>i>>j>>m;
00007: int **ia_rows=new int*[rows];
00008: for(int i=0;i<rows;i++){
00009:     ia_rows=new int[cols];
00010:     ia_rows[0]=i+(int)((i+1)*((1+sqrt(5))/2));
00011:     ia_rows[1]=ia_rows[0]*2-i;
00012: }
00013: for(int i=0;i<rows;i++){
00014:     cout<<ia_rows[0]<<'\t'<<ia_rows[1]<<'\t';
00015:     for(int j=2;j<cols;j++){
00016:       ia_rows[j]=ia_rows[j-1]+ia_rows[j-2];
00017:       cout<<ia_rows[j]<<'\t';
00018:     }
00019:     cout<<endl;
00020: }
00021: cout<<"The result is:"<<ia_rows[j]%m<<endl;
00022: for(int i=0;i<rows;i++){
00023:     delete[] ia_rows;
00024: }
00025: delete[] ia_rows;
00026: }
00027:

[ 本帖最后由 caterpilla 于 2008-7-20 11:09 编辑 ]

hflywolf

原帖由 caterpilla 于 2008-7-20 10:41 发表

/:good /:good /:good 是我错了，没读懂你的文章。我原来是用个笨方法做的。按你方法编，确实如此。找规律还是很重要的。

/:001 /:001
呵呵,可能是我表达的不太好....
恩,看了你的程序,个人觉得这题完全可以不用数组和这么多FOR语句

给你贴我写的:(不一定是最优的,写的不好还望海涵哦)

1. // 数字迷阵.cpp : Defines the entry point for the console application.
   
2.   /******************************************************************
   
3.   * FibI代表FIBNACCI(1,1,2,3,5,8....,....)数列的第N项(即F(N))         *
   
4.   * FibJ代表FIBNACCI(1,1,2,3,5,8....,....)数列的第N+1项(即F(N+1))     *
   
5.   ******************************************************************/
   
6.   /*****************************************************************
   
7.   * 此数字迷阵的第N项可以用公式:                                       *
   
8.   * M(I)(J)=(I-1)*F(J) + F(J+1)*取整(I*((1+sqrt(5))/2)              *
   
9.   ******************************************************************/
   
10. #include "iostream.h"
    
11. #include <cmath>
    
12. #define ROOT_OF_FIVE sqrt(5.0)
    
13. unsigned long fib(unsigned long n); //比较快速的方法
    
14. int main()
    
15. {
    
16.    unsigned long i,j,m;
    
17.    unsigned long result,FibI,FibJ;
    
18.       cin>>i>>j>>m;     //输入正整数i,j,m
    
19.       FibI = fib(j);    //调用函数求FIBNACCI数
    
20.        FibJ = fib(j+1);  
    
21.       result = (i-1)*FibI + FibJ*(unsigned long(i *((1+ROOT_OF_FIVE)/2)));
    
22.       result = result % m;   //取模
    
23.        cout<<result<<endl;    //输入结果
    
24.        return 0;
    
25. }
    
26. //使用迭代法求FIBNACCI数,速度比递归法快的多了。
    
27. unsigned long fib(unsigned long n)  
    
28. {
    
29.    unsigned long FibNum;
    
30.    unsigned long l,f1,f2;
    
31.       if (n==1 ||n==2)
    
32.       {
    
33.         FibNum = 1;
    
34.       }
    
35.       else
    
36.       {
    
37.          f1 = 1;
    
38.         f2 = 1;
    
39.          for(l=3;l<=n;l++)
    
40.         {
    
41.            FibNum = f1 + f2;
    
42.            f1 = f2;
    
43.            f2 = FibNum;
    
44.         }
    
45.       }
    
46.    return FibNum;
    
47. }

复制代码

[ 本帖最后由 hflywolf 于 2008-7-20 14:53 编辑 ]

hflywolf

/:017 /:017
再贴个改进后的(由于上面那段代码调用两次函数,所以改进了一下,速度比上面快了一倍多):

1. // 数字迷阵2.cpp : Defines the entry point for the console application.
   
2. /***************************************************
   
3.   * FibI代表数字迷阵第N行第1列的数                         *
   
4.   * FibJ代表数字迷阵第N行第2列的数                         *
   
5.   * 求第N行第1列的数的公式：                                *               
   
6.   * FibI = (i-1) + unsigned long(i *((1+sqrt(5))/2))*
   
7.   * 求第N行第2列的数的公式：                                *
   
8.   * FibJ = FibI*2 - (i-1)                           *
   
9.   ***************************************************/
   
10. #include <iostream.h>
    
11. #include <math.h>
    
12. #define ROOT_OF_FIVE sqrt(5.0)
    
13. unsigned long fib(unsigned long n,unsigned long m,unsigned long k); //比较快速的方法
    
14. int main()
    
15. {
    
16.     unsigned long i,j,m;
    
17.     unsigned long FibI,FibJ;
    
18.     unsigned long result;
    
19.         cin>>i>>j>>m;    //输入正整数i,j,m
    
20.         FibI = (i-1) + unsigned long(i *((1+ROOT_OF_FIVE)/2)); //第N行第1列的数
    
21.         if (j<=1) result = FibI % m;   //如果第1列的数
    
22.         if (j>1 && j<3)    //如果是第2列的数
    
23.         {
    
24.              FibJ = FibI*2 - (i-1);    //第N行第2的数
    
25.             result = FibJ % m;
    
26.         }
    
27.         if(j >= 3)   //如果是第N+2列的数(N为1,2,3,4....,....)
    
28.         {
    
29.             FibJ = FibI*2 - (i-1);
    
30.             result = fib(FibI,FibJ,j);    //调用fib函数求迷阵第N行第N+2列的数
    
31.            result = result % m;
    
32.         }
    
33.   cout<<result<<endl;  //输出结果
    
34.   return 0;
    
35. }
    
36. //使用迭代求FIBNACCI数，空间复杂度和时间复杂度都是O(n)
    
37. unsigned long fib(unsigned long n,unsigned long m,unsigned long k)  
    
38. {
    
39.    unsigned long FibNum;
    
40.    unsigned long l;
    
41.       for(l=3;l<=k;l++)
    
42.       {
    
43.          FibNum = n + m;
    
44.          n = m;
    
45.          m = FibNum;
    
46.       }
    
47.     return FibNum;
    
48. }

复制代码

[ 本帖最后由 hflywolf 于 2008-7-20 14:50 编辑 ]

caterpilla

原帖由 hflywolf 于 2008-7-20 14:39 发表
/:017 /:017
再贴个改进后的(由于上面那段代码调用两次函数,所以改进了一下,速度比上面快了一倍多):// 数字迷阵2.cpp : Defines the entry point for the console application.
/****************************** ...

/:good /:good /:good
高手！！！你的通项公式对的！我打印只想验证一下结果！！！