求解一个类似于斐波拉契数列的问题
Problem Description
A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
Output
For each test case, print the value of f(n) on a single line.
Sample Input
1 1 3
1 2 10
0 0 0
Sample Output
2
5
我的程序是这样的,但提交到OJ却显示Memory Limit Exceeded,超过内存限制,求各位大神教教小弟怎么修改?还有这种类似问题应该怎么做才能避免超内存呢?
#include<stdio.h>
int k[100000001];
int main()
{
int a,b,n,i;
while(scanf("%d %d %d",&a,&b,&n)==3,a!=0||b!=0||n!=0)
{
k[0]=1;
k[1]=1;
for(i=2;i<100000001;i++)
{
k[i]=(a*k[i-1]+b*k[i-2])%7;
}
printf("%d\n",k[n-1]);
}
return 0;
}
[解决办法]
这种题最好用递归吧,你那个好浪费内存空间,int k[100000001]这么大的内存。
下面是我找自己想法写的
[code=C/C++][/code]
#include<stdio.h>
int a = 0;
int b = 0;
int get_caculate(int n)
{
if(n==1 || n==2)
return 1;
else
/*f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7 */
return (a*get_caculate(n-1) + b*get_caculate(n-2)) % 7;
}
int main()
{
int n;
while(scanf("%d %d %d",&a,&b,&n)==3,a!=0||b!=0||n!=0)
{
printf("%d", get_caculate(n));
}
return 0;
}
自己看了下运行结果,能对上结果。
[解决办法]
这里有个稍微高效的算法,即使n很大,最多循环49次
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int flag[7][7];
int f[100];
int a, b, n;
int func()
{
int i, circle, ipos;
a %= 7, b %= 7;
memset(flag, 0, sizeof(flag));
flag[1][1] = 2;
f[1] = 1, f[2] = 1;
i = 3;
f[i] = (f[i - 1] * a + f[i - 2] * b) % 7;
while (flag[f[i - 1]][f[i]] == 0)
{
flag[f[i - 1]][f[i]] = i;
i++;
f[i] = (f[i - 1] * a + f[i - 2] * b) % 7;
}
ipos = flag[f[i - 1]][f[i]];
circle = i - ipos;
if (n <= ipos)
return f[ipos];
return f[ipos + (n - ipos) % circle];
}
int main()
{
while (scanf("%d %d %d", &a, &b, &n) && (a != 0 || b != 0 || n != 0))
printf("%d\n", func());
return 0;
}
[解决办法]
楼主的int k[100000001];直接就把栈用光了,所以程序根本无法运行。
楼主的主要思想是对的,
建议方法:在用户输入了A、B、N后,使用malloc动态申请内存。而不是直接使用全局变量。
如果还是超过内存,建议减少缓存个数,例如只使用三个int来保存f(n-1),f(n-2),f(n),而不是使用100000001个int。
如果超过运算时间,楼主可以尝试使用《组合数学》中的推导,看能不能推导出直接函数表达式。(个人组合数学学得太差……呜呜)
[解决办法]
#include<stdio.h>
void main()
{
long a,b,n,i;
int f1,f2,f3;
while(1)
{
printf("Input A,B,N:");
scanf("%ld %ld %ld",&a,&b,&n);
if(a==0&&b==0&&n==0)
break;
if(a<1 || b>1000 || n<1 ||n>100000000)
{
printf("Input Error!\n 1<=A, B <=1000, 1 <= n <=100,000,000\n");
continue;
}
f1=1;
f2=1;
if(n==1)
f3=1;
else if(n==2)
f3=1;
else
{
for(i=3;i<=n;i++)
{
f3=(a*f2+b*f1)%7;
f1=f2;
f2=f3;
}
}
printf("result:%ld\n",f3);
}
}
这是每输入一次数据得一次结果
如果要所有结果一起显示的话建议你用个链表把结果存起来最后显示