首页 > 代码库 > 每日编程-20170410

每日编程-20170410

题目描述
在农场中,奶牛家族是一个非常庞大的家族,对于家族中的母牛,从它出生那年算起,第三年便能成熟,成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛,它从第二年开始生小母牛。请设计一个高效算法,返回第n年的母牛总数,已知n的范围为int范围内的正整数。
给定一个正整数n,请返回第n年的母牛总数,为了防止溢出,请将结果Mod 1000000007。
测试样例:
6
返回:9

解答:

这道题研究了两天……

先写了一个数组的,告诉时间复杂度太高

 1 int countCow(int n) {
 2     // write code here
 3     int yearCow[5] = { 1,2,3,0,0 };
 4     int i = 3;
 5     while (i != n)
 6     {
 7         yearCow[i % 5 ] = yearCow[(i + 4) % 5] + yearCow[(i + 2) % 5];
 8         i++;
 9     }
10     return yearCow[(i - 1) % 5] % 1000000007;
11 }    

然后看看别人家的算法,发现要用快速幂乘矩阵法,于是去这个博客学习了一下,大概搞懂了,学了个样子

但是分治的思想还是没懂,写了个残缺的,时间还是太慢

主要在于求矩阵幂的时候,要用到分治思想,在这里就表示:

  如果求4次幂,先求tmp的平方,保存下来再求tmp平方的平方,减少了一次运算(一个是(tmp^2)^2,一个是tmp*tmp*tmp*tmp)

  如果求5次幂,由于是4-8之间,所以求到4次幂后,再乘一次tmp就好

另外,还学会了使用位运算代替除2,以及奇偶数判断(余2)

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 vector<vector<long long>> matrixMult(const vector<vector<long long>> &v1, const vector<vector<long long>> &v2) { //矩阵乘法
 6     if (v1[0].size() != v2.size()) cerr << "matrix wrong" << endl;
 7     vector<vector<long long>> answer(v1.size(), vector<long long>(v2[0].size(),0));
 8     for (size_t i = 0; i < v1.size(); i++)
 9     {
10         for (size_t j = 0; j < v2[0].size(); j++)
11         {
12             for (size_t k = 0; k < v1[0].size(); k++)
13             {
14                 answer[i][j] += (v1[i][k] % 1000000007) * (v2[k][j] % 1000000007) % 1000000007;
15             }
16         }
17     }
18     return answer;
19 }
20 vector<vector<long long>> matrixPow(const vector<vector<long long>> &v, int times) { //矩阵平方
21     vector<vector<long long>> answer( v.size(),vector<long long> (v[0].size(), 0));
22     for (size_t i = 0; i < answer[0].size(); i++)
23     {
24         answer[i][i] = 1;
25     }
26     vector<vector<long long>> tmp = v;
27     for (auto i = times; i != 0; i >>=1)
28     {
29         if (i&1) //最后一位是1
30         {
31             answer = matrixMult(answer, tmp);
32         }
33         tmp = matrixMult(tmp, tmp);
34     }
35     return answer;
36 }
37 void printMatrix(const vector<vector<long long>> &v) {
38     for (size_t i = 0; i < v.size(); i++)
39     {
40         for (size_t j = 0; j < v[0].size(); j++)
41         {
42             cout << v[i][j];
43         }
44         cout << endl;
45     }
46 }
47 int cowFamily(int n) {
48     vector<vector<long long>> v = { { 1, 1, 0 },{ 0, 0, 1 },{ 1, 0, 0 } };
49     vector<vector<long long>> answer = matrixPow(v, n - 3);
50     return ((3 * answer[0][0]) % 1000000007 + 
51         (2 * answer[1][0]) % 1000000007 + 
52         answer[2][0]) % 1000000007;
53 }

 

每日编程-20170410