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

每日编程-20170410

2024-09-13 22:24:07   217人阅读

题目描述
在农场中，奶牛家族是一个非常庞大的家族，对于家族中的母牛，从它出生那年算起，第三年便能成熟，成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛，它从第二年开始生小母牛。请设计一个高效算法，返回第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


联系
我们