我正在考瑟拉做算法工具箱课程,我被作业的问题7困住了。它需要得到两个给定Fibonacci数之间的部分和,实际上问题语句需要该和的最后一个数字。
我知道从0到Fn的和是Fn+2 -1。
因此,Fx和Fy之间的部分和是
Fx+2 - Fy+1,我说得对吗?
我将使用Pisano序列得到任何Fibonnacci数的最后一个数字,通过得到它的模与序列的长度,到目前为止还不错。
但是,当输入为:
9999999999999999 99999999999999999
我的程序输出4,答案实际上是6。
我已经检查了需要多少位来表示每个数字,两者都在64位的范围内,而且我使用的是无符号64位整数。
我不知道这有什么问题。
#include <iostream>
#include <vector>
using namespace std;
vector<uint64_t> fibList; // Fibonacci numbers List
vector<uint64_t> pisanoSequence; // Pisano Sequence list
void generatePisanoSequence(int mod)
{
fibList.push_back((*(fibList.end()-1) + *(fibList.end()-2)) % mod); // Get the last digits of the next Fibonacci number depending on the modulp.
pisanoSequence.push_back(*(fibList.end()-1)); //Put the last digit of the last Fibonacci number in the Pisano Sequence
if (*(pisanoSequence.end() - 1) == 1 && *(pisanoSequence.end() - 2) == 0) // If we return to having 0 then 1 as inputs to the Pisano sequence that mean we have reached the end of the period of the sequence
{
return; // Stop Generating entries
}
else
{
generatePisanoSequence(mod); // Calculate the next entry.
}
}
int main()
{
fibList.push_back(0); // Put 0 to the Fibonacci sequence
fibList.push_back(1); // Put 1 to the Fibonacci sequence
pisanoSequence.push_back(0); // Put 0 to the Pisano Sequence
pisanoSequence.push_back(1); // Put 1 to the Pisano sequence
generatePisanoSequence(1000); // An Examplry Modulos of 1000
uint64_t n, m; // Input Fibonacci numbers
cin >> n >> m;
if (m == n) //If the same number entered for both, simply get the last digit of that number/
{
m = m % pisanoSequence.size(); //Find its place in the Pisano sequence
cout << pisanoSequence[m] % 10; // Get the number and print and its units digits
return 0;
}
if (m > n) swap(m,n); //If m is bigger than n, i.e the second Fibonacci is bigger than the first, swap them.
n = n + 2; //Get Fn+2
m = m + 1; //Get Fm+1
n = n % (pisanoSequence.size()); // Get its position in Pisano Sequence
m = m % (pisanoSequence.size()); // Get its position in Pisano Sequence
uint64_t n2 = pisanoSequence[n]; //Get the number
uint64_t m2 = pisanoSequence[m]; //Get the number
int64_t z = n2 - m2; //Subtract the numbers to find the partial sum
z = abs(z); //If negative make it positive because the sum is +ve and the subtraction might yield negative.
cout << z % 10; // Print the units of the sum
return 0;
}发布于 2018-09-14 14:11:33
z = abs(z)错了
如果你得到-4,那么答案是6,所以它应该是z = (z % 10 + 10) % 10;,而不是z = abs(z)
https://stackoverflow.com/questions/52323682
复制相似问题